3 ms·
Too bad this guy never took a data structures course. Binary search on an array is O(log N) in the DAM model, while search in a B-tree is optimal: O(log N/log
by leif 15y ago
Too bad this guy never took a data structures course. Binary search on an array is O(log N) in the DAM model, while search in a B-tree is optimal: O(log N/log B).
Note that if your elements are english words, let's be extremely generous and say they are 12 bytes on average, with a 4-byte offset, that's 16 bytes per element, with a disk block size of 512K (and it's usually more), that means B is 32K, and my B-tree is 15 times faster than your array.
Of course, if your data set is only 11MB, who cares? You can read that in under the time it takes you to seek to the file.
- ynniv 15y agoIndeed, this post falls into the category "things that people often rediscover". Using storage optimized data structures and algorithms is very, very old. [ http://en.wikipedia.org/wiki/Merge_sort#Use_with_tape_drives http://en.wikipedia.org/wiki/Merge_sort#Use_with_tape_drives ]
- leif 15y agofunny you should bring up merge sort: in my first google phone screen, I was asked "why is merge sort good" and I gave "it's asymptotically optimal and stable" and couldn't come up with anything else, the interviewer eventually conceded that I was too young to know that it was also better than other sorting algorithms on tape :)
- andrewf 15y agoCS professors always bring up the tape example, but it's true for any medium where linear access is faster than random, which becomes applicable as you move down from L1 cache -> memory -> local disk -> network. Linked lists, too :)
- leif 15y agoof course, only years later would I understand the proof of why: M/B-way merge sort is optimal in external memory