Molti algoritmi funzionano utilizzando lo merge algorithm per unire due diversi array ordinati in un singolo array ordinato. Ad esempio, dato in ingresso gli arrayUn algoritmo di fusione adattivo alla memoria?
1 3 4 5 8
e
2 6 7 9
La fusione di queste matrici sarebbe matrice
1 2 3 4 5 6 7 8 9
Tradizionalmente, sembra che ci siano due diversi approcci alla fusione array ordinati (si noti che il caso di unire liste collegate è abbastanza diverso). Innanzitutto, esistono algoritmi di merge fuori posto che funzionano allocando un buffer temporaneo per l'archiviazione, quindi memorizzando il risultato dell'unione nel buffer temporaneo. In secondo luogo, se i due array sono parte dello stesso array di input, ci sono in-place merge algorithms che utilizzano solo lo spazio di memoria ausiliaria O (1) e riorganizzano le due sequenze contigue in una sequenza ordinata. Queste due classi di algoritmi vengono eseguite entrambe in tempo O (n), ma l'algoritmo di fusione fuori luogo tende ad avere un fattore costante molto più basso perché non ha requisiti di memoria così stringenti.
La mia domanda è se esiste un algoritmo di fusione noto che può "interpolare" tra questi due approcci. Cioè, l'algoritmo userebbe da qualche parte tra la memoria O (1) e O (n), ma più memoria ha a disposizione, più veloce è la sua esecuzione. Ad esempio, se dovessimo misurare il numero assoluto di letture/scritture di array eseguite dall'algoritmo, potrebbe avere un runtime del modulo ng (s) + f (s), dove s è la quantità di spazio disponibile ad esso e g (s) e f (s) sono funzioni derivabili da quella quantità di spazio disponibile. Il vantaggio di questa funzione è che potrebbe provare a unire due array nel modo più efficiente possibile, dati i vincoli di memoria: più memoria è disponibile sul sistema, più memoria si userà e (idealmente) migliore sarà la performance che avrebbe .
Più formalmente, l'algoritmo dovrebbe funzionare come segue. Dato come input un array A costituito da due intervalli adiacenti, ordinati, riorganizzare gli elementi nella matrice in modo che gli elementi siano completamente ordinati. L'algoritmo può utilizzare lo spazio esterno e le sue prestazioni dovrebbero essere nel caso peggiore O (n) in tutti i casi, ma dovrebbero essere eseguite progressivamente più rapidamente, data una maggiore quantità di spazio ausiliario da utilizzare.
È chiunque abbia familiarità con un algoritmo di questo tipo (o sa dove guardare per trovare una descrizione di uno?)
http://stackoverflow.com/questions/3156599/merge-two-sorted-parts-of-an-array-with-constant-memory-in-time-time – necromancer
@ agksmehx- Grazie per il collegamento. Tuttavia, non penso che questo sia esattamente quello che sto cercando.Sono già consapevole del fatto che è possibile unire O (1) spazio extra, e questa domanda è principalmente la domanda se c'è un modo per avere un algoritmo di fusione che migliora progressivamente più spazio libero gli dai, in modo che se puoi ottieni, ad esempio, 100 MB di spazio aggiuntivo per 500 MB di dati, ti uniresti più velocemente rispetto a 10 MB per 500 MB di dati. – templatetypedef
Quali sono gli ingressi e le uscite? Ad esempio, stai scrivendo in uno degli array di input o in un array separato? (Sospetto il primo, poiché se è il secondo, questo non è un problema.) – MSN