Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re^10: Indexing two large text files

by BrowserUk (Pope)
on Apr 12, 2012 at 18:16 UTC ( #964805=note: print w/ replies, xml ) Need Help??


in reply to Re^9: Indexing two large text files
in thread Indexing two large text files

In nearly all cases, I'd say that "put your filtering file in a hash and process the other file against it" is such a superior algorithm

I agree with your thoughts on the use of hashes for filtering.

that it's worth trying, even if you suspect it's going to force swapping to disk.

The problem is that hashes are just about the ultimate in 'cache unfriendly data structures'.

Once built, even if only a relatively small percentage of the total structure needs to be swapped out at any given time, their nature means that you will need to swap-in the bit that is out (and therefore swap out a bit that is currently in), for nearly every iteration of the lookup.

In turn, that has a disastrous affect upon the usually good performance of serial reading the other file from disk.

And if you enter swapping during hash creation, prior to the final doubling of the buckets, then the copying of the keys from the last intermediate stage to the final hash, just sends the disk head nuts. It can take forever.

It's a great way to check if your disk is working properly :)


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

The start of some sanity?


Comment on Re^10: Indexing two large text files

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (5)
As of 2014-09-18 03:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

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











    Results (105 votes), past polls