Fusionando 8 listas ordenadas en C++, que algoritmo debería usar

Question

Tengo 8 listas ordenadas que necesito fusionar en 1 lista ordenada. No sé la mejor manera de hacer esto. Estaba pensando en lo siguiente:

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]; 
} 

Pero, ¿sería mejor simplemente preocuparse por la última clasificación?

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 al margen: No me importa que las listas se hayan modificado.

Answer 1

Una simple extensión de la fase de combinación de mezcla de tipo puede hacer esto en O (n lg m) tiempo (donde n = número total de elementos y m = número de listas), utilizando un priority queue (por ejemplo, un heap). Pseudocódigo:

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 

y un simple (no probado!) La aplicación concreta en 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

usted podría intentar aplicar el ordenamiento por mezcla de uno en uno a cada una de las listas:

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

Esto tiene el algoritmo para la combinación de tipo. Básicamente irías con la lista 1 y 2 y combinarlas. Luego tomarías esa nueva lista combinada y ordenarías con la lista 3, y esto continuará hasta que tengas una lista completamente ordenada.

EDIT:

En realidad, debido a sus listas ya están ordenados, se necesitarían sólo la última parte de la fusión de clasificación. Combinaría iterativamente las listas en partes más grandes y más grandes al mismo tiempo ordenando cada una de esas listas más grandes hasta que tenga su lista completa, que es esencialmente lo que hace el tipo de fusión después de que se hace con su enfoque de divide y vencerás.

Answer 3

Si el rendimiento no es una preocupación, me gustaría ordenar las listas pasado. El código es más legible, más corto y menos propenso a ser arruinado por alguien que vuelva a visitar el código en el futuro.

Answer 4

Este es un tipo de combinación estándar (aunque de 8 vías).

Básicamente "abiertas" las ocho listas ordenadas a continuación, iniciar la tramitación de ellos, extraer el valor más bajo cada vez, algo así como:

# 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

Básicamente estás haciendo parte de multwayway mergesort, ex CEPT su materia ya está ordenada ...

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

acaba de encontrar las más bajas de cada matriz (casi usar como pilas) y puesto que en su salida hasta que todas las pilas están vacías ...

Answer 6

Usted quiere a merge sort. Sus listas ya están divididas, pero no del todo hasta el nivel más pequeño.Es posible que desee hacer esto:

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

que no debe ser una operación de tiempo/consumo de memoria debido a la concatenación debe agregar un enlace desde el último nodo en una lista en el primer elemento de la lista siguiente.