I guess you meant to store the first file as database records in a table, and for each record in the second file, do a select from the table? That will be millions of selects, can a perl/batch be faster? Thanks.

Millions of records? Not true at all!

You can do simply one query, say you want to find out all records that are in table1 but not table2, then you can either:

select blah from table1 t1
where not exists
(select 1 from table2 t2
where t1.blah = t2.blah
)
[download]

Or (if munus is supported):

select blah from table1
minus
select blah from table2
[download]

It should be easy for you to modify the query a bit to satisfy your needs.

DBD::SQLite might be the answer to this particular case, but it is slow when you try to insert into a table with index. (Not sure what happens without index, general speaking insert is slower with index, when select is faster with index. That's OT)

I compared DBD::SQLite, with ODBC, the same table structure and index. insert 1000 rows, and then select. It took ODBC 2 seconds to insert 1000 rows, and 0 (which means less than 1) second to select; but it took SQLite 310 seconds to insert (way to big), adn 0 second to select (which is virtually the same):

use DBI;
use Data::Dumper;


use strict;
use warnings;
  
my $dbh = DBI->connect("dbi:SQLite:dbname=dbfile","","");
#my $dbh = DBI->connect("dbi:ODBC:everything","","");

=document
#$dbh->do('create table table1(col1 number(10), col2 number(10))');
$dbh->do('create table table1(col1 int, col2 int)');
$dbh->do('create index index1 on table1(col1)');

#$dbh->do('create table table2(col1 number(10), col2 number(10))');
$dbh->do('create table table2(col1 int, col2 int)');
$dbh->do('create index index2 on table2(col1)');
=cut
$dbh->do('delete from table1');
$dbh->do('delete from table2');
my $st1 = $dbh->prepare('insert into table1(col1, col2) values(?, ?)')
+;
my $st2 = $dbh->prepare('insert into table2(col1, col2) values(?, ?)')
+;
print time, "\n";
for my $i (1..1000) {
    $st1->execute($i, $i * 2);
    if ($i % 2) {
        $st2->execute($i, $i * 3);
    }
}
print time, "\n";

{
    my $st3 = $dbh->prepare('SELECT t1.col1 FROM table1 t1 LEFT OUTER 
+JOIN table2 t2 ON (t1.col1 = t2.col1) WHERE t1.col1 IS NOT NULL AND t
+2.col1 IS NULL');
    $st3->execute();
    my $ref3 = $st3->fetchall_arrayref;
    #print Dumper($ref3);
}
print time, "\n";

$dbh->disconnect();
[download]

it took SQLite 310 seconds to insert

The SQLite docs say what you should do to improve speed: group instructions into transactions and eventually modify the "syncronous" pragma.

If you add $dbh->do('begin'); before your loop and $dbh->do('commit'); at the end, the insertion will take less than one second, as it should be.

use Time::HiRes qw(gettimeofday tv_interval);
my $start_time = [gettimeofday];
$dbh->do('begin');
for my $i (1..1000) {
    $st1->execute($i, $i * 2);
    if ($i % 2) {
        $st2->execute($i, $i * 3);
    }
}
$dbh->do('commit');
my  $elapsed = tv_interval ( $start_time, [gettimeofday]);
print "creation time: $elapsed\n";

__END__
insertion time: 0.263462
[download]

    $ comm -12 <(sort -u file1) <(sort -u file2)
[download]

Here's how to find the records that are unique to the first file:

    $ comm -23 <(sort -u file1) <(sort -u file2)
[download]

Cheers,
Tom

open FILE1,"<file1";
open FILE2,"<file2";
my $key1=<FILE1>;
my $key2=<FILE2>;
while((!eof(FILE1)&&(!eof(FILE2))){
  if($key1 gt $key2){
    # do something when you find a key in FILE2 and not in FILE1
    # read a line from FILE2
    $key2=<FILE2>
  }elsif($key1 lt $key2){
    # do something when you find a key in FILE1 and not in FILE2
    # read a line from FILE1
    $key1=<FILE1>;
  }else{
    #found a match, read a line from FILE1 and FILE2
    #this behavior may vary depending on how you want to 
    #handle multiple matches, i.e. a given line is in both
    #files more than once
    $key1=<FILE1>;
    $key2=<FILE2>;
  }
}
close FILE1;
close FILE2;
[download]

That way doing the check for common records is as fast as reading each file once and you never have to hold more than one record from each file in memory at a time.

L

After writing everything below it occurred to me that your original solution might work just fine if you used a DB_File tied hash rather than a Perl in-memory hash. Roughly:

use DB_File;
my $hash;
tie %hash, DB_File, "first_file.hash";
while (<FIRST_FILE>)
{
  $hash{$_} = undef;
}

while (<SECOND_FILE>)
{
  print $_ if exists $hash{$_};
}
[download]

Below is what I wrote first of all, it's still interesting as it explains a bit about how to make your own hash.

Your idea of a hash is correct but as you say, Perl's internal hash is not suitable. Instead, you could build your own hash.

First you need a hash function. This could be fairly simple. For example just add up the ascii values of the characters in each line and then find the remaineder mod 256

my $h = 0;
foreach (split("", $line)) {
  $h+=ord($_)
}
$h = $h % 256;
[download]

The thing now is that 2 lines which have differing hash values must be different, there is no need to compare them character by character. If the hash values are the same you do have to compare the lines character by character . So comparing the hash value first eliminates a large amount of work.

What you have now is exactly the same as a Perl internal hash except that Perl's hash buckets are stored in memory, yours are stored on disk. Also, Perl uses a more complicated function to make sure that things are spread evenly around all the buckets.

There are a couple of different things you can do now.

You could make 2 directories, one for each big file. Each directory will have 256 files - 1 for each bucket. Then you go through the big files, writing each line out into it's correct bucket file. You'll be left with 256 pairs of files, something like

file1/0
file1/1
...
file1/255
file2/0
file2/1
...
file2/255
[download]

Another approach is to split just 1 of the files into buckets and then go through the other file line by line, figuring out which bucket each line would be in and then checking to see if it is. This will be pretty slow. To speed it up, instead of each bucket just being a flat file, you could make each bucket a DB_File file, then you can use DB_File's hash lookup to see if a particular line is there. Basically you're using a 2-layered hash.

$ # Create two large files to work with.
$ perl -e 'printf "%08d\n", int rand 100_000_000 for 1 .. 10_000_000' 
+> big1
$ perl -e 'printf "%08d\n", int rand 100_000_000 for 1 .. 10_000_000' 
+> big2

# Sort them, make then unique.
$ time sort -u big1 > big1.s

real    4m0.489s
user    2m4.360s
sys     0m7.200s

$ time sort -u big2 > big2.s

real    3m24.848s
user    1m55.430s
sys     0m6.460s 

# Report the number of lines that are in the second file, and not in t
+he first
$ time comm -13 big1.s big2.s | wc -l
8611170

real    0m14.278s
user    0m12.850s
sys     0m0.400s
[download]

B. Actually for each record in the second file, I'd like to mark it 1/0 depending on whether it's in the first.