Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

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

by wrog (Friar)
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.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://951556]
[stevieb]: RT ticket for the csum mismatch of various versions of Strawberry Perl

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (6)
As of 2017-03-29 21:13 GMT
Find Nodes?
    Voting Booth?
    Should Pluto Get Its Planethood Back?

    Results (353 votes). Check out past polls.