Сохранение массива в PHP

Question

У меня есть PHP-скрипт, который читает большой CSV и выполняет определенные действия, но только если поле «username» уникально. CSV используется более чем в одном сценарии, поэтому изменение входных данных из 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(), учитывая, что он, вероятно, не знает, что массив отсортирован?

Answer 1

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

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

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

    // do stuff
  }
}

Answer 2

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

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

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

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

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 в самой функции.

Answer 3

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

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

Answer 4

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