Funzione usort. Ma come funziona esattamente?

[lucas726]

Ciao a tutti,

Stavo dando un'occhiata alla funzione usort di php qui:

https://www.php.net/manual/en/function.usort.php


Ma non mi è chiaro come esattamente funzioni.

Questi sono due esempi riportati:

  <?php
function cmp($a, $b)
{
    if ($a == $b) {
        return 0;
    }
    return ($a < $b) ? -1 : 1;
}

$a = array(3, 2, 5, 6, 1);

usort($a, "cmp");

foreach ($a as $key => $value) {
    echo "$key: $value\n";
}
?>

Risultato:

0: 1
1: 2
2: 3
3: 5
4: 6

Oppure questa che usa lo spaceshift:

  <?php
function cmp($a, $b)
{
    return $a <=> $b;
}

$a = array(3, 2, 5, 6, 1);

usort($a, "cmp");

foreach ($a as $key => $value) {
    echo "$key: $value\n";
}
?>

Ma esattamente alla funzione:

function cmp($a, $b)
...


quando e quale valore viene passato per $b?

Potete aiutarmi a capire i passaggi?

Grazie

[Dascos]

Se ricordo giusto è un QuickSort, che in pratica è basato su pivot. Una spiegazione ben fatta anche se inizialmente ostica di questo algoritmo è su wiki: https://it.wikipedia.org/wiki/Quicksort

[lucas726]

Se ricordo giusto è un QuickSort, che in pratica è basato su pivot. Una spiegazione ben fatta anche se inizialmente ostica di questo algoritmo è su wiki: https://it.wikipedia.org/wiki/Quicksort

Scusami ma così è anche più complicato.

[KillerWorm]

Ciao, forse la tua richiesta è formulata in maniera piuttosto generica; non si capisce bene su che livello la stai ponendo e quali risposte vorresti ottenere; se si tratta di "comune programmazione" oppure di "analisi degli algoritmi".

Provo comunque a rispondere in "umanese" cercando di interpretare l'intento delle tue domande:

quando e quale valore viene passato per $b?

la variabile $b (come anche $a) è sempre valorizzata dentro quella funzione di callback. Questi due parametri infatti rappresentano una coppia X di valori (relativi all'array processato), i quali vengono comparati attraverso tale funzione e, in base a ciò che questa restituisce, ne viene ridefinita la loro posizione dentro l'array.

Potete aiutarmi a capire i passaggi?

La funzione di callback (definita di fatto dall'utente) è solo la punta dell'iceberg per la quale viene giusto definito il criterio di comparazione dei valori. Questa deve restituire un valore minore, uguale o maggiore di zero che viene dato quindi in pasto a usort().

Infatti tutto il meccanismo di funzionamento sta poi nel core della funzione usort().

Questa funzione si occupa di chiamare in modo ciclico/iterativo il callback secondo uno specifico algoritmo di ordinamento per il quale è basato il core stesso di tale funzione. Al callback viene quindi passata, di volta in volta, una coppia X di valori, finché non risultano comparati tutti i valori dell'array, per cui si può stabilirne l'avvenuto ordinamento. Il risultato che viene restituito dal callback, relativo alla coppia correntemente comparata, è dato in pasto al core di usort() e viene usato per ridefinire la posizione degli elementi nell'array.

Alla fine del processo gli elementi dell'array risulteranno quindi riordinati secondo il criterio definito nel callback. Ma il callback in sé non esegue nessuna manipolazione dell'array né tantomeno decide quali valori devono essere di volta in volta comparati; il grosso del lavoro lo fa ciò che sta dietro la funzione usort().

Non c'è nulla di magico ma, essendo codice built-in di PHP, si presume che ad un comune programmatore (nell'ambito della normale programmazione) non interessi quali passaggi sono compiuti per arrivare a quel particolare risultato (per questo la mia osservazione iniziale). Questi passaggi infatti sono stabiliti in base all'algoritmo di ordinamento usato in PHP per tale funzione (vedi risposta di Dascos).

L'attuale versione di PHP, per l'ordinamento dei dati, si basa appunto su una implementazione dell'algoritmo Quicksort; ma non è sicuro che per future versioni sia mantenuto sempre esattamente questo stesso algoritmo; potrebbe essere implementato, modificato, cambiato con un altro.

Con questo particolare algoritmo viene stabilito il modo con cui devono essere selezionati i valori da comparare. In linea di massima, nel caso di Quicksort, i valori sono scelti e comparati per coppie in modo ciclico, selezionando dei valori "perno", secondo un particolare schema, più o meno complesso, per il quale non è possibile dirti con semplicità che passaggi vengono eseguiti di preciso dalla funzione usort(), e quali valori assumono quindi le due variabili nel callback. Per saperlo andrebbe analizzato il meccanismo dell'algoritmo e come è stato implementato nello specifico in PHP.

Suppongo comunque che tu non volessi sapere il meccanismo di funzionamento di tale algoritmo, ma semplicemente che ruolo ha quella funzione di callback.

Spero di aver chiarito qualche dubbio.

[Dascos]

Scusami ma così è anche più complicato.

Mi riaggancio anche alla risposta di KillerWorm.
In pratica, diciamo che tu hai questi valori nell'array: 3,6,1,8,4,9,5
Diciamo che li vuoi ordinare in modo ascendente e quindi definisci la tua funzione in uno dei due modi che hai portato di esempio.
Andiamo "dietro" alla funzione usort, che usa l'algoritmo QuickSort.
Più o meno succede così...l'algoritmo usort cerca un "pivot", cioè un valore iniziale da usare poi come "paragone" e, per semplicità, facciamo finta che vada a prendere il valore finale, cioè 5. Questo 5 è "a".
Ora l'algoritmo prende uno a uno tutti i valori a sinistra e li confronta a 5 in base alla tua funzione: alla funzione arriverà quindi la coppia 5-3. Siccome 3 è inferiore (perchè così stabilisce la tua funzione di confronto), viene lasciato lì dov'è.
Poi arriva la coppia 5-6. 6 è superiore, quindi viene posizionato a destra e, internamente, l'array è diventato 3,1,8,4,9,5,6
Poi arriva 5-1 e resta così com'è. Poi 5-8 e siccome 8 è maggiore finisce a destra, e l'array è 3,1,4,9,5,6,8. Poi arriva al 5-9 e trasforma l'array in 3,1,4,5,6,8,9.
Ora procedo a cercare un nuovo pivot e l'algoritmo sceglie il 4 e lavora sulla parte a sinistra del pivot originale (quindi sui numeri 3,1, e 4). Per "sfiga" in questo ciclo resta tutto uguale. Poi passa a un nuovo pivot da scegliere nella parte sinistra dell'ultimo pivot scelto, e avendo solo due numeri alla fine sposta il 3 a destra, arrivando all'array 1,3,4,5,6,8,9....

[Dascos]

Ps: nel caso dell'esempio, le coppie che arrivano sono
3 - 2
5 - 2
3 - 5
5 - 6
6 - 1
5 - 1
3 - 1
2 - 1

:-)

[lucas726]

Il problema principalmente è dovuto al fatto che non sono un programmatore e mi diverto solo a mettere insieme qualcosa di semplice e utile alle mie modeste esigenze (lista clienti, gallerie ecc). Spesso mi ritocca imparare o riprendere le basi da capo visto che può passare molto tempo tra un progetto e l'altro, dimenticando così quasi tutto sul linguaggio.


In ragione di ciò scrivo solo codice "semplice" che posso capire subito anche a distanza di tempo. Qualche volta però, quando ho un po' più di tempo a disposizione, cerco di implementare le mie competenze provando ad usare codice più complesso e funzioni che possono velocizzare verosimilmente il lavoro.

Il codice di cui sopra era oggetto di un video di uno dei corsi e video sul php che si trovano in giro sul web, e per me quel passaggio era poco chiaro. In questi casi chiedo nei forum.


Per una funzione qualsiasi tipo:

function cmp($a, $b)
...

mi aspetto ingenuamente che vengano forniti chiaramente due parametri che possono essere variabili, array o altre funzioni.
In questo caso come primo parametro riuscivo ad indivifuare l'array $a, ma non il secondo parametro $b.

Pare quindi che tutto dipende dalla funzione usort e dal modo in cui funzionino le callback che forse ancora non mi sono chiare.
Ho copiato il codice in VScode e avviato poi il debug osservando come cambiavano i valori di $a e $b nella funzione "cmp", ma anche in questo caso mi sfugge il meccanismo.

Di solito quando non capisco come funzioni una cosa faccio a meno di usarla, mi sa che è uno di quei casi, magari non mi sarà mai utile.

Grazie in ogni caso per le spiegazioni

[lucas726]

Mi riaggancio anche alla risposta di KillerWorm.
In pratica, diciamo che tu hai questi valori nell'array: 3,6,1,8,4,9,5
Diciamo che li vuoi ordinare in modo ascendente e quindi definisci la tua funzione in uno dei due modi che hai portato di esempio.
Andiamo "dietro" alla funzione usort, che usa l'algoritmo QuickSort.
Più o meno succede così...l'algoritmo usort cerca un "pivot", cioè un valore iniziale da usare poi come "paragone" e, per semplicità, facciamo finta che vada a prendere il valore finale, cioè 5. Questo 5 è "a".
Ora l'algoritmo prende uno a uno tutti i valori a sinistra e li confronta a 5 in base alla tua funzione: alla funzione arriverà quindi la coppia 5-3. Siccome 3 è inferiore (perchè così stabilisce la tua funzione di confronto), viene lasciato lì dov'è.
Poi arriva la coppia 5-6. 6 è superiore, quindi viene posizionato a destra e, internamente, l'array è diventato 3,1,8,4,9,5,6
Poi arriva 5-1 e resta così com'è. Poi 5-8 e siccome 8 è maggiore finisce a destra, e l'array è 3,1,4,9,5,6,8. Poi arriva al 5-9 e trasforma l'array in 3,1,4,5,6,8,9.
Ora procedo a cercare un nuovo pivot e l'algoritmo sceglie il 4 e lavora sulla parte a sinistra del pivot originale (quindi sui numeri 3,1, e 4). Per "sfiga" in questo ciclo resta tutto uguale. Poi passa a un nuovo pivot da scegliere nella parte sinistra dell'ultimo pivot scelto, e avendo solo due numeri alla fine sposta il 3 a destra, arrivando all'array 1,3,4,5,6,8,9....

Qualcosa adesso penso di averla afferrata....spero.

Possiamo dire allora che è la funzione usort che fornisce sia il valore $a e $b prendendoli dall'array $a stesso? Poi a sua volta la funzione cmp fornisce una valore di ritorno

-1 : 1

oppure


return $a <=> $b;

utili alla funzione usort per mettere in ordine i valori dell'array progressivamente?
Poi, come si diceva sopra, a noi interessa poco cosa faccia e quale meccanismo utlizzi esattamente usort.

Ho azzeccato almeno qualcosa nel mio ragionamento?
Grazie

[Dascos]

No.
Nel senso....usort è una funzione standard di php che "fa qualcosa". Il come lo faccia, internamente, non ti deve interessare. Ti deve interessare "come usarla per raggiungere uno scopo" o, al contrario, "per raggiungere un certo scopo cosa devo usare".
Mettendo insieme le funzioni di Php (o qualsiasi altro linguaggio), partendo da dei dati devi ottenere dei risultati ma il come vengano fatte, internamente, certe cose non ti deve interessare. Non per programmare, almeno.
Diverso è se vuoi migliorare delle funzioni, ma in questo caso lavori sul codice sorgente di Php.

In pratica quindi, nel caso di esempio, non ti deve interessare come lavora dietro ma come lavora davanti, cioè che per ottenere quel risultato devi usare una funzione che faccia un "paragone" di qualche tipo al fine di ordinare due valori. Se i valori della funzione (l'array) sono più di due, la funzione eseguirà i confronti su tutti gli elementi in un certo modo (che non ti interessa) per ottenere un ordinamento come definito nella tua funzione.
Il "come" vuoi ordinare è una tua scelta e questa è la "potenza" delle callback.
Esistono infatti delle funzioni predefinite per ordinare un array ma a volte non sono adatte a ciò che serve a te e quindi si sono "inventati" le funzioni tipo usort, dove sei tu a dire come vanno fatte le cose

[Dascos]

Qualcosa adesso penso di averla afferrata....spero.

Possiamo dire allora che è la funzione usort che fornisce sia il valore $a e $b prendendoli dall'array $a stesso? Poi a sua volta la funzione cmp fornisce una valore di ritorno

-1 : 1

oppure


return $a <=> $b;

utili alla funzione usort per mettere in ordine i valori dell'array progressivamente?
Poi, come si diceva sopra, a noi interessa poco cosa faccia e quale meccanismo utlizzi esattamente usort.

Ho azzeccato almeno qualcosa nel mio ragionamento?
Grazie

Sì.
Diciamo che l'esempio è poco chiaro e tende a confondere.
Sarebbe stato meglio qualcosa di questo tipo

<?php
function cmp($a, $b)
{
    if ($a == $b) {
        return 0;
    }
    return ($a < $b) ? -1 : 1;
}


$arr = array(3, 2, 5, 6, 1);


usort($arr, "cmp");


foreach ($arr as $key => $value) {
    echo "$key: $value\n";
}
?>