3 ms·

Reverse a 100 GB file

5 points by nreece 18y ago

mahmud 18y ago
holly adsense-laden batman. that site is unreadably over stuffed with ads.
- moe 18y ago
  Adblock helps. The page was a clean read for me, not a single ad.
chethan 18y ago
I wasn't sure whether he meant words as in the data size unit or words as in English words. However, since we are assuming it's ASCII, 1 char = 1 byte. Reverse the order of the bytes in each word. Reverse the order of bytes in the file. [edit]If you're doing 1 word = the unit of size, the first step isn't necessary since all words will obviously be the same length. Just go through and swap the 1st word with the Nth, the 2nd with the (N-1)th, etc.[/edit] Since you are doing in-place swapping, you aren't using any extra memory aside from a 1-byte (word) temporary register. If you want to be really clever, you can use the XOR swap algorithm and not use the byte at all (at the cost of more CPU use). This will work in O(N) time.
chethan 18y ago
The trie doesn't require a limited set of words. Counts can easily be used or not. If you were to write the entire path to disk, you'd be optimizing the time complexity while probably hammering the filesystem (and greatly increasing the (externalized/ignored) FS portion of the time complexity). If you do a left-biased traversal/generation of a trie in tiers, you get a merge-like sort and reduce the space cost of a normally distributed set of data. Your merge files should be offsets of the original file. Divide the offsets into an appropriate number of divisions (one for each of the characters in the set). Using the offsets, divided into sets of N starting characters, you'd get 256 (for first byte) or 64k (for two bytes) (sub)sets. You can continue the pattern, if appropriate, or just do the merge sort. Your first-pass cost is the generation of the first level sets, and then your additional costs are limited to the division of each set as you reach them. Create sets by the next character (an additional 256 files), and keep moving down. You're creating a tree structure on disk and creating/traversing it in tiers. Your worst case for this is a common prefix. In the most basic implementation, you'd end up with NM comparisons, in NM^2 space, across M files (N:words, M:prefix length). A reasonable implementation would delete the parent file, so you should stay near the 2NM space for disk. Your in-memory cost is almost zero though, since you're relying on M in the worst implementation and '1' in the best.
dave_au 18y ago
I like the first solution in the comments - use mmap, work page by page (or pair of pages by pair of pages).

5 points by nreece 18y ago

mahmud 18y ago

holly adsense-laden batman. that site is unreadably over stuffed with ads.

moe 18y ago
Adblock helps. The page was a clean read for me, not a single ad.

chethan 18y ago

I wasn't sure whether he meant words as in the data size unit or words as in English words. However, since we are assuming it's ASCII, 1 char = 1 byte. Reverse the order of the bytes in each word. Reverse the order of bytes in the file. [edit]If you're doing 1 word = the unit of size, the first step isn't necessary since all words will obviously be the same length. Just go through and swap the 1st word with the Nth, the 2nd with the (N-1)th, etc.[/edit] Since you are doing in-place swapping, you aren't using any extra memory aside from a 1-byte (word) temporary register. If you want to be really clever, you can use the XOR swap algorithm and not use the byte at all (at the cost of more CPU use). This will work in O(N) time.

chethan 18y ago

The trie doesn't require a limited set of words. Counts can easily be used or not. If you were to write the entire path to disk, you'd be optimizing the time complexity while probably hammering the filesystem (and greatly increasing the (externalized/ignored) FS portion of the time complexity). If you do a left-biased traversal/generation of a trie in tiers, you get a merge-like sort and reduce the space cost of a normally distributed set of data. Your merge files should be offsets of the original file. Divide the offsets into an appropriate number of divisions (one for each of the characters in the set). Using the offsets, divided into sets of N starting characters, you'd get 256 (for first byte) or 64k (for two bytes) (sub)sets. You can continue the pattern, if appropriate, or just do the merge sort. Your first-pass cost is the generation of the first level sets, and then your additional costs are limited to the division of each set as you reach them. Create sets by the next character (an additional 256 files), and keep moving down. You're creating a tree structure on disk and creating/traversing it in tiers. Your worst case for this is a common prefix. In the most basic implementation, you'd end up with NM comparisons, in NM^2 space, across M files (N:words, M:prefix length). A reasonable implementation would delete the parent file, so you should stay near the 2NM space for disk. Your in-memory cost is almost zero though, since you're relying on M in the worst implementation and '1' in the best.

dave_au 18y ago

I like the first solution in the comments - use mmap, work page by page (or pair of pages by pair of pages).