Giữ một mảng được sắp xếp theo PHP

Question

Tôi có một tập lệnh PHP đọc một tệp CSV lớn và thực hiện các hành động nhất định, nhưng chỉ khi trường "tên người dùng" là duy nhất. CSV được sử dụng trong nhiều hơn một tập lệnh, do đó việc thay đổi đầu vào từ CSV thành chỉ chứa tên người dùng duy nhất không phải là một tùy chọn.

Các chương trình rất cơ bản (mà tôi đang tự hỏi về) dòng chảy đi như thế này:

$allUsernames = array(); 
while($row = fgetcsv($fp)) { 
    $username = $row[0]; 
    if (in_array($username, $allUsernames)) continue; 
    $allUsernames[] = $username; 
    // process this row 
} 

Kể từ CSV này thực sự có thể là khá lớn, đó là in_array chút trong đó có tôi đã suy nghĩ. Tình huống lý tưởng nhất khi tìm kiếm thông qua một mảng cho một thành viên là nếu nó đã được sắp xếp, do đó, làm thế nào bạn sẽ xây dựng một mảng từ đầu, giữ nó theo thứ tự? Một khi nó là theo thứ tự, sẽ có một cách hiệu quả hơn để tìm kiếm nó hơn bằng cách sử dụng in_array(), xem xét rằng nó có lẽ không biết mảng được sắp xếp?

Answer 1

Không giữ mảng theo thứ tự, nhưng làm thế nào về loại tối ưu hóa này? Tôi đoán isset() cho khóa mảng phải nhanh hơn tìm kiếm in_array().

$allUsernames = array(); 
while($row = fgetcsv($fp)) { 
    $username = $row[0]; 

    if (isset($allUsernames[$username])) { 
    continue; 
    } else { 
    $allUsernames[$username] = true; 

    // do stuff 
    } 
} 

Answer 2

Loại mảng trong php là bản đồ được sắp xếp (php array type). Nếu bạn chuyển vào một trong hai int hoặc chuỗi dưới dạng khóa, bạn sẽ có một bản đồ được sắp xếp ...

Vui lòng xem lại mục số 6 trong liên kết ở trên.

Answer 3

Cách xây dựng một mảng từ đầu trong thứ tự sắp xếp là một loại sắp xếp. Trong PHP-ish giả:

$list = [] 
for ($element in $elems_to_insert) { 
    $index = binary_search($element, $list); 
    insert_into_list($element, $list, $index); 
} 

Mặc dù, nó có thể thực sự bật ra được nhanh hơn để chỉ cần tạo các mảng theo thứ tự không được phân loại và sau đó sử dụng quicksort (chức năng phân loại được xây dựng trong PHP sử dụng quicksort)

Và để tìm một phần tử trong danh sách được sắp xếp:

function binary_search($list, $element) { 
    $start = 0; 
    $end = count($list); 
    while ($end - $start > 1) { 
     $mid = ($start + $end)/2; 
     if ($list[$mid] < $element){ 
      $start = $mid; 
     } 
     else{ 
      $end = $mid; 
     } 
    } 
    return $end; 
} 

với thực hiện điều này, bạn sẽ phải kiểm tra $list[$end] để xem nếu nó là yếu tố mà bạn muốn, vì nếu phần tử không có trong mảng, điều này sẽ tìm ra điểm nơi nó sẽ được chèn vào. Tôi đã làm theo cách đó để nó phù hợp với mẫu mã trước đó. Nếu muốn, bạn có thể kiểm tra $list[$end] === $element trong chính chức năng đó.

Answer 4

in_array() không được hưởng lợi từ việc có mảng được sắp xếp. PHP chỉ đi dọc theo toàn bộ mảng như thể nó là một danh sách liên kết.