a

Câu hỏi Danh sách Big-O cho các hàm PHP


Sau khi sử dụng PHP trong một thời gian, tôi đã nhận thấy rằng không phải tất cả các hàm PHP được xây dựng đều nhanh như mong đợi. Hãy xem xét hai triển khai có thể có của một hàm có thể tìm thấy nếu một số là số nguyên tố bằng cách sử dụng một mảng các số nguyên tố được lưu trong bộ nhớ cache.

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $prime_array => $number ) {
    $result_array[$number] = in_array( $number, $large_prime_array );
}

//speed is much less dependent on size of $prime_array, and runs much faster.
$prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL,
                       11 => NULL, 13 => NULL, .... 104729 => NULL, ... );
foreach( $prime_array => $number ) {
    $result_array[$number] = array_key_exists( $number, $large_prime_array );
}

Điều này là do in_array được thực hiện với một tìm kiếm tuyến tính O (n) sẽ tuyến tính chậm lại khi $prime_array mọc. Ở đâu array_key_exists chức năng được thực hiện với một tra cứu băm O (1) mà sẽ không làm chậm trừ khi bảng băm được dân cư rất đông (trong trường hợp đó nó chỉ O (n)).

Cho đến nay tôi đã phải khám phá ra của Big-O thông qua thử và sai, và đôi khi nhìn vào mã nguồn. Bây giờ cho câu hỏi ...

Có một danh sách các O lớn lý thuyết (hoặc thực tế) cho tất cả các * các hàm dựng sẵn PHP không?

* hoặc ít nhất là những điều thú vị

Ví dụ, rất khó để dự đoán hàm O lớn được liệt kê bởi vì việc triển khai có thể phụ thuộc vào cấu trúc dữ liệu lõi không xác định của PHP: array_merge, array_merge_recursive, array_reverse, array_intersect, mảng_combine, str_replace (với mảng đầu vào), v.v.


286
2018-03-18 23:12


gốc


Hoàn toàn tắt chủ đề nhưng, 1 không phải là nguyên tố. - Jason Punyon♦
Mảng trong PHP là hashtables. Điều đó sẽ cho bạn biết mọi thứ bạn cần biết. Tìm kiếm một khóa trong một hashtable là O (1). Tìm kiếm một giá trị là O (n) - mà bạn không thể đánh bại trên một tập hợp chưa được phân loại. Hầu hết các chức năng mà bạn tò mò đều có thể là O (n). Tất nhiên, nếu bạn thực sự muốn biết, bạn có thể đọc nguồn: cvs.php.net/viewvc.cgi/php-src/ext/standard/… - Frank Farmer
Đối với hồ sơ, việc thực hiện nhanh nhất những gì bạn đang cố gắng làm sẽ là (thay vì sử dụng NULL cho các giá trị của bạn) sử dụng true và sau đó kiểm tra sự hiện diện bằng isset($large_prime_array[$number]). Nếu tôi nhớ chính xác, nó theo thứ tự nhanh hơn hàng trăm lần in_array chức năng. - mattbasta
Ký hiệu Big O không phải là về tốc độ. Đó là giới hạn hành vi. - Gumbo
@Kendall Tôi không so sánh với array_key_exists, Tôi so sánh với in_array. in_array lặp lại từng mục trong mảng và so sánh giá trị với kim mà bạn truyền cho nó. Nếu bạn lật các giá trị vào khóa (và chỉ thay thế từng giá trị bằng một giá trị giả như true, sử dụng isset nhanh gấp nhiều lần. Điều này là do các khóa của một mảng được lập chỉ mục bởi PHP (giống như một hashtable). Do đó, việc tìm kiếm một mảng theo cách này có thể có một sự cải thiện đáng kể về tốc độ. - mattbasta


Các câu trả lời:


Vì nó không có vẻ như bất cứ ai đã làm điều này trước khi tôi nghĩ rằng nó là ý tưởng tốt để có nó để tham khảo một nơi nào đó. Tôi đã đi và mặc dù thông qua điểm chuẩn hoặc mã lướt để mô tả đặc điểm array_* chức năng. Tôi đã cố gắng đặt Big-O thú vị hơn ở gần đầu. Danh sách này không đầy đủ.

Lưu ý: Tất cả các Big-O trong đó tính toán giả định một tra cứu băm là O (1) mặc dù nó thực sự là O (n). Hệ số của n quá thấp, chi phí của ram lưu trữ một mảng đủ lớn sẽ làm tổn thương bạn trước khi các đặc điểm tra cứu Big-O sẽ bắt đầu có hiệu lực. Ví dụ: sự khác biệt giữa cuộc gọi đến array_key_exists tại N = 1 và N = 1.000.000 là tăng 50% thời gian.

Điểm thú vị:

  1. isset/array_key_exists nhanh hơn nhiều in_array và array_search
  2. +(công đoàn) nhanh hơn một chút so với array_merge (và trông đẹp hơn). Nhưng nó hoạt động khác nhau nên hãy ghi nhớ điều đó.
  3. shuffle ở cùng cấp Big-O array_rand
  4. array_pop/array_push nhanh hơn array_shift/array_unshift do hình phạt tái chỉ mục

Tra cứu:

array_key_exists O (n) nhưng thực sự gần với O (1) - điều này là do bỏ phiếu tuyến tính trong va chạm, nhưng vì cơ hội va chạm là rất nhỏ, hệ số cũng rất nhỏ. Tôi thấy bạn xử lý tra cứu băm như O (1) để cung cấp cho một lớn hơn thực tế-O. Ví dụ khác nhau giữa N = 1000 và N = 100000 chỉ chậm hơn khoảng 50%.

isset( $array[$index] ) O (n) nhưng thực sự gần với O (1) - nó sử dụng tra cứu giống như array_key_exists. Kể từ khi xây dựng ngôn ngữ, sẽ lưu bộ nhớ cache nếu khóa được mã hóa cứng, dẫn đến tăng tốc trong trường hợp cùng một khóa được sử dụng nhiều lần.

in_array O (n) - điều này là bởi vì nó thực hiện tìm kiếm tuyến tính mặc dù mảng cho đến khi nó tìm thấy giá trị.

array_search O (n) - nó sử dụng hàm lõi giống như in_array nhưng trả về giá trị.

Các hàm hàng đợi:

array_push O (∑ var_i, cho tất cả i)

array_pop O (1)

array_shift O (n) - nó phải reindex tất cả các phím

array_unshiftO (n + ∑ var_i, cho tất cả i) - nó phải reindex tất cả các phím

Giao lộ mảng, Liên minh, Phép trừ:

array_intersect_key nếu giao lộ 100% làm O (Max (param_i_size) * ∑param_i_count, cho tất cả i), nếu giao cắt 0% giao nhau O (∑param_i_size, cho tất cả i)

array_intersect nếu giao lộ 100% làm O (n ^ 2 * ∑param_i_count, cho tất cả i), nếu giao cắt 0% giao nhau với O (n ^ 2)

array_intersect_assoc nếu giao lộ 100% làm O (Max (param_i_size) * ∑param_i_count, cho tất cả i), nếu giao cắt 0% giao nhau O (∑param_i_size, cho tất cả i)

array_diff O (π param_i_size, cho tất cả i) - Đó là sản phẩm của tất cả param_sizes

array_diff_key O (∑ param_i_size, cho i! = 1) - điều này là do chúng ta không cần phải lặp qua mảng đầu tiên.

array_merge O (∑ mảng_i, i! = 1) - không cần phải lặp qua mảng đầu tiên

+ (union) O (n), trong đó n là kích thước của mảng thứ 2 (tức là array_first + array_second) - ít hơn so với array_merge vì nó không phải đổi số

array_replace O (∑ mảng_i, cho tất cả i)

Ngẫu nhiên:

shuffle Trên)

array_rand O (n) - Yêu cầu một cuộc thăm dò tuyến tính.

Rõ ràng Big-O:

array_fill Trên)

array_fill_keys Trên)

range Trên)

array_splice O (bù đắp + chiều dài)

array_slice O (offset + length) hoặc O (n) nếu chiều dài = NULL

array_keys Trên)

array_values Trên)

array_reverse Trên)

array_pad O (pad_size)

array_flip Trên)

array_sum Trên)

array_product Trên)

array_reduce Trên)

array_filter Trên)

array_map Trên)

array_chunk Trên)

array_combine Trên)

Tôi muốn cảm ơn Eureqa để dễ dàng tìm thấy Big-O của các chức năng. Thật tuyệt vời miễn phí chương trình có thể tìm thấy hàm phù hợp nhất cho dữ liệu tùy ý.

CHỈNH SỬA:

Đối với những người nghi ngờ rằng tra cứu mảng PHP là O(N), Tôi đã viết một điểm chuẩn để kiểm tra điều đó (chúng vẫn hiệu quả O(1) cho hầu hết các giá trị thực tế).

php array lookup graph

$tests = 1000000;
$max = 5000001;


for( $i = 1; $i <= $max; $i += 10000 ) {
    //create lookup array
    $array = array_fill( 0, $i, NULL );

    //build test indexes
    $test_indexes = array();
    for( $j = 0; $j < $tests; $j++ ) {
        $test_indexes[] = rand( 0, $i-1 );
    }

    //benchmark array lookups
    $start = microtime( TRUE );
    foreach( $test_indexes as $test_index ) {
        $value = $array[ $test_index ];
        unset( $value );
    }
    $stop = microtime( TRUE );
    unset( $array, $test_indexes, $test_index );

    printf( "%d,%1.15f\n", $i, $stop - $start ); //time per 1mil lookups
    unset( $stop, $start );
}

544
2018-03-20 19:43



@Kendall: Cảm ơn! Tôi đã làm một chút đọc và nó chỉ ra PHP sử dụng hashtables 'lồng nhau' cho va chạm. Đó là, thay vì một cấu trúc logn cho các va chạm, nó đơn giản sử dụng một hashtable khác. Và tôi hiểu rằng thực tế nói rằng hashtables PHP cho O (1) hiệu suất, hoặc ít nhất là O (1) trung bình - đó là những gì hashtables cho. Tôi đã chỉ tò mò là tại sao bạn nói rằng họ là "thực sự O (n)" và không "thực sự O (logn)". Great đăng bài bằng cách này! - Cam
Thời gian phức tạp nên được bao gồm với các tài liệu hướng dẫn! Chọn đúng chức năng có thể giúp bạn tiết kiệm rất nhiều thời gian, hoặc yêu cầu bạn tránh làm những gì bạn dự định: p Cảm ơn bạn đã có danh sách này! - Samuel
Tôi biết điều này là cũ ... nhưng những gì? Đường cong đó không hiển thị O (n) ở tất cả, nó cho thấy O (log n), en.wikipedia.org/wiki/Logarithm. Mà cũng chính xác với những gì bạn mong đợi cho các bản đồ băm lồng nhau. - Andreas
Big-O của unset trên một phần tử của một mảng là gì? - Chandrew
Trong khi hashtables thực sự có trường hợp xấu nhất O (n) tra cứu phức tạp, trường hợp trung bình là O (1) và trường hợp cụ thể điểm chuẩn của bạn là thử nghiệm thậm chí là được đảm bảo O (1), vì nó là mảng dựa trên số không liên tục, không được lập chỉ mục, sẽ không bao giờ có xung đột băm. Lý do tại sao bạn vẫn nhìn thấy một sự phụ thuộc vào kích thước mảng không có gì để làm với phức tạp thuật toán, nó được gây ra bởi hiệu ứng bộ nhớ cache CPU. Mảng càng lớn thì khả năng tra cứu truy cập ngẫu nhiên càng có nhiều khả năng sẽ làm cho bộ nhớ cache bị mất (và bộ đệm ẩn cao hơn trong cấu trúc phân cấp). - NikiC


Bạn hầu như luôn muốn sử dụng isset thay vì array_key_exists. Tôi không nhìn vào bên trong, nhưng tôi khá chắc chắn rằng array_key_exists là O (N) bởi vì nó lặp qua mỗi và mọi khóa của mảng, trong khi isset cố truy cập phần tử bằng cách sử dụng cùng một thuật toán băm được sử dụng khi bạn truy cập vào chỉ mục mảng. Đó nên là O (1).

Một "gotcha" để xem ra là:

$search_array = array('first' => null, 'second' => 4);

// returns false
isset($search_array['first']);

// returns true
array_key_exists('first', $search_array);

Tôi tò mò, vì vậy tôi đã đánh giá sự khác biệt:

<?php

$bigArray = range(1,100000);

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    isset($bigArray[50000]);
}

echo 'is_set:', microtime(true) - $start, ' seconds', '<br>';

$iterations = 1000000;
$start = microtime(true);
while ($iterations--)
{
    array_key_exists(50000, $bigArray);
}

echo 'array_key_exists:', microtime(true) - $start, ' seconds';
?>

is_set: 0.132308959961 giây
array_key_exists: 2.33202195168 giây

Tất nhiên, điều này không hiển thị thời gian phức tạp, nhưng nó cho thấy làm thế nào 2 chức năng so sánh với nhau.

Để kiểm tra độ phức tạp về thời gian, hãy so sánh lượng thời gian cần để chạy một trong các hàm này trên khóa đầu tiên và khóa cuối cùng.


3
2018-03-20 05:07



Cái này sai. Tôi chắc chắn array_key_exists 100% không phải lặp qua từng khóa. Nếu bạn không tin là hãy xem liên kết bên dưới. Lý do isset nhanh hơn rất nhiều là nó là một ngôn ngữ xây dựng. Điều đó có nghĩa là nó không có phí thực hiện cuộc gọi hàm. Ngoài ra, tôi nghĩ rằng nó có thể được bộ nhớ đệm tra cứu, vì điều này. Ngoài ra, đây không phải là câu trả lời cho CÂU HỎI! Tôi muốn một danh sách Big (O) cho các hàm PHP (như các trạng thái câu hỏi). Không phải là một điểm chuẩn duy nhất của các ví dụ của tôi. svn.php.net/repository/php/php-src/branches/PHP_5_3/ext/… - Kendall Hopkins
Nếu bạn vẫn không tin tôi, tôi đã tạo ra một điểm chuẩn nhỏ để chứng minh quan điểm. pastebin.com/BdKpNvkE - Kendall Hopkins
Điều gì là sai với điểm chuẩn của bạn là bạn phải vô hiệu hóa xdebug. =) - Guilherme Blanco
Có hai lý do quan trọng tại sao bạn muốn sử dụng isset trên array_key_exists. Đầu tiên, isset là một ngôn ngữ xây dựng giảm thiểu chi phí của một cuộc gọi hàm. Điều này giống như $arrray[] = $append so với array_push($array, $append) tranh luận. Thứ hai, array_key_exists cũng phân biệt giữa các giá trị không được thiết lập và null. Dành cho $a = array('fred' => null);  array_key_exists('fred', $a) sẽ trả về đúng trong khi isset($['fred']) sẽ trả về false. Bước bổ sung này là không tầm thường và sẽ tăng đáng kể thời gian thực hiện. - orca


Giải thích cho trường hợp bạn mô tả cụ thể là các mảng kết hợp được triển khai dưới dạng các bảng băm - vì vậy hãy tra cứu bằng khóa (và tương ứng, array_key_exists) là O (1). Tuy nhiên, mảng không được lập chỉ mục theo giá trị, do đó, cách duy nhất trong trường hợp chung để khám phá liệu giá trị tồn tại trong mảng có phải là tìm kiếm tuyến tính hay không. Không có gì ngạc nhiên ở đó.

Tôi không nghĩ rằng có tài liệu toàn diện cụ thể về sự phức tạp về thuật toán của các phương thức PHP. Tuy nhiên, nếu đó là một mối quan tâm đủ lớn để đảm bảo nỗ lực, bạn luôn có thể xem qua mã nguồn.


2
2018-03-18 23:17



Đây không thực sự là câu trả lời. Như tôi đã nói trong câu hỏi, tôi đã thử xem xét mã nguồn PHP. Kể từ khi PHP được thực hiện được viết bằng C làm cho việc sử dụng các macro phức tạp, có thể làm cho nó khó khăn vào những lúc "xem" hàm O lớn bên dưới cho các hàm. - Kendall Hopkins
@Kendall Tôi bỏ qua tham chiếu của bạn để đi sâu vào mã nguồn. Tuy nhiên, có một câu trả lời trong câu trả lời của tôi: "Tôi không nghĩ rằng có tài liệu toàn diện cụ thể về sự phức tạp về thuật toán của các phương thức PHP". "Không" là câu trả lời hoàn toàn hợp lệ. (c: - Dathan


Nếu mọi người gặp rắc rối trong thực tế với các va chạm chính, họ sẽ thực hiện các thùng chứa với một tra cứu băm thứ cấp hoặc cây cân bằng. Cây cân bằng sẽ cho O (log n) hành vi xấu nhất và O (1) avg. trường hợp (bản thân hàm băm). Các chi phí không phải là giá trị nó trong thực tế nhất trong các ứng dụng bộ nhớ, nhưng có lẽ có cơ sở dữ liệu mà thực hiện hình thức này của chiến lược hỗn hợp như trường hợp mặc định của họ.


0
2017-11-18 21:38