"be consistent" | |
PerlMonks |
Re^4: Out of Memory when generating large matrix (space complexity)by LanX (Saint) |
on Mar 07, 2018 at 01:31 UTC ( [id://1210440]=note: print w/replies, xml ) | Need Help?? |
> but there is also Counting Sort, Radix Sort, and other forms of distribution sorting that are of high utility in real-world applications. These algorithms are all limited to elements of fixed length (which is the case), but Sundial suggested unix sort which knows nothing about the nature of the input. And did you try to look into the space complexity of your suggestions? Counting Sort requires 4**21 buckets. Seriously ??? Radix Sort is still the best in this respect, but has O(l*n) with l length of alphabet (here 21). Even worse identical elements are in worst case only identified in the last step, requiring to be able to hold all elements in memory, while shifting them all l times from bucket to bucket. A hash count can go thru different files without keeping them all in memory, because identical elements collapse into one count. Last but not least, a hash count is much easier implemented.
Cheers Rolf
In Section
Seekers of Perl Wisdom
|
|