You already mentioned using a database which is a fine solution. It need not be heavy - I have used DBD::SQLite for problems like this. It would take less time to set up and have working then you have spent thinking about the problem.

Update: As an after thought, depending on how sparse your keys are, it may make sense to transform your file into fixed width records. You determine how many bytes the largest value you need to hold is and make all records that size. You no longer need to have keys in the file because the record number equates to the key name. Unfortunately, you need to pad missing records which may grow your file to an unmanageable size depending on how sparse things are. Something to think about.

What would be the best way (defining best as the ratio between efficiency / simplicity of implementation) of doing this?

Is making a DB with the file or writing C subroutines to access the file the only way of improving this task?

The binary-search approach explained elsewhere in the thread seems like a reasonable approach, although I would be hesitant to go that route myself. If even loading an index swamps your machine then it seems like we are talking about serious quantities.

On that criterion alone, I would load it into a relational database and be done with it. At least then you don't have to worry about ensuring that the file is always sorted, which is one less thing to worry about when adding new keys.

Without presuming to know what you need this for, I can't help but thinking that if it were my baby, I know that sooner or later people would ask me questions like "how many keys have been used between 215000 and 220000. In that case the binary search algorithm doesn't buy you anything, but you get all that for free in database.

Be that as it may, if you really don't want to go to DB route, you can always apply a divide-and-conquer strategy to your file: take the first two (or last, or three, or multi-level) digits of the key, and write the key/value pairs out to a corresponding filename.

When you need to look up a key, figure out what file it would be located in, then slurp the entire file and do a pattern match with

    my ($val) = ($_ =~ /\b$key\t(\d+)\b/);
[download]

That is, don't even bother reading the file line by line, that's too slow. Again, this is a clumsy approach: if your lookups are all over the search space, you'll spend all your time sucking up files. Then you start thinking about a cache of least-recently used files... nah, just put it in a database and be done with it.

A couple of methods you could try:

• Scan the file and build a hash of (key,file position) pairs so you can immediately seek to the line you want. However, this requires a complete scan through the file (the first time).
• Alternatively, sort the file and use a binary search to locate the line. This way, you'd need roughly log2(line_count) seek/reads to get the data you're looking for.

In either case, you'll probably want to refer to the functions:

perldoc -f seek

perldoc -f tell

...roboticus

Scan the file and build a hash of (key,file position) pairs so you can immediately seek to the line you want.

Well, if a hash of key => values doesn't fit into memory I 'm afraid that a hash with keys => positions will not fit either.

Alternatively, sort the file and use a binary search to locate the line. This way, you'd need roughly log2(line_count) seek/reads to get the data you're looking for.

That would be a better solution (the file is already sorted)

Thanks

citromatik

You could have an array where subscript N indicates key N thousand, and the value of the array element would be the disk offset to look at.

Let's assume you have fixed length records of 30 bytes. Element 21 having value 999990 would mean the first key greater than or equal to 21,000 was stored at disk offset 999,990.

Having said all that, I'd also suggest using a binary search.

my $db = DBM::Deep->new( $filename );

print "$db->{32}\n"; # prints 14456
[download]

As others stated: Binary Search is the key to speed! I assume you know about binary search algorithms. I think, you need not fill the keys to get a fixed record length.

As you already have a sorted file, simply seek to the files center by dividing its size in bytes by 2. Then read one line. This one is to be discarded as it is most surely incomplete. Get the current fileposition as your corrected value for the file's center and read the next line in order to find out whther you hit the correct key or whether you have to advance to the upper half or go back into the lower half.

again you will always have to read one line and discard it.

You might miss one line using this approach:

1230 value AAA
1235 value AA
1240 value A
[download]

in such a case you will have to read all the lines from lower to upper bound to check for a hit.

This is just a rough idea i've never tested!

1. How many lines in your file?
2. Over what range are the keys and values spread?
3. How many lookups per load?

   Eg. Is this a web app that does half a dozen lookups per load, or a system app that does thousands per load.

4. Is concurrency a requirement?
5. How often does the dataset change?
6. How fast a lookup are you hoping for?

How many lines in your file?

18885025

Over what range are the keys and values spread?

keys from 6 to 164664533
values from 0 to 494514

How many lookups per load?

This is a stand-alone system application that does up to thousands lookups per run (although it could be called for just one lookup).This is an intermediate step in the app. The others step are well optimized for performance.

Is concurrency a requirement?

In principle, no

How often does the dataset change?

More or less, once in a month

How fast a lookup are you hoping for?

As much as I can. As I told before, the rest of the script is optimized for speed and memory usage and it is a bit frustrating to see how the others parts of the program (which seems to be much more complicated), runs very fast and these lookups are slowing down so much the overall process

Thanks,

citromatik

Can you afford 108 MB of ram?

If so, rewrite your file in binary, packing each KV pair using 'NS'. 18885025 * 6 / 2**20 = 108 MB.

Slurp the entire file into a single string and then use a binary chop on it something along the lines of:

open DATA, '<:raw', $datafile or die $!;
my $data;
sysread( DATA, $data, -s( $datafile ) ) or die $!;
close DATA;

sub lookup {
    my $target = shift;
    my( $left, $right ) = ( 0, length( $data ) / 6 );
    while( $left < $right ) {
        my $mid = int( ( $left + $right ) / 2 );
        my( $key, $val ) = unpack 'NS', substr $data, $mid * 6, 6;
        if( $key < $target ) {
            $left = $mid +1;
        }
        elsif( $key > $target ) {
            $right = $mid - 1;
        }
        elsif( $key == $target ) {
            return $val;
        }
        else {
            return;
        }
    }
}
[download]

In a quick test this achieved lookups 12,500 per second. (Let's see them do that with an RDBMS :)

Notes: I would not be surprised if the above contains bugs it was thrown together. My test data was only 10e6 lines, so expect a little slower.

---

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.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

I think there is also a small unix tool that does line based binary search in files, but I can't remember the name. Update: It seems look (1) (in Debian shipped with in the bsdmainutils package) does the trick, but I'm not sure if it works with numerically sorted lines.

...but I'm not sure if it works with numerically sorted lines.

Then make a processed copy of the file, where you pad the numbers to the right to a fixed length, with sprintf, so they sort the same numerically and asciibetically.

Right, but again it requires the size of the index to be known in advance - in which case you can use the binary data much more efficient.

For the simple things, like packing a number into 4 bytes, there is pack, which does that, and many more things. The usual approach would be to pack all the offsets of the lines (or a better key) into one long string, as four bytes per line:

my $offsets = '';
while (<$fh>) {
    my $offset = tell $fh;
    $offsets .= pack 'N', $offset;
};
[download]

Whether to store the whole file or just the offset of every 10 lines is a matter of (low-level) optimization.

Instead of using a full relational database, how about using dbmopen? It binds a hash to a Berkley DB file. Unless you use "keys" or "values", you should be fine with that, I guess.

Well, this looks like a perfect job for GDBM_File: it ties a hash to a GDBM file. So you load the hash into the file, and then you can use it just as a regular hash, except it's on disk. That's probably the solution that will involve the less extra coding on your part.

Since you know that the large-file is already sorted, the most efficient processing technique would be to sort the other input file(s) by the same key. Then, you can process the two streams side-by-side sequentially: no “search” is involved.

If it is at all possible to do this, then this is what you should do. “Inconvenience yourself” to do it this way:   you'll be glad you did.

You do not have to worry about updating the original file. Write the changes to another file in the same format, then sort that file by the same key, then merge them into the original file. In each case, you're doing the job by means of sorts (which are unexpectedly fast), and sequential reads. When you're finished, you'll have the original input master-file (unchanged), the delta-file (now sorted), and the updated master-file.

Yes, that is exactly how data-processing was done, using punched cards, long before digital computers were invented... And it worked.

Failing that, an appropriate strategy would be to use something like a DB_File i(e.g./i a Berkeley DB) ... but beware. Random seeks are time-consuming in large quantities.

... the most efficient processing technique would be to sort the other input file(s) by the same key.

What other input files?

---

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.

"Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."

    my $newpos=look *FILE, $string, 0, 0;