Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Re: nested combinations: algorithm advice?

by BrowserUk (Pope)
on Sep 22, 2004 at 19:00 UTC ( #393022=note: print w/replies, xml ) Need Help??


in reply to nested combinations: algorithm advice?

If you have thousands of lines to process this may be quicker than some other approaches. It will process 100,000 lines (of 2 to 4 elements each) in under 4 seconds.

I won't attempt to categorise the algorithm because it relies on using hashes for lookups, and there is always the argument about whether they are O(1) or 0(logN).

Update: On emperical evidence this is O(N) (at ~4secs/100,000) upto the limit of memory.

#! perl -slw use strict; our $LINES ||= 1000; ## Gen some test data to a simulated file my @a = qw[ one two three four five six seven eight nine ];; my @lines = map{ join '_', @a[ map{ rand @a } 1 .. 2+rand 3 ] } 1 .. $ +LINES; warn "Processing " . @lines . " start: " . localtime; ## Index the lines my %index; for my $idx ( 0 .. $#lines ) { $index{ $_ }{ $idx }++ for split '_', $lines[ $idx ]; } my @keys = keys %index; while( my $first = pop @keys ) { for my $second ( @keys ) { print "$first/$second: ", join "\n\t", @lines[ grep{ exists $index{ $second }{ $_ } } keys %{ $index{ $first } } ]; } } warn "Processing " . @lines . " stop: " . localtime; __END__ P:\test>392861 -LINES=100000 >nul Processing 100000 start: Wed Sep 22 19:58:46 2004 at P:\test\392861.pl + line 10. Processing 100000 stop: Wed Sep 22 19:58:50 2004 at P:\test\392861.pl + line 31.

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
"Memory, processor, disk in that order on the hardware side. Algorithm, algorithm, algorithm on the code side." - tachyon

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (4)
As of 2019-12-12 06:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?