- push @{ $data{ $cols[ 0 ] } }, pack 'C*', @cols[ 1 .. $#cols ];
All your data values appear to be small positive integers. so rather than store them as an array, I chose to save some space (and given the size of the dataset you mentioned), and gain some considrable performance, by storing them as an array of chars. Ie. As strings.
This will only work if all your values are in the range 0 .. 255. However, you could also use pack 'S' for values 0 .. 65535 to gain similar benefits. If all your values are very small, then you might pack them even more tightly, though the benefits are less easily achieved.
The benefits of the compacted representation include:
- Space:
An ordinary array of 1000 integers requires just under 32k on my 64-bit system. A thousand byte string requires just 1056 bytes.
That's less than 4% of the space requirement.
- Speed:
I can detect if any two corresponding bytes in two 1000-bytes string are equal in 0.000003 seconds.
Doing the same thing using two 1000-element arrays takes 0.00025 seconds.
That's just 1.2% of the time. Or over 80 times faster.
- my $mask = $keyset1 ^ $keyset2;
This exclusive-ORs the two arrays of ints being compared, together (as strings). This effectively compares each corresponding pair of integers in both arrays (strings) in a single, very fast operation. If the two integers are equal, then the corresponding byte in $mask will be set to chr(0). If the are different, the corresponding byte will be non-zero.
This allows a a very fast check for there being any correspondance between the arrays...
- next unless 1+ index $mask, chr( 0 );
This uses index to search $mask for any zero byte. If none is found, then it skips to the next pair of arrays.
If one (one more) zero bytes are found...
- printf "%3d : %3d : ", $key1, $key2;
Print the ids of the two datasets being compared and ...
- print join ', ', map{ substr( $mask, $_, 1 ) eq chr(0) ? $_+1 : () } 0 .. length( $mask )-1;
Print a list of all the column (array index+1) positions where the corresponding integers are equal.
Ie. For each character position in the mask, if the byte equals chr(0), then the corresponding integers in the datasets are a match. As the mask indexes are zero-based, but the column indexes are 1-based, add 1 to each matching index.
join them with commas and print them out.
I hope that will clarify both the logic, and the reasoning behind the code.
Also, how can I use String::LCSS_XS on the hash of arrays (%data) to get the longest common substring between the various of rows apart from the ones having same id number.
If all your integers are in the range 0 .. 255, and can therefore be packed into strings, then it is very fortuitous, as String::LCSS_XS only operates upon strings :)
It also makes modifying my posted code to use it very simple:
#! perl -slw
use strict;
use String::LCSS_XS qw[ lcss ];
my %data;
while( <DATA> ) {
chomp;
my @cols = split ' ';
push @{ $data{ $cols[ 0 ] } }, pack 'C*', @cols[ 1 .. $#cols ];
}
my @keys = sort{ $a <=> $b } keys %data;
for my $i ( 0 ..$#keys ) {
my $key1 = $keys[ $i ];
for my $keyset1 ( @{ $data{ $key1 } } ) {
for my $key2 ( @keys[ $i+1 .. $#keys ] ) {
for my $keyset2 ( @{ $data{ $key2 } } ) {
my( $s, $i1, $i2 ) = lcss( $keyset1, $keyset2 );
printf "%4d(%4d) - %4d(%4d) : %s\n",
$key1, $i1, $key2, $i2,
join ', ', unpack 'C*', $s;
}
}
}
}
__DATA__
12 1 2 1 2 1 1 1 1
12 2 1 2 2 1 1 1 1
15 2 1 2 2 1 1 1 1
15 2 1 2 1 1 2 1 1
16 2 1 2 1 1 2 1 1
16 2 1 2 2 1 1 1 1
19 2 1 2 1 1 2 1 1
19 1 2 1 2 1 1 1 1
116 1 2 2 2 1 1 1 1
116 2 1 2 1 1 2 1 1
Which produces this from your sample input: c:\test>819256
## Note that the offsets are zero-based excluding the ID field
#id1 offset1 id2 offset2 values
12( 3) - 15( 3) : 2, 1, 1, 1, 1
12( 1) - 15( 0) : 2, 1, 2, 1, 1
12( 1) - 16( 0) : 2, 1, 2, 1, 1
12( 3) - 16( 3) : 2, 1, 1, 1, 1
12( 1) - 19( 0) : 2, 1, 2, 1, 1
12( 0) - 19( 0) : 1, 2, 1, 2, 1, 1, 1, 1
12( 3) - 116( 3) : 2, 1, 1, 1, 1
12( 1) - 116( 0) : 2, 1, 2, 1, 1
12( 0) - 15( 0) : 2, 1, 2, 2, 1, 1, 1, 1
12( 0) - 15( 0) : 2, 1, 2
12( 0) - 16( 0) : 2, 1, 2
12( 0) - 16( 0) : 2, 1, 2, 2, 1, 1, 1, 1
12( 0) - 19( 0) : 2, 1, 2
12( 3) - 19( 3) : 2, 1, 1, 1, 1
12( 2) - 116( 2) : 2, 2, 1, 1, 1, 1
12( 0) - 116( 0) : 2, 1, 2
15( 0) - 16( 0) : 2, 1, 2
15( 0) - 16( 0) : 2, 1, 2, 2, 1, 1, 1, 1
15( 0) - 19( 0) : 2, 1, 2
15( 3) - 19( 3) : 2, 1, 1, 1, 1
15( 2) - 116( 2) : 2, 2, 1, 1, 1, 1
15( 0) - 116( 0) : 2, 1, 2
15( 0) - 16( 0) : 2, 1, 2, 1, 1, 2, 1, 1
15( 0) - 16( 0) : 2, 1, 2
15( 0) - 19( 0) : 2, 1, 2, 1, 1, 2, 1, 1
15( 0) - 19( 1) : 2, 1, 2, 1, 1
15( 2) - 116( 3) : 2, 1, 1
15( 0) - 116( 0) : 2, 1, 2, 1, 1, 2, 1, 1
16( 0) - 19( 0) : 2, 1, 2, 1, 1, 2, 1, 1
16( 0) - 19( 1) : 2, 1, 2, 1, 1
16( 2) - 116( 3) : 2, 1, 1
16( 0) - 116( 0) : 2, 1, 2, 1, 1, 2, 1, 1
16( 0) - 19( 0) : 2, 1, 2
16( 3) - 19( 3) : 2, 1, 1, 1, 1
16( 2) - 116( 2) : 2, 2, 1, 1, 1, 1
16( 0) - 116( 0) : 2, 1, 2
19( 2) - 116( 3) : 2, 1, 1
19( 0) - 116( 0) : 2, 1, 2, 1, 1, 2, 1, 1
19( 3) - 116( 3) : 2, 1, 1, 1, 1
19( 1) - 116( 0) : 2, 1, 2, 1, 1
HTH.
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".
In the absence of evidence, opinion is indistinguishable from prejudice.
| [reply]
[d/l]
[select] |