Thread Hash mit Arrays zu langsam - wie sortieren und suchen?
(38 answers)
Opened by Gast at 2009-01-28 14:02 Gast+2009-01-28 19:43:20-- Geht alles :-) Hier mal der Beispielcode, mit dem ich gestern herumgespielt habe. Code (perl): (dl
)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 use strict; use warnings; use Time::HiRes qw/time/; my ( @data1, @data2 ); push @data1, [rand(10), rand(10), rand(10), rand(10)] for 1 .. 100_000; push @data2, [rand(10), rand(10), rand(10), rand(10)] for 1 .. 100; for my $point2 ( @data2 ) { my %nearest = ( distance => 1_000_000, point => [0,0,0,0], ); for my $point1 ( @data1 ) { next if abs( $point1->[0] - $point2->[0] ) > $nearest{distance}; next if abs( $point1->[1] - $point2->[1] ) > $nearest{distance}; next if abs( $point1->[2] - $point2->[2] ) > $nearest{distance}; next if abs( $point1->[3] - $point2->[3] ) > $nearest{distance}; my $distance = sqrt( ($point1->[0]-$point2->[0]) ** 2 + ($point1->[1]-$point2->[1]) ** 2 + ($point1->[2]-$point2->[2]) ** 2 + ($point1->[3]-$point2->[3]) ** 2 ); if ( $distance < $nearest{distance} ) { $nearest{distance} = $distance; $nearest{point } = [ @$point1 ]; } } #print $nearest{distance} . "\n"; } Man beachte die Zeilen 16 bis 19. Diese verkürzen die Laufzeit des Programms auf weniger als ein drittel, da sie sehr schnell testen können, ob die bisher gefundene, kürzeste Entfernung kleiner ist, als die Entfernung zum momentan betrachteten Punkt in einer einzelnen Dimension. $_=unpack"B*",~pack"H*",$_ and y&1|0& |#&&print"$_\n"for@.=qw BFA2F7C39139F45F78
0A28104594444504400 0A2F107D54447DE7800 0A2110453444450500 73CF1045138445F4800 0 F3EF2044E3D17DE 8A08A0451412411 F3CF207DF41C79E 820A20451412414 83E93C4513D17D2B |