Unione di 8 elenchi ordinati in C++, quale algoritmo dovrei usare

Question

Ho 8 elenchi ordinati che ho bisogno di unire in 1 elenco ordinato. Non conosco il modo migliore per farlo. Stavo pensando a quanto segue:

void merge_lists_inplace(list<int>& l1, const list<int>& l2) 
{ 
    list<int>::iterator end_it = l1.end(); 
    --end_it; 
    copy(l2.begin(), l2.end(), back_inserter(l1)); 
    ++end_it; 
    inplace_merge(l1.begin(), end_it, l1.end()); 
} 

list<int> merge_8_lists(list<int>[8] lists) 
{ 
    merge_lists_inplace(lists[0], lists[1]); 
    merge_lists_inplace(lists[2], lists[3]); 
    merge_lists_inplace(lists[4], lists[5]); 
    merge_lists_inplace(lists[6], lists[7]); 

    merge_lists_inplace(lists[0], lists[2]); 
    merge_lists_inplace(lists[4], lists[6]); 

    merge_lists_inplace(lists[0], lists[4]); 

    return lists[0]; 
} 

Ma sarebbe meglio preoccuparsi solo dell'ordinamento ultimo?

list<int> merge_8_lists(list<int>[8] lists) 
{ 
    for (int i = 1; i < 8; ++i) 
     copy(lists[i].begin(), lists[i].end(), back_inserter(lists[0]));   
    lists[0].sort(); 
    return lists[0]; 
} 

Nota a margine: non mi interessa che gli elenchi vengano modificati.

Answer 1

Una semplice estensione della fase di unione di merge sort può essere eseguita nel tempo O (n lg m) (dove n = numero totale di elementi e m = numero di elenchi), utilizzando (ad esempio, heap). Pseudocodice:

Let P = a priority queue of the sorted lists, sorted by the smallest element in each list 
Let O = an empty output list 
While P is not empty: 
    Let L = remove the minimum element from P 
    Remove the first element from L and add it to O 
    If L is not empty, add L to P 

e una semplice (non testata!) L'attuazione concreta in C++:

#include <list> 
#include <set> 

template<typename T> 
struct cmp_list { 
    bool operator()(const std::list<T> *a, const std::list<T> *b) const { 
     return a->front() < b->front(); 
    } 
}; 

template<typename T> 
void merge_sorted_lists(std::list<T> &output, std::list<std::list<T> > &input) 
{ 
    // Use a std::set as our priority queue. This has the same complexity analysis as 
    // a heap, but has a higher constant factor. 
    // Implementing a min-heap is left as an exercise for the reader, 
    // as is a non-mutating version 
    std::set<std::list<T> *, cmp_list<T> > pq; 

    for (typename std::list<std::list<T> >::iterator it = input.begin(); 
      it != input.end(); it++) 
    { 
     if (it->empty()) 
      continue; 
     pq.insert(&*it); 
    } 

    while (!pq.empty()) { 
     std::list<T> *p = *pq.begin(); 
     pq.erase(pq.begin()); 

     output.push_back(p->front()); 
     p->pop_front(); 

     if (!p->empty()) 
      pq.insert(p); 
    } 
} 

Answer 2

Si potrebbe provare l'applicazione del merge sort uno alla volta per ciascuna delle liste:

http://en.wikipedia.org/wiki/Merge_sort

questo ha l'algoritmo per il merge sort. In sostanza andresti con la lista 1 e 2 e unirmi per ordinarli. Quindi prendi la nuova lista combinata e ordina con la lista 3, e continua fino a quando non hai una lista completamente ordinata.

EDIT:

In realtà, perché le vostre liste sono già ordinati, sarebbero necessari solo l'ultima parte del merge sort. Vorrei combinare iterativamente le liste in parti sempre più grandi per tutto il tempo, ordinando ognuna di quelle liste più grandi fino a che non hai la tua lista completa, che è essenzialmente ciò che fa l'unire sort dopo averlo fatto con il suo approccio divide and conquer.

Answer 3

Se le prestazioni non è una preoccupazione, vorrei ordinare gli elenchi scorso. Il codice è più leggibile, più breve e meno probabilità di essere rovinato da qualcuno che rivisita il codice in futuro.

Answer 4

Questo è un ordinamento di unione standard (sebbene a 8 vie).

Fondamentalmente è "aperte" le otto liste ordinate poi iniziare a elaborare, estrarre il valore più basso ogni volta, qualcosa di simile:

# Open all lists. 

open newlist for write 
for i = 1 to 8: 
    open list(i) for read 
end for 

 

# Process forever (break inside loop). 

while true: 
    # Indicate that there's no lowest value. 

    smallidx = -1 

    # Find lowest value input list. 

    for i = 1 to 8: 
     # Ignore lists that are empty. 

     if not list(i).empty: 
      # Choose this input list if it's the first or smaller 
      # than the current smallest. 

      if smallidx = 1: 
       smallidx = i 
       smallval = list(i).peek() 
      else: 
       if list(i).peek() < smallval: 
        smallidx = i 
        smallval = list(i).peek() 
       end if 
      end if 
     end if 
    end for 

 

# No values left means stop processing. 

    if smallidx = -1: 
     exit while 
    end if 

    # Transfer smallest value then continue. 

    smallval = list(smallidx).get() 
    newlist.put(smallval) 
end while 

Answer 5

Fondamentalmente stai facendo parte del mergesort multiway, es CEPT la tua roba è già ordinato ...

http://lcm.csa.iisc.ernet.in/dsa/node211.html

Basta trovare il più basso in ogni matrice (quasi usare come stack) e che mettere in l'output fino a tutte le pile sono vuote ...

Answer 6

È voglio a merge sort. Le tue liste sono già divise, ma non fino al livello più basso.Si consiglia di fare questo:

unsorted_list = concatenate(list[0], list[1], list[2], ... , list[7]); 
sorted_list = merge_sort(unsorted_list); 

Questo non dovrebbe essere un consumo di memoria di funzionamento/tempo perché la concatenazione dovrebbe aggiungere un collegamento dal ultimo nodo in un elenco per il primo elemento della lista successiva.