Re^5: In-place sort with order assignment

In other words, instead of doing the sorting after populating the file with all of the hash keys, do the sorting one element at a time as each hash key is added to the file.

From what I understand, a huge hash structure already exists and foreach keys %hash makes a list of the hash keys, which essentially doubles the amount of memory required. My question is how to spew all of the keys into a file without making an intermediate structure that contains all of the keys. I suspect that there is a way to do that. If so, the the sort part belongs to another process that will release its memory when done. The Perl hash table assignments of 1,2,3,4 will cause %hash to grow, but only as much as needed and presumably less than 2*storage required for the keys.

Comment on Re^5: In-place sort with order assignment Download Code

Replies are listed 'Best First'.
Re^6: In-place sort with order assignment by dasgar (Priest) on Sep 20, 2010 at 05:06 UTC
Ah, figured there was something that I either missed or didn't understand. I've never really tried looking under the hood to understand fully what Perl is doing behind the scenes. I didn't realize that the `foreach` command would make a copy of the data structure. Now that you've enlightened me about this, I realize how foolish my idea was. And that leads me back to thinking along the lines of what you had said in the post that I responded too. (By the way, thanks for teaching me something new. I sincerely appreciate you kindly pointing out something that I overlooked.) My question is how to spew all of the keys into a file without making an intermediate structure that contains all of the keys. Well, here's a thought on that. I'm assuming that there had to have been some Perl code that created the keys in the hash. If you have access to modify that code, modify it so that it's printing to a file instead creating the hash. That leaves the unsorted keys in a file and no initial hash. That in turn frees up more memory for a sorting method, which can be applied as the keys are written to file and/or after all keys have been written to file. In other words, "extract" the keys before the hash is created and then do the sort. Then after the sorting is complete, create the hash. Of course, if the code where the hash keys are added cannot be modified for some reason, the above idea can't be implemented. Does that sound like a reasonable idea or have I missed something else due to my lack of knowledge and experience?	[reply] [d/l]

Replies are listed 'Best First'.

Re^6: In-place sort with order assignment
by dasgar (Priest) on Sep 20, 2010 at 05:06 UTC

Ah, figured there was something that I either missed or didn't understand. I've never really tried looking under the hood to understand fully what Perl is doing behind the scenes. I didn't realize that the foreach command would make a copy of the data structure.

Now that you've enlightened me about this, I realize how foolish my idea was. And that leads me back to thinking along the lines of what you had said in the post that I responded too. (By the way, thanks for teaching me something new. I sincerely appreciate you kindly pointing out something that I overlooked.)

My question is how to spew all of the keys into a file without making an intermediate structure that contains all of the keys.

Well, here's a thought on that. I'm assuming that there had to have been some Perl code that created the keys in the hash. If you have access to modify that code, modify it so that it's printing to a file instead creating the hash. That leaves the unsorted keys in a file and no initial hash. That in turn frees up more memory for a sorting method, which can be applied as the keys are written to file and/or after all keys have been written to file.

In other words, "extract" the keys before the hash is created and then do the sort. Then after the sorting is complete, create the hash.

Of course, if the code where the hash keys are added cannot be modified for some reason, the above idea can't be implemented.

Does that sound like a reasonable idea or have I missed something else due to my lack of knowledge and experience?

[reply]
[d/l]