[Perl] Wat is sneller (inArray)?

[Verwijderd]

Hallo,

Ik zou graag willen weten welke methode sneller is om te achterhalen of een item al in een bepaalde array aanwezig is.

In onderstaande functies is het eerste argument een referentie naar een array en het tweede argument is de te vergelijken variabele.

Methode 1:

code:

sub inArray1() {
  foreach(@{$_[0]}) {
    if($_ eq $_[1]) {
    return 1;
    }
  }
  return 0;
}

Methode 2:

code:

sub inArray2() {
  if((${$_[0]}[0] ne $_[1]) #eerste cel
    && (${$_[0]}[$#{$_[0]}] ne $_[1]) #laatste cel 
    && (index("@{$_[0]}", " $_[1] ") == -1)) { #tussenin 
    return 0;
  }
  return 1; 
}

Alvast bedankt.

[Verwijderd]

methode 1 is sneller.

Arrays zijn zwaar geoptimaliseerd in perl.
Daarom is het niet zo erg om er helemaal doorheen te lopen.

methode 2 is alleen al langzamer omdat je meer handelingen verricht. En string comparisons zijn sowieso langzamer

[eek]

als dit een assosiative(jezus wat een klote woord)
array is dan kan je gewoon
if ( defined($arr{"iets"}) )
doen

[tomato]

_eek_: als dit een assosiative(jezus wat een klote woord)
array is dan kan je gewoon
if ( defined($arr{"iets"}) )
doen

Nee, hij wil niet weten of het als key voor komt, maar of het als value voor komt.

Overigens worden associative arrays of structs in perl meestal hashes genoemd

[tomato]

Wat jij voorstelt (kijken of een key voor komt) kan overigens even goed met Arrays als met Hashes:

code:

# Bestaat dit element?
print $array[3] if exists($array[3]);
print $hash{"key"} if exists($hash{"key"});

# Heeft het element een waarde?
print $array[3] if defined($array[3]);
print $hash{"key"} if defined($hash{"key"});

[Verwijderd]

Op dinsdag 15 januari 2002 15:12 schreef _eek_ het volgende:
als dit een assosiative(jezus wat een klote woord)
array is dan kan je gewoon
if ( defined($arr{"iets"}) )
doen

sheesh, dit is gewoon zoooo irrelevant!
Hij vraagt naar hoe je een value in een array-ref het snelst kan vinden, niet hoe je checkt of een bepaalde key in een hash bestaat.

de groeten!

[Verwijderd]

lama....

[chem]

Op dinsdag 15 januari 2002 20:38 schreef ludohelder het volgende:
lama....

ik dacht al

[Juup]

Of je sorteert je array en doet er een binarysearch op. Als je met GROTE arrays van doen hebt scheelt dat enorm.

(de zoektijd schaalt bij binarysearch met log n en bij 'lineaire' search met n. (n is lengte array))

[Juup]

Methode 2:

code:

sub inArray2() {
  if((${$_[0]}[0] ne $_[1]) #eerste cel
    && (${$_[0]}[$#{$_[0]}] ne $_[1]) #laatste cel 
    && (index("@{$_[0]}", " $_[1] ") == -1)) { #tussenin 
    return 0;
  }
  return 1; 
}

En waar blijven de andere cellen? Je loopt niet door de volledige array heen.

edit:

wat doet die index functie? En waarom gebruik je die niet voor de eerste en de laatste?

[Verwijderd]

En waar blijven de andere cellen? Je loopt niet door de volledige array heen.
wat doet die index functie? En waarom gebruik je die niet voor de eerste en de laatste?

Die index functie zoekt in de string die van de array gemaakt is ("@{$_[0]}") naar een string welke de te vergelijken variabele voorstelt met 2 spaces (" $_[1] ").
Als het array dus gevuld is met de waarden 1,2,3 en 4 zoekt de index functie in de string: "1 2 3 4" naar de waarde van de te vergelijken variabele. Vandaar dat de index functie niet voor de eerste en laatste cel gebruikt kan worden.

Mensen nogmaals bedankt voor de antwoorden.

[Ees]

Het antwoord is niet zo eenduidig. Het hangt er namelijk vanaf:
- Is de array constant, hoe gebruik je 'm
- Wat voor elementen zitten erin (strings/getallen, groot/klein)
- Is het waarschijnlijk dat de te zoeken elementen voorkomen, of juist niet. Is het waarschijnlijk dat ze vooraan staan, of juist niet
- Etcetera

Bijvoorbeeld: het zou veel efficienter kunnen zijn om (al dan niet eenmalig) een index-array/hash/vector bij te houden, en vervolgens *daarop* te testen:

code:

my @klinkers = qw/a e i o u y/;
my %isklinker;
@isklinker{@klinkers} = (1) x @klinkers;

if ( $isklinker{"a"} ) { print "yep\n" }

Kortom, zie perlfaq4: How can I tell whether a list or array contains a certain element?

En als je zeker wilt weten wat het snelst is: perldoc Benchmark.