Сохранение массива, отсортированного по PHP

У меня есть PHP script, который читает большой CSV и выполняет определенные действия, но только если поле "имя пользователя" уникально. CSV используется более чем в одном script, поэтому изменение ввода из CSV только с уникальными именами пользователей не является вариантом.

Самый простой поток программы (о котором мне интересно) выглядит следующим образом:

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

Поскольку этот CSV действительно может быть довольно большим, это бит in_array, который заставил меня задуматься. Самая идеальная ситуация при поиске по массиву для члена - если он уже отсортирован, поэтому как вы создадите массив с нуля, сохранив его в порядке? Как только он будет в порядке, будет ли более эффективный способ его поиска, чем при использовании in_array(), учитывая, что он, вероятно, не знает, что массив отсортирован?

Ответ 1

Не хранить массив в порядке, но как насчет такой оптимизации? Я предполагаю, что isset() для ключа массива должен быть быстрее, чем in_array() search.

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

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

    // do stuff
  }
}

Ответ 2

Способ создания массива с нуля в отсортированном порядке - это сортировка вставки. В псевдокоде PHP-ish:

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

Хотя на самом деле может оказаться быстрее создать массив в несортированном порядке, а затем использовать quicksort (функции сортировки PHP встроены в quicksort)

И найти элемент в отсортированном списке:

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

С помощью этой реализации вам нужно будет протестировать $list[$end], чтобы убедиться, что это тот элемент, который вы хотите, поскольку, если элемент не находится в массиве, он найдет точку, в которую он должен быть вставлен. Я сделал это так, чтобы он соответствовал предыдущему образцу кода. Если вы хотите, вы можете проверить $list[$end] === $element в самой функции.

Ответ 3

Тип массива в php - упорядоченное отображение (тип массива php). Если вы передаете либо ints, либо строки как ключи, у вас будет упорядоченная карта...

Пожалуйста, просмотрите пункт №6 в приведенной выше ссылке.

Ответ 4

in_array() не использует сортированный массив. PHP просто идет по всему массиву, как если бы это был связанный список.