Schrift
[thread]8596[/thread]

suche in einem array

Leser: 1


<< |< 1 2 3 >| >> 21 Einträge, 3 Seiten
bo
 2006-12-21 12:12
#72662 #72662
User since
2006-05-09
76 Artikel
BenutzerIn
[default_avatar]
hi community,

ich suche innerhalb eines arrays den vorgänger und den nachfolger eines elements
gibt es dafür eine elegantere lösung?

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
use strict;
use warnings;

my @ids = (1, 3, 4, 12, 41, 43, 44);
my $id = 4;
my $prev_id = 'undef';
my $next_id = 'undef';

for (my $i = 0; $i < scalar(@ids); ++$i)
{
if ($ids[$i] == $id)
{
$prev_id = $ids[$i-1] if ($i > 0);
$next_id = $ids[$i+1] if ($i+1 < scalar(@ids));
last;
}
}

print qq(ID: $id => NEXT: $next_id => PREV: $prev_id\n);
PerlProfi
 2006-12-21 12:18
#72663 #72663
User since
2006-11-29
340 Artikel
BenutzerIn
[default_avatar]
Du brauchst die for-Schleife da gar nicht:
Code (perl): (dl )
1
2
3
4
5
6
7
8
9
use strict;
use warnings;

my @ids = (1, 3, 4, 12, 41, 43, 44);
my $id = 4;
my $prev_id = defined($ids[$id-1]) ? $ids[$id-1] : 'undef';
my $next_id = defined($ids[$id+1]) ? $ids[$id+1] : 'undef';

print qq(ID: $id => NEXT: $next_id => PREV: $prev_id\n);


MfG PerlProfi
PerlProfi
 2006-12-21 12:20
#72664 #72664
User since
2006-11-29
340 Artikel
BenutzerIn
[default_avatar]
upps, sorry hab die Frage nicht richtig gelesen.

Ich kenne auch keinen einfacheren Weg.\n\n

<!--EDIT|PerlProfi|1166696534-->
bloonix
 2006-12-21 13:25
#72665 #72665
User since
2005-12-17
1615 Artikel
HausmeisterIn
[Homepage]
user image
[quote=bo,21.12.2006, 11:12]
Code: (dl )
1
2
my $prev_id = 'undef';
my $next_id = 'undef';
[/quote]
was hast du denn hier versucht? :)

Edit: ok, habs verstanden...\n\n

<!--EDIT|opi|1166700795-->
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.
bo
 2006-12-21 13:36
#72666 #72666
User since
2006-05-09
76 Artikel
BenutzerIn
[default_avatar]
das ist nur hier so fürs print... dann muss ich vorher nicht noch auf defined überprüfen :)
im 'echten' code heisst es natürlich so
Code: (dl )
1
2
my $prev_id = undef;
my $next_id = undef;

;)
Ishka
 2006-12-21 15:23
#72667 #72667
User since
2003-08-04
771 Artikel
HausmeisterIn
[Homepage] [default_avatar]
Sind die ids immer sortiert?

Wenn ja, kannst du in die Mitte springen und schauen, ob die gesuchte id größer oder kleiner ist, dann einen halb so großen Sprung nach vorne oder hinten machen und das solange wiederholen, bis du das Element gefunden hast, das sind deutlich weniger Abfragen, bei 1000 Elementen sind das zB. noch 10 Abfragen.

Wenn nein, dann lohnt es sich vielleicht das ganze über einen Hash zu lösen.
sub z{if(@_){1while$x[$k=rand 10];t($t=$x[$k]=1)}print map"$z[$x[$_]]$_".($_%3?
"":"\n"),1..9}sub t{$j=0;$x[$_+1]==$t&&($j+=2**$_)for 0..8;z,die"Gewinner $z[$t]
"if grep$_==($j&$_),7,56,73,84,146,273,292,448;z,die"Gleichstand\n"if@x>9&&!grep
!$_,@x}@x=4;@z=qw{. [ (};z$^T&1;while(<>){next if$_>9||$x[$_];t$t=$x[$_]=2;z 1}
docsnyder
 2006-12-21 15:57
#72668 #72668
User since
2005-09-08
300 Artikel
BenutzerIn
[Homepage] [default_avatar]
@Ishka

Das nennt man "binäre Suche" ...

@bo

Ich weiss nicht, wie gross Deine Liste von ID's werden kann und ob die Liste statisch ist, oder sich ständig ändert. Bei grossen statischen Listen, könntest Du Laufzeit auf Kosten von Speicherplatz sparen (letzteres sollte heutzutage ja weniger das Problem sein):

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
my @ids = (1, 3, 4, 12, 41, 43, 44);
my $id = 4;

sub addID {
for ( $i=0; $i<scalar(@_); $i++ ) {
$idMap{$_[$i]} = $i;
}
}

addID(@ids);

printf("ID: $id, NEXT: %d, PREV: %d\n", $ids[$idMap{$id}+1], $ids[$idMap{$id}-1]);


Um das Beispiel einfach zu halten, habe ich die Prüfung, ob PREV bzw. NEXT überhaupt existiert, weggelassen (das einzufügen ist straightforward).

Gruß, Doc
bo
 2006-12-21 16:39
#72669 #72669
User since
2006-05-09
76 Artikel
BenutzerIn
[default_avatar]
@ishka @docsnyder

danke euch beiden

die liste ist dynamisch, sortiert und kann schon recht gross werden (bis zu 100000, vielleicht auch mehr)... grösstenteils wird sie aber überschaubar bleiben, etwa zwischen 10 und 1000 einträgen...

ich werde wohl beide vorschläge aufgreifen, abhängig von der grösse des arrays, aber erst nächtes jahr ;)

die ids kommen von einer datenbank, es gibt doch bestimmt auch ein schönes select...join...whatever-konstrukt, mit dem man das lösen kann... ist aber wohl eher was für nen neuen thread... nächstes jahr ;)

so long
docsnyder
 2006-12-21 17:06
#72670 #72670
User since
2005-09-08
300 Artikel
BenutzerIn
[Homepage] [default_avatar]
@bo

Es wird Dir nicht gelingen, beide Vorschläge aufzugreifen, da Du Dir bei der Sache mit dem Hash ja die Suche im Array ersparst. Willst Du dagegen binär suchen, wozu dann noch ein Hash?

Gruß, Doc
topeg
 2006-12-21 23:29
#72671 #72671
User since
2006-07-10
2611 Artikel
BenutzerIn

user image
Wie wäre es mit einer abschätzenden Suche:

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
#!/usr/bin/perl
use strict;
use warnings;

my @ids = qw/1 3 4 12 41 43 44 55 67 78 103 156 167 176 198 244 300 345 355/;
my $id = 4;
my $prev_id = 'undef';
my $next_id = 'undef';

if($id>=$ids[0] && $id<=$ids[-1])
{
  my $abstand=($ids[-1]-$ids[0])/scalar(@ids);
  my $pos=int($id/$abstand);
  if($ids[$pos]<$id)
  { $pos+=1 while($id>$ids[$pos]); }
  elsif($ids[$pos]>$id)
  { $pos-=1 while($id<$ids[$pos]); }
  if($id==$ids[$pos])
  {
   $prev_id =$ids[$pos-1] if($pos-1>=0);
   $next_id =$ids[$pos+1]if($pos+1<=$#ids);
  }
}
print "VOR  ID: $prev_id\n";
print "     ID: $id\n";
print "NACH ID: $next_id\n";
\n\n

<!--EDIT|topeg|1166737034-->
<< |< 1 2 3 >| >> 21 Einträge, 3 Seiten



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