3 ms·
Hey! Here's a fun trick I learned from Knuth's TAOCP, the one with the tape drive algorithms. You want to search an array for an element: int i; for (
by ridiculous_fish 8y ago
Hey! Here's a fun trick I learned from Knuth's TAOCP, the one with the tape drive algorithms.
You want to search an array for an element:
int i;
for (i=0; i < array.length; i++) {
if (array[i] == value) break;
}
return i;
This is bad because we have two comparisons every loop iteration. But simply append our search term:
array.push(value);
int i;
for (i=0; ; i++) {
if (array[i] == value) break;
}
array.pop();
return i;
and we've cut our comparisons in half!
- pvorb 8y agoI'd prefer the first version in almost all situations except for a major performance bottle neck. The second version is less clear to the reader and thus likely done wrong.
- ridiculous_fish 8y agoYeah tape-based algorithms are an anachronism, but the idea of eliminating bounds checking via a terminal value is very powerful. An example of this in action is LLVM's MemoryBuffer [1], which is input to a parser. How to write a parser? Perhaps it performs bounds checking at each production. However LLVM guarantees that the MemoryBuffer is NUL (0) terminated. A parser can then arrange for NUL to be a terminating character, and handle it uniformly. The resulting parsers are faster, and also significantly clearer and easier to write, because there's no need for bounds checking at all. http://llvm.org/doxygen/classllvm_1_1MemoryBuffer.html http://llvm.org/doxygen/classllvm_1_1MemoryBuffer.html
- magicalhippo 8y agoHowever it requires that the terminal value does not occur in the input. For a parser that's probably not a problem (it can transform NULs in the input to a different token), in other situations it's not so easy.
- brisance 8y agoDon't most modern compilers in the last 20 years do this for you automatically?
- ridiculous_fish 8y agoNo way! Compilers won't secretly append to an array.
- egypturnash 8y agoWouldn’t you want something like “if (i == array.length) { return FALSE}” before the return statement? Returning array.length+1 as “not found” feels like it’s just begging for an out of bounds exploit. Clever example of this approach, though!
- scarejunba 8y agoFor this to be guaranteed to work, underlying storage has to be resizable (clearly not using linked list like semantics since it's named 'array'). So that means some small amount of the time, a linear search (a supposed read-only op) results in a possibly massive allocation or I need to allocate one extra space each time? Search is now not multi-reader thread-safe either. I mean, I can see the value, but surely a modern filter findAny is superior to this. EDIT: can't post in response but I thought you meant that this trick carried over.
- ridiculous_fish 8y agoIt was literally using magnets to write a new value to the end of the tape.
- jcelerier 8y agoand introduced a dynamic memory allocation ! yay, unuseable in real-time systems !
- pjc50 8y agoThis is the one that leads to the joke with the punchline "... insert a known lion in Capetown to ensure the search terminates", isn't it?
- K2L8M11N2 8y agoI thought it was an https://en.wikipedia.org/wiki/Elephant_in_Cairo https://en.wikipedia.org/wiki/Elephant_in_Cairo?