4 ms·

I note how time flies: sorting 300,000 phone numbers took 30 minutes. in python (and yes, this cheats a bit): nums = [random.randint(1000000000,9999999999) fo

I note how time flies: sorting 300,000 phone numbers took 30 minutes. in python (and yes, this cheats a bit): nums = [random.randint(1000000000,9999999999) for x in range(0,300000)] nums.sort() total time < 1 second on my macbook air. As I think about it, seems like a trie would be a good solution, you can add to it as you go with minimal memory usage. When done, you can just read off the trie top to bottom.

kragen 15y ago
Yes, a trie sort is one kind of radix sort. However, a trie is very far from minimal memory usage. Minimal memory usage for 300 000 (USA) phone numbers is about 1.5 megabytes, 5 bytes per number. A straightforward Patricia trie in C on a 32-bit machine is going to need minimally 16 bytes per number, about three times as much, 4.5 megabytes. If you're boxing each number, that's going to double your memory usage. I think he has an order-of-magnitude error: he says the 3600 was paging continuously because it was "reading a 30 megabyte file into VM", but 30 megabytes / 300k phone numbers is 100 bytes per phone number, which seems like a lot for a text file full of phone numbers. I think he had 3 million phone numbers, ten or eleven bytes each, so 30 or 33 megabytes, so building a naive trie in memory on a 64-megabyte machine is not going to work. If you wanted to sort a 30-megabyte file of 3 million phone numbers, a machine with four 9-track tape drives, no disk, and a kilobyte or so of memory would be able to do it in 22 passes over the tapes. (Practically you'd probably need at least 12 kilobytes.) On 1970-era tape drives, running at 1.25 megabytes per second, each pass would take a little under a minute. From the fact that the 64-megabyte RISC machine ran at 50 MIPS and was considered capable of handling "massive data sets", I'm guessing this anecdote dates to about 1992, plus or minus 2 years, which means that the machine in question probably had about a 5-megabyte-per-second SCSI disk and maybe a shared ten-megabit Ethernet. Without doing any nifty compression or anything, on a machine like that, you could easily read thirty one-megabyte chunks off the disk, sorting each one in memory before writing it to a temp file, and then merging the thirty one-megabyte chunks in a second pass. This is not too far from what GNU sort or Unix sort would have done, and it would have used a total of 120 megabytes of disk transfer, about 24 seconds. That is, it would have been CPU-limited, not I/O-limited. And you could have even done it in MIT Scheme, which was perfectly capable of reading a megabyte of numbers into memory even in 1990.
- vessenes 15y ago
  I'm impressed with all your math and algorithm knowledge. One comment; the guy responsible for scheme read posted in a comment on philg's site acknowledging that read was too slow for the described task. As to the size of the task, interesting math. I'd bet on you being correct as to the size of the file implying more numbers.
  - kragen 15y ago
    > I'm impressed with all your math and algorithm knowledge. You shouldn't be! I'm disappointed to discover that radix trees are usually relegated to a graduate-level data-structures class along with such curiosities as AVL trees, interval trees, and double-ended priority queues.

kragen 15y ago

Yes, a trie sort is one kind of radix sort. However, a trie is very far from minimal memory usage. Minimal memory usage for 300 000 (USA) phone numbers is about 1.5 megabytes, 5 bytes per number. A straightforward Patricia trie in C on a 32-bit machine is going to need minimally 16 bytes per number, about three times as much, 4.5 megabytes. If you're boxing each number, that's going to double your memory usage. I think he has an order-of-magnitude error: he says the 3600 was paging continuously because it was "reading a 30 megabyte file into VM", but 30 megabytes / 300k phone numbers is 100 bytes per phone number, which seems like a lot for a text file full of phone numbers. I think he had 3 million phone numbers, ten or eleven bytes each, so 30 or 33 megabytes, so building a naive trie in memory on a 64-megabyte machine is not going to work. If you wanted to sort a 30-megabyte file of 3 million phone numbers, a machine with four 9-track tape drives, no disk, and a kilobyte or so of memory would be able to do it in 22 passes over the tapes. (Practically you'd probably need at least 12 kilobytes.) On 1970-era tape drives, running at 1.25 megabytes per second, each pass would take a little under a minute. From the fact that the 64-megabyte RISC machine ran at 50 MIPS and was considered capable of handling "massive data sets", I'm guessing this anecdote dates to about 1992, plus or minus 2 years, which means that the machine in question probably had about a 5-megabyte-per-second SCSI disk and maybe a shared ten-megabit Ethernet. Without doing any nifty compression or anything, on a machine like that, you could easily read thirty one-megabyte chunks off the disk, sorting each one in memory before writing it to a temp file, and then merging the thirty one-megabyte chunks in a second pass. This is not too far from what GNU sort or Unix sort would have done, and it would have used a total of 120 megabytes of disk transfer, about 24 seconds. That is, it would have been CPU-limited, not I/O-limited. And you could have even done it in MIT Scheme, which was perfectly capable of reading a megabyte of numbers into memory even in 1990.

vessenes 15y ago
I'm impressed with all your math and algorithm knowledge. One comment; the guy responsible for scheme read posted in a comment on philg's site acknowledging that read was too slow for the described task. As to the size of the task, interesting math. I'd bet on you being correct as to the size of the file implying more numbers.
- kragen 15y ago
  > I'm impressed with all your math and algorithm knowledge. You shouldn't be! I'm disappointed to discover that radix trees are usually relegated to a graduate-level data-structures class along with such curiosities as AVL trees, interval trees, and double-ended priority queues.