Ordenar una matriz de matrices PHP por orden personalizado

Tengo una variedad de matrices:

Array ( 
    [0] => Array (
        [id] = 7867867,
        [title] = 'Some Title'),
    [1] => Array (
        [id] = 3452342,
        [title] = 'Some Title'),
    [2] => Array (
        [id] = 1231233,
        [title] = 'Some Title'),
    [3] => Array (
        [id] = 5867867,
        [title] = 'Some Title')
)

La necesidad de ir en un orden específico:

1. 3452342
2. 5867867
3. 7867867
4. 1231233

¿Cómo haría para hacer eso? He ordenado matrices antes y leí muchas otras publicaciones al respecto, pero siempre se basan en comparaciones (es decir, valorA <valorB).

Se agradece la ayuda.

Jan 01 '70 08:01 Honus Wagner

Ampliando la respuesta de Salathe para este requisito adicional:

Ahora, ¿qué sucede cuando agrego elementos a la matriz y no al ordenamiento? Lógicamente no me importa el orden en que aparezcan, siempre y cuando vengan después de los que sí especifiqué. ¿Cómo manejo eso?

Debe agregar dos condiciones adicionales en la función de clasificación:

1. Un artículo "no importa" debe considerarse mayor que un artículo "pedido personalizado"
2. Dos elementos "no importa" deben considerarse iguales (podría agregar una condición de desempate para este caso)

Aquí está la implementación sucinta de la lógica:

$array = [
    ["id" => 7867867, "title" => "Must Be #3"],
    ["id" => 3452342, "title" => "Must Be #1"],
    ["id" => 1231233, "title" => "Must Be #4"],
    ["id" => 5867867, "title" => "Must Be #2"],
    ["id" => 1111111, "title" => "Dont Care #1"],
    ["id" => 2222222, "title" => "Dont Care #2"],
    ["id" => 3333333, "title" => "Dont Care #3"],
    ["id" => 4444444, "title" => "Dont Care #4"],
];
$order = [
    3452342,
    5867867,
    7867867,
    1231233
];

usort($array, function ($a, $b) use ($order) {
    $ai = array_search($a["id"], $order);
    $bi = array_search($b["id"], $order);
    if ($ai === false && $bi === false) {
        // both items are dont cares
        // relative order of a and b is irrelevant
        return 0;
    } elseif ($ai === false) {
        // a is a dont care
        // put a after b
        return 1;
    } elseif ($bi === false) {
        // b is a dont care
        // put a before b
        return -1;
    } else {
        // put a and b in ascending order
        return $ai - $bi;
    }
});

Y aquí está la versión más rápida con menos líneas de código:

$lookup = array_flip($order);

usort($array, function ($a, $b) use ($lookup) {
    $ai = $lookup[$a["id"]] ?? PHP_INT_MAX;
    $bi = $lookup[$b["id"]] ?? PHP_INT_MAX;
    return $ai <=> $bi;
});

Jun 22 '2012 14:06 Salman A

Solución más eficiente

$dict = array_flip($order);
$positions = array_map(function ($elem) use ($dict) { return $dict[$elem['id']] ?? INF; }, $array);
array_multisort($positions, $array);

No recalcular posiciones en cada comparación

Cuando su matriz es grande o obtener la identificación es más costoso, el uso usort()puede volverse malo, porque vuelve a calcular la identificación para cada comparación. Pruebe array_multisort()con posiciones precalculadas (consulte mediumsorto fastsorten el ejemplo siguiente), lo cual no es más complicado.

Además, buscar la identificación en la matriz de orden en cada comparación (como en la respuesta aceptada) no mejora el rendimiento, ya que se repite en cada comparación. Calcúlalo una vez.

En el siguiente fragmento de código puede ver las tres funciones principales de clasificación:

• slowsort
  La respuesta aceptada. Busca la posición en cada comparación.
• mediumsort
  Mejorado slowsortcalculando las posiciones por adelantado.
• fastsort
  Mejorado mediumsortal evitar buscar por completo.

Tenga en cuenta que estos manejan elementos con una identificación que no figura en el orden proporcionando un valor alternativo de INF. Si su matriz de orden coincide con los identificadores de la matriz original 1 a 1, entonces evite ordenarlos todos juntos y simplemente insertar los elementos en la posición correcta es el camino a seguir. Agregué una función cheatsortque hace exactamente eso.

De manera más general, puede ordenar una matriz por peso (ver weightedsorten el ejemplo). Asegúrate de calcular el peso solo una vez, para lograr un buen rendimiento.

Rendimiento (para una matriz de longitud 1000)

fastsort     about  1 ms
mediumsort   about  3 ms
slowsort     about 60 ms

Sugerencia: para matrices más grandes, la diferencia empeora.

Comparación de funciones de clasificación

<?php

/**
 * accepted answer
 *
 * re-evaluate position in order on each comparison
 */
function slowsort(&$array, $order, $key = 'id')
{
  usort($array, function ($a, $b) use ($order, $key) {
    $pos_a = array_search($a[$key], $order);
    $pos_b = array_search($b[$key], $order);
    return $pos_a - $pos_b;
  });
}

/**
 * calculate element positions once
 */
function mediumsort(&$array, $order, $key = 'id')
{
  $positions = array_map(function ($elem) use ($order, $key) {
    return array_search($elem[$key], $order);
  }, $array);
  array_multisort($positions, $array);
}

/**
 * calculate positions without searching
 */
function fastsort(&$array, $order, $key = 'id')
{
  $dict = array_flip($order);
  $positions = array_map(function ($elem) use ($dict, $key) {
    return $dict[$elem[$key]] ?? INF;
  }, $array);
  array_multisort($positions, $array);
}

/**
 * when each order element gets used exactly once, insert elements directly
 */
function cheatsort(&$array, $order, $key = 'id')
{
  $dict = array_flip($order);
  $copy = $array;
  foreach ($copy as $elem) {
    $pos = $dict[$elem[$key]];
    $array[$pos] = $elem;
  }
}

/**
 * Sort elements in $array by their weight given by $weight_func
 * 
 * You could rewrite fastsort and mediumsort by replacing $position by a weight function
 */
function weightedsort(&$array, $weight_func)
{
  $weights = array_map($weight_func, $array);
  array_multisort($weights, $array);
}



/**
 * MEASUREMENTS
 */

/**
 * Generate the sorting problem
 */
function generate($size = 1000)
{
  $order = array();
  $array = array();

  for ($i = 0; $i < $size; $i++) {
    $id = random_int(0, PHP_INT_MAX);
    $order[] = $id;
    $array[] = array('id' => $id);
  }
  shuffle($order);
  return [$array, $order];
}

/**
 * Time $callable in ms
 */
function time_it($callable)
{
  $then = microtime(true);
  $callable();
  $now = microtime(true);
  return 1000 * ($now - $then);
}

/**
 * Time a sort function with name $sort_func
 */
function time_sort($sort_func) 
{
  echo "Timing $sort_func", PHP_EOL;
  [$array, $order] = generate();
  echo time_it(function () use ($sort_func, &$array, $order) {
    $sort_func($array, $order);
  }) . ' ms' . PHP_EOL;
}

time_sort('cheatsort');
time_sort('fastsort');
time_sort('mediumsort');
time_sort('slowsort');

Apr 17 '2020 08:04 Josef Wittmann

Sin clasificación también puedes conseguirlo.

1. Si no hay identificadores duplicados y $ordercontiene todos idlos valores de $arrayy la idcolumna en $arraycontiene todos los valores en $order, puede lograr el mismo resultado invirtiendo los valores en claves en $order, luego asigna claves temporales de primer nivel a la matriz y luego fusiona o reemplaza $arrayen $order.

   $order = array(3452342, 5867867, 7867867, 1231233);
   $array = array(
       array('id' => 7867867, 'title' => 'Some Title'),
       array('id' => 3452342, 'title' => 'Some Title'),
       array('id' => 1231233, 'title' => 'Some Title'),
       array('id' => 5867867, 'title' => 'Some Title'),
   );
   
   $order = array_flip($order);
   $array = array_column($array,null,"id");
   $result = array_replace($order,$array);
   var_dump(array_values($result));
   

2. Con identificadores potencialmente duplicados en $array:

   $order = array(3452342, 5867867, 7867867, 1231233);
   $array = array(
       array('id' => 7867867, 'title' => 'Some Title'),
       array('id' => 3452342, 'title' => 'Some Title'),
       array('id' => 1231233, 'title' => 'Some Title'),
       array('id' => 5867867, 'title' => 'Some Title'),
   );
   
   $order_dict = array_flip($order);
   $order_dict = array_combine($order, array_fill(0, count($order), []));
   foreach($array as $item){
       $order_dict[$item["id"]][] = $item;
   }
   //$order_dict = array_filter($order_dict);  // if there is empty item on some id in $order array
   $result = [];
   foreach($order_dict as $items){
       foreach($items as $item){
           $result[] = $item;
       }
   }
   var_dump($result);
   

Jan 16 '2019 06:01 LF-DevJourney

@salathe Para aquellos de ustedes que tienen dificultades para entender qué está haciendo el usort de salathe:

Cada elemento en $array es un 'campeón' en un torneo que estará al comienzo de una nueva matriz (excepto que en lugar de ser el número uno quieren ser el número 0).

$a es el campeón local y $b el campeón oponente en un partido.

$pos_a y $pos_b de la devolución de llamada son los atributos que se usarán en la lucha por los campeones a y b. En este caso, este atributo es el índice de la identificación de los campeones en $order.

Luego está la pelea en el regreso. Ahora miramos para ver si tener más o menos atributo es mejor. En una batalla de usort, el campeón local quiere un número negativo para poder estar más rápido en la alineación. El campeón visitante quiere un número positivo. Y si hay un 0 es un empate.

Entonces, siguiendo esta analogía, cuando el atributo de los campeones visitantes (índice en orden $) se resta del atributo del equipo local, cuanto mayor sea el atributo de los campeones visitantes, es menos probable que gane al obtener un número positivo. Sin embargo, si invirtieras la forma en que se usan los atributos, ahora el atributo del campeón local se resta del del campeón visitante. En este caso, es más probable que un número mayor para el campeón visitante haga que el partido termine con un número positivo.

El código se vería así:

nota: el código se ejecuta muchas veces, de forma muy similar a como un torneo real tiene muchas batallas para decidir quién llega primero (es decir, 0/inicio de la matriz)

//tournament with goal to be first in array
    usort($champions, function ($home, $away) use ($order) {
        $home_attribute = array_search($a['id'], $order);
        $away_attribute = array_search($b['id'], $order);
        //fight with desired outcome for home being negative and away desiring positive
        return $home_attribute - $away_attribute;
    });

Aug 17 '2016 19:08 Jason Basanese