Algoritmo per unire due array ordinati con un numero minimo di confronti

Question

Algoritmo per unire due array ordinati con un numero minimo di confronti

#1 da (30 voti)
#2 da (1 voti)

24

Sono presenti due array ordinati a , b di tipo T con dimensioni n e m . Sto cercando un algoritmo che unisce i due array in un nuovo array (di dimensione massima n + m).

Se si dispone di un'operazione di confronto a basso costo, questo è piuttosto semplice. Prendi dall'array il primo elemento più in basso fino a quando uno o entrambi gli array sono completamente attraversati, quindi aggiungi gli elementi rimanenti. Qualcosa come questo link

Tuttavia, la situazione cambia quando il confronto di due elementi è molto più costoso della copia di un elemento dall'array di origine all'array di destinazione . Ad esempio, potresti avere una matrice di numeri interi o stringhe di precisione arbitraria di grandi dimensioni, in cui un confronto può essere piuttosto costoso. Supponiamo che la creazione di array e gli elementi di copia siano gratuiti, e l'unica cosa che costa è il confronto degli elementi.

In questo caso, vuoi unire i due array con un numero minimo di confronti tra elementi . Ecco alcuni esempi in cui dovresti essere in grado di fare molto meglio del semplice algoritmo di fusione:

a = [1,2,3,4, ... 1000]
b = [1001,1002,1003,1004, ... 2000]

o

a = [1,2,3,4, ... 1000]
b = [0,100,200, ... 1000]

Ci sono alcuni casi in cui l'algoritmo di fusione semplice sarà ottimale, come

a = [1,3,5,7,9,....,999]
b = [2,4,6,8,10,....,1000]

Quindi l'algoritmo dovrebbe idealmente degradarsi ed eseguire un massimo di confronti n + m-1 nel caso in cui gli array siano intercalati, o almeno non peggiori significativamente.

Una cosa che dovrebbe fare abbastanza bene per gli elenchi con una differenza di grandi dimensioni sarebbe quella di utilizzare la ricerca binaria per inserire gli elementi dell'array più piccolo nell'array più grande. Ma questo non si degraderà con grazia nel caso in cui entrambi gli elenchi siano della stessa dimensione e interlacciati.

L'unica cosa disponibile per gli elementi è una (totale) funzione di ordinamento, quindi qualsiasi schema che rende i confronti più economici non è possibile.

Qualche idea?

Ho trovato questo bit in Scala . Credo che sia ottimale per quanto riguarda il numero di confronti, ma è oltre la mia capacità di dimostrarlo. Almeno è molto più semplice di quanto ho trovato in letteratura.

E dal post originale, ho scritto un post sul blog su come funziona.

algorithms comparison big-o

posta Rüdiger Klaehn 26.12.2014 - 13:15

fonte

2 risposte

1

Supponiamo che i due array abbiano elementi N e M, N ≥ M, e che tutti gli elementi siano diversi.

Se la matrice ordinata contiene un elemento x di N seguito da un elemento y di M o viceversa, x e y devono essere stati confrontati, altrimenti non sapremmo in quale ordine appartengono. (Non può esserci una catena di altri elementi dire a, b, c dove sappiamo che x < a < b < c < y, ad esempio, perché non ci sono elementi tra x e y. Quindi x e y deve essere stato confrontato direttamente.

Se N > M allora è possibile avere un array in cui ogni elemento di M è sia preceduto sia seguito da un elemento di N, il che significa che sono necessari almeno 2M confronti - anche se si utilizza un algoritmo di ordinamento non deterministico che può fare un'ipotesi perfetta quali numeri confrontare. (Cosa significa: supponiamo che tu abbia N grande, M = 1. La ricerca binaria richiede passi O (log2 N), un algoritmo non deterministico indovina tra quali due elementi appartiene l'elemento del secondo array e fai due confronti con conferma l'ipotesi).

risposta data 05.01.2016 - 18:06

fonte

Leggi altre domande sui tag algorithms comparison big-o

Abbiamo una grande applicazione Ruby on Rails (25 milioni di utenti mensili), la nostra gestione ha deciso di riscrivere in Node.js, sono pazzo? Come può una persona non tecnica imparare a scrivere una specifica per piccoli progetti?

score 30 · Accepted Answer

L'algoritmo di ordinamento di tipo merge normale - passo di unione con confronti normalmente n + m -1, dove una lista ha dimensione n e l'altra lista di dimensione m. L'utilizzo di questo algoritmo è l'approccio più semplice per combinare due elenchi ordinati.

Se i confronti sono troppo costosi potresti fare due cose: o minimizzi il numero di confronti o minimizzi il costo dei confronti.

Concentriamoci sulla minimizzazione del costo del confronto. Tu e solo tu puoi decidere se i dati che stai confrontando possono essere quantizzati o meno. Se puoi quantizzarli, che è una forma di implementazione di un metodo hash, che sta mantenendo l'ordine. Per esempio. se i tuoi dati vengono confrontati per nome, allora il primo tname, ... puoi prendere il primo in caratteri del nome "Klaehn, Ruediger" e ridurre / quantizzare il tuo elemento di dati in "Kl.Ru", se lo paragoni a "Packer, The" si salva l'ordine "Pa.Th" - ora è possibile applicare un algoritmo di confronto più economico, confrontando i valori ridotti. Ma se trovi un altro "Kl.Ru", ora hai un valore prossimo e potresti ora passare a un approccio più costoso confrontando questi elementi.

Se puoi estrarre questo valore quantizzato dai tuoi dati, più veloce che confrontarlo, questa è la prima cosa che fai, confronti prima il valore quantizzato o con l'hash. Tieni presente che questo valore deve essere calcolato una sola volta, quindi puoi calcolarlo sulla creazione dell'elemento dati.

Ho anche menzionato un altro modo, per ridurre al minimo i tuoi confronti.

Ho dato un'occhiata al classico libro TAOCP- Volume 3-Ordinamento e ricerca, (pp.197-207, sezione 5.3.2) che ha 10 pagine complete su questo argomento. Ho trovato due riferimenti ad algoritmi che sono più veloci dei confronti con n + m-1.

Prima c'è l'algoritmo di fusione Hwang-Lin e il secondo un miglioramento di Glenn K Manacher - entrambi sono citati da TAOCP e un algoritmo di Christen, che si avvicina al limite inferiore dei confronti necessari, a condizioni speciali sulla lunghezza n e m degli elenchi.

L'algoritmo di Manacher è stato presentato nel Journal of the ACM Vol. 26 Numero 3, pagine 434-440: "Miglioramenti significativi all '" Algoritmo di fusione "di Hwan-Lin". la lista con m elementi e la lista con n elementi possono essere di lunghezza diversa, ma devono anche essere odered dal numero di elementi che contengono m < = n

L'algoritmo di Hwang-Lin rompe gli elenchi per fondersi, a parte liste più piccole e ordina le liste confrontando il primo elemento di ciascuna sottolista e per decidere se alcuni elementi nella sottolista devono essere confrontati o meno. Se la prima lista è più piccola della seconda lista, allora la possibilità è alta, che gli elementi consecutivi della lista più lunga possono essere trasferiti nella lista risultante senza confronto. Se il primo elemento dell'ist piccolo è maggiore del primo elemento dell'elenco più grande suddiviso, tutti gli elementi davanti a Sottolista possono essere copiati senza confronto.

Analisi del caso medio dell'algoritmo di fusione di Hwang e Lin (Vega, Frieze, Santha) nella Sezione 2 puoi trovare uno pseudocodice dell'algoritmo HL. Che è molto meglio della mia descrizione E puoi capire perché ci sono meno confronti - l'algoritmo usa una ricerca binaria, per trovare l'indice, dove inserire l'elemento dalla lista più corta.

Se gli elenchi non sono interlacciati come nel tuo ultimo esempio, nella maggior parte dei casi dovresti avere un elenco più piccolo e rimanente. Questo è quando l'algoritmo HL inizia a funzionare meglio.