4 ms·

x = [(randint(20,80), "John Smith") for x in range(2_300_000)] x.sort(key=lambda x: x[0]) x[2_300_000//2] Takes under a second. You can expand it to g

x = [(randint(20,80), "John Smith") for x in range(2_300_000)] x.sort(key=lambda x: x[0]) x[2_300_000//2] Takes under a second. You can expand it to generate random names rather than just ages, if you feel like it, but the end result wouldn't be much different. In short: this is something you shouldn't even think about in modern computers since it's that fast.

vlovich123 4y ago
On my laptop generating it takes ~1s and sorting takes ~280ms. As always, dependent on the power of the machine running things.
- thrown_22 4y ago
  After thinking about it for a while, the reason why it was a hard problem back then is that the payroll wouldn't fit in memory and you'd need to do a sort on disk. In this day and age it would be like trying to sort 100 TB of data. Not a hard problem, but not exactly something you do daily either. And still dreadfully slow since you need to use disk memory while copying everything over. A more modern version of the question would be: >You have a list of integers, in random order, that is 20 times larger than the hard drive you have on your work station and 1,000 times larger than your work station ram....
  - vlovich123 4y ago
    Naw. Sorting is a total waste here. I can read off an "infinite" amount of records of the wire with O(1) space usage and O(n) result. Even back then. Look at my radix sort solution: https://news.ycombinator.com/item?id=32684017 https://news.ycombinator.com/item?id=32684017 The intent behind the problem in the textbook is fine - think non-linearly about the problem. Just the example used has a trivial solution not mentioned (i.e. option 5).
    - thrown_22 4y ago
      Yes, that's why I changed it to having a list of arbitrary integers. You're also assuming integer ages when a more natural comparison would have date of birth. Which has 365 times the number of buckets. Something that was again problematic to fit into a 1980s memory.
bobsmooth 4y ago
Haha, removing the library I used to generate random names took my code down to a few seconds.

vlovich123 4y ago

On my laptop generating it takes ~1s and sorting takes ~280ms. As always, dependent on the power of the machine running things.

thrown_22 4y ago
After thinking about it for a while, the reason why it was a hard problem back then is that the payroll wouldn't fit in memory and you'd need to do a sort on disk. In this day and age it would be like trying to sort 100 TB of data. Not a hard problem, but not exactly something you do daily either. And still dreadfully slow since you need to use disk memory while copying everything over. A more modern version of the question would be: >You have a list of integers, in random order, that is 20 times larger than the hard drive you have on your work station and 1,000 times larger than your work station ram....
- vlovich123 4y ago
  Naw. Sorting is a total waste here. I can read off an "infinite" amount of records of the wire with O(1) space usage and O(n) result. Even back then. Look at my radix sort solution: https://news.ycombinator.com/item?id=32684017 https://news.ycombinator.com/item?id=32684017 The intent behind the problem in the textbook is fine - think non-linearly about the problem. Just the example used has a trivial solution not mentioned (i.e. option 5).
  - thrown_22 4y ago
    Yes, that's why I changed it to having a list of arbitrary integers. You're also assuming integer ages when a more natural comparison would have date of birth. Which has 365 times the number of buckets. Something that was again problematic to fit into a 1980s memory.

bobsmooth 4y ago

Haha, removing the library I used to generate random names took my code down to a few seconds.