in reply to Using indexing for faster lookup in large file

A pure perl solution that results in an average lookup time of < 1/2 a millisecond per record.

This indexes the 30GB/160e6 record file in around 45 minutes. (10 lines):

#! perl -sw
use strict;

open IN, '<', $ARGV[ 0 ] or die $!;
open OUT, '>:raw', $ARGV[1] or die $!;

my $pos = 0;
print( OUT pack 'NQ', m[^(\d+),], $pos ), $pos = tell( IN ) while <IN>
+;

close OUT; close IN;

[download]

And this loads the 2GB index into memory, uses a binary search to find the index entry, seek to locate and readline to read the record. (50 lines)

<Reveal this spoiler or all spoilers in this node or all in this thread>
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". I'm with torvalds on this
In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Replies are listed 'Best First'.
Re^2: Using indexing for faster lookup in large file (PP < 0.0005s/record)
by anli_ (Novice) on Mar 02, 2015 at 18:09 UTC

    Thinks looks very interesting, but I cannot get the code to work for me.
    It's seems as if the indexing might not catch what I would like since it won't find anything I'm looking for. Also running the code you wrote as-is only produced "Not found" for me.

    I'm not familiar enough with this as to find anything. But I'm thinking that the first snippet of code walks through the data and gets the position, in bytes, for each starting number?

[reply]
      But I'm thinking that the first snippet of code walks through the data and gets the position, in bytes, for each starting number?

      Correct. (But that "snippet" is a complete working program to create the index file. You did run that first didn't you?)

      1. It gets the position (in bytes) of the start of the record (using tell),
      2. and the first number on the line using the regex (m[^(\d+),]),
      3. and then packs the two into a 12-byte binary record and writes it to the index file.
      Also running the code you wrote as-is only produced "Not found" for me.

      The first thing that comes to mind is that you never answered my question above about the sort order of your data files.

      If they are not sort numerically, then you will need to sort the file; or the index file; before the binary search will work.

      It's seems as if the indexing might not catch what I would like since it won't find anything I'm looking for.

      I'll need a little more information to go on.

      Could you run the following steps in your console and copy&paste the output (in <code></code> tags).

      Substitute whatever names you gave to the two programs above for 1118102-indexer.pl & 1118102-indexer.pl below.

      The test file need only be a few dozen lines; but the lines must start with numbers, and it must be sorted numerically. The 200 sample lines you posted above would be ideal. :

      >perl -V

>1118102-indexer smallFile.txt smallFile.idx

>1118102-searcher -N=10 smallFile.txt smallfile.idx

      [download]

      If you post the output from all 3 commands, it might give some clues as to what is going on.

      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". I'm with torvalds on this
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom