保持数组在PHP中排序

Question

我有一个PHP脚本,它读取大型CSV并执行某些操作,但前提是"用户名"字段是唯一的.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-ish 伪代码中：

$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入函数本身。