3 ms·

Are there any other algorithms that work on data that can't all fit into memory? I've used Merge sort multiple times just for that ability.

by mark-r 7y ago

ska 7y ago
Do you mean other sorting algorithms, or other out-of-core algorithms in general? There are many - this has been an area of study since CS began. Have a look at vol 3 of Knuth, for starters. Also, https://en.wikipedia.org/wiki/External_sorting https://en.wikipedia.org/wiki/External_sorting talks about distribution sort; there are others.
- mark-r 7y ago
  Yes, I meant sorting algorithms in particular - I thought that was obvious by the context. I don't have a copy of Knuth, but thanks for the link. I'm not surprised that this is a well known problem, but you don't hear much about it.
  - ska 7y ago
    Early algorithm development thought about this quite a bit because system memory was really constrained.
    - mark-r 7y ago
      This reminds me of the first task I had at a new job. The company had a cross-assembler for their custom processor that ran on a PDP-11 with a 65KB total task space. I was told to add an option to turn off the cross reference output, because it was taking 30 minutes to add it to a 2 minute assembly run. Before starting I decided to figure out why the cross reference was taking so long. Each reference was added to a dynamic memory array, until the memory was filled and then the references were written to a disk file instead. At the end of the assembly, the array was sorted with a Bubble sort. Then for each symbol in the symbol table, the table and file were read linearly to find each reference for that symbol. This was an O(n^2) process - no wonder it was so slow! I took out the Bubble sort and did a Merge sort on the file, then read the file to create the cross reference directly since it was in the proper order. When the time went from 30 minutes to 30 seconds, suddenly it wasn't important to have an option to turn it off anymore.

Are there any other algorithms that work on data that can't all fit into memory? I've used Merge sort multiple times just for that ability.

by mark-r 7y ago

Are there any other algorithms that work on data that can't all fit into memory? I've used Merge sort multiple times just for that ability.

ska 7y ago

Do you mean other sorting algorithms, or other out-of-core algorithms in general? There are many - this has been an area of study since CS began. Have a look at vol 3 of Knuth, for starters. Also, https://en.wikipedia.org/wiki/External_sorting https://en.wikipedia.org/wiki/External_sorting talks about distribution sort; there are others.

mark-r 7y ago
Yes, I meant sorting algorithms in particular - I thought that was obvious by the context. I don't have a copy of Knuth, but thanks for the link. I'm not surprised that this is a well known problem, but you don't hear much about it.
- ska 7y ago
  Early algorithm development thought about this quite a bit because system memory was really constrained.
  - mark-r 7y ago
    This reminds me of the first task I had at a new job. The company had a cross-assembler for their custom processor that ran on a PDP-11 with a 65KB total task space. I was told to add an option to turn off the cross reference output, because it was taking 30 minutes to add it to a 2 minute assembly run. Before starting I decided to figure out why the cross reference was taking so long. Each reference was added to a dynamic memory array, until the memory was filled and then the references were written to a disk file instead. At the end of the assembly, the array was sorted with a Bubble sort. Then for each symbol in the symbol table, the table and file were read linearly to find each reference for that symbol. This was an O(n^2) process - no wonder it was so slow! I took out the Bubble sort and did a Merge sort on the file, then read the file to create the cross reference directly since it was in the proper order. When the time went from 30 minutes to 30 seconds, suddenly it wasn't important to have an option to turn it off anymore.