Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re^3: Using indexing for faster lookup in large file

by BrowserUk (Patriarch)
on Mar 04, 2015 at 08:51 UTC ( [id://1118727]=note: print w/replies, xml ) Need Help??


in reply to Re^2: Using indexing for faster lookup in large file
in thread Using indexing for faster lookup in large file

(on an admittedly slowish AMD 8120, 8 GB memory)

I'll trade you your 3.4/4.0 GHz 8-thread processor for my 2.4Ghz 4 core if you like :)

If you haven't thrown away that 25GB file and can spare your processor for an hour, I'd love to see a like-for-like comparison of my code in Re: Using indexing for faster lookup in large file (PP < 0.0005s/record).


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^4: Using indexing for faster lookup in large file
by erix (Prior) on Mar 04, 2015 at 13:26 UTC

    The 25GB file that I used isn't sorted. Your indexer program indexes it in 7 minutes but subsequently the searcher cannot find anything in it (reports 'Not found' 1000 times).

    I've also tried with the file ordered but initially I could not get it to find anything. It turns out the regex used in your indexer [^(\d+),] did not match anything in the file. When I fixed that (it had to be [^(\d+);] for the OP's lines), the results were as follows (both measurements are very repeatable).

    Files:

    $ ls -lh hominae.txt hominae_renumbered.* -rw-rw-r--. 1 aardvark aardvark 1.5G Mar 4 13:48 hominae_renumbered.i +dx -rw-r--r--. 1 aardvark aardvark 25G Mar 4 13:17 hominae_renumbered.t +xt -rw-rw-r--. 1 aardvark aardvark 25G Feb 28 01:41 hominae.txt

    hominae.txt is the 25GB file which I made by repeating the OP's 200 lines.

    hominae_renumbered.txt is the same file but with the initial numbers replaced by 1 to 13M (so it is ordered).

    Timing, your pointer file:

    $ perl browseruk2_searcher.pl \ hominae_renumbered.txt \ hominae_renumbered.idx > bukrun; tail -n1 bukrun 'Lookup averaged 0.012486 seconds/record

    Timing, database search:

    # I took a join to 1000 random numbers as equivalent to 1000 searches: # table hm is the table with the 25GB data loaded into it $ echo "select * from (select (random()*131899400)::int from generate_series(1,1000)) a +s r(n) join hm on r.n = hm.id;" | psql -q | tail -n 1 Time: 19555.717 ms

    So your pointer file is faster but only by a small margin ( I thought it was small, anyway; I had expected a much larger difference (of course, with the db always being the slower contender)).

    Your indexing was faster too: it took only ~7 minutes to create. I forgot to time the db load but that was in the region of half an hour (could have been speeded up a bit by doing import and index separately).

    Just for the record, here is also the db load:

    time < hominae.txt perl -ne ' chomp; my @arr = split(/;/, $_, 2); print $arr[1], "\n"; ' \ | psql -c " drop table if exists hm; create table if not exists hm (line text, id serial primary key); copy hm (line) from stdin with (format csv, delimiter E'\t', head +er FALSE); "; testdb=# \dti+ hm* List of relations Schema | Name | Type | Owner | Table | Size --------+---------+-------+----------+-------+--------- public | hm | table | aardvark | | 29 GB public | hm_pkey | index | aardvark | hm | 2825 MB (2 rows)

      Thanks for doing that erix.

      'Lookup averaged 0.012486 seconds/record

      Hm. Disappointed with that. I suspect a good deal of that time is down to writing the 1000 found records to the disk.

      I suspect that if you commented out the print of the records and reran it, it'd be more in line with the numbers I get here:

      for my $i ( 1 .. $N ) { my $rndRec = 1 + int rand( 160e6 ); # printf "Record $rndRec: "; my $pos = binsearch( \$idx, $rndRec ); if( $pos ) { seek DATA, $pos, 0; # printf "'%s'", scalar <DATA>; }

      The first number is the time taken to load the index. The second run is with a warm cache:

      E:\>c:\test\1118102-searcher e:30GB.dat e:30GB.idx 16.8919820785522 Lookup averaged 0.009681803 seconds/record E:\>c:\test\1118102-searcher e:30GB.dat e:30GB.idx 4.17907309532166 Lookup averaged 0.009416031 seconds/record

      Of course, if I run it on an SSD, it looks much nicer, especially as the cache warms up:

      E:\>c:\test\1118102-searcher s:30GB.dat s:30GB.idx 33.1236040592194 Lookup averaged 0.000902344 seconds/record E:\>c:\test\1118102-searcher s:30GB.dat s:30GB.idx 3.44389009475708 Lookup averaged 0.000789429 seconds/record E:\>c:\test\1118102-searcher s:30GB.dat s:30GB.idx 4.35790991783142 Lookup averaged 0.000551061 seconds/record E:\>c:\test\1118102-searcher s:30GB.dat s:30GB.idx 3.86181402206421 Lookup averaged 0.000482989 seconds/record E:\>c:\test\1118102-searcher s:30GB.dat s:30GB.idx 4.66845011711121 Lookup averaged 0.000458750 seconds/record

      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

        Did you see that I had to fix the indexer? You do not say whether you did fix it or whether your file format is perhaps different from the OP's.

        When I searched without pointers (=pointerfile made with the wrong regex) it was very fast too but I call that cheating ;)

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others admiring the Monastery: (5)
As of 2024-03-29 12:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found