Xây dựng quicksort với php

Question

Gần đây tôi đã đọc về quicksort và đã tự hỏi liệu nó sẽ là thông minh để xây dựng chức năng của riêng tôi để sắp xếp mọi thứ với quicksort hoặc nếu nó sẽ không hiệu quả. Bạn nghĩ gì là chức năng sắp xếp được xây dựng tốt hơn chức năng quicksort tự phát?

Answer 1

Từ http://php.net/sort

Note : Giống như hầu hết các hàm phân loại PHP , sắp xếp() sử dụng triển khai của »Quicksort.

Chức năng PHP cốt lõi sẽ được triển khai trong c, thay vì PHP, vì vậy chúng thường nhanh hơn đáng kể so với bất kỳ thứ gì bạn có thể tự viết bằng PHP. Sẽ có những trường hợp viết nhanh của riêng bạn, nhưng tôi đoán đây là trường hợp bạn có một trường hợp rất cụ thể và bạn có thể tự mình thực hiện tối ưu hóa cho điều đó. Tôi nghĩ rằng đó không phải là trường hợp ở đây.

Answer 2

Gắn bó với chức năng sắp xếp được tích hợp sẵn. Quicksort là một thuật toán đơn giản, nhưng để có được hiệu suất tốt trên các máy tính đang thực sự được sử dụng, cần một chút khéo léo. Nhiều khả năng là chức năng tích hợp sẵn đã được tối ưu hóa nhiều hơn bất cứ thứ gì bạn sẽ viết trong một khoảng thời gian hợp lý. (Việc tăng tốc hệ số không đổi từ được viết bằng C thay vì PHP cũng có thể hữu ích.)

Nếu bạn sắp xếp quá nhiều thành phần mà bạn bị chậm lại bởi chức năng sắp xếp, có thể bạn đang làm sai điều gì đó. (Đây là PHP sau khi tất cả. Bạn nên sử dụng một ngôn ngữ có mục đích chung cho xử lý dữ liệu chuyên sâu. Nó sẽ được dễ dàng hơn để viết mã của bạn, và nó sẽ chạy nhanh hơn.)

Answer 3

Trong thực tế, tôi đã làm điều này cho một điểm dữ liệu trên bản trình bày mà tôi đang tập hợp lại. Bài kiểm tra sắp xếp một mảng 250.000 số nguyên bằng cách sử dụng hàm sắp xếp gốc và triển khai thuật toán quicksort được viết bằng php. Nội dung của mảng giống hệt nhau cho cả hai lần chạy, dữ liệu được phân ngẫu nhiên và thời gian được báo cáo chỉ để thực hiện sắp xếp, không phải xử lý khác cần thiết để gọi trình thông dịch php.

Kết quả:

 
    Native sort implementation: 1.379 seconds 
PHP quicksort implementation: 30.615 seconds 

Chắc chắn sử dụng thi hành bản địa. Đó là trường hợp của bất kỳ ngôn ngữ thông dịch nào.

Các kết quả cho các ngôn ngữ khác mà tôi thử nghiệm với cùng điều kiện sử dụng thực hiện như nhau trên cùng một phần cứng và hệ điều hành, cung cấp một so sánh hiệu suất hấp dẫn và đưa kết quả PHP trong quan điểm:

 
       C: 0.107 seconds 
      Java: 0.250 seconds 
JavaScript (FF3): 4.401 seconds 

Đáng chú ý, Chrome và Safari đã thực hiện thử nghiệm JavaScript nhanh hơn, nhưng tôi không bao gồm những người ở đây vì những thử nghiệm đó được ghi lại trong một môi trường khác.

Answer 4

Để tham khảo có một thực hiện PHP ở đây:

http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Quicksort#C.23

Answer 5

Một điều về php sắp xếp nhanh chóng (asort, arsort, vv) được rằng họ mớ hỗn độn các giá trị tương đương của bạn, có nghĩa là để nói rằng giá trị với các phím khác nhau sẽ hoán đổi vị trí ngẫu nhiên, ngay cả giữa các lần chạy khác nhau. Tuyệt vời là mã có thể tạo ra một thứ tự khác nhau bằng cách sử dụng cùng một dữ liệu một lần nữa và một lần nữa. Cuối cùng tôi đã phải thực hiện loại nhanh chóng của riêng mình để loại bỏ sự bất thường này.

Answer 6

Chỉ để cho vui, đây là một phiên bản tại chỗ của quicksort trong PHP tôi đã đưa ra. Bí quyết ở đây là vượt qua mảng để được sắp xếp làm tham chiếu.

function partition(&$arr,$leftIndex,$rightIndex) 
{ 
    $pivot=$arr[($leftIndex+$rightIndex)/2]; 

    while ($leftIndex <= $rightIndex) 
    {   
     while ($arr[$leftIndex] < $pivot)    
       $leftIndex++; 
     while ($arr[$rightIndex] > $pivot) 
       $rightIndex--; 
     if ($leftIndex <= $rightIndex) { 
       $tmp = $arr[$leftIndex]; 
       $arr[$leftIndex] = $arr[$rightIndex]; 
       $arr[$rightIndex] = $tmp; 
       $leftIndex++; 
       $rightIndex--; 
     } 
    } 
    return $leftIndex; 
} 

function quickSort(&$arr, $leftIndex, $rightIndex) 
{ 
    $index = partition($arr,$leftIndex,$rightIndex); 
    if ($leftIndex < $index - 1) 
     quickSort($arr, $leftIndex, $index - 1); 
    if ($index < $rightIndex) 
     quickSort($arr, $index, $rightIndex); 
}