3 ms·
Isn't sorting 1000 of 1TB strings even more inefficient? You need to read and compare the 1TB strings 1000 * log(1000) or 3000 times, while hashing only needs
by ww520 8y ago
Isn't sorting 1000 of 1TB strings even more inefficient? You need to read and compare the 1TB strings 1000 * log(1000) or 3000 times, while hashing only needs 1000 times.
- _cs2017_ 8y agoTypically, you can tell the order between two strings early, after you read just the starting few characters. So for comparison you would usually read maybe 10 bytes per file on average, or 3 x 1000 x 10 bytes = 30KB in total. Or maybe 30MB if the strings have long common prefixes. Of course, in a highly specialized distribution, all the strings could be identical except for the last few characters, and then sorting would be horrible. Ultimately you have to have some idea about the distribution of your data to say anything about average complexity.