Perché array_udiff usa una funzione di confronto invece di una funzione di predicato?

Question

array_udiff calcola la differenza tra due array utilizzando una funzione di callback. Tuttavia, richiede una funzione di confronto anziché una funzione di predicato.

Un confronta funzione confronta oggetto A rispetto al punto B. Una funzione predicato sarebbe solo determinare se elemento A è uguale al punto B.

Compare funzioni sono normalmente necessari per funzioni di ordinamento per determinare l'ordine corretto. Poiché array_udiff sta semplicemente calcolando le differenze, una funzione di predicato che determina se ciascuna coppia è uguale sembra che dovrebbe essere sufficiente.

Perché array_udiff utilizza una funzione di confronto anziché una funzione di predicato? Importa se utilizzo invece un predicato? Ad esempio, posso scegliere di utilizzare solo i valori di ritorno 0 e 1 per indicare la disuguaglianza e l'uguaglianza, scartando la possibilità -1? Quale effetto negativo, se del caso, avrebbe questo sui miei risultati?

Answer 1

L'implementazione per php_array_diff() (che fornisce l'implementazione per un numero di funzioni di matrice userspace) funziona riutilizzando un numero di funzioni di confronto interno.

Questo perché le funzioni di confronto esistono già per altri scopi e soddisfano l'attività richiesta: determinare se due elementi sono uguali o meno. Che facciano un piccolo lavoro in più non è importante; ciò che è importante è la riduzione relativa del codice che deve essere considerata. (Una funzione uguale potrebbe essere facilmente scritta in termini di funzione di confronto o come entità separata, ma ora hai due funzioni per svolgere lo stesso lavoro.)

L'implementazione effettiva funziona anche con sorting. Quindi è necessario utilizzare un algoritmo di confronto adatto per l'ordinamento, o otterrete risultati inaspettati. Per esempio:

$a = [0, 1, 2, 3, 4, 5, 6]; 
$b = [4]; 

print_r(array_udiff($a, $b, function($x, $y) { 
    return $x <=> $y; //Sorting comparison function, correct 
})); 

print_r(array_udiff($a, $b, function($x, $y) { 
    return $x != $y; // Equality test, incorrect 
})); 

dà

Array //Sorting comparison function, correct 
(
    [0] => 0 
    [1] => 1 
    [2] => 2 
    [3] => 3 
    [5] => 5 
    [6] => 6 
) 
Array // Equality test, incorrect 
(
    [0] => 0 
    [1] => 1 
    [2] => 2 
    [3] => 3 
    [4] => 4 // equality test causes udiff to incorrectly include 4 
    [5] => 5 
    [6] => 6 
) 

La ragione di questo è l'algoritmo di php_array_diff() utilizza. Fondamentalmente va in questo modo:

• duplicati e ordinare tutti gli array in input
• impostare l'uscita OUT uguale alla ordinato prima matrice di ingresso
• Per ogni elemento in SRC
  • V è il valore dell'elemento corrente in SRC
  • Per ogni array di input Un partire dalla seconda
    • passare al successivo elemento nella Un cioè>V, ma creare una nota se andiamo un passato che è == V.
    • Se abbiamo trovato una corrispondenza per V, rimuoverlo da OUT.
    • Se non (in modo che rimanga in array di input), passare in SRC finché abbiamo un nuovo V> = quella attuale

Così , l'algoritmo si basa su tutti gli input in fase di ordinamento e utilizza tale fatto (e la funzione di confronto), quindi deve solo ispezionare ogni elemento in ogni array di input una sola volta. Se la funzione di confronto non risulta in un array effettivamente ordinato, l'algoritmo fallisce e si ottiene un risultato negativo.

HHVM può causare un risultato diverso, poiché HHVM utilizza un algoritmo di ordinamento diverso. HHVM utilizza uno pure quicksort, mentre PHP utilizza uno quicksort implementation derived from llvm che include un'ottimizzazione dell'inserimento.

Normalmente, diversi algoritmi di ordinamento arrivano alla stessa soluzione con mezzi diversi. Cioè, algoritmi diversi causano la comparazione di elementi in un ordine diverso, in momenti diversi e in quantità diverse. Nel caso di una funzione di confronto errata, questo può avere un grande effetto sull'ordine finale dell'array.

Answer 2

Deve essere più economico integrare gli array ordinati. Senza l'ordinamento ci vorrà O (m * n) tempo.