apa yang lebih cepat: in_array atau isset? [Tutup]

96

Pertanyaan ini hanya untuk saya karena saya selalu suka menulis kode yang dioptimalkan yang dapat berjalan juga di server lambat yang murah (atau server dengan BANYAK lalu lintas)

Saya melihat sekeliling dan saya tidak dapat menemukan jawaban. Saya bertanya-tanya apa yang lebih cepat di antara dua contoh tersebut dengan mengingat bahwa kunci array dalam kasus saya tidak penting (pseudo-code secara alami):

<?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
    }
}
?>

Karena poin pertanyaannya bukanlah tabrakan array, saya ingin menambahkan bahwa jika Anda takut untuk menyisipkan bertabrakan $a[$new_value], Anda dapat menggunakan $a[md5($new_value)]. itu masih dapat menyebabkan tabrakan, tetapi akan menghilangkan kemungkinan serangan DoS saat membaca dari file yang disediakan pengguna ( http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html )

Fabrizio
sumber
3
Jika Anda selalu berusaha untuk menulis kode yang dioptimalkan, Anda pasti menggunakan profiler sesekali?
mario
60
Saya memilih untuk membuka kembali. Pertanyaannya disusun dengan baik dan jawaban didukung dengan fakta dan referensi. Sementara mikro- optimalisasi, jenis pertanyaan ini konstruktif .
Jason McCreary
5
@JasonCCary kedua; hanya satu lagi.
Ja͢ck
7
Ini bertahun-tahun kemudian, tetapi saya bahkan tidak akan menganggap ini sebagai pengoptimalan mikro. Untuk kumpulan data yang besar, ini dapat membuat banyak perbedaan !!
Robert
2
... pertanyaan ini tampak "membangun" bagi saya. Saya akan memulai kampanye pembukaan kembali lainnya.
mickmackusa

Jawaban:

117

Jawabannya sejauh ini tepat. Menggunakan issetdalam kasus ini lebih cepat karena

  • Ini menggunakan pencarian hash O (1) pada tombol sedangkan in_array harus memeriksa setiap nilai sampai menemukan kecocokan.
  • Sebagai opcode, ia memiliki overhead yang lebih sedikit daripada memanggil in_arrayfungsi bawaan.

Ini dapat ditunjukkan dengan menggunakan larik dengan nilai (10.000 dalam pengujian di bawah), memaksa in_arrayuntuk melakukan lebih banyak pencarian.

isset:    0.009623
in_array: 1.738441

Ini dibangun di atas tolok ukur Jason dengan mengisi beberapa nilai acak dan sesekali menemukan nilai yang ada dalam larik. Semuanya acak, jadi berhati-hatilah karena waktu akan berfluktuasi.

$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
sumber
Saya tahu tentang hash, tetapi bertanya-tanya mengapa sesuatu yang serupa tidak dilakukan pada nilai array bila memungkinkan untuk mempercepat fungsi, itu juga akan mengurangi konsumsi memori jika nilai serupa digunakan hanya dengan menambahkan tambahan hashing pada nilai .. benar?
Fabrizio
3
@Fabrizio - Nilai array dapat diduplikasi dan berisi objek yang tidak dapat di-hash. Kunci harus unik dan hanya dapat berupa string dan integer yang membuatnya mudah di-hash. Meskipun Anda dapat membuat peta satu-ke-satu yang meng-hash kedua kunci dan nilai, ini bukanlah cara kerja array PHP.
David Harkness
3
Jika Anda yakin bahwa array Anda berisi nilai unik maka ada opsi lain - flip + isset .
Arkadij Kuzhel
perlu dicatat bahwa isset yang dibalik masih lebih cepat dalam contoh ini daripada in_array: `` `` $ start = microtime (true); $ foo = larik_flip ($ a); untuk ($ i = 0; $ i <10000; ++ $ i) {isset ($ foo [rand (1, 1000000)]); } $ total_time = microtime (true) - $ start; echo "Total waktu (isset terbalik):", number_format ($ total_time, 6), PHP_EOL;
Andre Baumeier
@AndreBaumeier Mana yang lebih cepat akan tergantung pada ukuran array dan berapa banyak tes yang akan Anda lakukan. Membalik sepuluh ribu elemen array untuk melakukan tiga pengujian mungkin tidak efisien.
David Harkness
42

Mana yang lebih cepat: isset()vs.in_array()

isset() lebih cepat.

Meskipun harus jelas, isset()hanya menguji satu nilai. Sedangkanin_array() akan mengulangi seluruh array, menguji nilai setiap elemen.

Pembandingan kasar cukup mudah digunakan microtime().

Hasil:

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

Catatan: Hasil serupa terlepas dari apakah ada atau tidak.

Kode:

<?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;

Sumber daya tambahan

Saya mendorong Anda untuk juga melihat:

Jason McCreary
sumber
Solusi bagus. Saya terkejut lebih banyak orang tidak membagi waktu fungsi / kode mereka lebih banyak menggunakan microtime()atau alat lain. Sangat berharga.
nickhar
1
Mencari array kosong untuk kunci yang sama hanya menyoroti overhead pemanggilan in_arrayfungsi versus menggunakan issetbuilt-in. Ini akan lebih baik dengan array yang berisi sekumpulan kunci acak dan terkadang mencari kunci / nilai yang ada.
David Harkness
Saya menggunakan benchmark dan microtime cukup banyak, tetapi saya juga menyadari, ketika saya menguji whiledan foreachbahwa pada setiap penyegaran saya mendapatkan "pemenang" yang berbeda. itu selalu bergantung pada terlalu banyak variabel server, dan yang terbaik adalah mengulang berkali-kali pada waktu yang berbeda dan mendapatkan yang menang lebih sering, atau hanya tahu apa yang terjadi di latar belakang dan ketahuilah bahwa itu akan menjadi pemenang akhir tidak peduli apa
Fabrizio
@David Harkness, Anda sudah memilih jawaban saya. Jika Anda ingin lebih, berdiri di pundak saya dan posting jawaban Anda sendiri. :) Meskipun demikian, jika overhead fungsi sudah secara signifikan lebih mahal dibandingkan isset(), apa yang membuat Anda berpikir bahwa meneruskannya ke array yang lebih besar akan membuatnya lebih cepat ?
Jason McCreary
1
@Fabrizio - Baca tentang fungsi hashing dan tabel hash .
David Harkness
19

Menggunakan isset()mengambil keuntungan dari pencarian yang lebih cepat karena menggunakan tabel hash , menghindari kebutuhan untuk O(n)pencarian.

Kuncinya di-hash terlebih dahulu menggunakan fungsi hash djb untuk menentukan keranjang kunci dengan hash serupa di O(1). Bucket kemudian ditelusuri secara berulang hingga kunci yang tepat ditemukan diO(n) .

Jika tidak ada benturan hash yang disengaja , pendekatan ini menghasilkan kinerja yang jauh lebih baik daripadain_array() .

Perhatikan bahwa saat menggunakan isset()dengan cara yang Anda tunjukkan, meneruskan nilai akhir ke fungsi lain membutuhkan penggunaanarray_keys() untuk membuat larik baru. Kompromi memori dapat dilakukan dengan menyimpan data di kunci dan nilai.

Memperbarui

Cara yang baik untuk melihat bagaimana keputusan desain kode Anda memengaruhi kinerja waktu proses, Anda dapat memeriksa versi terkompilasi dari skrip Anda:

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

Tidak hanya in_array()menggunakan O(n)pencarian yang relatif tidak efisien , itu juga perlu dipanggil sebagai fungsi ( DO_FCALL) sedangkan isset()menggunakan satu opcode ( ZEND_ISSET_ISEMPTY_DIM_OBJ) untuk ini.

Mendongkrak
sumber
7

Yang kedua akan lebih cepat, karena hanya mencari kunci array tertentu dan tidak perlu mengulang seluruh array sampai ditemukan (akan melihat setiap elemen array jika tidak ditemukan)

Mike Brant
sumber
tetapi juga tergantung dari keberadaan var yang ditelusuri dalam lingkup global
el Dude
@ EL2002, dapatkah Anda menjelaskan lebih lanjut tentang pernyataan itu?
Fabrizio
1
Mike, tidak akan melihat seluruh larik bahkan dengan isset()jika tidak ditemukan?
Fabrizio
1
@Fabrizio Tidak, tidak perlu mengulang. Secara internal (dalam C) array PHP hanyalah tabel hash. Untuk mencari nilai indeks tunggal, C hanya membuat hash dari nilai tersebut dan mencari lokasi yang ditetapkan di memori. Ada nilai di sana atau tidak ada.
Mike Brant
1
@Fabrizio Artikel ini memberikan gambaran yang baik tentang bagaimana array secara internal diwakili dalam C oleh PHP. nikic.github.com/2012/03/28/…
Mike Brant