Apakah fungsi count () PHP O (1) atau O (n) untuk array?

96

Apakah count()benar-benar menghitung semua elemen array PHP, atau apakah nilai ini disimpan di cache di suatu tempat dan baru saja diambil?

php arrays performance Dexter
sumber
6
Mengapa tidak mengujinya? cukup sederhana untuk melakukan loop yang menambahkan elemen ke array dan menghitung setiap waktu dan melakukan beberapa pengaturan waktu.
Marc B
3
Lihatlah pertanyaan ini: stackoverflow.com/questions/2473989/…
Pengembang Pixel
Kata kunci Google - pertanyaan ini juga dapat dirumuskan sebagai: Apakah PHP count () iterasi atas array atau apakah itu mengambil hitungan dari properti array?
jave.web

Jawaban:

136

Nah, kita bisa lihat sumbernya:

/ext/standard/array.c

PHP_FUNCTION(count)panggilan php_count_recursive(), yang pada gilirannya memanggil zend_hash_num_elements()larik non-rekursif, yang diimplementasikan dengan cara ini:

ZEND_API int zend_hash_num_elements(const HashTable *ht)
{
    IS_CONSISTENT(ht);

    return ht->nNumOfElements;
}

Jadi Anda bisa lihat, ini O(1)untuk $mode = COUNT_NORMAL.

Vladislav Rastrusny
sumber
6
Apa yang IS_CONSISTENT(ht)dilakukannya?
Matius
1
Terima kasih! Saya tidak yakin di mana saya harus mencari di sumber atau di mana mendapatkan sumber (tanpa harus memeriksanya dari repositori).
Dexter
3
@Matt Ini memeriksa apakah struktur hash valid, seperti yang saya lihat. Ini didefinisikan di zend_hash.c dan juga O (1).
Vladislav Rastrusny
10
Tidak dapat melewatkan untuk memilih seseorang yang mencari jawaban di kode sumber PHP :)
Lamy
1
@Matt IS_CONSISTENT () hanyalah pemeriksaan kewarasan pada array github.com/php/php-src/blob/PHP-5.3/Zend/zend_hash.c#L51
John Carter
7

Dalam PHP 5+, panjangnya disimpan dalam array sehingga penghitungan tidak dilakukan setiap waktu.

EDIT: Anda juga mungkin menemukan analisis ini menarik: PHP Count Performance . Meskipun panjang array dipertahankan oleh array, sepertinya lebih cepat untuk menahannya jika Anda akan memanggil count()berkali-kali.

jberg
sumber
Saya pikir Anda mungkin benar bahwa perubahan dilakukan dimulai dengan PHP 5. Namun, saya belum menemukan bukti bahwa PHP 4 adalah O (n) untuk count (); Saya hanya melihat komentar anekdot. Apakah Anda dapat menemukan bukti (yaitu implementasi count () untuk PHP 4)? Terima kasih,
Kristopher Windsor
3

PHP menyimpan ukuran array secara internal, tetapi Anda masih membuat pemanggilan fungsi ketika yang lebih lambat daripada tidak membuatnya, jadi Anda akan ingin menyimpan hasilnya dalam variabel jika Anda melakukan sesuatu seperti menggunakannya dalam putaran:

Sebagai contoh,

$cnt = count($array);
for ($i =0; $i < $cnt; $i++) {
   foo($array[$i]);
}

Selain itu, Anda tidak selalu bisa memastikan countdipanggil dalam array. Jika dipanggil pada objek yang mengimplementasikan Countablemisalnya, countmetode objek itu akan dipanggil.

mfonda.dll
sumber
Sebagai tindak lanjut Anda mungkin ingin membaca josephscott.org/archives/2010/01/php-count-performance Ini pada dasarnya merinci bagaimana mendapatkan panjang array o (1) dan dampak dari pemanggilan fungsi yang berulang.
TheClair
1
Apakah membuat panggilan fungsi selalu lebih lambat daripada tidak melakukannya? Saya tidak akan terkejut menemukan penerjemah memiliki pengoptimalan sebaris.
corsiKa
1
the count method of that object will be called, dapatkah Anda menjelaskan sedikit tentang ini
Steel Brain
1
@SteelBrain jika sebuah kelas mengimplementasikan Countableantarmuka, maka pemanggilan count($object)sama dengan memanggil $object->count(). Lihat 3v4l.org/oYSSC sebagai contoh.
mfonda
you're still making a function call when which is slower than not making onePernyataan ini bisa saja salah. Jika Anda melakukan traversal manual, itu adalah O(n)operasi. Tetapi jika Anda hanya ingin mengambil nilai yang telah dihitung sebelumnya, maka operasinya adalah O(1).
Jamshad Ahmad