StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I would simply sort the array by key, and use a binary search.</p> <p>(untested)</p> <pre><code>int compare_entry(ENTRY *k1, ENTRY *k2) { int d = k1->a1 - k2->a1; if (d == 0) { d = k1->a2 - k2->a2; if (d == 0) { d = k1->a3 - k2->a3; } } return d; // >0 is k1 > k2, 0 if k1 == k2, <0 if k1 < k2 } // Derived from Wikipedia int find(ENTRY *list, int size, ENTRY *value) { int low = 0; int n = size - 1; int high = n; while (low < high) { int mid = low + (high - low) / 2 int cmp = compare_entry(&list[mid], value); if (cmp < 0) { low = mid + 1; } else { high = mid; } } if (low < n) { int cmp = compare_entry(&list[low], value); if (cmp == 0) { return low; // found item at 'low' index } } else { return -1; // not found } } </code></pre> <p>Absolutely worst case, you run through this thing, what, 10 times, and end up actually doing all of the comparisons in the key comparison. So that's, what, 85 integer math operations (additions, subtraction, and 1 shift)?</p> <p>if your a1-a3 are ranging 0-100, then you can make your key a1 * 10000 + a2 * 100 + a3, and do a single compare, and worst case is 63 integer math operations. And your entire array fits within cache on most any modern processor. And it's memory efficient.</p> <p>You can burn memory with a perfect hash or some other sparse matrix. Even with a perfect hash, I bet the hash calculation itself is competitive with this time, considering multiplication is expensive. This hits the memory bus harder, obviously.</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