StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Nothing in your <em>implementation</em> strikes me as particularly inefficient. I'll admit I don't really follow your hashing/lookup <em>strategy</em>, but if you say it's performant in your circumstances, I'll believe you.</p> <p>The only thing that I would expect might make <em>some</em> difference is to move the key out of the values array of <code>Entry</code>.</p> <p>Instead of having this:</p> <pre><code>class Entry { long[] values; } //... if ( entry.values[key_index] == key ) { //... </code></pre> <p>Try this:</p> <pre><code>class Entry { long key; long values[]; } //... if ( entry.key == key ) { //... </code></pre> <p>Instead of incurring the cost of accessing a member, plus doing bounds checking, then getting a value of the array, you should just incur the cost of accessing the member.</p> <h2>Is there a random-access data type faster than an array?</h2> <p>I was interested in the answer to this question, so I set up a test environment. This is my Array interface:</p> <pre><code>interface Array { long get(int i); void set(int i, long v); } </code></pre> <p>This "Array" has undefined behaviour when indices are out of bounds. I threw together the obvious implementation: </p> <pre><code>class NormalArray implements Array { private long[] data; public NormalArray(int size) { data = new long[size]; } @Override public long get(int i) { return data[i]; } @Override public void set(int i, long v) { data[i] = v; } } </code></pre> <p>And then a control:</p> <pre><code>class NoOpArray implements Array { @Override public long get(int i) { return 0; } @Override public void set(int i, long v) { } } </code></pre> <p>Finally, I designed an "array" where the first 10 indices are hardcoded members. The members are set/selected through a switch:</p> <pre><code>class TenArray implements Array { private long v0; private long v1; private long v2; private long v3; private long v4; private long v5; private long v6; private long v7; private long v8; private long v9; private long[] extras; public TenArray(int size) { if (size > 10) { extras = new long[size - 10]; } } @Override public long get(final int i) { switch (i) { case 0: return v0; case 1: return v1; case 2: return v2; case 3: return v3; case 4: return v4; case 5: return v5; case 6: return v6; case 7: return v7; case 8: return v8; case 9: return v9; default: return extras[i - 10]; } } @Override public void set(final int i, final long v) { switch (i) { case 0: v0 = v; break; case 1: v1 = v; break; case 2: v2 = v; break; case 3: v3 = v; break; case 4: v4 = v; break; case 5: v5 = v; break; case 6: v6 = v; break; case 7: v7 = v; break; case 8: v8 = v; break; case 9: v9 = v; break; default: extras[i - 10] = v; } } } </code></pre> <p>I tested it with this harness: </p> <pre><code>import java.util.Random; public class ArrayOptimization { public static void main(String[] args) { int size = 10; long[] data = new long[size]; Random r = new Random(); for ( int i = 0; i < data.length; i++ ) { data[i] = r.nextLong(); } Array[] a = new Array[] { new NoOpArray(), new NormalArray(size), new TenArray(size) }; for (;;) { for ( int i = 0; i < a.length; i++ ) { testSet(a[i], data, 10000000); testGet(a[i], data, 10000000); } } } private static void testGet(Array a, long[] data, int iterations) { long nanos = System.nanoTime(); for ( int i = 0; i < iterations; i++ ) { for ( int j = 0; j < data.length; j++ ) { data[j] = a.get(j); } } long stop = System.nanoTime(); System.out.printf("%s/get took %fms%n", a.getClass().getName(), (stop - nanos) / 1000000.0); } private static void testSet(Array a, long[] data, int iterations) { long nanos = System.nanoTime(); for ( int i = 0; i < iterations; i++ ) { for ( int j = 0; j < data.length; j++ ) { a.set(j, data[j]); } } long stop = System.nanoTime(); System.out.printf("%s/set took %fms%n", a.getClass().getName(), (stop - nanos) / 1000000.0); } } </code></pre> <p>The results were somewhat surprising. The TenArray performs non-trivially faster than a NormalArray does (for sizes <= 10). Subtracting the overhead (using the NoOpArray average) you get TenArray as taking ~65% of the time of the normal array. So if you know the likely max size of your array, I suppose it <em>is</em> possible to exceed the speed of an array. I would imagine switch uses either less bounds checking or more efficient bounds checking than does an array.</p> <pre><code>NoOpArray/set took 953.272654ms NoOpArray/get took 891.514622ms NormalArray/set took 1235.694953ms NormalArray/get took 1148.091061ms TenArray/set took 1149.833109ms TenArray/get took 1054.040459ms NoOpArray/set took 948.458667ms NoOpArray/get took 888.618223ms NormalArray/set took 1232.554749ms NormalArray/get took 1120.333771ms TenArray/set took 1153.505578ms TenArray/get took 1056.665337ms NoOpArray/set took 955.812843ms NoOpArray/get took 893.398847ms NormalArray/set took 1237.358472ms NormalArray/get took 1125.100537ms TenArray/set took 1150.901231ms TenArray/get took 1057.867936ms </code></pre> <p>Now whether you can in practice get speeds faster than an array I'm not sure; obviously this way you incur any overhead associated with the interface/class/methods.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload