4 ms·

> For anything but the smallest lists [6], binary search is much quicker than the linear search above. > In my experience, binary search becomes faster than li

by orf 3y ago

> For anything but the smallest lists [6], binary search is much quicker than the linear search above. > In my experience, binary search becomes faster than linear search after about 8-12 elements It depends on your data, but CPUs are extremely good at scanning through contiguous vectors. Binary searching might make a difference at tens of thousands of elements. If you’re using Python then it’s different as nothing is contiguous, or you have a complex equality function, but then a simple improvement is to put the data in a numpy array of dataframe.

hinkley 3y ago
> or you have a complex equality function This is part of my thesis that Knuth today is wrong to the point of harm. That we need a new complexity theory built on top of Information Theory. We are steering kids wrong more often than right at this point. Data sets we work with are at least six orders of magnitude larger than they were in the eighties. There are almost no comparisons in Real Data that run in constant time, and for big enough n even addition and multiplication are not constant time. For large enough n, storage accesses are sqrt(n). Even in primary storage. Imagine you have a list of a million distinct strings. Case sensitive, alphanumeric. Complexity theory tells us you can sort those in nlogn time. But that’s pure fantasy because n unique strings have an average length of logn, meaning the compares all take logn time. Mergesort for any real data type is n (logn)². Now sort a quintillion unique strings. That takes 65-70 exabytes of space, just for starters, so it’s going to involve Ethernet cables and NVME RAID arrays. Your mergesort is now in the neighborhood of n^1.5 (log n)². Your piece of paper says this might run in hours, while the real implementation runs for weeks. For most purposes, you should multiply every algorithm in TAOC by logn. In some cases, sqrt(n). And as n actually approaches infinity, multiply by both. From another angle, I think the fact that it took 54 years to get from mergesort to Timsort has more to do with sacred cows than Tim’s brilliance. I’d like to see benchmarks on Pentium hardware, maybe even 486. “If I have not seen further it is because giants are stepping on my toes.”
- mythhabit 3y ago
  The complexity of sorting is done in comparisons. If your system can compare in constant time the complexity is indeed n*log n - if your strings are limited in length there is a constant time upper limit and the complexity holds. Saying that the average length of input strings are log n, seems to be for specific data sets and not a general conclusion. Remember that big-O notation is not about calculating the actual runtimes, but the growths as the input grows. One of the first things you learn in theory is that you must profile this no matter what. Basic complexity theory is not concerned with access times because they work in operations. If your operation involves slow random access over network, then that is the basis. There are branches of complexity theory that takes those exact examples into account. Branches that proves certain time complexity in arbitrary cache hierarchy, or only allow streaming algorithms with no lookback. They all explicitly do this in terms of IO operations. The basic theory is fine, and should be as it is for an introduction. Trying to teach a novice with respect to extremely complex CPUs or broader computer architecture is premature and sure to make many run away screaming. The overarching message should be, and in my experience is, that theory only guides you and profiling is superior.
  - hinkley 3y ago
    > The complexity of sorting is done in comparisons. Yes, and the difference often enough comes down to whether a calculation can be performed in an affordable manner. It may be on demand is not fast enough and a calculation should be done at update time, or in a queue. But it also come down to capacity planning. If you’re off by a factor of logn, it gives a bigger lie to the concept of “economies of scale” (which have always been BS in our field) and you can transition a project from making a healthy profit off of a set of features to going bankrupt on it. Each new customer costing more than you can make off of them until the VC money runs out. Who here hasn’t worked on that project? > Trying to teach a novice with respect to extremely complex CPUs or broader computer architecture I’m not talking about CPU architecture here at all. I’m talking about Information Theory, which they absolutely should be taught, and Physics, which often enough is a requirement for graduation. At least at schools where CS is lumped into the college of engineering. I haven’t sorted integers in about a decade, and maybe three times in two decades. I use BI and telemetry tools that sort them, sure, but that’s someone else’s problem and not part of OLTP workflows. For me it’s a toy problem. Nobody has ever sorted strings in O(nlogn) time. Nobody has ever inserted String->Object mappings into a hash map in O(1) time. Stop lying to intellectuals. They either learn to distrust you or you break them if they don’t.
- nerpderp82 3y ago
  Knuth isn't wrong, he is taken out of context. Knuth doesn't say programmers shouldn't worry about performance. You still have to define in the problem and the requirements and fulfill those reqs. > There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3 %. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools for seven years, I've become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off. He says we need better tooling that continuously tells us which parts of the program are taking the most time and why. Yes! We do need this. page 268, https://dl.acm.org/doi/10.1145/356635.356640 https://dl.acm.org/doi/10.1145/356635.356640 Structured Programming with go to Statements
  - hinkley 3y ago
    I’m not talking about the “premature optimization” conversation for once. I’m talking about complexity theory, which he is the father of, being unmoored from information theory and problematic in this day and age - actually problematic back to 2000 if you’re working on problems that require clusters of machines. In the last 20 years we’ve flipped from less than 20% of developer working in horizontally scaled systems to perhaps 20% who have never had to. I believe that accentuated the discrepancy.
- svat 3y ago
  > Complexity theory tells us you can sort those in nlogn time. You seem to be attacking a strawman — no CS textbook says you can sort n strings in O(n log n) time (that's just the number of comparisons); of course sorting n strings each of length m will take O(mn log n) time — that is, you have to multiply by the average time for each comparison. This is what complexity theory says, and what any good textbook would also say. You don't need "a new complexity theory built on top of Information Theory"; the current one already does so. (And m could be much bigger than log n too.)
  - hinkley 3y ago
    I’ve seen actual implementations of hash tables claim O(1) amortized insertion time, not O(m). And I misspent a summer about 5 years back thinking I had a constant space overhead mergesort (when what I had was poorly chosen input data. Bummer). I read a lot of mergesort papers then. Nobody mentioned m. I may get bored and check your theory on textbooks, but I suspect you’re letting optimism get the better of you. In a conversation about pragmatism that’s not good. All of my examples at the top were not hypothetical, they were all actual arguments I’ve had with real people or documentation I bitched to someone about. Edit: I mean fuck, even Wikipedia has it wrong: > In sorting n objects, merge sort has an average and worst-case performance of O(n log n). N objects. Not n numbers. If you want to fix the world instead of declaring bankruptcy with me, start there. At least they get space overhead right farther down: > In this case, the notion of "in-place" can be relaxed to mean "taking logarithmic stack space", because standard merge sort requires that amount of space for its own stack usage.
    - svat 3y ago
      Well, Wikipedia is obviously wrong there. I've fixed it to say number of comparison operations: https://en.wikipedia.org/w/index.php?title=Merge_sort&diff=prev&oldid=1185699028 https://en.wikipedia.org/w/index.php?title=Merge_sort&diff=p... Note also that in computational complexity theory, "n" is the length of the input in bits: if you have k strings each of length l, using a regular sort, with a comparison subroutine that takes O(l) time, will take O(kl log k) time — O(k log k) operations each taking O(l) time — which, as n=kl, is O(n log k), upper-bounded by O(n log n). ———— I looked up a couple of influential algorithms textbooks in the meantime, and I must admit this is less clear than I'd have liked (though complexity theorists are very aware of it). • TAOCP vol 3 (which starts with Chapter 5, Sorting) says, on page 5 (in the introduction section of the chapter, where he often says things informally and not exactly): > The time required to sort N records, using a decent general-purpose sorting algorithm, is roughly proportional to NlogN; we make about logN “passes” over the data. This is the minimum possible time, as we shall see in Section 5.3.1, if the records are in random order and if sorting is done by pairwise comparisons of keys. Thus if we double the number of records, it will take a little more than twice as long to sort them, all other things being equal. (Actually, as N approaches infinity, a better indication of the time needed to sort is N(logN)^2, if the keys are distinct, since the size of the keys must grow at least as fast as logN; but for practical purposes, N never really approaches infinity.) It's emphasized less than I'd have liked but he has already mentioned your observation though (and I checked this was present in the first edition in 1973). BTW, note no "O" here: where possible he actually gives the number of machine operations, including the constant factor. TAOCP is very much a "nothing up my sleeve" book, where everything is analyzed down to the constants (where possible) and machine code given. He starts with a very concrete problem where what's being sorted are numbers that each fit in a machine word: > “Memory locations R+1, R+2, R+3, R+4, and R+5 contain five numbers. Write a computer program that rearranges these numbers, if necessary, so that they are in ascending order.” and he makes it clear that what's being sorted are records that contain keys and satellite information, and he's going to mostly assume the keys are integers that fit in a word, sometimes even part of a word. The mention of sorting strings (can get there via the index) is an exercise on page 178: > Design an algorithm to sort strings α1, ..., αn on an m-letter alphabet into lexicographic order. The total running time of your algorithm should be O(m+n+N), where N = |α1| + · · · + |αn| is the total length of all the strings. Note that this running time is better than O(n (N/n) log n) — assuming that the strings are of about equal length N/n, and using a standard sorting algorithm — that I mentioned above. The solution is essentially to construct a trie. • CLRS starts its sorting section with "A sequence of n numbers" and has: > A sorting algorithm describes the method by which we determine the sorted order, regardless of whether we are sorting individual numbers or large records containing many bytes of satellite data. Thus, when focusing on the problem of sorting, we typically assume that the input consists only of numbers. Translating an algorithm for sorting numbers into a program for sorting records… Its index on sorting variable-length items points to p206 (in the 3rd edition) where, similar to TAOCP: > 8-3 Sorting variable-length items > a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time. > b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time.

by orf 3y ago

hinkley 3y ago

> or you have a complex equality function This is part of my thesis that Knuth today is wrong to the point of harm. That we need a new complexity theory built on top of Information Theory. We are steering kids wrong more often than right at this point. Data sets we work with are at least six orders of magnitude larger than they were in the eighties. There are almost no comparisons in Real Data that run in constant time, and for big enough n even addition and multiplication are not constant time. For large enough n, storage accesses are sqrt(n). Even in primary storage. Imagine you have a list of a million distinct strings. Case sensitive, alphanumeric. Complexity theory tells us you can sort those in nlogn time. But that’s pure fantasy because n unique strings have an average length of logn, meaning the compares all take logn time. Mergesort for any real data type is n (logn)². Now sort a quintillion unique strings. That takes 65-70 exabytes of space, just for starters, so it’s going to involve Ethernet cables and NVME RAID arrays. Your mergesort is now in the neighborhood of n^1.5 (log n)². Your piece of paper says this might run in hours, while the real implementation runs for weeks. For most purposes, you should multiply every algorithm in TAOC by logn. In some cases, sqrt(n). And as n actually approaches infinity, multiply by both. From another angle, I think the fact that it took 54 years to get from mergesort to Timsort has more to do with sacred cows than Tim’s brilliance. I’d like to see benchmarks on Pentium hardware, maybe even 486. “If I have not seen further it is because giants are stepping on my toes.”

mythhabit 3y ago
The complexity of sorting is done in comparisons. If your system can compare in constant time the complexity is indeed n*log n - if your strings are limited in length there is a constant time upper limit and the complexity holds. Saying that the average length of input strings are log n, seems to be for specific data sets and not a general conclusion. Remember that big-O notation is not about calculating the actual runtimes, but the growths as the input grows. One of the first things you learn in theory is that you must profile this no matter what. Basic complexity theory is not concerned with access times because they work in operations. If your operation involves slow random access over network, then that is the basis. There are branches of complexity theory that takes those exact examples into account. Branches that proves certain time complexity in arbitrary cache hierarchy, or only allow streaming algorithms with no lookback. They all explicitly do this in terms of IO operations. The basic theory is fine, and should be as it is for an introduction. Trying to teach a novice with respect to extremely complex CPUs or broader computer architecture is premature and sure to make many run away screaming. The overarching message should be, and in my experience is, that theory only guides you and profiling is superior.
- hinkley 3y ago
  > The complexity of sorting is done in comparisons. Yes, and the difference often enough comes down to whether a calculation can be performed in an affordable manner. It may be on demand is not fast enough and a calculation should be done at update time, or in a queue. But it also come down to capacity planning. If you’re off by a factor of logn, it gives a bigger lie to the concept of “economies of scale” (which have always been BS in our field) and you can transition a project from making a healthy profit off of a set of features to going bankrupt on it. Each new customer costing more than you can make off of them until the VC money runs out. Who here hasn’t worked on that project? > Trying to teach a novice with respect to extremely complex CPUs or broader computer architecture I’m not talking about CPU architecture here at all. I’m talking about Information Theory, which they absolutely should be taught, and Physics, which often enough is a requirement for graduation. At least at schools where CS is lumped into the college of engineering. I haven’t sorted integers in about a decade, and maybe three times in two decades. I use BI and telemetry tools that sort them, sure, but that’s someone else’s problem and not part of OLTP workflows. For me it’s a toy problem. Nobody has ever sorted strings in O(nlogn) time. Nobody has ever inserted String->Object mappings into a hash map in O(1) time. Stop lying to intellectuals. They either learn to distrust you or you break them if they don’t.
nerpderp82 3y ago
Knuth isn't wrong, he is taken out of context. Knuth doesn't say programmers shouldn't worry about performance. You still have to define in the problem and the requirements and fulfill those reqs. > There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3 %. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified. It is often a mistake to make a priori judgments about what parts of a program are really critical, since the universal experience of programmers who have been using measurement tools has been that their intuitive guesses fail. After working with such tools for seven years, I've become convinced that all compilers written from now on should be designed to provide all programmers with feedback indicating what parts of their programs are costing the most; indeed, this feedback should be supplied automatically unless it has been specifically turned off. He says we need better tooling that continuously tells us which parts of the program are taking the most time and why. Yes! We do need this. page 268, https://dl.acm.org/doi/10.1145/356635.356640 https://dl.acm.org/doi/10.1145/356635.356640 Structured Programming with go to Statements
- hinkley 3y ago
  I’m not talking about the “premature optimization” conversation for once. I’m talking about complexity theory, which he is the father of, being unmoored from information theory and problematic in this day and age - actually problematic back to 2000 if you’re working on problems that require clusters of machines. In the last 20 years we’ve flipped from less than 20% of developer working in horizontally scaled systems to perhaps 20% who have never had to. I believe that accentuated the discrepancy.
svat 3y ago
> Complexity theory tells us you can sort those in nlogn time. You seem to be attacking a strawman — no CS textbook says you can sort n strings in O(n log n) time (that's just the number of comparisons); of course sorting n strings each of length m will take O(mn log n) time — that is, you have to multiply by the average time for each comparison. This is what complexity theory says, and what any good textbook would also say. You don't need "a new complexity theory built on top of Information Theory"; the current one already does so. (And m could be much bigger than log n too.)
- hinkley 3y ago
  I’ve seen actual implementations of hash tables claim O(1) amortized insertion time, not O(m). And I misspent a summer about 5 years back thinking I had a constant space overhead mergesort (when what I had was poorly chosen input data. Bummer). I read a lot of mergesort papers then. Nobody mentioned m. I may get bored and check your theory on textbooks, but I suspect you’re letting optimism get the better of you. In a conversation about pragmatism that’s not good. All of my examples at the top were not hypothetical, they were all actual arguments I’ve had with real people or documentation I bitched to someone about. Edit: I mean fuck, even Wikipedia has it wrong: > In sorting n objects, merge sort has an average and worst-case performance of O(n log n). N objects. Not n numbers. If you want to fix the world instead of declaring bankruptcy with me, start there. At least they get space overhead right farther down: > In this case, the notion of "in-place" can be relaxed to mean "taking logarithmic stack space", because standard merge sort requires that amount of space for its own stack usage.
  - svat 3y ago
    Well, Wikipedia is obviously wrong there. I've fixed it to say number of comparison operations: https://en.wikipedia.org/w/index.php?title=Merge_sort&diff=prev&oldid=1185699028 https://en.wikipedia.org/w/index.php?title=Merge_sort&diff=p... Note also that in computational complexity theory, "n" is the length of the input in bits: if you have k strings each of length l, using a regular sort, with a comparison subroutine that takes O(l) time, will take O(kl log k) time — O(k log k) operations each taking O(l) time — which, as n=kl, is O(n log k), upper-bounded by O(n log n). ———— I looked up a couple of influential algorithms textbooks in the meantime, and I must admit this is less clear than I'd have liked (though complexity theorists are very aware of it). • TAOCP vol 3 (which starts with Chapter 5, Sorting) says, on page 5 (in the introduction section of the chapter, where he often says things informally and not exactly): > The time required to sort N records, using a decent general-purpose sorting algorithm, is roughly proportional to NlogN; we make about logN “passes” over the data. This is the minimum possible time, as we shall see in Section 5.3.1, if the records are in random order and if sorting is done by pairwise comparisons of keys. Thus if we double the number of records, it will take a little more than twice as long to sort them, all other things being equal. (Actually, as N approaches infinity, a better indication of the time needed to sort is N(logN)^2, if the keys are distinct, since the size of the keys must grow at least as fast as logN; but for practical purposes, N never really approaches infinity.) It's emphasized less than I'd have liked but he has already mentioned your observation though (and I checked this was present in the first edition in 1973). BTW, note no "O" here: where possible he actually gives the number of machine operations, including the constant factor. TAOCP is very much a "nothing up my sleeve" book, where everything is analyzed down to the constants (where possible) and machine code given. He starts with a very concrete problem where what's being sorted are numbers that each fit in a machine word: > “Memory locations R+1, R+2, R+3, R+4, and R+5 contain five numbers. Write a computer program that rearranges these numbers, if necessary, so that they are in ascending order.” and he makes it clear that what's being sorted are records that contain keys and satellite information, and he's going to mostly assume the keys are integers that fit in a word, sometimes even part of a word. The mention of sorting strings (can get there via the index) is an exercise on page 178: > Design an algorithm to sort strings α1, ..., αn on an m-letter alphabet into lexicographic order. The total running time of your algorithm should be O(m+n+N), where N = |α1| + · · · + |αn| is the total length of all the strings. Note that this running time is better than O(n (N/n) log n) — assuming that the strings are of about equal length N/n, and using a standard sorting algorithm — that I mentioned above. The solution is essentially to construct a trie. • CLRS starts its sorting section with "A sequence of n numbers" and has: > A sorting algorithm describes the method by which we determine the sorted order, regardless of whether we are sorting individual numbers or large records containing many bytes of satellite data. Thus, when focusing on the problem of sorting, we typically assume that the input consists only of numbers. Translating an algorithm for sorting numbers into a program for sorting records… Its index on sorting variable-length items points to p206 (in the 3rd edition) where, similar to TAOCP: > 8-3 Sorting variable-length items > a. You are given an array of integers, where different integers may have different numbers of digits, but the total number of digits over all the integers in the array is n. Show how to sort the array in O(n) time. > b. You are given an array of strings, where different strings may have different numbers of characters, but the total number of characters over all the strings is n. Show how to sort the strings in O(n) time.