Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re^3: how to merge many files of sorted hashes?

by wrog (Monk)
on Feb 02, 2012 at 23:25 UTC ( #951556=note: print w/ replies, xml ) Need Help??


in reply to Re^2: how to merge many files of sorted hashes?
in thread how to merge many files of sorted hashes?

so let's see if I'm reading this right:

  • you have 100 points
  • for every possible triple (1,000,000 combinations) you're computing a matrix
  • each matrix gets pushed 100 times (onto 100 different keys)
  • you start a new file every 1000 matrices (so there'll be 1000 files when you're done, and each file will have 100,000 matrices.
but you don't say how many distinct keys there are (i.e., how finely binning is grouping things).

But it doesn't matter. For every single key you are doing a linear search through every file. So that's (number of keys) * 100,000,000 matrices to wade through; no wonder this is slow.

You need to be writing each %small_hash in sorted order. Sorting 1000 small_hashes will be faster than sorting the big hash (1000*(n/1000)*log(n/1000) = n log(n/1000) < n log(n) but the really important thing is this will enable the merge I was talking about before, which only reads each file once rather than once for every key value.


Comment on Re^3: how to merge many files of sorted hashes?
Select or Download Code

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://951556]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (3)
As of 2014-09-22 00:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (176 votes), past polls