EvbCFfp1XB

problem and my answer.

November 2013

I have read chokudai's Submission46. I saw he use HashMap. I wrote Java version of his code.
It is faster than java.util.HashMap.

result

[put, 0.337204343]
[get, 0.340456201]
[put, 0.990776216]
[get, 2.399216921]

source code

import java.util.Arrays;
import java.util.HashMap;

public class ChokudaisHashMap {
private int COUNTMAX = 1600000;
private int hashmax = (1 << 24);
private int nowhashcount;
private int[] prehash = new int[hashmax];
private int[] nextpos = new int[COUNTMAX];
private long[] keys = new long[COUNTMAX];
private int[] values = new int[COUNTMAX];

public void init() {
nowhashcount = 0;
for (int i = 0; i < hashmax; i++)
prehash[i] = -1;
}

public int get(long key) {
int h = (int) (key & (hashmax - 1));
int nowpos = prehash[h];
while (nowpos != -1) {
if (keys[nowpos] == key) {
return values[nowpos];
}
nowpos = nextpos[nowpos];
}
return 0;
}

public void put(long key, int value) {
int h = (int) (key & (hashmax - 1));
nextpos[nowhashcount] = prehash[h];
prehash[h] = nowhashcount;
keys[nowhashcount] = key;
values[nowhashcount] = value;
nowhashcount++;
}

public static void main(String[] args) {
int n = 1000000;
{
ChokudaisHashMap map = new ChokudaisHashMap();
map.init();
{
XorShift rnd = new XorShift();
long start = System.nanoTime();
for (int i = 0; i < n; i++) {
map.put(rnd.nextLong(), rnd.nextInt());
}
double time = (System.nanoTime() - start) / 1e9;
message("put", time);
}
{
XorShift rnd = new XorShift();
long start = System.nanoTime();
for (int i = 0; i < n; i++) {
int v = map.get(rnd.nextLong());
if (v != rnd.nextInt()) {
throw new RuntimeException();
}
}
double time = (System.nanoTime() - start) / 1e9;
message("get", time);
}
}
{
HashMap<Long, Integer> map = new HashMap<Long, Integer>(2 * n);
{
XorShift rnd = new XorShift();
long start = System.nanoTime();
for (int i = 0; i < n; i++) {
map.put(rnd.nextLong(), rnd.nextInt());
}
double time = (System.nanoTime() - start) / 1e9;
message("put", time);
}
{
XorShift rnd = new XorShift();
long start = System.nanoTime();
for (int i = 0; i < n; i++) {
int v = map.get(rnd.nextLong());
if (v != rnd.nextInt()) {
throw new RuntimeException();
}
}
double time = (System.nanoTime() - start) / 1e9;
message("get", time);
}
}
}

private static final void message(Object... o) {
System.err.println(Arrays.deepToString(o));
}

}

class XorShift {
private int w = 88675123;
private int x = 123456789;
private int y = 362436069;
private int z = 521288629;

/**
* Returns the next pseudorandom {@code double} value, greater than or equal to {@code 0.0} and less than {@code 1.0}.
*
* @return the next pseudorandom
*/
public double nextDouble() {
return (double) (nextInt() + (1L << 31)) / (1L << 32);
}

/**
* Returns the next pseudorandom {@code int} value, greater than or equal to {@code Integer.MIN_VALUE} and less than or equal to {@code Integer.MAX_VALUE}.
*
* @return the next pseudorandom
*/
public int nextInt() {
final int t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = w ^ (w >>> 19) ^ (t ^ (t >>> 8));
return w;
}

/**
* Returns the next pseudorandom {@code long} value.
*
* @return the next pseudorandom
*/
public long nextLong() {
return ((long) nextInt() << 32) ^ (((long) nextInt() << 32) >>> 32);
}

}

I measured time to execute some codes. I see that static method is fast and synchronized method is slow.


result

     second process
0.377192935 empty loop
0.291664212 publicEmptyMethod
0.303606105 protectedEmptyMethod
0.286344766 emptyMethod
0.314491063 privateEmptyMethod
0.153063679 staticEmptyMethod
0.316276520 finalEmptyMethod
2.460220468 synchronizedEmptyMethod
0.280653043 strictfpEmptyMethod
0.331532345 Math.max(i,j)
0.331514772 inlined Math.max(i,j)
0.473257116 non static version of Math.max(i,j)

source code

import org.junit.Test;

public class TimeOfProcessOfMethod {
@Test
public void test0() {
int n = 10000;
System.out.format("%11s %s\n", "second", "process");
System.out.format("%.9f empty loop\n", emptyLoop(n));

System.out.format("%.9f publicEmptyMethod\n", publicEmptyMethod(n * n));
System.out.format("%.9f protectedEmptyMethod\n", protectedEmptyMethod(n * n));
System.out.format("%.9f emptyMethod\n", emptyMethod(n * n));
System.out.format("%.9f privateEmptyMethod\n", privateEmptyMethod(n * n));
System.out.format("%.9f staticEmptyMethod\n", staticEmptyMethod(n * n));
System.out.format("%.9f finalEmptyMethod\n", finalEmptyMethod(n * n));
System.out.format("%.9f synchronizedEmptyMethod\n", synchronizedEmptyMethod(n * n));
System.out.format("%.9f strictfpEmptyMethod\n", strictfpEmptyMethod(n * n));

System.out.format("%.9f Math.max(i,j)\n", MathMax(n));
System.out.format("%.9f inlined Math.max(i,j)\n", MathMaxInline(n));
System.out.format("%.9f non static version of Math.max(i,j)\n", MathMaxNonStatic(n));
}

private double emptyLoop(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double publicEmptyMethod(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
publicEmptyMethod();
}
return (System.nanoTime() - start) * 1e-9;
}

public void publicEmptyMethod() {
}

private double emptyMethod(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
emptyMethod();
}
return (System.nanoTime() - start) * 1e-9;
}

void emptyMethod() {
}

private double protectedEmptyMethod(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
protectedEmptyMethod();
}
return (System.nanoTime() - start) * 1e-9;
}

protected void protectedEmptyMethod() {
}

private double privateEmptyMethod(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
privateEmptyMethod();
}
return (System.nanoTime() - start) * 1e-9;
}

private void privateEmptyMethod() {
}

private double staticEmptyMethod(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
staticEmptyMethod();
}
return (System.nanoTime() - start) * 1e-9;
}

static void staticEmptyMethod() {
}

private double finalEmptyMethod(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
finalEmptyMethod();
}
return (System.nanoTime() - start) * 1e-9;
}

final void finalEmptyMethod() {
}

private double synchronizedEmptyMethod(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
synchronizedEmptyMethod();
}
return (System.nanoTime() - start) * 1e-9;
}

synchronized void synchronizedEmptyMethod() {
}

private double strictfpEmptyMethod(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
strictfpEmptyMethod();
}
return (System.nanoTime() - start) * 1e-9;
}

strictfp void strictfpEmptyMethod() {
}

private double MathMax(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = Math.max(i, j);
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double MathMaxInline(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = (i >= j) ? i : j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double MathMaxNonStatic(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = max(i, j);
}
}
return (System.nanoTime() - start) * 1e-9;
}

private int max(int i, int j) {
return (i >= j) ? i : j;
}

}



I measured the time to execute various codes 100 million times. I see that division and remainder are slow.

result


     second process
0.316777686 empty loop
0.283630017 Additive operator (i+j)
0.265407043 Subtraction operator (i-j)
0.492547572 Multiplication operator of int (i*j)
1.456519753 Multiplication operator of double (i*j)
4.551947737 Division operator of int (i/j)
5.114029987 Division operator of double (i/j)
4.580279227 Remainder operator (i%j)
0.275577814 Bitwise AND (i&j)
0.276286173 Bitwise inclusive OR (i|j)
0.266279400 Bitwise exclusive OR (i^j)
0.297788600 bitwise complement (~j)
0.452274089 Signed left shift (i<<j)
0.536472793 Signed right shift (i>>j)
0.522385877 Unsigned right shift (i>>>j)
0.266839468 Increment operator of int (a++)
0.334460716 Increment operator of byte (a++)
0.289277652 Increment operator of short (a++)
0.268729481 Increment operator of long (a++)
0.355655773 Increment operator of float (a++)
0.358708802 Increment operator of double (a++)
0.565726136 Equal to (i==j)
0.475734033 Not equal to (i!=j)
0.495599468 Greater than (i>j)
0.499592582 Greater than or equal to (i>=j)
0.494089391 Less than (i<j)
0.506896959 Less than or equal to (i<=j)
1.142540911 Conditional-AND (i&&j)
1.395354743 Conditional-OR (i||j)
0.509939531 Ternary (shorthand for if-then-else statement) (i?0:1)
4.917874652 isEvenByRemainder (i%2==0)
0.565641762 isEvenByBitAnd ((i&1)==0)
0.286526496 multiply2ByMultiply (i*2)
0.265691370 multiply2ByShift (i<<1)
4.487871397 divide2ByDivide (i/2)
0.284582014 divide2ByShift (i>>1)

source code

import org.junit.Test;

public class TimeOfProcess {
@Test
public void test0() {
int n = 10000;
System.out.format("%11s %s\n", "second", "process");
System.out.format("%.9f empty loop\n", emptyLoop(n));

System.out.format("%.9f Additive operator (i+j)\n", add(n));
System.out.format("%.9f Subtraction operator (i-j)\n", subtract(n));
System.out.format("%.9f Multiplication operator of int (i*j)\n", multiply(n));
System.out.format("%.9f Multiplication operator of double (i*j)\n", multiplyDouble(n));
System.out.format("%.9f Division operator of int (i/j)\n", divide(n));
System.out.format("%.9f Division operator of double (i/j)\n", divideDouble(n));
System.out.format("%.9f Remainder operator (i%%j)\n", remainder(n));

System.out.format("%.9f Bitwise AND (i&j)\n", bitAnd(n));
System.out.format("%.9f Bitwise inclusive OR (i|j)\n", or(n));
System.out.format("%.9f Bitwise exclusive OR (i^j)\n", xor(n));
System.out.format("%.9f bitwise complement (~j)\n", complement(n));
System.out.format("%.9f Signed left shift (i<<j)\n", left(n));
System.out.format("%.9f Signed right shift (i>>j)\n", signedRight(n));
System.out.format("%.9f Unsigned right shift (i>>>j)\n", unsignedRight(n));

System.out.format("%.9f Increment operator of int (a++)\n", intIncrement(n * n));
System.out.format("%.9f Increment operator of byte (a++)\n", byteIncrement(n * n));
System.out.format("%.9f Increment operator of short (a++)\n", shortIncrement(n * n));
System.out.format("%.9f Increment operator of long (a++)\n", longIncrement(n * n));
System.out.format("%.9f Increment operator of float (a++)\n", floatIncrement(n * n));
System.out.format("%.9f Increment operator of double (a++)\n", doubleIncrement(n * n));

System.out.format("%.9f Equal to (i==j)\n", equalTo(n));
System.out.format("%.9f Not equal to (i!=j)\n", notEqualTo(n));
System.out.format("%.9f Greater than (i>j)\n", greaterThan(n));
System.out.format("%.9f Greater than or equal to (i>=j)\n", greaterThanOrEqualTo(n));
System.out.format("%.9f Less than (i<j)\n", lessThan(n));
System.out.format("%.9f Less than or equal to (i<=j)\n", lessThanOrEqualTo(n));
System.out.format("%.9f Conditional-AND (i&&j)\n", conditionalAND(n));
System.out.format("%.9f Conditional-OR (i||j)\n", conditionalOR(n));
System.out.format("%.9f Ternary (shorthand for if-then-else statement) (i?0:1)\n", ternary(n));

System.out.format("%.9f isEvenByRemainder (i%%2==0)\n", isEvenByRemainder(n * n));
System.out.format("%.9f isEvenByBitAnd ((i&1)==0)\n", isEvenByBitAnd(n * n));
System.out.format("%.9f multiply2ByMultiply (i*2)\n", multiply2ByMultiply(n * n));
System.out.format("%.9f multiply2ByShift (i<<1)\n", multiply2ByShift(n * n));
System.out.format("%.9f divide2ByDivide (i/2)\n", divide2ByDivide(n * n));
System.out.format("%.9f divide2ByShift (i>>1)\n", divide2ByShift(n * n));

}

private double emptyLoop(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double ternary(int n) {
long start = System.nanoTime();
boolean c = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++, c = !c) {
int a = c ? 0 : 1;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double conditionalOR(int n) {
long start = System.nanoTime();
boolean c = true;
boolean d = true;
for (int i = 1; i <= n; i++, c = !c) {
for (int j = 1; j <= n; j++, d = !d) {
boolean a = c || d;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double conditionalAND(int n) {
long start = System.nanoTime();
boolean c = true;
boolean d = true;
for (int i = 1; i <= n; i++, c = !c) {
for (int j = 1; j <= n; j++, d = !d) {
boolean a = c && d;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double lessThanOrEqualTo(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
boolean a = i <= j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double lessThan(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
boolean a = i < j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double greaterThanOrEqualTo(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
boolean a = i >= j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double greaterThan(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
boolean a = i > j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double notEqualTo(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
boolean a = i != j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double equalTo(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
boolean a = i == j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double intIncrement(int n) {
long start = System.nanoTime();
int a = 0;
for (int i = 1; i <= n; i++) {
a++;
}
return (System.nanoTime() - start) * 1e-9;
}

private double byteIncrement(int n) {
long start = System.nanoTime();
byte a = 0;
for (int i = 1; i <= n; i++) {
a++;
}
return (System.nanoTime() - start) * 1e-9;
}

private double shortIncrement(int n) {
long start = System.nanoTime();
short a = 0;
for (int i = 1; i <= n; i++) {
a++;
}
return (System.nanoTime() - start) * 1e-9;
}

private double longIncrement(int n) {
long start = System.nanoTime();
long a = 0;
for (int i = 1; i <= n; i++) {
a++;
}
return (System.nanoTime() - start) * 1e-9;
}

private double doubleIncrement(int n) {
long start = System.nanoTime();
double a = 0;
for (int i = 1; i <= n; i++) {
a++;
}
return (System.nanoTime() - start) * 1e-9;
}

private double floatIncrement(int n) {
long start = System.nanoTime();
float a = 0;
for (int i = 1; i <= n; i++) {
a++;
}
return (System.nanoTime() - start) * 1e-9;
}

private double divide2ByShift(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
int a = i >> 1;
}
return (System.nanoTime() - start) * 1e-9;
}

private double divide2ByDivide(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
int a = i / 2;
}
return (System.nanoTime() - start) * 1e-9;
}

private double multiply2ByShift(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
int a = i << 1;
}
return (System.nanoTime() - start) * 1e-9;
}

private double multiply2ByMultiply(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
int a = i * 2;
}
return (System.nanoTime() - start) * 1e-9;
}

private double unsignedRight(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i >>> j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double signedRight(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i >> j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double left(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i << j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double complement(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = ~j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double xor(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i ^ j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double or(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i | j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double bitAnd(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i & j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double remainder(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i % j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double divide(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i / j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double divideDouble(int n) {
long start = System.nanoTime();
for (double i = 1; i <= n; i++) {
for (double j = 1; j <= n; j++) {
double a = i / j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double multiply(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i * j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double multiplyDouble(int n) {
long start = System.nanoTime();
for (double i = 1; i <= n; i++) {
for (double j = 1; j <= n; j++) {
double a = i * j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double add(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i + j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double subtract(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int a = i - j;
}
}
return (System.nanoTime() - start) * 1e-9;
}

private double isEvenByRemainder(int n) {
long start = System.nanoTime();
for (int i = 0; i <= n; i++) {
boolean a = i % 2 == 0;
}
return (System.nanoTime() - start) * 1e-9;
}

private double isEvenByBitAnd(int n) {
long start = System.nanoTime();
for (int i = 1; i <= n; i++) {
boolean a = (i & 1) == 0;
}
return (System.nanoTime() - start) * 1e-9;
}
}


このページのトップヘ