Opened by bo at 2006-12-21 12:12
User since
2006-07-10
2611 Artikel
BenutzerIn
2006-07-10
2611 Artikel
BenutzerIn
@docsnyder
Dein Code sieht zwar hübscher aus, meiner ist aber schneller. ;-)
Übergens für Arrays ohne Zufallsverteilung der Wertdifferenzen ( z.B. Graphen ) gibt es noch eine Verbesserung:
Dein Code sieht zwar hübscher aus, meiner ist aber schneller. ;-)
Code: (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
33
34
35
36
37
38
39
40
41
42
43
44
45
#!/usr/bin/perl
use strict;
use warnings;
use Benchmark qw/cmpthese/;
my @ids=(int(rand(10)));
push(@ids,$ids[-1]+int(rand(10))) while(@ids<10000);
my $id=$ids[int(rand(scalar(@ids)))];
cmpthese (-1,
{
'docsnyder' => sub { binSearch(\@ids, $id, 0, $#ids) },
'ToPeG' => sub { tpgSearch(\@ids, $id, 0, $#ids) },
}
);
sub binSearch {
my($arrRef, $val, $minIdx, $maxIdx) = @_;
my($mid) = int(($maxIdx + $minIdx)/ 2);
my($idx);
return(($arrRef->[$mid] == $val) ? $mid : (($minIdx == $maxIdx) ? undef : (($arrRef->[$mid] >= $val) ? binSearch($arrRef, $val, $minIdx, $mid) : binSearch($arrRef, $val, $mid+1, $maxIdx))));
}
sub tpgSearch
{
my ($ref, $val, $min, $max) = @_;
if($id>=$$ref[$min] && $id<=$$ref[$max])
{
my $diff=($ids[$max]-$ids[$min])/($max-$min);
my $pos=int($val/$diff);
if($$ref[$pos]<$val)
{ $pos++ while($val>$$ref[$pos]); }
elsif($$ref[$pos]>$val)
{ $pos-- while($id<$$ref[$pos]); }
return $pos if($val==$$ref[$pos]);
}
return undef;
}
Übergens für Arrays ohne Zufallsverteilung der Wertdifferenzen ( z.B. Graphen ) gibt es noch eine Verbesserung:
Code: (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
33
34
35
36
37
38
39
sub tpgSearch
{
my ($ref, $val, $min, $max) = @_;
return undef if($max==$min);
return $min if($$ref[$min]==$val);
return $max if($$ref[$max]==$val);
my $diff=($ids[$max]-$ids[$min])/($max-$min);
my $pos=$min+int(($val-$ids[$min])/$diff);
if($$ref[$pos]==$val)
{ return $pos; }
else
{
if($$ref[$pos]<$val)
{
my $n_max=$pos+int(($val-$$ref[$pos])/$diff);
$max=$n_max<@{$ref}?$n_max:@{$ref};
$min=$pos;
if($min==$max)
{
$pos++ while($$ref[$pos]<$val);
return $$ref[$pos]==$val?$pos:undef;
}
}
if($$ref[$pos]>$val)
{
my $n_min=$pos-int(($$ref[$pos]-$val)/$diff);
$min=$n_min>0?$n_min:0;
$max=$pos;
if($min==$max)
{
$pos-- while($$ref[$pos]>$val);
return $$ref[$pos]==$val?$pos:undef;
}
}
return tpgSearch($ref,$val,$min,$max);
}
}