Por que o Radix Sort não é usado com mais frequência?

É estável e tem uma complexidade de tempo de O (n). Deve ser mais rápido que algoritmos como o Quicksort e o Mergesort, mas quase nunca o vejo sendo usado.

Diferentemente da classificação radix, o quicksort é universal, enquanto a classificação radix é útil apenas para chaves inteiras de comprimento fixo.

Você também precisa entender que O (f (n)) realmente significa em ordem de K * f (n), onde K é uma constante arbitrária. Para classificação de raiz, esse K é bastante grande (pelo menos, a ordem do número de bits nos números inteiros classificados), por outro lado, o quicksort possui um dos K ​​mais baixos entre todos os algoritmos de classificação e complexidade média de n * log (n). Assim, no cenário da vida real, o quicksort será muitas vezes mais rápido que o tipo radix.

A maioria dos algoritmos de classificação é de uso geral. Dada uma função de comparação, eles funcionam em qualquer coisa, e algoritmos como Quicksort e Heapsort classificam com O (1) memória extra.

A classificação Radix é mais especializada. Você precisa de uma chave específica que esteja em ordem lexicográfica. Você precisa de um balde para cada símbolo possível na chave, e os baldes precisam manter muitos registros. (Como alternativa, você precisa de uma grande variedade de buckets que armazenam todos os valores-chave possíveis.) É provável que você exija muito mais memória para fazer a classificação de radix, e você a usará aleatoriamente. Nada disso é bom para computadores modernos, pois é provável que você tenha falhas de página como o Quicksort terá falhas de cache.

Finalmente, as pessoas geralmente não escrevem mais seus próprios algoritmos de classificação. A maioria dos idiomas possui recursos de biblioteca para classificar, e a coisa certa a fazer é normalmente usá-los. Como a classificação radix não é universalmente aplicável, geralmente precisa ser adaptada ao uso real e usa muita memória extra, é difícil colocá-la em uma função ou modelo de biblioteca.

É muito raro que as chaves pelas quais você classifique sejam realmente números inteiros em um intervalo conhecido e escasso. Geralmente, você tem campos alfabéticos, que parecem oferecer suporte a classificação não comparativa, mas como as seqüências do mundo real não são distribuídas uniformemente pelo alfabeto, isso não funciona tão bem quanto deveria em teoria.

Outras vezes, o critério é definido apenas operacionalmente (dados dois registros, você pode decidir o que vem primeiro, mas não é possível avaliar até que ponto um nível isolado da escala é um registro isolado). Portanto, o método geralmente não é aplicável, menos aplicável do que você imagina, ou apenas não mais rápido que O (n * log (n)).

Eu o uso o tempo todo, na verdade mais do que tipos baseados em comparação, mas sou reconhecidamente um excêntrico que trabalha mais com números do que qualquer outra coisa (quase nunca trabalho com cordas, e elas geralmente são internadas nesse caso, nesse ponto a classificação pode ser útil novamente para filtrar duplicatas e calcular interseções de conjuntos; eu praticamente nunca faço comparações lexicográficas).

Um exemplo básico são os pontos de classificação de base por uma determinada dimensão, como parte de uma pesquisa ou divisão mediana ou uma maneira rápida de detectar pontos coincidentes, fragmentos de classificação em profundidade ou classificação de uma matriz de índices usados ​​em vários loops para fornecer um acesso mais fácil ao cache padrões (não indo e voltando na memória apenas para voltar e recarregar a mesma memória em uma linha de cache). Há um aplicativo muito amplo, pelo menos no meu domínio (computação gráfica), apenas para classificação em chaves numéricas de tamanho fixo de 32 e 64 bits.

Uma coisa que eu queria dizer é que o tipo de raiz pode funcionar com números de ponto flutuante e negativos, embora seja difícil escrever uma versão FP o mais portátil possível. Além disso, embora seja O (n * K), K apenas deve ser o número de bytes do tamanho da chave (por exemplo: um milhão de inteiros de 32 bits geralmente leva 4 passos do tamanho de byte se houver 2 ^ 8 entradas no bucket ) O padrão de acesso à memória também tende a ser muito mais amigável ao cache do que o quicksort, embora precise de uma matriz paralela e uma matriz de bucket pequena normalmente (a segunda geralmente pode se encaixar perfeitamente na pilha). O QS pode fazer 50 milhões de swaps para classificar uma matriz de um milhão de números inteiros com padrões de acesso aleatório esporádicos. A classificação radix pode fazer isso em 4 passagens lineares e amigáveis ​​ao cache sobre os dados.

No entanto, a falta de consciência de poder fazer isso com um K pequeno, em números negativos junto com ponto flutuante, pode muito bem contribuir significativamente para a falta de popularidade dos tipos de raiz.

Quanto à minha opinião sobre por que as pessoas não o usam com mais frequência, isso pode ter a ver com muitos domínios que geralmente não precisam classificar números ou usá-los como chaves de pesquisa. No entanto, apenas com base na minha experiência pessoal, muitos dos meus ex-colegas também não o usaram nos casos em que era perfeitamente adequado, e em parte porque não sabiam que isso poderia ser feito para trabalhar com PF e negativos. Portanto, além de trabalhar apenas com tipos numéricos, geralmente é ainda menos aplicável do que realmente é. Eu também não teria tanta utilidade se pensasse que não funcionava em números de ponto flutuante e números inteiros negativos.

Alguns benchmarks:

Sorting 10000000 elements 3 times...

mt_sort_int: {0.135 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

mt_radix_sort: {0.228 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

std::sort: {1.697 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

qsort: {2.610 secs}
-- small result: [ 12 17 17 22 52 55 67 73 75 87 ]

E isso é apenas com minha implementação ingênua ( mt_sort_inttambém é uma classificação de radix, mas com um ramo de código mais rápido, já que ele pode assumir que a chave é um número inteiro). Imagine a rapidez com que uma implementação padrão escrita por especialistas pode ser.

O único caso em que achei que a classificação radix se saiu pior do que a comparação muito rápida do C ++ std::sortfoi para um número muito pequeno de elementos, digamos 32, quando acredito que std::sortcomeça a usar classificações mais adequadas para o menor número de elementos, como heapsorts ou tipos de inserção, embora nesse momento minha implementação apenas use std::sort.

Mais um motivo: atualmente, a classificação é implementada com uma rotina de classificação fornecida pelo usuário, anexada à lógica de classificação fornecida pelo compilador. Com uma classificação radix, isso seria consideravelmente mais complexo e fica ainda pior quando a rotina de classificação atua sobre várias chaves de comprimento variável. (Diga, nome e data de nascimento.)

No mundo real, eu realmente implementei uma classificação radix uma vez. Nos velhos tempos, quando a memória era limitada, não conseguia trazer todos os meus dados para a memória de uma só vez. Isso significava que o número de acessos aos dados era muito mais importante que O (n) vs O (n log n). Fiz uma passagem pelos dados alocando cada registro em uma lixeira (por uma lista de quais registros estavam em lixeiras, sem mover nada de verdade.) Para cada lixeira não vazia (minha chave de classificação era texto, haveria muito caixas vazias) Verifiquei se realmente conseguia trazer os dados para a memória - se sim, traga-os e use o quicksort. Se não, crie um arquivo temporário contendo apenas os itens na bandeja e chame a rotina recursivamente. (Na prática, alguns compartimentos estourariam.) Isso causou duas leituras completas e uma gravação completa no armazenamento em rede e algo como 10% disso no armazenamento local.

Hoje em dia, essas questões de big data são muito mais difíceis de encontrar, provavelmente nunca mais escreverei algo assim. (Se hoje eu tivesse os mesmos dados, simplesmente especificaria o SO de 64 bits, adicione RAM se você se debater nesse editor.)

Se todos os seus parâmetros forem inteiros e se você tiver mais de 1024 parâmetros de entrada, a classificação do radical será sempre mais rápida.

Por quê?

Complexity of radix sort = max number of digits x number of input parameters.

Complexity of quick sort = log(number of input parameters) x   number of input parameters

Portanto, a classificação do radical é mais rápida quando

log(n)> max num of digits

O número máximo máximo em Java é 2147483647. Com 10 dígitos

Portanto, a classificação do radical é sempre mais rápida quando

log(n)> 10

Portanto, a classificação do radical é sempre mais rápida quando n>1024