Manteniendo una matriz ordenada en PHP

Question

Tengo una secuencia de comandos PHP que lee una gran CSV y realiza ciertas acciones, pero solo si el campo "nombre de usuario" es único. El CSV se usa en más de un script, por lo que cambiar la entrada del CSV para que solo contenga nombres de usuario únicos no es una opción.

El flujo del programa muy básico (que estoy preguntando) es la siguiente:

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

Desde este CSV en realidad podría ser bastante grande, es que in_array bits que tiene me puso a pensar. La situación más ideal cuando se busca a través de una matriz para un miembro es si ya está ordenada, por lo que ¿cómo crearía una matriz desde cero, manteniéndola en orden? Una vez que esté en orden, ¿habría una manera más eficiente de buscarlo que usando in_array(), teniendo en cuenta que probablemente no sepa que la matriz está ordenada?

Answer 1

No mantener la matriz en orden, pero ¿qué tal este tipo de optimización? Supongo que isset() para una clave de matriz debe ser más rápido que in_array() de búsqueda.

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

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

    // do stuff 
    } 
} 

Answer 2

El tipo de matriz en php es un mapa ordenado (php array type). Si ingresa ints o cadenas como claves, tendrá un mapa ordenado ...

Por favor revise el ítem n. ° 6 en el enlace de arriba.

Answer 3

La forma de crear una matriz desde cero en orden ordenado es una ordenación por inserción. En PHP-ish pseudocódigo:

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

Aunque, en realidad podría llegar a ser más rápido que acaba de crear la matriz con el fin de clasificar y luego usar la clasificación rápida (funciones de clasificación incorporados de PHP utilizan quicksort)

Y para encontrar un elemento en una lista ordenada:

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

con esta implementación se tendría que probar $list[$end] para ver si es el elemento que desee, ya que si el elemento no está en la matriz, esto va a encontrar el punto donde debe ser insertado Lo hice de esa manera, así sería coherente con la muestra del código anterior. Si lo desea, puede marcar $list[$end] === $element en la función misma.

Answer 4

in_array() no se beneficia de tener una matriz ordenada. PHP simplemente camina a lo largo de toda la matriz como si fuera una lista vinculada.