in reply to The Best Hash
How I can decide which hash is the least differing from other hashes?
If I understand you correctly, you want to measure the 'fit' of each ordered set of hash values against every other set of hash values and accumulate their scores and sort them via that criteria.
For this purpose a (A,B,C,D) -v- (A,B,D,C) scores 2, and (A,B,C,D) -v- (B,A,D,C) scores 0.
This is an O(n^2) problem. Add to this the cost of comparing two arrays of strings and counting the matches and you have a slow and expensive process.
Those little diagrams above gave me an idea.
If you XOR a number with itself, you get zero. Perl (uniquely?) can do bitwise operations on strings. If you XOR 2 strings and they are the same, you end up with a string of null bytes. A slow method of comparing two string, and no good at all for comparing arrays of strings, even if you concatenated the arrays into a single string unless all the string were the same length. However, you said that the set of values in each hash is the same, its only the ordering that distinguishes them. Therefore it is possible to represent each set of values by a string with each value represented by a single character (provided that there are less than 255 unique values in each hash).
Once you have the sets represented this way, deriving the 'fit' of any pair of hashes comes down to XORing 2 substitute strings and counting the number of null bytes. Doing this for all the pairs and accumulating the scores determines a fit value of each hash relative to every other.
You then need to order these fits whilst retaining the index for which hash they belong to. You can then use the print them out in order of relative fit.
The code below does this for 50 hashes of 9 values each in a few seconds. You don't say how many hashes or how large your sets, but it may complete in a reasonable time if your numbers aren't too extreme.
The whole process only takes 6 (fairly complex) lines:)
#! perl -slw use strict; use Inline::Files; #! Not necessary for the algorithm. #! Just convenience in my test program #! If anyone else gets the following warnings from the #! above module, please let me know. =pod Comment only Use of uninitialized value in length at e:/Perl/site/lib/Inline/Files/ +Virtual.pm line 89, <FILE> chunk 1. Use of uninitialized value in transliteration (tr///) at e:/Perl/site/ +lib/Inline/Files/Virtual.pm line 167, <FILE> chunk 1. =cut #! Some silly hash keys for testing purposes. my @keys = qw(one two three four five six seven eight nine); #! Build an array of hashes from the __DATA__ section. #! The array above as keys, the words from each line as values my @AoH; push @AoH, do{ my $i=0; +{ map{ $keys[$i++] => $_ } split } } while <D +ATA>; #! Build a lookup table from one (any) hash's values. my %lookup = do{ my $i=1; map{ $_ => $i++ } values %{$AoH[0]} }; #! Build an array of substitute strings, mapping each value to a singl +e char. #! I've used an offset of 65 to make things readable when testing. #! Start at chr(1) if your hashes have more than 222 values. #! You might need to specify [no utf-8] if you use values above 127? I +'m not sure. my @subs; push @subs, join'', map{ chr 65+$lookup{$_} } values %{$_} for @AoH; #! XOR every substitute with every substitute, count the nuls in the r +esult #! Accumulate them in an array in the same order as the subs. my @fits = ( (0)x@subs ); for my $i (0 .. $#subs) { $fits[$i] += scalar ($subs[$i] ^ $_) =~ tr/\0// for @subs; } #! The sort is a slightly funky (I wonder where I got that word from:) + version of the ST sort. #! It feeds in and sorts on the values of the array and feeds out the +indices of the sorted values. my @sorted = map{ $_->[1] } sort{ $b->[0] <=> $a->[0] } #! Descending sort, higher is better f +it. map{ [ $fits[$_] => $_ ] } 0 .. $#fits; #! Output the values sets ordered by and prefixed with their relative +'fit'. print OUTPUT "$fits[$_] : @{[ values %{$AoH[$_]} ]}\n" for @sorted;
test data
__DATA__ indigo hotel bravo charlie echo foxtrot golf alpha delta hotel indigo bravo foxtrot charlie alpha delta golf echo indigo hotel foxtrot bravo alpha charlie golf echo delta bravo charlie indigo foxtrot delta hotel alpha echo golf alpha indigo bravo echo charlie delta hotel golf foxtrot indigo bravo delta charlie alpha foxtrot golf echo hotel golf foxtrot hotel bravo alpha echo indigo charlie delta charlie foxtrot hotel golf alpha delta indigo echo bravo hotel indigo charlie echo foxtrot alpha bravo delta golf indigo delta alpha foxtrot hotel golf echo bravo charlie echo foxtrot bravo golf indigo hotel delta charlie alpha golf delta bravo hotel alpha foxtrot indigo charlie echo alpha foxtrot golf hotel indigo echo delta bravo charlie indigo bravo delta foxtrot hotel golf echo alpha charlie bravo indigo golf foxtrot echo charlie alpha hotel delta foxtrot golf delta indigo charlie alpha bravo echo hotel foxtrot golf charlie indigo delta hotel alpha echo bravo indigo hotel echo foxtrot golf delta charlie bravo alpha foxtrot echo charlie golf bravo hotel indigo delta alpha golf hotel bravo charlie foxtrot echo delta indigo alpha charlie alpha golf echo hotel bravo delta indigo foxtrot bravo hotel charlie foxtrot alpha golf echo indigo delta golf charlie delta echo foxtrot bravo hotel alpha indigo golf hotel charlie bravo foxtrot delta indigo alpha echo indigo bravo foxtrot delta golf charlie echo alpha hotel alpha hotel indigo charlie echo delta foxtrot bravo golf delta indigo bravo foxtrot echo golf charlie alpha hotel charlie echo alpha delta bravo foxtrot golf indigo hotel indigo echo delta charlie foxtrot bravo golf hotel alpha charlie golf echo indigo alpha hotel bravo delta foxtrot charlie foxtrot bravo alpha echo delta indigo golf hotel alpha bravo delta echo golf foxtrot charlie indigo hotel indigo foxtrot bravo hotel delta alpha charlie golf echo charlie foxtrot bravo echo indigo hotel golf alpha delta bravo foxtrot hotel delta golf alpha echo indigo charlie foxtrot hotel delta alpha golf bravo indigo echo charlie echo bravo charlie delta alpha foxtrot golf indigo hotel charlie golf hotel indigo alpha bravo foxtrot delta echo hotel echo delta foxtrot indigo bravo alpha golf charlie foxtrot alpha golf indigo delta bravo hotel echo charlie hotel alpha indigo foxtrot bravo delta charlie echo golf golf indigo charlie bravo alpha echo delta hotel foxtrot indigo golf bravo delta charlie foxtrot alpha hotel echo indigo golf delta bravo foxtrot hotel alpha echo charlie alpha golf foxtrot echo delta bravo indigo hotel charlie hotel echo indigo bravo delta foxtrot golf alpha charlie delta foxtrot bravo alpha golf hotel echo indigo charlie delta foxtrot echo bravo alpha charlie hotel golf indigo golf alpha bravo foxtrot charlie echo delta hotel indigo hotel golf delta alpha echo bravo foxtrot indigo charlie
Results
__OUTPUT__ 78 : indigo charlie foxtrot delta golf hotel echo alpha bravo 76 : indigo hotel alpha delta bravo foxtrot echo golf charlie 73 : indigo delta echo bravo hotel foxtrot alpha golf charlie 72 : foxtrot charlie golf delta hotel bravo echo indigo alpha 71 : charlie delta indigo bravo foxtrot hotel alpha golf echo 71 : delta charlie golf bravo foxtrot hotel indigo echo alpha 70 : indigo charlie hotel delta bravo golf alpha echo foxtrot 69 : charlie hotel echo bravo foxtrot delta golf indigo alpha 69 : hotel charlie indigo delta echo bravo golf alpha foxtrot 68 : indigo echo charlie bravo golf foxtrot hotel alpha delta 68 : indigo delta alpha foxtrot hotel charlie echo golf bravo 67 : hotel charlie echo delta golf bravo indigo foxtrot alpha 66 : bravo delta alpha charlie hotel golf indigo echo foxtrot 65 : indigo echo delta bravo foxtrot alpha golf charlie hotel 65 : hotel echo charlie bravo indigo alpha golf delta foxtrot 65 : golf alpha foxtrot bravo hotel echo indigo delta charlie 65 : indigo alpha foxtrot delta echo bravo hotel golf charlie 64 : delta hotel echo bravo indigo golf alpha charlie foxtrot 64 : golf echo foxtrot charlie hotel delta alpha indigo bravo 64 : alpha charlie delta foxtrot golf bravo hotel indigo echo 64 : hotel charlie delta indigo echo foxtrot alpha golf bravo 63 : echo hotel alpha charlie bravo foxtrot indigo golf delta 63 : alpha hotel golf delta bravo foxtrot indigo charlie echo 62 : charlie bravo alpha hotel foxtrot delta echo indigo golf 61 : bravo charlie golf hotel foxtrot alpha indigo echo delta 61 : golf echo alpha bravo delta foxtrot charlie indigo hotel 61 : golf indigo charlie bravo alpha echo hotel delta foxtrot 61 : golf delta alpha hotel foxtrot echo charlie indigo bravo 60 : golf foxtrot alpha charlie indigo echo hotel delta bravo 60 : indigo alpha golf echo hotel delta bravo charlie foxtrot 59 : foxtrot charlie delta golf alpha bravo echo hotel indigo 59 : foxtrot hotel charlie delta golf alpha echo bravo indigo 57 : foxtrot bravo delta charlie golf hotel echo alpha indigo 57 : alpha foxtrot charlie bravo indigo delta golf hotel echo 57 : charlie echo alpha hotel golf bravo delta foxtrot indigo 56 : golf indigo foxtrot delta charlie bravo alpha hotel echo 56 : indigo hotel golf foxtrot bravo charlie alpha echo delta 55 : indigo charlie hotel alpha delta golf bravo echo foxtrot 55 : charlie hotel bravo alpha echo foxtrot indigo golf delta 55 : bravo golf delta indigo charlie hotel echo alpha foxtrot 55 : echo alpha indigo bravo foxtrot hotel charlie delta golf 54 : charlie foxtrot hotel golf alpha bravo indigo delta echo 54 : hotel golf bravo indigo alpha delta echo charlie foxtrot 54 : alpha charlie indigo golf foxtrot echo bravo delta hotel 53 : bravo delta echo golf indigo charlie hotel alpha foxtrot 53 : charlie foxtrot alpha echo golf hotel delta bravo indigo 51 : delta indigo alpha echo foxtrot charlie golf hotel bravo 48 : hotel golf foxtrot charlie indigo alpha delta bravo echo 48 : foxtrot alpha bravo charlie echo hotel delta indigo golf 46 : alpha golf echo indigo hotel delta bravo foxtrot charlie __END__
I hope the results mean something to you, cos I can't see the pattern:)
Examine what is said, not who speaks.
|
|---|