co jest szybsze: in_array czy isset? [Zamknięte]

96

To pytanie jest tylko dla mnie, ponieważ zawsze lubię pisać zoptymalizowany kod, który może działać również na tanich, powolnych serwerach (lub serwerach z DUŻYM ruchem)

Rozejrzałem się i nie mogłem znaleźć odpowiedzi. Zastanawiałem się, co jest szybsze między tymi dwoma przykładami, pamiętając, że klucze tablicy w moim przypadku nie są ważne (oczywiście pseudokod):

<?php
$a = array();
while($new_val = 'get over 100k email addresses already lowercased'){
    if(!in_array($new_val, $a){
        $a[] = $new_val;
        //do other stuff
    }
}
?>

<?php
$a = array();
while($new_val = 'get over 100k email addresses already lowercased'){
    if(!isset($a[$new_val]){
        $a[$new_val] = true;
        //do other stuff
    }
}
?>

Ponieważ nie chodzi o kolizję tablic, to dodam, że jeśli boisz się kolizji wstawek $a[$new_value]to możesz użyć $a[md5($new_value)]. nadal może powodować kolizje, ale eliminuje możliwy atak DoS podczas odczytu z pliku dostarczonego przez użytkownika ( http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html )

Fabrizio
źródło
3
Jeśli zawsze starasz się pisać zoptymalizowany kod, na pewno używasz profilera od czasu do czasu?
mario
60
Głosuję za ponownym otwarciem. Pytanie jest dobrze sformułowane, a odpowiedzi są poparte faktami i odniesieniami. Choć mikro -optimization, tego typu pytania są konstruktywne .
Jason McCreary
5
@JasonMcCreary second; jeszcze tylko jeden.
Ja͢ck
7
To jest wiele lat później, ale nawet nie uważałbym tego za mikro optymalizację. W przypadku dużych zestawów danych może to mieć ogromne znaczenie!
Robert
2
... to pytanie wygląda dla mnie "konstruktywnie". Zacznę kolejną kampanię ponownego otwarcia.
mickmackusa

Odpowiedzi:

117

Dotychczasowe odpowiedzi są trafne. Używanie issetw tym przypadku jest szybsze, ponieważ

  • Używa wyszukiwania skrótu O (1) na kluczu, podczas gdy in_arraymusi sprawdzać każdą wartość, dopóki nie znajdzie dopasowania.
  • Będąc kodem operacyjnym, ma mniej narzutów niż wywołanie funkcji in_arraywbudowanej.

Można to zademonstrować, używając tablicy z wartościami (10 000 w poniższym teście), wymuszając in_arraydalsze wyszukiwanie.

isset:    0.009623
in_array: 1.738441

Opiera się to na benchmarku Jasona, wypełniając kilka losowych wartości i od czasu do czasu znajdując wartość, która istnieje w tablicy. Wszystkie losowe, więc uważaj, że czasy będą się zmieniać.

$a = array();
for ($i = 0; $i < 10000; ++$i) {
    $v = rand(1, 1000000);
    $a[$v] = $v;
}
echo "Size: ", count($a), PHP_EOL;

$start = microtime( true );

for ($i = 0; $i < 10000; ++$i) {
    isset($a[rand(1, 1000000)]);
}

$total_time = microtime( true ) - $start;
echo "Total time: ", number_format($total_time, 6), PHP_EOL;

$start = microtime( true );

for ($i = 0; $i < 10000; ++$i) {
    in_array(rand(1, 1000000), $a);
}

$total_time = microtime( true ) - $start;
echo "Total time: ", number_format($total_time, 6), PHP_EOL;
David Harkness
źródło
Wiem o hashach, ale zastanawiam się, dlaczego czegoś podobnego nie robi się na wartościach tablic, jeśli jest to możliwe, aby przyspieszyć funkcje, zmniejszy to również zużycie pamięci, jeśli zostaną użyte podobne wartości, po prostu dodając dodatkowe hashowanie do wartości ... prawda?
Fabrizio
3
@Fabrizio - wartości tablic mogą być zduplikowane i zawierać obiekty, których nie można haszować. Klucze muszą być unikalne i mogą być tylko łańcuchami i liczbami całkowitymi, co sprawia, że ​​można je łatwo mieszać. Chociaż możesz stworzyć mapę jeden do jednego, która haszuje zarówno klucze, jak i wartości, nie tak działa tablica PHP.
David Harkness,
3
Jeśli jesteś pewien, że tablica zawiera unikalne wartości, istnieje inna opcja - flip + isset .
Arkadij Kuzhel
warto zauważyć, że odwrócony isset jest nadal szybszy w tym przykładzie niż in_array: `` $ start = microtime (true); $ foo = array_flip ($ a); for ($ i = 0; $ i <10000; ++ $ i) {isset ($ foo [rand (1, 1000000)]); } $ total_time = microtime (true) - $ start; echo "Całkowity czas (odwrócony isset):", number_format ($ total_time, 6), PHP_EOL;
Andre Baumeier
@AndreBaumeier To, co jest szybsze, zależy od rozmiaru tablicy i liczby testów, które wykonasz. Odwrócenie tablicy zawierającej dziesięć tysięcy elementów w celu wykonania trzech testów prawdopodobnie nie jest wydajne.
David Harkness,
42

Co jest szybsze: isset()vsin_array()

isset() jest szybszy.

Chociaż powinno to być oczywiste, isset()testuje tylko jedną wartość. Natomiast in_array()będzie iterować po całej tablicy, testując wartość każdego elementu.

Szorstkie testy porównawcze są dość łatwe w użyciu microtime().

Wyniki:

Total time isset():    0.002857
Total time in_array(): 0.017103

Uwaga: wyniki były podobne, niezależnie od tego, czy istniały, czy nie.

Kod:

<?php
$a = array();
$start = microtime( true );

for ($i = 0; $i < 10000; ++$i) {
    isset($a['key']);
}

$total_time = microtime( true ) - $start;
echo "Total time: ", number_format($total_time, 6), PHP_EOL;

$start = microtime( true );

for ($i = 0; $i < 10000; ++$i) {
    in_array('key', $a);
}

$total_time = microtime( true ) - $start;
echo "Total time: ", number_format($total_time, 6), PHP_EOL;

exit;

Dodatkowe zasoby

Zachęcam również do obejrzenia:

Jason McCreary
źródło
Niezłe rozwiązanie. Jestem zaskoczony, że więcej ludzi nie dzieli czasu swoich funkcji / kodu częściej przy użyciu microtime()innych narzędzi. Niezwykle cenne.
nickhar,
1
Przeszukiwanie pustej tablicy dla tego samego klucza uwydatnia tylko narzut wywołania in_arrayfunkcji w porównaniu z użyciem funkcji issetwbudowanej. Byłoby to lepsze w przypadku tablicy zawierającej zestaw losowych kluczy i od czasu do czasu wyszukującej istniejący klucz / wartość.
David Harkness,
Zrobić użytku wzorce i microtime sporo, ale ja też sobie sprawę, a ja testuje whilei foreachże na każdym odświeżeniu ja dostawałem różne „zwycięzców”. zawsze zależy od zbyt wielu zmiennych serwera, a najlepiej jest iterować bardzo dużą liczbę razy w różnych momentach i uzyskać ten, który wygrywa częściej, lub po prostu wiedzieć, co dzieje się w tle i wiedzieć, że będzie to ostateczny zwycięzca nie ważne co
Fabrizio
@David Harkness, już wybrałeś moją odpowiedź. Jeśli chcesz więcej, stań na moich ramionach i napisz własną odpowiedź. :) Niemniej jednak, jeśli narzut funkcji jest już znacznie droższy w porównaniu do isset()tego, co sprawia, że ​​myślisz, że przekazanie jej większej tablicy przyspieszyło ?
Jason McCreary
1
@Fabrizio - Przeczytaj o funkcjach haszujących i tabelach skrótów .
David Harkness,
19

Używanie isset()korzysta z szybszego wyszukiwania, ponieważ używa tablicy skrótów , unikając potrzebyO(n) wyszukiwania.

Klucz jest najpierw szyfrowany za pomocą funkcji skrótu djb w celu określenia zasobnika podobnie zaszyfrowanych kluczy O(1). Zasobnik jest następnie przeszukiwany iteracyjnie, aż dokładny klucz zostanie znaleziony w O(n).

Z wyjątkiem jakichkolwiek celowych kolizji hash , to podejście zapewnia znacznie lepszą wydajność niż in_array().

Zwróć uwagę, że podczas używania isset()w pokazany sposób, przekazanie końcowych wartości do innej funkcji wymaga użycia array_keys()do utworzenia nowej tablicy. Naruszenie pamięci może nastąpić poprzez przechowywanie danych zarówno w kluczach, jak i wartościach.

Aktualizacja

Dobrym sposobem sprawdzenia, jak decyzje dotyczące projektu kodu wpływają na wydajność środowiska uruchomieniowego, możesz sprawdzić skompilowaną wersję swojego skryptu:

echo isset($arr[123])

compiled vars:  !0 = $arr
line     # *  op                           fetch      ext  return  operands
-----------------------------------------------------------------------------
   1     0  >   ZEND_ISSET_ISEMPTY_DIM_OBJ              2000000  ~0      !0, 123
         1      ECHO                                                 ~0
         2    > RETURN                                               null

echo in_array(123, $arr)

compiled vars:  !0 = $arr
line     # *  op                           fetch      ext  return  operands
-----------------------------------------------------------------------------
   1     0  >   SEND_VAL                                             123
         1      SEND_VAR                                             !0
         2      DO_FCALL                                 2  $0      'in_array'
         3      ECHO                                                 $0
         4    > RETURN                                               null

Nie tylko in_array()używa stosunkowo nieefektywnego O(n)wyszukiwania, ale również musi być wywoływane jako funkcja ( DO_FCALL), podczas gdy isset()używa do tego pojedynczego opcode ( ZEND_ISSET_ISEMPTY_DIM_OBJ).

Jacek
źródło
7

Drugi byłby szybszy, ponieważ szuka tylko tego konkretnego klucza tablicy i nie musi iterować po całej tablicy, dopóki nie zostanie znaleziony (sprawdzi każdy element tablicy, jeśli nie zostanie znaleziony)

Mike Brant
źródło
ale zależy to również od miejsca pobytu przeszukiwanego var w zakresie globalnym
el Dude,
@ EL2002, czy możesz rozwinąć to stwierdzenie?
Fabrizio
1
Mike, czy nie patrzyłbyś na całą tablicę, nawet isset()jeśli nie została znaleziona?
Fabrizio
1
@Fabrizio Nie, to nie wymaga iteracji. Wewnętrznie (w C) tablica PHP jest po prostu tablicą mieszającą. Aby wyszukać pojedynczą wartość indeksu, C po prostu tworzy skrót tej wartości i wyszukuje przypisaną lokalizację w pamięci. Jest albo wartość, albo jej nie ma.
Mike Brant
1
@Fabrizio Ten artykuł zawiera dobry przegląd tego, jak tablice są wewnętrznie reprezentowane w języku C przez PHP. nikic.github.com/2012/03/28/…
Mike Brant