Re: searching through data

What about getting the job done in less than a half of second? (no DBMs, no Hashes):

use strict;
use warnings;

my ($file1, $file2) = @ARGV;

my $ids = 1000000;  # last id
my $bin=0;
substr($bin,$_,1,pack ("c",0)) for (0..$ids);

# Create the index
open my $fh1, "<", $file1 or die $!;
while (my $id = <$fh1>){
  chomp $id;
  substr($bin, $id,1,pack ("c",1));
}
close $fh1;

# Search $ids from file 2
open my $fh2, "<", $file2 or die $!;
while (my $id2 = <$fh2>){
  chomp $id2;
  print "$id2\n" if ((unpack "c",substr ($bin,$id2,1)) == 1);
}
close $fh2;
[download]

file1 contains 400000 numbers between 0 and 1000000. file2 contains 10000 numbers in the same range. Processing both takes less than half a second.

time perl sp.pl file1 file2 > /dev/null
real    0m0.448s
user    0m0.448s
sys     0m0.000s
[download]

A bit of explanation: The program constructs an scalar ($bin) containing 1000000 of 0s. While processing the index (the first list of ids), it substitutes every 0 at position $id with a 1.

Then, it reads the second file of ids and checks if at position $id2, the $bin scalar has a 0 (not seen previously) or a 1 ($id already seen in the first file).

Hope this helps

citromatik

Comment on Re: searching through data Select or Download Code

Replies are listed 'Best First'.
Re^2: searching through data by almut (Canon) on Apr 16, 2009 at 14:31 UTC
getting the job done in less than a half of second While this is certainly a neat approach, and much better memory-wise (as long as you can keep the maximum possible number within limits...), it isn't actually faster than using a hash. The slightly modified code (to make it comparable with the hash version I suggested) takes about the same running time on my system. For example, with 1000_000 values to look up: $ time ./757954_bytevector.pl >out real 0m4.421s user 0m4.368s sys 0m0.048s ---------- #!/usr/bin/perl # create file with numbers to look up open (my $fh, ">", "in.txt") \|\| die "$!"; for (1..1000000) { print $fh int rand 1e6, "\n"; } close $fh; my $ids = 1000000; # last id my $bin=0; substr($bin,$_,1,pack ("c",0)) for (0..$ids); # Create the index for (1..400000) { my $id = int rand 1e6; substr($bin, $id,1,pack ("c",1)); } # Search $ids open my $fh2, "<", "in.txt" or die $!; while (<$fh2>){ my ($num) = m/^(\d+)/; print "$num, " if ((unpack "c",substr ($bin,$num,1)) == 1); } [download]	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: searching through data
by almut (Canon) on Apr 16, 2009 at 14:31 UTC

getting the job done in less than a half of second

While this is certainly a neat approach, and much better memory-wise (as long as you can keep the maximum possible number within limits...), it isn't actually faster than using a hash. The slightly modified code (to make it comparable with the hash version I suggested) takes about the same running time on my system. For example, with 1000_000 values to look up:

$ time ./757954_bytevector.pl >out

real    0m4.421s
user    0m4.368s
sys     0m0.048s

----------

#!/usr/bin/perl

# create file with numbers to look up
open (my $fh, ">", "in.txt") || die "$!";
for (1..1000000) {
    print $fh int rand 1e6, "\n";
}
close $fh;

my $ids = 1000000;  # last id
my $bin=0;
substr($bin,$_,1,pack ("c",0)) for (0..$ids);

# Create the index
for (1..400000) {
    my $id = int rand 1e6;
    substr($bin, $id,1,pack ("c",1));
}

# Search $ids
open my $fh2, "<", "in.txt" or die $!;
while (<$fh2>){
    my ($num) = m/^(\d+)/;
    print "$num, " if ((unpack "c",substr ($bin,$num,1)) == 1);
}
[download]

[reply]
[d/l]