Aplicações práticas do Radix Sort

20

A classificação Radix é teoricamente muito rápida quando você sabe que as teclas estão em um determinado intervalo limitado, digamos valores no intervalo por exemplo. Se você apenas converter os valores para a base de que leva tempo, fazer uma base radix sort e depois converter de volta para sua base original para um total algoritmo.n[0 0...nk-1]k<lgnnΘ(n)nΘ(nk)

No entanto, eu li que, na prática, a classificação do radical é geralmente muito mais lenta do que fazer, por exemplo, uma classificação rápida aleatória :

Para matrizes grandes, a classificação radix tem a menor contagem de instruções, mas devido ao seu desempenho de cache relativamente ruim, seu desempenho geral é pior que as versões otimizadas para memória do mergesort e quicksort.

Radix sort é apenas um bom algoritmo teórico ou tem usos práticos comuns?

Robert S. Barnes
fonte

Respostas:

15

As classificações Radix são, na prática, as classificações mais rápidas e úteis em máquinas paralelas.

Em cada nó do multiprocessador, você provavelmente faz algo como uma classificação rápida, mas a classificação radix permite que vários nós trabalhem juntos com menos sincronização do que os vários tipos recursivos.

Existem outras situações também. Se você precisar de uma classificação estável (uma classificação em que sempre que duas chaves forem iguais, elas permanecerão na mesma ordem, em vez de serem reorganizadas), não conheço nenhuma versão do quicksort que seja útil. O mergesort também é estável (se implementado corretamente). Seu link é a primeira vez que ouvi alguém dizer que o mergesort pode ser feito para ter um melhor comportamento de cache do que o tipo de raiz.

Lógica Errante
fonte
Patterson e Hennessy fazem o mesmo ponto que o artigo de Lamarca acima, em seu livro Computer Organization and Design.
Robert S. Barnes
Sua menção a Patterson me lembrou o importante trabalho que Andrea Arpaci-Dusseau realizou sobre a classificação de clusters há cerca de 15 anos. (Patterson foi co-autor). No artigo de 1997, eles realmente decidiram que o tipo de raio parcial era preferível à classificação rápida também nos nós individuais. (Adicionei as referências à resposta).
Wandering Logic
Isso é interessante. Na quarta edição de 2009 do CompOrg, eles referem que o trabalho de Lamarca em versões anteriores da classificação Radix não é amigável (pág. 489), mas, na página 490, em gráficos comparando a classificação Quicksort e Radix, eles dizem: "Devido a esses resultados, novas versões de Inventou-se o tipo Radix que leva em consideração a hierarquia de memória para recuperar suas vantagens algorítmicas ". Estou curioso para saber como essas novas versões do Radix Sort funcionam.
Robert S. Barnes
Minha suspeita é que Lamarca usou apenas uma classificação estúpida de radix (que mantém seus baldes como listas vinculadas). Ninguém jamais faria isso. Você implementaria os buckets usando algum tipo de matriz dinâmica otimizada (por exemplo, como um C ++ vector). Mas não sei, porque não li os papéis de Lamarca.
Wandering Logic
@WanderingLogic, onde a classificação radix usa baldes? Você quer dizer balde aqui?
Bar
3

@ Robert: Seu link é bastante surpreendente (na verdade eu não consegui encontrar a frase citada). Minha experiência pessoal é de entrada aleatória, a classificação do radical é muito mais rápida que a STL std::sort(), que usa uma variante do quicksort. Eu costumava fazer um algoritmo 50% mais rápido substituindo-o std::sort()por uma classificação de raiz instável. Não sei ao certo qual é a "versão otimizada para memória" do quicksort, mas duvido que possa ser duas vezes mais rápido que a versão STL.

Esta postagem no blog avaliou a classificação do radical juntamente com vários outros algoritmos de classificação. Resumidamente, nesta avaliação, são std::sort()necessários 5,1 segundos para classificar 50 milhões de números inteiros, enquanto a classificação de raiz no local / instável leva 2,0 segundos. A classificação estável do radical deve ser ainda mais rápida.

A classificação Radix também é amplamente usada para classificar cordas de maneira estável. Às vezes, variantes de classificação de raiz são vistas para a construção de matrizes de sufixos, BWT etc.

user172818
fonte