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]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (4)
As of 2018-02-19 20:51 GMT
Find Nodes?
    Voting Booth?
    When it is dark outside I am happiest to see ...

    Results (266 votes). Check out past polls.