SQLite would be an excellent database alternative for your needs. 2-million phone numbers isn't all that big of a deal for a lightweight database like SQLite. And it's self contained; all you need is DBI and DBD::SQLite.

But I wonder if even a lightweight database is needed. What you could use is a series of area-code specific flat files. Maintain each flat file in sorted order. Put one phone number per line in the file, so that each line is the same length. That gives you a simple starting point for doing binary searches. If each line is twelve characters long (11 digit phone plus newline), you can use seek to read from offsets within the file.

The idea behind a binary search is to start at the halfway point in the file. If that record is too 'high', divide the first half into half and look there. If that's too low, divide the 2nd quarter into half and look there. ...and so on. There are lots of examples on the net for binary search algorithms. The good thing about a binary search is that it takes place in O(log n) average time, whereas a linear search (what you're doindg now) takes O(n) time without the complexity of a database.

...just another thought. But honestly, have we forgotton about our computer science 101 classes? A binary search of a fixed-width record length flat file is "how it's done" programatically. Using a database is convenient, but it shouldn't be the only option considered. As for slurping flat files, that doesn't scale well, and with 2 million (and growing) records, you need to think about that.

...doing binary searches.

And guess what, someone already did all the work for you (and I already mentioned it above) ;-)

Seems almost like overkill when it can be done in just a few lines. The function below searches three million records very quickly.

# Usage: record_search($search_string, $filename, 11);
# Returns the record number if the record is found, undef otherwise.
# Searched file must be sorted.

sub record_search {
    my ($key, $filename, $recordsize) = @_;
    my $fh = IO::File->new($filename, 'r')
        or croak("Could not open `$filename': $!");

    my $hi = ($fh->stat)[7] / $recordsize;
    my $lo = 0;

    while ($lo < $hi) {
        my $mid = int(($lo + $hi) / 2);
        $fh->seek($mid * $recordsize, 0);
        my $target = $fh->getline();
        chomp($target);

        if ($target < $key) {
            $lo = $mid + 1;
        } elsif ($target == $key) {
            return $mid;
        } else {
            $hi = $mid;
        }
    }
}
[download]

Update Forgot to mention: even though this function opens the file every time, it can successfully search 3 million records about 2000 times per second on a 3Ghz Pentium 4. I can't see much justification for anything more complicated. Threads? Bit strings? Crazy! :)

There is a lot you can do to make your code better, as shown below. Note that this will not make your code faster.

• Localize your variables (using my).
• Localize file handles too, after making them lexicals. (Now that they're scoped, close is no longer needed.)
• Use strict to make sure your variables are localized.
• Use warnings to detect errors.
• Don't open four files when you only need to open one or two.
• Indent properly.
• Use the safer 3-arg open.
• Don't hardcode the area codes.
• Don't use regexp to search for strings. Use index for a great speed boost.

use strict;
use warnings;

use File::Spec qw( );
use IO::Dir    qw( );

my $dir  = 'E:\\Documents and Settings\\ebrine';
my $cell = File::Spec->catfile($dir, 'Cell.txt');

my %area_codes = map { /(\d+)/; $1 => File::Spec->catfile($dir, $_) }
                 grep /^\d+\.txt\z/i,
                 IO::Dir->new($dir)->read();

my $num;


... Tk code ...

    
sub search {
   my $found = 0;
   my @number = split(/-/, $num);
   my $search_text = join '', @number;

   my $file = $area_codes{$num[0]};
   if (defined $file) {
      open(my $fh, '<', $file)
         or die("Unable to open file for areacode $num[0]: $!\n");

      $found = search_file($fh, $search_text);
   }

   if (not $found) {        
      open(my $fh, '<', $cell)
         or die("Unable to open file for cellphones: $!\n");

      $found = search_file($fh, $search_text);
   }

   ... Show results ...
}


sub search_file {
   my ($fh, $search_text) = @_;
   
   while (<$fh>) {
      return 1 if index($_, $search_text) >= 0;

      ... Update ticker ...
   }

   return;
}
[download]

#3 is the idea I like most

I don't know much about american phone numbers, but if they all have a fixed length of 10, you'd just need slightly more than 1GB disk space to store one bit for each existing number.

I wouldn't create this bit vector in memory. Just create a big enough file, initialized with zeros and then go through your text file and position with fseek to $phone_num >> 3 and set bit number $phone_num & 7.

do the same positioning for read access, but check the bit.

I think searching will be done in less than a second.

Update: Of course you can couple this with the idea of splitting for each area code. This should reduce the summed size of your three files to 1/333 (about 4MB) if the area code has 3 numbers.

Update #2: If you have 10 numbers in each phone number and have 2million numbers you already have 21MB disk space used. So the bit vector on disk will save you 16MB.

---

s$$([},&%#}/&/]+}%&{})*;#$&&s&&$^X.($'^"%]=\&(|?*{%
+.+=%;.#_}\&"^"-+%*).}%:##%}={~=~:.")&e&&s""`$''`"e

Update: I Misread your post, your 4MiB are for 3 area codes, thus the same result (1.2MiB per Area Code). Being able to read cleary is an advantage. Sorry.

As you stated, the most practical approach would be to split it by area code. The point where i disagree is, that you think that it would eat up 4MB of space per area code.

rminner@Rosalinde:~$ bc
bc 1.06
Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'. 
obase=1024
10^7-1
 0009 0549 0639
last/8
 0001 0196 0719
[download]

i get 10 Million Bits (minus 1) for 7 digits. That would mean roughly 1.2 MiB and not 4MiB. Depending on the amount of memory available, you could load only a limited number of area codes. Like this the data structure for all do not call numbers in one are should be just a little bit more than those 1.2 MiB. Thus 5 Area Codes would only eat up 6 MiB, and as i said, a lookup would be instantaneous (from a user perspective) as it requires only to check one bit. One could allocate a limited number of slots for area codes, and could free them using whatever replacement algorithm one prefers (for example LRU or LFU). Loading should be also fast using File::Slurp, as directly slurping 1MiB into Memory using sysread, should be really fast when DMA is active.(you could also seek directly in the file (as stated by skeeve), reducing it to a single seek statement is also possible, keeping memory consumption even lower, and just requiring a single hd seek.)
The Caching of the bitstring could be done very easily. Simply store the bitstring in a file, with the same name but for example with the extension .bin . Afterwards set the same mtime for the .bin file as for the .txt file. Later if the mtime is identical, you can use your precomputed bitstring and if the mtimes differs, the txt file has been modified, and the .bin file can be recreated from scratch (also shouldn't take more than 1-2 seconds). Like this your data would be always up-to-date just using plain .txt files, but speed should still be more or less instantaneous.

Combining the above two great ideas, I would suggest not just a straight-forward database, but I would also split up the numbers into area code, exchange, extention. (And, if you want, country code - but sounds like you're just dealing with the US, so this would always be '1'.) This would allow the database to also set up indexes on area code and exchange for faster lookups. Ok, you have to tell the database to create indexes, but then you'll be able to do so.

Off Topic a Bit

Area codes, exchanges and extensions are US/Canada/Carribean concepts. Very few other areas use them. Germany for example uses over four thousand prefixes to represent local dialing zones, but they are not analagous to exchanges nor to area codes (and are of variable lengths). If you design your software with 3-3-4 in mind your software isnt going to work anywhere else in the world except maybe Switzerland (who use the NA system internally). My own telephone number is 11 digits for instance, and thats NOT including the country code. I know of peope who entire number is only 6 digits.

I would say that indexing based on the full CLI is the best, and most portable.

---
$world=~s/war/peace/g

No, There is not, I was just Trying to find the best way to do this since my way sucks

If you are just looking for exact matches, then a non-SQL database like DB_File (the tied-hash interface) is probably adequate; if not, then a SQL database using 1 table, 1 column, and an index. Then of course you have to develop processes to update the database and keep in sync with the text files.

There is also File::SortedSeek which I have no experience with, but might be "good enough" if the files are sorted, and would save you from keeping the database in sync with the text files.

It appears that you are installing and running this on each desktop. This is highly inefficient a slient server model would be a lot better as this would decrease the workload on the desktop machine.
The simplest way of doing this is using a database and you get the performance benifits if server caching index.
Your current code appears to do a straight string match similar to a like. Indexes are not as good as handling these kinds of searches as the whole string is not matched. If you are matching a complete sting an index is very fast.
If you need fast lookups on partial numbers you might look at either reverse indexes that sort based on the digits in reverse order or preprocessing the numbers and extracting sequences of digits and then indexing them.

UnderMine

#!/usr/bin/perl
use warnings;
use strict;

my $file = shift or die;

open (FH,">$file") or die;

for(1..1000){
 my $first = sprintf('%03d', int rand 999);
 my $second = sprintf('%03d', int rand 999);
 my $third = sprintf('%04d', int rand 9999);
 print FH  "$first-$second-$third\n";
}
[download]

Now here is a way to search them for a single number, which stops all the threads when a number is found and reports the line number. Your Tk code could use some minor fixing, but that is up to you. There is also alot of code cleanup and opportunities for ingenious juggling of the return data....like search certain threads only for certain prefixes, or looking for the same number on multiple lists. But I made this as simple as I could to demonstrate the basics... like the timer to watch the shared variables, and how to cleanup the threads when exiting. Also you will need to work out proper messaging and resetting the threads after an empty search

#!/usr/bin/perl
use warnings;
use strict;
use Tk;
use Tk::Dialog;
use threads;
use threads::shared;


my @sfiles = qw(numbers1 numbers2 numbers3 numbers4);

# make threads first before any tk code
my %shash;
my %thash;
my $numworkers = scalar @sfiles;
my $searchnum;
share $searchnum; 
$searchnum = '002-339-7473';

foreach my $dthread(1..$numworkers){
 share ($shash{$dthread}{'go'});
 share ($shash{$dthread}{'die'});
 share ($shash{$dthread}{'file'});
 share ($shash{$dthread}{'return'});

   
 $shash{$dthread}{'go'} = 0;
 $shash{$dthread}{'file'} = shift @sfiles;
 $shash{$dthread}{'die'} = 0;
 $shash{$dthread}{'return'} = '';
 
 $thash{$dthread}{'thread'} = threads->new(\&work,$dthread);
}



my $count = 1;

my $mw = MainWindow->new;

my $c = $mw->Canvas(
    -width =>400,
    -height=>200,
    -background => "white");
$c->pack;
############################Main window
my $quit = $mw->Button(
        -text        => "Quit",
        -padx        => "8",
        -command    => \&Quit);
$quit->place(-x => 350, -y => 180);
###########################adds the quit button

my $Find = $mw->Button(
        -text        => "Search",
        -command    => \&Search);
$Find->place(-x => 300, -y => 180);
################################################

my $lab = $mw->Label (
        -text    =>    "Enter Phone Number",
        -background => "white"
        );
$lab->place(-x => 5, -y => 50);
##############################Label

my $Entry = $mw->Entry(
        -textvariable    =>    \$searchnum,
        -background        =>    "white"
        );
$Entry->place(-x => 5, -y => 68);

##################################Entry

my $text = $mw->Text(
        -height        => 5,
        -width        => 55,
        -wrap        => 'char'
        );
$text->place(-x => 5, -y => 90);

#################################

my $labWarning = $mw->Label (
        -text    =>    'Example XXX - XXX - XXXX',
        -background => "white"
        );
$labWarning->place(-x => 140, -y => 68);

my $index = 1;
 



#######################################

sub Quit {

    my $d = $mw->Dialog(
        -text        => "Are you sure you want to quit?",
        -buttons    => ["Yes", "No"]);
    my $answer = $d->Show();

    close(UNLOCK);

    #cleanup threads
    if($answer eq "Yes"){
        for(1..$numworkers){
           $shash{$_}{'die'} = 1;
       $thash{$_}{'thread'}->join;
          }
    exit;
    }  

}

sub Search {

my $found = 0;

for(1..$numworkers){
    $shash{$_}{'go'} = 1;
  }

  #setup a timer to watch for returns thru shared variables
 my $timer; # declare outside of block so you can kill it in callback
 $timer = $mw->repeat(10,sub{
                            
                for(1..$numworkers){
        
            if( length $shash{$_}{'return'} > 0){
                  
                 if( $shash{$_}{'return'} > 0  ){
                    my $message = "thread  $_ detected number at line 
+$shash{$_}{'return'} \n";
                    print "$message\n";
                $text->insert('end',"$message\n");
              }
              #stop other threads
                      for(1..$numworkers){ $shash{$_}{'return'} = 0 }
                  #stop timer
              $timer->cancel;
            }
            }
                });


}

MainLoop;    

######################################################################
+#
sub work{
  my $dthread = shift;
    $|++; 
    
    my $file = $shash{$dthread}{'file'};
    open(FH,"< $file") or die "$!\n";
    print "thread $dthread created\n";
    
    while(1){
       if($shash{$dthread}{'die'} == 1){ goto END }; 
      
             if ( $shash{$dthread}{'go'} == 1 ){
                     seek FH, 0, 0;  #reset to top
                     $shash{$dthread}{'return'} = '';
             print "thread $dthread going\n";
               while(my $line = <FH>){
                  chomp $line;
              
              if($line eq $searchnum){   
                     $shash{$dthread}{'return'} = __LINE__ ;
                     print "$dthread found $shash{$dthread}{'return'}\
+n";
                 goto RESET;
                   }
                    
                         if($shash{$dthread}{'go'} == 0){goto RESET}
                         if($shash{$dthread}{'die'} == 1){ goto END };
+ 
                        }
             RESET:
             $shash{$dthread}{'go'} = 0; #turn off self before returni
+ng      
             print "thread $dthread going back to sleep\n";
       }else
         { select(undef,undef,undef,.1) } # tenth second sleep, can be
+ smaller
    }
END:
}
[download]

My first suggestion is that you do not start an application by creating the GUI. Start with a simple command-line script which will solve your problem, and make sure it works; they you can play with UI.

Now, the fastest solution is, IMO, the use of CDB_File. It will return data in a fraction of millisecond.

It usually takes two scripts: the first one is used to create a CDB file from your data:

    use CDB_File;

    $t = new CDB_File ('t.cdb', "t.$$") or die ...;
    $t->insert('key', 'value');
    $t->finish;
[download]

The second script simply ties the CDB to a hash and look for a key:

    use CDB_File;

    tie %data, 'CDB_File', $filename or
            die "$0: can't tie to $filename: $!\n";

    if (defined $data{}) {
      # ...
    }
[download]

That's it! The fact that it doesn't require a relational database will make it easier to set up your application. Think about that!

Finally, take a look at Tie::File::AsHash -- it can be usefull.

grep $phone_num file1 file2 file3
[download]

my $result = `grep $phone_num file1 file2 file3`;
if($result) {
  print "number is in blocked list";
}
[download]

Not the way to solve the OP's problem, but for those who come across this in the future:

• gnu grep
• egrep
• tcgrep

I also have what I hope is a comprehensive list of *nix-like utilities for Windows here.

Update: It would seem, however, that several of those links are b0rk, so this should be the updated version:

• Perl Power Tools
• Cygwin
• The Berkeley Utilities - 40 unix commands ported to DOS
• GNU utilities for Win32
• Unix Utils for DOS
• CMD Line Tools for Windows 95/98/NT/2000/XP
• Batch File Utilities

HTH,

planetscape

you can get a <...> grep.exe for windows as well...

Why bother, when windows has a native tool that serves a similar purpose:

my $result = `findstr $phone_num file1 file2 file3`;
if ( $result ) {
  print "DO NOT CALL $phone_num\n";
}
else {
  print "You can annoy $phone_num with your gratuitous cold calling\n"
+;
}
[download]

grep and findstr are both O(n) linear searches. Maybe I'm missing something here, but I think that's what the OP is trying to avoid; a linear search that takes O(n) time to fail.




Dave

Perhaps have a look at DBM::Deep? It's pure Perl, well suited to large lookup tables and, according to the docs, "pretty fast".

The docs also discuss speed/memory issues which you may find suit your requirements.

if( $do_not_call{ $test_number } ){
    print "Do Not Call $test_number\n";
}
[download]

Slurping the files into hashes will consume (assuming two million entries) about 22 megabytes JUST for the data. That doesn't seem unreasonable by todays standards, but it won't scale; someday someone will be sorry they used that approach as the dataset grows. 22 megs of phone numbers will take around 44 megs of total space including Perl's internal overhead (very approximately, assuming 11 bytes per number, plus hash and sv overhead).

Plus, if the files are slurped, that means each time someone starts up the program, it will have to do all the work all over again. If it's slurping into an array, it'll have to be sorted so it can be searched efficiently (the sort will be O(n log n), and searches will be O(log n) if a bin-search is used. If it's slurping into a hash, that operation alone consumes O(n log n) to hashify, every time the program starts up... and then searches will be O(1) after that. Every time the script starts, it'll have to re-slurp, and re-organize.




Dave

Of course, with Tk and threads, you must take precautions so that all threads are started before the main Tk thread is coded, and don't try to access any Tk widget from the threads. But you can use shared variables to communicate, and just have your search code in the threads.

If you can wait a bit, I'll post a minimal example.

Hmmm, a fun chance to play with Entry validate, and to simplify a UI. I'm getting around 8 milliseconds for the look() call on a file with just over two million numbers in it, so it makes sense to call it whenever the number is valid, and thus no "Search" button is needed.

#!/usr/bin/perl

use Search::Dict;
use Tk;
use strict;

my $file = 'd.search'; # combined *sorted* file with phone numbers
open my $fh, '<', $file or die "$0: $! opening $file";

my $mw = new MainWindow;
my $label = $mw->Label( -font => 'fixed 40', -height => 3,
  )->pack(-fill => 'x');
$mw->Entry( -font => 'fixed 40', -validate => 'key', -vcmd => \&test,
  )->pack->focus;

test('');  # do once before first key

MainLoop;  ############################################

sub test
  {
  tr/0-9//cd for my $n = shift;
  $label->configure(
    length $n == 0 ? (-bg => 'gold', -text => 'enter number below') :
    length $n < 10 ? (-bg => 'yellow', -text => 'need more digits') :
    length $n > 10 ? (-bg => 'yellow', -text => 'too many digits') :
    look($fh, $n, 0, 0) >= 0 && <$fh> == $n
      ? (-bg => 'red', -text => 'DO NOT CALL !!')
      : (-bg => 'green', -text => 'go ahead and call'));
  return 1;
  }
[download]

You mean like I suggested way up at the top? :)

/home/phones/1/2/3/1/1/3/5/5/6
[download]

if ( -f "$directory/".join '/' split '' $number ) {
  print "Lordy! don't call them!";
}
[download]

... A mere two million new directories. Hope you've got this on its own partition!

Heck, you could even build it all in a ram disk, then it'll be good and quick to access!
will: do{ perl programing } for ($cash);

Speed, scalability and low memory are major advantages. Disadvantages include a tunable rate of false positives and not telling which phone number did match.

Your application could use a precomputed and 'store'ed filter. Reimplement the algorithm using Bit::Vector if you need more speed.

#!/usr/bin/perl
open in,"987.txt" or die " could not open 987.txt as input";
# assign bit mask for this area code and pack it to binary
$a = "00000001";
$b = pack('b8',$a);
# load an array with the phone number less the area code as the subscr
+ipt
@arr;
while (<in>){
   chomp;
   $arr[$_]=$b;
}
# takes time to load about 10 seconds for all 10 million recs
print "\n\narray loaded\n";


# response for lookup is sub-second
while (true){
   print "enter phone number: ";
   $pni = <>;
   chomp $pni;
   $pna = unpack('b8',$arr[$pni]);
   if (substr($pna,7,1) eq "1" ){
     print "on file\n";
   }else{
     print "not on file\n";
   }
}
[download]

If you know that your data mostly consists of long runs of consecutive numbers instead of occasional numbers scattered at random through the number space, then you'll get better results by changing the algorithm to look at number prefixes like I do in Number::Phone::UK. The scripts I use for creating the database that uses are in the tarball on the CPAN.

Basic data structures and algorithms question: use a binary search.

Assumption: Files are sorted lines of 10 numbers followed by a newline.

Your record size is 10+length('\n') (this is a text file by definition)

See seek(), wikipedia, google, and a book on the topic. Most introductary CS texts will also address this topic.

Your search time should be O(log₂(n)), which is execllent - for 3 million records you are looking at a maximum of 22 comparisons.

I hate to say this, but most of the answers on this thread are way too complex.

Did you ever settle upon a solution?

For grins, I just ran a test that looked up 1000 randomly generated 10-digit telephone numbers (nnn-nnn-nnnn) in a flatfile database containing approximately 6.6% (2e6 / 3e7) of the 1e10 numbers:

c:\test>572961
9991230061
9991230061 is not found
9991230062
9991230062 is found
9991230063
9991230063 is not found
Terminating on signal SIGINT(2)

c:\test>perl -wle"printf qq[%03d%03d%04d\n], int( rand 1000 ), int( ra
+nd 1000 ), int( rand 10000 ) for 1 .. 1e3" | perl 572961.pl >nul
File for area code '000' not found at 572961.pl line 12, <STDIN> line 
+57.
999 trials of lookup (32.287s total), 32.319ms/trial
[download]

Each lookup takes around 33 ms which ought to be quick enough for most purposes.

The disk files (for all 999 possible area codes) require 10 GB, though that could trivially be reduced to 2.5 GB. Each area code is stored in a separate file, with one line of 10,000 characters for each of the 999 subarea codes; and each byte in the line representing a single telephone number by a simple '0' or '1'.

The lookup process is:

1. Split the number into it's 3 component parts. (nnn-nnn-nnnn);
2. Open the appropriate areacode file.
3. Seek to the appropriate subarea line and read it.
4. substr the appropriate byte of the line and it's value tells you whether the number is 'found' or 'not found'.

Care to trade 10 MB (2.5 MB) of diskspace per area code for 32 ms lookup time regardless of how the application grows?

#! perl -slw
use strict;
use Benchmark::Timer;

my $T = new Benchmark::Timer;


while( my $number = <STDIN> ) {
    chomp $number;
    $T->start( 'lookup' );
    if( my( $area, $subarea, $no ) = $number =~ m[^(\d{3})(\d{3})(\d{4
+})$] ) {
        open FILE, '<', "./tele/$area" 
            or warn "File for area code '$area' not found" and next;
        seek FILE, ( $subarea - 1 ) * 10002, 0;
        my $mask = <FILE>;
        print "$number is ", ( substr $mask, ( $no - 1 ), 1 ) 
            ? 'found' : 'not found';
    }
    else {
        print "Invalid telephone number: $number";
    }
    $T->stop( 'lookup' );
}

$T->report;
[download]