Schrift
Start · Board · Anwendungen/Programme/Skripte in Perl · Allgemeines zu Perl
[thread]8596[/thread]

suche in einem array (Seite 2)

Leser: 1


<< |< 1 2 3 >| >> 21 Einträge, 3 Seiten
docsnyder
 2006-12-22 10:55
#72672 #72672
User since
2005-09-08
300 Artikel
BenutzerIn
[Homepage] [default_avatar]
Na, dann aber doch gleich richtig suchen:

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
my(@ids) = qw/1 3 4 12 41 43 44 55 67 78 103 156 167 176 198 244 300 345 355/;
my($id, $idx) = (4, undef);

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))));
}

printf("IDX: %s\n", defined($idx=binSearch(\@ids, $id, 0, $#ids)) ? $idx : "UNDEF");


Gruß, Doc\n\n

<!--EDIT|docsnyder|1166779635-->
bloonix
 2006-12-22 12:44
#72673 #72673
User since
2005-12-17
1615 Artikel
HausmeisterIn
[Homepage]
user image
[quote=docsnyder,22.12.2006, 09:55]
Code: (dl )
$arrRef->[$mid] >= $val
[/quote]
hmmm... "=" scheint hier eine Prüfung zuviel zu sein.\n\n

<!--EDIT|opi|1166784417-->
What is a good module? That's hard to say.
What is good code? That's also hard to say.
One man's Thing of Beauty is another's man's Evil Hack.
docsnyder
 2006-12-22 13:15
#72674 #72674
User since
2005-09-08
300 Artikel
BenutzerIn
[Homepage] [default_avatar]
@opi

Warum?

Die Intervalle, in denen gesucht wird, sind [$minIdx, $mid] und [$mid+1, $maxIdx]. Ich suche in dem entspechenden Intervall, wenn der Wert (einschliesslich den Grenzen! ) innerhalb des jeweiligen Intervalls liegt.

Was wäre wenn:
Code: (dl )
@ids = qw/10 20 30 40 50/;

Angenommen, es gilt "$minIdx == 0", und "$mid == 2" und ich suche den Wert 30. Dann evaluiert "$arrRef->[$mid] > $val" zu "30 > 30". Dies evaluiert wiederum zu "false" und die Suche würde im Intervall [$mid+1, $maxIdx] (= [3, 4] = (40, 50)) durchgeführt werden.

Das wäre definitiv falsch!

Gruß, Doc\n\n

<!--EDIT|docsnyder|1166786387-->
bloonix
 2006-12-22 13:25
#72675 #72675
User since
2005-12-17
1615 Artikel
HausmeisterIn
[Homepage]
user image
Lieber Doc,

ich versuch es dir zu erklären. Zuerst versuche ich aber mal deinen Code
"etwas" lesbarer zu machen.

Code: (dl )
1
2
3
4
5
6
7
      1 return $arrRef->[$mid] == $val
      2           ? $mid
      3           : $minIdx == $maxIdx
      4              ? undef
      5              : $arrRef->[$mid] >= $val
      6                 ? binSearch($arrRef, $val, $minIdx, $mid)
      7                 : binSearch($arrRef, $val, $mid+1, $maxIdx);


In Zeile 1 steht die Bedingung $arrRef->[$mid] == $val.
In Zeile 5 steht die Bedingung $arrRef->[$mid] >= $val.

$val kann in Zeile 5 niemals gleich $arrRef->[$mid] sein,
da dies schon in Zeile 1 abgefangen wird.

Wenn also $val in Zeile 5 nicht gleich $arrRef->[$mid] ist,
kann der Wert in Zeile 5 nur größer oder kleiner sein.

Sehe ich das richtig?\n\n

<!--EDIT|opi|1166786922-->
What is a good module? That's hard to say.
What is good code? That's also hard to say.
One man's Thing of Beauty is another's man's Evil Hack.
docsnyder
 2006-12-22 13:34
#72676 #72676
User since
2005-09-08
300 Artikel
BenutzerIn
[Homepage] [default_avatar]
@opi

Yep, das siehst Du natürlich vollkommen richtig. Ich hatte nicht bedacht, daß der "=="-Fall ja schon vor der ">="-Prüfung abgefangen wird.

Gut aufgepasst!

Gruß, Doc
bloonix
 2006-12-22 13:50
#72677 #72677
User since
2005-12-17
1615 Artikel
HausmeisterIn
[Homepage]
user image
[quote=docsnyder,22.12.2006, 12:34]Gut aufgepasst![/quote]
Na klar! Meinst du etwa, dass ich dein Codestück in meine Beispiel-
sammlung ohne einen kritischen Blick aufnehme? :)
What is a good module? That's hard to say.
What is good code? That's also hard to say.
One man's Thing of Beauty is another's man's Evil Hack.
topeg
 2006-12-22 21:54
#72678 #72678
User since
2006-07-10
2611 Artikel
BenutzerIn

user image
@docsnyder
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);
  } 
}
docsnyder
 2006-12-29 12:41
#72679 #72679
User since
2005-09-08
300 Artikel
BenutzerIn
[Homepage] [default_avatar]
@topeq

Dein Ansatz gefällt mir super-gut: Du suchst zwar nicht binär, aber durch eine sehr einfache, aber auch sehr geschickte Wahl des Start-Index ist Dein Algorithmus sehr schnell.

Für einige Spezialfälle dürfte meine binäre Suche aber rotzdem schneller sein:
Code: (dl )
@ids = ( 0..10000, 10000000000);

Wenn ich jetzt das Element '10000' suche, beginnt die Suche bei Index '0' und hangelt sich mit $pos++ bis 10000 durch. Nicht gerade optimal.

D.h. 'ein' Ausreisser kann die Suche ungünstig gestalten. Umso gleicher die Werte im Array verteilt sind, desto schneller die Suche.

Fazit: in der überwiegenden Anzahl der Fälle wird Deine Suche aber sehr schnell sein.

Gruß, Doc
topeg
 2006-12-29 13:52
#72680 #72680
User since
2006-07-10
2611 Artikel
BenutzerIn

user image
Sicher bei so extremen Werten ist der Algorythmus langsamer.
Darum habe ich auch eine etwas kompliziertere Variante programmiert, die bei jedem Sprung abschätzt, bis sie sehr nahe dran ist. Die ist noch ein tacken schneller als die binäre Suche.
bloonix
 2006-12-29 17:24
#72681 #72681
User since
2005-12-17
1615 Artikel
HausmeisterIn
[Homepage]
user image
Doc's Beispiel kann man auch noch tunen. Der Aufruf von Subs ist ja
für gewöhnlich etwas langsamer... mit ner Schleife lässt es sich nochmal
um knapp 100% verbessern.

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
use strict;
use warnings;
use Data::Dumper;
use Benchmark qw(cmpthese);

my @ids = (0..10000);
my $id  = 10000;

Benchmark::cmpthese(-1,{
   'docSearch' => sub { docSearch(\@ids, $id, 0, $#ids) },
   'tpgSearch' => sub { tpgSearch(\@ids, $id, 0, $#ids) },
   'tunSearch' => sub { tunSearch(\@ids, $id, 0, $#ids) },
});

sub tunSearch {
   my ($arrRef, $val, $minIdx, $maxIdx) = @_;
   my $mid;

   while ($minIdx != $maxIdx) {
      $mid = int(($maxIdx + $minIdx)/ 2);
      if ($arrRef->[$mid] == $val) {
         return $mid;
      } elsif ($arrRef->[$mid] > $val) {
         #? docSearch($arrRef, $val, $minIdx, $mid)
         $maxIdx = $mid
      } else {
         #: docSearch($arrRef, $val, $mid+1, $maxIdx);
         $minIdx = $mid+1;
      }
   }

   return undef;
}

sub docSearch {
   my ($arrRef, $val, $minIdx, $maxIdx) = @_;
   my $mid = int(($maxIdx + $minIdx)/ 2);

   return $arrRef->[$mid] == $val
             ? $mid
             : $minIdx == $maxIdx
                ? undef
                : $arrRef->[$mid] > $val
                   ? docSearch($arrRef, $val, $minIdx, $mid)
                   : docSearch($arrRef, $val, $mid+1, $maxIdx);
}

sub tpgSearch {
   my ($ref, $val, $min, $max) = @_;

   if($id >= $$ref[$min] && $id <= $$ref[$max]) {
      my $diff = ($ref->[$max] - $ref->[$min]) / ($max - $min);
      my $pos = int($val / $diff);

      if ($$ref[$pos] < $val) {
         $pos++ while ($val > $$ref[$pos]);
      } elsif($$ref[$pos] > $val) {
         $pos-- while ($val < $$ref[$pos]);
      }

      return $pos if $val == $$ref[$pos];
   }

   return undef;
}


             Rate docSearch tunSearch tpgSearch
docSearch  32881/s        --      -48%      -87%
tunSearch  63621/s       93%        --      -75%
tpgSearch 256955/s      681%      304%        --\n\n

<!--EDIT|opi|1167405867-->
What is a good module? That's hard to say.
What is good code? That's also hard to say.
One man's Thing of Beauty is another's man's Evil Hack.
<< |< 1 2 3 >| >> 21 Einträge, 3 Seiten



View all threads created 2006-12-21 12:12.