E mais sobre as sortes

Atrevo-me a levantar esse tópico novamente. Começarei com um link para um artigo de Mikhail Opanasenko (oms7) , que é muito impressionante em termos de quantidade de trabalho realizado, bem como no número de links citados. Ele começou a preparar seu material, sem conhecer esta publicação, que posteriormente, após a familiarização, levou à necessidade de seu processamento substancial. Para quem já leu este artigo, informo que, no meu material, são estudados tipos mais diversos de dados, em particular cadeias de caracteres e números reais, as bibliotecas boost e bsd, e são mencionados alguns outros tópicos ausentes do artigo.

Existem dezenas de maneiras diferentes de organizar os itens de dados em ordem. Entre eles, existem aqueles que trabalham rápido, como, por exemplo, eles podem classificar qualquer matriz de dados localizada na RAM do computador em no máximo minutos. Mais especificamente, pode-se dizer que a classificação rápida organiza um bilhão de números inteiros em um bom computador pessoal moderno em menos de cem segundos. Se você usar métodos lentos e primitivos, por exemplo, classificação de bolhas ou classificação, para classificar um número maior de elementos, o tempo gasto nesse processamento de dados poderá exceder qualquer expectativa - esse "processamento" pode levar vários dias, semanas e até anos. Essa grande diferença é causada pelo fato de o tempo de classificação por métodos rápidos levar aproximadamente proporcional a N log N e primitivo - N ² . Com o aumento de N, a diferença entre os dois valores se torna muito perceptível. Portanto, é razoável usar métodos primitivos apenas para trabalhar com dados pequenos, por exemplo, em computadores modernos, com vários milhares de elementos. Também é natural usá-los para ensinar os conceitos básicos de programação e pensamento lógico, uma vez que são muito mais simples que os métodos rápidos.

Gostaria de entender os métodos de classificação existentes nas bibliotecas padrão atuais. Descubra quão grande é a diferença entre eles em termos de suas principais características, velocidade do trabalho e também seus recursos. Além disso, consideraremos ao longo do caminho para comparação e exercícios para a mente alguns métodos que não são difíceis de implementar. Também é importante notar que o otimizador do compilador GCC e possivelmente outros bons compiladores funcionam muito bem, acelerando o código várias vezes (às vezes até mais de 5 vezes).

Vamos começar com o método de classificação de bolhas como o mais simples e o mais lento. De acordo com esse método, você precisa percorrer a matriz de dados repetidamente, comparando elementos vizinhos e alterando seus lugares se a ordem entre eles for quebrada. Após cada passagem, pelo menos um elemento (o maior ou o menor - depende da ordem selecionada) está em seu lugar. Além da simplicidade, esse método possui mais uma vantagem: não requer memória adicional. É possível observar mais um recurso do método da bolha - ele processa muito rapidamente os dados já solicitados e, em alguns casos, o torna um dos métodos mais rápidos. Se os dados forem solicitados apenas parcialmente, esse método funcionará com eles mais rapidamente, mas na maioria dos casos apenas muito levemente. Para testes, usei a seguinte implementação .

Outro método lento é a classificação por seleção. Aqui, em cada passagem, os elementos maiores e menores dos dados são encontrados primeiro e, em seguida, esses elementos são colocados nas posições extremas correspondentes à ordem selecionada. Na próxima passagem, classificamos os dados sem esses elementos extremos. Esse método é tão simples quanto a classificação de bolhas e também não requer memória adicional, mas é visivelmente mais rápido. Além disso, a classificação por esse método realiza um número mínimo de permutações de elementos de dados. Portanto, quando as permutações são muito mais lentas que as comparações, a ordenação pelo método de seleção pode ser aceitável se o número de elementos de dados for pequeno. Aqui está a minha implementação . Com mais freqüência, essa classificação é realizada, colocando apenas um elemento por passagem. A classificação de pilha (ou piramidal), que será discutida mais adiante, é a versão mais avançada da classificação em questão.

O código do último método considerado lento, a classificação por inserção, é provavelmente o menor de todos os códigos que implementam a classificação; portanto, esse método às vezes é usado por classificações rápidas complexas para casos em que o número de itens a serem classificados é pequeno (várias dezenas). É um pouco semelhante à classificação por uma bolha, pois aqui e ali os elementos vizinhos são comparados sucessivamente. Mas a classificação por inserções procura o próximo elemento para a posição correta na parte já classificada dos dados, e não apenas empurra o elemento extremo para a posição extrema. Com essa abordagem, também não é necessária memória adicional. Como a classificação por bolhas, a classificação por inserção é muito rápida nos dados solicitados e mais rápida nos dados parcialmente solicitados. Neste último caso, significativamente mais rápido que a bolha. Normalmente, a classificação por inserções é um pouco mais rápida que a seleção por seleção. E, ao contrário do último, ele, como a classificação de bolhas, é estável. O pior de tudo é que a classificação por inserção funciona com os dados na ordem inversa, com a qual às vezes se torna o mais lento e o mais lento. Para testes, a seguinte implementação foi usada. Pode ser acelerado um pouco se você usar a pesquisa não linear, mas a binária, por exemplo, usando a função std :: bsearch. Uma aceleração significativa pode ser alcançada usando uma estrutura de tipo de lista, a inserção de um elemento no qual é muito rápido. Você também pode perceber que essa é a classificação mais natural - por exemplo, geralmente é usada intuitivamente ao jogar cartas.

A classificação de shell é a mais simples dentre os métodos rápidos e é bastante adequada para os alunos que estão começando a aprender programação. É apenas uma modificação da classificação das bolhas. A única diferença entre eles é que, na classificação de Shell, a distância entre os elementos comparados é tomada variando de passagem para passagem, de maior na primeira passagem, a 1 na última, assim, nessas últimas passagens, o método Shell degenera em uma classificação primitiva por uma bolha. Donald Shell publicou o algoritmo básico de classificação que recebeu esse nome em 1959. Portanto, essa é uma das primeiras classificações universais que funcionam rapidamente. Para comparação, o algoritmo de classificação rápida foi publicado dois anos depois, e a classificação popular de Tim ou classificação introspectiva ficou conhecida apenas nos anos 90. Vários problemas matemáticos interessantes não resolvidos estão associados à classificação do Shell, o principal deles é como selecionar de maneira otimizada os deslocamentos entre os elementos comparados. Algumas seqüências de registros foram encontradas, por exemplo, A102549 . Essas seqüências são encontradas através de cálculos colossais, portanto, possuem um comprimento muito curto; o A102549 possui apenas 8 elementos, o que é suficiente apenas para dados de até 3.000 elementos. Para big data, as sequências precisam ser vistas quase aleatoriamente. Valores usados ​​próximos às potências de 2, e , 2,25 e 3. Os números primos próximos às potências de 2 apresentaram os piores resultados, visivelmente inferiores aos melhores. Mas as outras três opções foram aproximadamente as mesmas em termos de impacto no desempenho e provavelmente muito próximas do ideal. Além disso, nesses três casos, o uso de números primos não deu vantagens tangíveis. É curioso que os vieses propostos na Wikipedia (com base em 2,25) baseados em referências aos trabalhos correspondentes não tenham apresentado os melhores resultados nos testes, embora suas diferenças em relação aos melhores tenham sido muito insignificantes (não mais que 5-10%). Usar o A102549 como ponto de partida também não deu nenhum resultado perceptível. Mikhail Opanasenko também tentou desvendar a classificação da Shell e obteve um resultado interessante de que os deslocamentos selecionados pela fórmula s _{n + 1} = 10s _n / 3 produzem um efeito muito bom e talvez até próximo do ideal. Meus resultados confirmam isso. Em muitos casos, foram esses vieses que deram o melhor resultado, embora esse nem sempre tenha sido o caso e a diferença do resultado mais próximo foi bastante pequena (cerca de 5%). Meu código para implementar as classificações do Shell usa pequenas tabelas com deslocamentos, embora se você não usar números primos, esses deslocamentos para tabelas podem ser calculados quase instantaneamente, como foi feito na implementação de uma das variantes fornecidas dessa classificação.

É interessante que, se tirarmos as compensações próximas às potências dos triplos de uma maneira um pouco diferente e usarmos um algoritmo ligeiramente diferente (ver implementação ), em números de 32 bits obteremos velocidades próximas das melhores, mas em números mais longos e nas linhas obteremos uma desaceleração significativa, às vezes mais de 100%. Os resultados para o melhor algoritmo usado por oms7 também estão na tabela abaixo, mas, embora mostre bons resultados em ordem, fica significativamente atrás dos líderes em termos de valores absolutos.

Alguma vez haverá uma maneira de encontrar as melhores compensações? Talvez, mas ouso sugerir que não é tão cedo. A classificação de shell é usada no kernel do Linux e, em pelo menos uma biblioteca C, seu código é usado para a função qsort () padrão. Foi teoricamente provado que a velocidade ideal de classificação da Shell é apenas um pouco mais lenta que os métodos logarítmicos rápidos "reais". De fato, a dependência do tempo médio de processamento de dados em seu tamanho para a classificação ideal de Shell é descrita pela fórmula ∽ N (log N / log log N ) ² , que mesmo para N muito grande é muito próxima da fórmula ∽ N log N típica para outros métodos rápidos. Geralmente, a classificação do shell geralmente é ainda mais rápida do que os métodos teoricamente mais rápidos e só começa a render um pouco para eles ao processar matrizes bastante grandes (da ordem de 10 milhões de elementos). Essa classificação absolutamente não precisa de memória adicional e se comporta de maneira estável para uma ampla variedade de opções para o preenchimento de dados, comparando favoravelmente com as classificações rápidas. O método Shell não possui a propriedade de estabilidade.

A classificação rápida é apenas um pouco mais complexa que o algoritmo Shell e ainda é a maneira mais rápida de organizar dados dispersos aleatoriamente. No entanto, essa classificação tem várias desvantagens. Ela precisa de memória adicional e, em casos muito raros, funciona extremamente devagar, de acordo com uma dependência quadrática. A idéia principal desse método é dividir os dados em duas partes: os dados em uma parte devem ser mais ou menos (depende da ordem selecionada) do que na outra. Existem vários métodos para essa separação. Idealmente, com cada divisão, ambas as partes devem ter aproximadamente o mesmo tamanho e, o pior de tudo, quando uma das partes acaba por ser composta por apenas um elemento durante a divisão. Vamos considerar várias implementações de algoritmos de classificação rápida, em particular o método Hoar , no qual um elemento de referência que divide os dados em duas partes é selecionado no meio dos dados classificados.

Também consideramos o algoritmo Lomuto extremamente compacto, que às vezes é ligeiramente (cerca de 1%) mais rápido do que o método Hoare considerado. No entanto, em casos especiais típicos, por exemplo, em dados ordenados, inversos ou malovariantes, o método Lomuto mostra lentidão extrema. Além disso, entre as opções consideradas para a classificação rápida, essa foi a mais gananciosa para o tamanho da pilha durante execuções práticas: ao classificar matrizes relativamente pequenas, apenas essa classificação não tinha 8 megabytes suficientes para a pilha, tive que definir esse tamanho com ulimite mais. Essa ganância pela pilha leva a grandes lentidões ao processar grandes dados (dezenas de milhões de linhas), e estou tendo dificuldade em chamar sua natureza. Só posso afirmar que é melhor não usar essa classificação do próximo parágrafo com esses dados.

O método Lomuto seleciona o último elemento como o de referência, mas é possível implementar a classificação rápida sem nenhum elemento de suporte , mais precisamente, a seleção de um desses elementos aqui ocorre como resultado da bissecção de dados já realizada. Essa classificação por características de velocidade mostrou-se próxima ao método Lomuto, embora geralmente seja um pouco mais rápido e, em casos extremos, é visivelmente mais rápida que Lomuto, mas mais lenta que Hoar.

Em 2009, um algoritmo de classificação rápida de duas âncoras foi publicado, que se tornou padrão para a linguagem Java. Esse algoritmo reduz o número de permutações em 20% em comparação com as melhores, mas o número de comparações não muda. Seu autor é Vladimir Yaroslavsky. Ele realmente funciona, via de regra, mais rápido do que outros tipos rápidos. Eu o otimizei um pouco, usando o fato conhecido de que na arquitetura x86, o swap geralmente funciona mais rápido que a atribuição, e para cadeias de caracteres C ++ é muito, muito mais rápido. Todas as classificações rápidas consideradas até agora não possuem a propriedade de estabilidade.

É necessária memória adicional para classificação rápida para organizar chamadas recursivas. No entanto, a segunda chamada pode ser substituída por um loop, otimizando a recursão da cauda , que em termos de velocidade pode não gerar ganhos, mas reduz significativamente o tamanho dos dados adicionais utilizados. Eu implementei a opção de classificação Hoar com essa otimização. Além disso, nos programas do sistema, você pode verificar o ponteiro da pilha e, se ele se aproximar de um valor crítico, pode simplesmente redefinir todas as chamadas recursivas e começar a classificar novamente - nesse caso, é óbvio que você precisa usar a opção de classificação rápida que não diminui a velocidade dos dados quase pedidos, por exemplo , a versão proposta acima do Hoar. Combater o uso de memória adicional pode ser considerado a idéia principal da classificação rápida da biblioteca de idiomas C padrão no GCC. Geralmente abandonava a recursão. Em vez disso, eles usam a simulação, que permite que um terço reduza a carga na pilha. O código ficou bastante grande, cerca de 150 linhas. Sobre essa classificação, ainda haverá um pouco de material abaixo.

A classificação de hash pode ser muito rápida, próxima a N. No entanto, às vezes pode funcionar em uma dependência quadrática. A velocidade deste método de classificação é muito dependente da entrada. Se os dados forem distribuídos uniformemente pela função hash na matriz auxiliar, obtemos o relacionamento linear mais rápido. E se todos os dados estiverem agrupados próximos a vários "centros de massa" distantes ou quando houver muitos elementos de dados idênticos, ou seja, quando ocorrerem muitas colisões de hash, obteremos o pior tipo ^de dependência ∽ N2 . Como na classificação em árvore, para classificar o hash, são necessários muitos dados adicionais. Na lista de códigos abaixo , são necessários, por exemplo, 12 bytes adicionais para cada número inteiro classificável (int32, x86-64). Uma propriedade interessante da classificação de hash é a ausência de operações de comparação entre elementos de dados, que distingue essa classificação de todas as consideradas acima. Mais precisamente, essas operações são necessárias apenas para colisões. Ao classificar dados em que a chave corresponde ao elemento de dados inteiro, você pode usar um contador adicional para o número de elementos idênticos, mas essa é uma otimização duvidosa. Você também pode usar uma árvore binária em vez de uma lista para armazenar dados de colisão de hash, isso acelera bastante o trabalho para casos particulares individuais quando há muitas colisões, mas no geral, ao usar uma árvore binária, em muitos casos ela fica lenta e isso apesar do fato de que, neste caso, o elemento os dados precisam armazenar quase 100 bytes de informações adicionais. Eu implementei três opções para a classificação de hash usando uma árvore binária: uma usa uma árvore não ordenada e as outras duas usam árvores padrão das bibliotecas std e boost. A classificação de hash é praticamente inadequada para a classificação de seqüências de texto, exceto as muito curtas, pois é impossível criar uma boa função de hash para esses dados. Não consegui adaptar o hash C ++ padrão (unordered_multiset) para classificar: tentei usar funções hash monótonas e ordenar relações em vez de igualdade - isso não funcionou.

A classificação da matriz é muito semelhante à anterior. Também é usada uma matriz auxiliar, na qual os valores são inseridos pela função hash. No caso de uma colisão, é necessário deslocar o fragmento contínuo dos elementos ocupados para a posição esquerda ou direita, liberando a posição indicada pela função hash para o novo elemento. Para obter uma boa velocidade, é necessário que a matriz auxiliar seja várias vezes (de 2 a 3) mais que a original. Com um aumento no tamanho da matriz auxiliar, a velocidade aumenta apenas para um determinado limite, dependendo dos dados classificados e da função hash associada a eles, e depois (normalmente de 4-5) diminui. A velocidade de operação é quase a mesma que a do hash, mas com dados bons um pouco mais rápidos e com dados ruins, é visivelmente mais lenta. Esse tipo também precisa de muita memória extra.Se limitarmos o número de elementos na matriz classificada a pouco mais de quatro bilhões, uma matriz auxiliar tripla exigirá a mesma quantidade de dados adicionais que a classificação com um hash, e uma tripla exigirá 28 bytes, o que é notavelmente menor do que o da classificação por uma árvore ou muito menos do que o hash com árvores. Essa classificação também é quase inadequada para trabalhar com strings. Não existe um artigo da Wikipedia sobre esse algoritmo, mas aqui está minha implementação .

Curiosamente, na Wikipedia, em um bom artigo de visão geral , não há menção de métodos intermediários, como classificação de matriz e hash, que naturalmente podem ser colocados entre métodos com base na comparação de elementos e métodos com base no valor absoluto dos elementos.

Uma das classificações mais rápidas, que nunca usa comparações, é a classificação bit a bit conhecida desde o século XIX.(classificação do radical). A ideia dela é muito simples - você precisa trabalhar com grupos de bits de representação de dados (para testes fiz grupos de 8, 11 e 16 bits). As tabelas são criadas para cada grupo e os resultados são combinados de maneira relativamente simples. Existem duas maneiras principais de usar a classificação bit a bit. É mais conveniente usar os dígitos para classificar números da direita para a esquerda (esta é a opção LSD - Menos Dígito Significativo) e para classificar cadeias da esquerda para a direita (essa é a opção MSD - Dígito Mais Significativo). A classificação bit a bit geralmente é significativamente mais rápida que qualquer outro método de pedido de dados. Surpreendentemente, o suporte à classificação bit a bit ainda não é muito significativo: ele não está no boost nem na biblioteca C ++ padrão; eu nem conheço sua versão para qualquer biblioteca conhecida por trabalhar com números ou seqüências de caracteres C ++. Este tipo temé claro, e desvantagens. É muito sensível ao tipo de dados para classificação, por exemplo, você precisa ter sua própria versão dessa classificação para dados de cada tamanho, precisa fazer opções especiais para números inteiros não assinados e assinados, e o suporte ao trabalho com números reais pode exigir muito esforço. Ao usar a ordem do byte menos significativo ao mais importante, sua variante geralmente requer memória adicional, um pouco mais do que para os dados iniciais (isso é significativamente menor do que para a classificação por um hash ou matriz, e ainda mais por uma árvore). Além disso, essa opção é pouco útil para classificar seqüências longas. Meu código para esse tipovocê precisa fazer opções especiais para números inteiros não assinados e assinados, e o suporte para trabalhar com números reais pode exigir bastante esforço. Ao usar a ordem do byte menos significativo ao mais importante, sua variante geralmente requer memória adicional, um pouco mais do que para os dados iniciais (isso é significativamente menor do que para a classificação por um hash ou matriz, e ainda mais por uma árvore). Além disso, essa opção é pouco útil para classificar seqüências longas. Meu código para esse tipovocê precisa fazer opções especiais para números inteiros não assinados e assinados, e o suporte para trabalhar com números reais pode exigir bastante esforço. Ao usar a ordem do byte menos significativo ao mais importante, sua variante geralmente requer memória adicional, um pouco mais do que para os dados iniciais (isso é significativamente menor do que para a classificação por um hash ou matriz, e ainda mais por uma árvore). Além disso, essa opção é pouco útil para classificar seqüências longas. Meu código para esse tipoEsta opção não é adequada para classificar seqüências longas. Meu código para esse tipoEsta opção não é adequada para classificar seqüências longas. Meu código para esse tipoaqui , ele se baseia no código do artigo oms7 mencionado. A opção de ordem inversa de bytes é mais versátil e muito adequada para a classificação de strings. Essa opção pode ser implementada sem o uso de memória adicional (o preço disso é a perda da propriedade de estabilidade), como é feito na função radixsort () da biblioteca bsd. Meu códigopara esta opção, ela também é baseada no código oms7, usa memória extra, dados de origem um pouco maiores, possui a propriedade de estabilidade, mas não é otimizada para strings e, portanto, apresenta características de desempenho significativamente piores que a função semelhante sradixsort () da biblioteca bsd já mencionada . Essa classificação pode mostrar resultados surpreendentemente ruins ao trabalhar com pequenas matrizes numéricas, trabalhando várias ordens de magnitude mais lentas que as bolhas, embora falemos de valores muito pequenos de não mais do que alguns milissegundos e essa diferença não é fácil de notar. Isso se deve ao fato de usar matrizes auxiliares de tamanho pequeno, mas ao classificar dados de tamanho pequeno, esses tamanhos pequenos podem ser maiores que os próprios dados classificados.Para evitar lentidões, a opção "da esquerda para a direita" usa a classificação de inserção em vez da principal nesses casos. Em conclusão, vale a pena notar que esta é a única classificação relativamente popular conhecida por mim que sempre funciona com confiabilidade a uma velocidade de ∽N , mas o coeficiente de proporcionalidade aqui depende do tamanho dos elementos de dados e, para cadeias ou números longos, pode ser bastante perceptível.

Uma opção para classificação MSD bit a bit é a classificação por feixe , uma estrutura de dados que permite colocar com eficiência as chaves de uma matriz associativa. Minha implementação , apesar de otimizar o uso da memória, ainda se mostrou muito gananciosa por isso. Por velocidade, os melhores resultados foram obtidos na classificação das linhas longas.

Além disso, consideraremos algumas classificações que podem ser encontradas nas bibliotecas padrão.

Vamos começar com o rápido da biblioteca C padrão (qsort, uma variante do GCC), eu já escrevi sobre isso. Só posso acrescentar aqui que essa classificação e outras classificações C (por exemplo, as seguintes da biblioteca BSD) não são adequadas para trabalhar com dados de objetos, em particular cadeias C ++, causadas pelo fato de que esses dados não são POD. Tendo a fonte, o problema pode ser facilmente resolvido substituindo operações memcpy por atribuições regulares. Você também pode notar que, em algumas bibliotecas C padrão, essa classificação pode não ser necessariamente rápida, pode ser substituída por outras. Na versão atual do GCC, essa classificação ainda possui a propriedade de estabilidade. Às vezes, havia surpresas com as c-ordenações mencionadas ao coletar dados, por exemplo, ao trabalhar com o tipo std :: vector através de um objeto funcional, elas poderiam criar dificuldades - eu recomendo usá-lo com dados de objeto com cautela. De acordo com as execuções, essa classificação às vezes é relativamente lenta: é notavelmente inferior em velocidade a outras implementações de classificação rápida ao trabalhar com números, mas ao trabalhar com strings si é melhor, apenas a classificação com dois pontos de controle às vezes o leva adiante,mas em linhas longas, o qsort padrão quase sempre o ultrapassa. O mais interessante foi descoberto quando tentei classificar um bilhão de números inteiros com sua ajuda - descobriu-se que o preenchimento do tipo 7 leva a uma dependência de tempo próxima a uma lei quadrática, ou seja, a um possível "processamento" com duração de vários anos (não esperei pelo fim e o parei às 21 horas de execução). Com menos dados, essa classificação geralmente pode selecionar pontos de ancoragem com os quais trabalha rapidamente.Com menos dados, essa classificação geralmente pode selecionar pontos de ancoragem com os quais trabalha rapidamente.Com menos dados, essa classificação geralmente pode selecionar pontos de ancoragem com os quais trabalha rapidamente.

A classificação introspectiva é usada na biblioteca padrão C ++, embora o método exato usado em std :: sort dependa da implementação, fornecendo informações apenas sobre o GCC. De acordo com as execuções, este é o segundo mais rápido após a classificação por dispersão ao trabalhar com números, e a vantagem da classificação por dispersão é pequena (de quase 0 a 30%), mas com a classificação por sequência tudo é muito pior - pode ser 3-4 vezes menor que os líderes . Essa é, na verdade, uma classificação rápida, na qual dois casos especiais são levados em consideração: 1) se o número de recursões se tornar muito grande, ocorre a troca para a classificação por heap; 2) se o número de elementos para classificação for pequeno, ocorrerá a troca para classificação por inserções.

Classificação estável da biblioteca padrão C ++ ( std :: stable_sort), como o nome indica, tem a propriedade de estabilidade - preserva a ordem relativa entre os elementos com a mesma chave. Essa propriedade é relativamente raramente necessária, embora eu escreva sobre ela de forma infundada, apenas com base em minha própria experiência. Ele pode usar memória adicional, o que o torna mais rápido. Surpreendentemente, essa classificação geralmente é mais rápida que std :: sort.

No python de linguagem super popular, a classificação de Tim é usada como padrão . Para testes, usei sua versão no repositório github. Ele mostra bons resultados recordes em dados parcialmente pedidos, mas, em média, ainda é visivelmente mais lento que os líderes. Geralmente, sua velocidade é a média entre a classificação rápida e a classificação da Shell, embora nas linhas às vezes esteja próxima dos líderes. Tem a propriedade de estabilidade. Ele implementa um algoritmo relativamente complicado, na implementação padrão do qual um erro foi descoberto em 2015, o que, no entanto, requer uma situação pouco realista para sua manifestação.

A biblioteca BSD C possui classificação bit a bit ( radixsort) e sua versão estável (sradixsort). Infelizmente, esses dois tipos podem ser usados ​​apenas para cordas C. Como será visto nos dados de teste, esta é a maneira mais rápida de classificar seqüências de caracteres hoje e, portanto, é surpreendente que não exista uma opção padrão para seqüências de caracteres C ++.

A biblioteca BSD C tem mais sorte merge ( a mergesort) Essa classificação é conhecida como uma das mais rápidas para dados de acesso seqüencial (arquivos, listas) e provavelmente é usada na biblioteca padrão C ++ para classificar listas (std :: list e std :: forward_list). A propósito, ela era conhecida desde 1948 e um de seus desenvolvedores era um matemático muito conhecido e especialista nos primeiros sistemas de computadores von Neumann. Dos métodos rápidos, essa classificação não se distingue pelas melhores características, embora, como regra, seja um pouco mais rápida que os métodos Shell. Requer memória adicional e geralmente é implementado de maneira sustentável.

Além disso, ainda há uma classificação por vários(montão). O heap geralmente é usado para enfileiramento ideal com prioridades, mas também pode ser usado para classificação. Os heaps de classificação não requerem memória adicional, mas não possuem a propriedade de estabilidade. Na velocidade dos números, é significativamente (até 3-6 vezes) mais lento que os métodos Shell, mas para linhas não muito curtas, mostra resultados muito bons, ultrapassando (com o aumento do comprimento da linha, a vantagem aumenta) os métodos Shell.

A classificação de heap também está disponível na biblioteca padrão C ++. Essa classificação é feita em duas operações: construindo o heap (std :: make_heap) e depois classificando ( std :: sort_heap)) Aqui, diferentemente da biblioteca bsd, a classificação é apenas uma das operações do heap. Geralmente, essa opção de classificação é um pouco mais rápida que a anterior (a opção bsd mostra melhores resultados apenas em números curtos e linhas s longas).

Usando a biblioteca C ++ padrão, você pode classificar a árvore balanceada binária (std :: multiset) - apenas preencha a árvore e depois circule. Esse método pode ser considerado uma classificação rápida não-recursiva. Algum problema surge no fato de que o alocador de memória padrão é notável por ser lento; portanto, para obter os melhores resultados, você precisa usar seu próprio alocador, que acelera em cerca de 10 a 30%. Também é possível observar que esse método requer muita memória adicional, com g ++ para cada elemento de dados; além disso, você também precisa armazenar 32 bytes (na arquitetura x86-64) - seria interessante tentar armazenar essa árvore como um monte, ou seja, sem adicional byte Se você usar boost :: container :: multiset, precisará de menos memória: apenas 24 bytes extras por elemento de dados. No entanto, como impulso,e a biblioteca padrão mostrou uma surpresa desagradável - no processo, às vezes eles exigiam mais memória do que o necessário. Talvez isso se deva ao balanceamento de árvores binárias. Códigos -aqui .

A biblioteca boost possui spreadsort , um algoritmo que foi inventado no século XXI. Esse é o método geral mais rápido disponível hoje em bibliotecas conhecidas. Essa classificação usa algumas idéias bit a bit e, como ela, pode ser bastante sombria sobre o tipo de argumento. Normalmente, essa classificação mostra resultados recordes, às vezes significativamente melhores que os dos concorrentes mais próximos. A única exceção é a classificação das linhas C, onde é significativamente inferior aos métodos bit a bit da biblioteca bsd. Ao classificar linhas C longas, ele pode ser inferior a outros métodos, por exemplo, classificação por rotação ou classificação rápida com dois pontos de ancoragem. A classificação da propagação (aumento v1.62) mostrou um problema muito desagradável- ao classificar pequenas matrizes de cadeia C (até 1000 elementos), ele funciona com erros.

Há também um novo algoritmo pdqsort que aprimora, como declarado pelo autor, a classificação introspectiva. Este novo algoritmo, que ainda não está descrito na Wikipedia. Seus resultados - embora não sejam ruins, mas não particularmente impressionantes. É mais lento que std :: sort em inteiros curtos, mas mais rápido em strings e inteiros longos. Nos dois casos, a diferença é bastante insignificante. Os melhores resultados para essa classificação foram obtidos para seqüências longas de C ++ - aqui é inferior, embora visivelmente, apenas ao líder, na classificação por dispersão.

No impulso você ainda pode encontrar spinsort. Este também é um novo algoritmo, que, diferentemente do anterior, possui a propriedade de estabilidade e ainda não está descrito na Wikipedia. Geralmente ele está perto do líder, mas com um atraso perceptível atrás dele. Requer, embora não muito, memória adicional. Vamos terminar

com flat_stable_sort da mesma biblioteca de impulso. Este é outro novo algoritmo robusto que ainda não está descrito na Wikipedia. Esse é de longe o método mais rápido, mas um pouco inferior ao da maioria dos outros métodos de biblioteca rápida. Ele usa muito pouca memória adicional (no entanto, sempre precisa de uma tabela de tamanho fixo de 8 KB) e geralmente é visivelmente mais rápido que o método Shell.

Considere a tabelatempo (em ms) da operação desses algoritmos em um computador com 8 GB de RAM com um processador AMD Phenom ™ II X4 955 a 3.214 MHz. O computador funcionou por vários meses e o tamanho total dos dados coletados em dois arquivos json carregados com tabelas é de quase 400 KB. Os tempos são dados pela média do número de execuções; para tamanhos menores, essas execuções foram maiores. Trabalhar com o cache de uma maneira bastante complicada altera a velocidade dos cálculos, de modo que os resultados obtidos são apenas aproximados na melhor das hipóteses (posso assumir que as imprecisões de tempo podem chegar a 20%). Acredito que nos melhores processadores modernos para PCs, o resultado pode ser obtido 2-3 vezes mais rápido, mas lembre-se de que muitos processadores modernos funcionam alternando entre diferentes frequências e o resultado obtido com eles,será ainda mais aproximado.

Esta e a tabela a seguir são interativas. Além dos valores absolutos dos tempos, você também pode ver seus valores em relação à média, mediana, mínimo e máximo. Você pode alterar a precisão dos caracteres. Você também pode obter relacionamentos de tempo para diferentes tipos de preenchimentos e tipos de dados. O último, por exemplo, pode mostrar que a classificação de seqüências de caracteres C é visivelmente mais rápida que as seqüências de caracteres C ++. Nos métodos de classificação, você também pode selecionar e montar uma variedade de subconjuntos. Obviamente, você pode definir a classificação por qualquer coluna. Infelizmente, não sei como usar o Javascript no artigo no hub, portanto, as tabelas estão disponíveis apenas por referência. No caso de o imtqy.com estar sobrecarregado, também forneço links de backup para a primeira e a segunda tabelas.

O tempo é medido em milissegundos, mas, na lei da dependência do tempo, para evitar coeficientes muito pequenos, são fornecidas fórmulas para microssegundos. Portanto, se substituirmos o valor por N na fórmula , o resultado também deve ser dividido por 1000 para obter um número próximo ao correspondente da tabela. A lei da dependência do tempo é derivada com base nos tempos obtidos, a partir de uma comparação de dois resultados (geralmente os extremos são tomados). Você pode verificar a qualidade da lei derivada usando a opção de desvio relativo do valor real da saída.

Algumas conclusões gerais dos resultados desta tabela:

• as melhores classificações de shell em dados de até 10 milhões de elementos podem ultrapassar o timsort e até algumas classificações rápidas;
• O timsort está muito próximo da velocidade qsort (clib), às vezes ultrapassando um pouco e às vezes vice-versa atrás;
• O heapsort e especialmente o treesort geralmente diminuem visivelmente, mas no contexto de uma bolha ou mesmo de uma escolha, fica claro que esses ainda são métodos rápidos. Curiosamente, esses dois métodos geralmente têm características muito semelhantes - ambos constroem árvores. É fácil notar que as dependências para heapsort e treesort, embora não sejam claramente quadráticas, obviamente não são N log N , mas muito pior - compare com a classificação do Shell, que se comporta muito melhor com o aumento do volume de dados do que o heapsort ou o treesort, enquanto que ela própria é mais lenta que N log N. Assim, as implementações práticas de ordenação de heap e árvore não correspondem às suas especificações teóricas;
• os dados sobre a classificação de cadeias de caracteres mostram que as leis das dependências de tempo aqui não são as mesmas dos números - os comprimentos das cadeias ordenadas são de alguma forma sobrepostas a essas leis aqui. Infelizmente, eu não conheço as fórmulas para classificações conhecidas que dariam leis exatas das dependências de tempo ao trabalhar com strings;
• é interessante que a velocidade de trabalhar com números reais seja quase a mesma que números inteiros - isso é uma conseqüência do fato de que na arquitetura moderna x86 são feitas otimizações muito eficazes para trabalhar com a pilha;
• hash_sort mostrou resultados bastante medíocres, isso é possível devido ao fato de que, devido ao uso de memória adicional, o desempenho dos caches do processador diminui acentuadamente. Em pequenos dados aleatórios (menos de cem mil elementos), a classificação de hash ultrapassa as melhores classificações rápidas. Você também pode perceber que é possível novamente devido a caches, alguns dos resultados dessa classificação são muito estranhos, por exemplo, 10 ⁵ , 10 ⁶ e 10 ⁷ números inteiros de 32 bits ao usar preenchimento parcialmente ordenado são classificados aproximadamente para o mesmo valor hora! Algum tipo de efeitos quase quânticos. :) Tenho certeza de que, se você pesquisar, poderá encontrar outros resultados difíceis de explicar.

Vou acrescentar mais algumas conclusões sobre alguns casos especiais:

• alguns tipos de preenchimento de dados revelam fraquezas nas classificações rápidas. No entanto, a escolha de um elemento de suporte de maneira complicada aumenta a probabilidade de cair em uma sequência incorreta para classificar praticamente zero. Você também pode selecionar um elemento de suporte em cada passagem de maneiras diferentes ou aleatoriamente. Talvez eles o façam em qsort (clib). O método Hoare em consideração funciona muito lentamente apenas em seqüências especialmente projetadas, encontradas por acaso durante o trabalho prático - este é um caso com uma probabilidade de 2 ^{N -3} / N ^N , ou seja, um evento quase absolutamente impossível. Embora se considerarmos sequências nas quais o método Hoar não funciona o mais lentamente possível, mas apenas com uma desaceleração significativa, existem muito mais casos, o que, no entanto, deixa a probabilidade de um caso de processamento de dados inaceitavelmente lento ainda ser praticamente insignificante, embora muito irritante em sua diferença de zero. Também é quase impossível obter acidentalmente dados sobre os quais a classificação rápida com dois pontos de controle funcionará lentamente, de acordo com a lei quadrática. As opções de classificação rápida do Lomuto sem e sem um elemento de suporte mostram resultados muito ruins em quase todos os casos de preenchimento específicos;
• em alguns casos especiais, a classificação mais lenta da “bolha” produz excelentes resultados, e algumas das mais rápidas e rápidas, pelo contrário, são muito ruins;
• A classificação de hash mostrou um resultado muito ruim nos preenchimentos dos tipos 8 e 9, isso ocorre porque a sequência monótona é obtida a partir de valores consecutivos, começando pelo menor, e 1% dos números aleatórios é retirado da faixa do valor mais baixo ao máximo, que contém 99% dos dados consecutivos em um elemento de hash. Este caso demonstra muito bem os problemas que podem surgir ao usar essa classificação ou classificação com uma matriz com dados desconhecidos;
• a classificação por seleção se comporta de maneira muito estável em todos os tipos de preenchimento; a classificação por pilhas e árvores também é bastante estável, sem picos e quedas óbvios. Isso é verdade, é claro, para os tipos de Shell, bem como para a maioria dos outros métodos rápidos das bibliotecas padrão.

Agora é hora de falar sobre os tipos de dados usados ​​nos algoritmos de classificação:

1. números inteiros de 32 bits assinados (int32_t), mas apenas não negativos foram usados. Outros dados numéricos também foram obtidos apenas como não negativos - isso não reduz a generalidade dos resultados, mas facilita muito a obtenção deles para alguns algoritmos;
2. números inteiros, assinados de 64 bits (int64_t);
3. números inteiros, assinados em 128 bits (__int128 - suportado por pelo menos GCC);
4. estruturas de cinco números inteiros (int32_t), um dos quais é usado como chave (INT1P4). Ao classificar esses dados, o número de permutações começa a afetar o tempo computacional de maneira mais significativa, portanto, métodos com menos permutações ganham alguma vantagem;
5. números reais, como precisão dupla, dupla (números flutuantes);
6. cadeias curtas C ++ e C. Foram utilizadas cadeias de 1 a 16 (cadeias curtas e c-cadeias curtas);
7. strings C e C ++ de comprimento médio, cujo comprimento é de 1 a 256 (strings e c-strings);
8. linhas longas C e C ++, cujo comprimento é de 1 a 2 ²⁰ (isso é um pouco mais de um milhão), e as linhas são selecionadas para que seu comprimento médio não exceda 512; portanto, as linhas foram selecionadas apenas para preenchimento aleatório; em outros casos, as linhas foram simplesmente utilizadas comprimentos de 1 a 512 (cordas longas e c-longas).

E também sobre como preencher a matriz de origem para classificação:

1. por acaso;
2. estritamente ascendente (ordenado);
3. estritamente descendente (ordem inversa, reversa);
4. valores aleatórios da faixa de 0 a 99 (pequena variação, baixa variação 100);
5. sequência aleatória de 0 e 1 (pequena variação, baixa variação 2);
6. constante 0 (spread pequeno, baixa variação 1);
7. a sequência que leva a versão qsort (Hoare) à execução mais lenta. É curioso que existam exatamente 2 ^{N -3} dessas seqüências entre todas as sequências de comprimento N ;
8. estritamente ascendente, com a inserção de 1% de números aleatórios (parcialmente pedidos);
9. estritamente descendente, com inserção de 1% de variáveis ​​aleatórias (parcialmente revertidas).

Deve-se enfatizar que dados aleatórios são o caso mais típico de preenchimento de uma matriz, todos os outros métodos são extremamente raros e até quase impossíveis durante a operação normal de um determinado.

Vejamos os resultados do teste, onde as classificações funcionam com todas as sequências de dados possíveis. O número de tais seqüências é igual ao fatorial de seu comprimento; portanto, para as seqüências de comprimento 12, existem 479'001'600 variantes - um bom PC moderno calcula seu número em menos de um minuto. Se tomarmos seqüências de comprimento 14, já temos 87'178'291'200 variantes para várias horas de operação do computador. Portanto, a tabela a seguir mostra o tempo médio (em ciclos do processador obtido através da instrução RDTSC ) de uma classificação ao classificar todas as permutações até apenas 12. Nos dados, os tipos numéricos e seqüências de caracteres anteriores são obtidos. Obviamente, pode-se notar que seqüências com elementos repetidos não são consideradas. No entanto, atrevo-me a sugerir que a presença deles não alteraria qualitativamente os resultados, mas poderia retardar significativamente o recebimento.

Os resultados para esses dados pequenos não são muito representativos, e especialmente para métodos de classificação complexos, mas ainda complementam a ideia do comportamento de classificação. Alguns tipos, até onde eu sei, substituem seu algoritmo principal por outro ao trabalhar com matrizes pequenas - são tipos espalhados, rápidos com dois pontos de ancoragem e radix_msd (os últimos dois usam inserções). E algumas classificações (flat_stable e radix) usam tabelas pequenas, mas com pequenos tamanhos de dados, essas tabelas acabam sendo muito maiores que os dados em si, o que diminui bastante esses métodos em comparação com outros e produz resultados estranhos. Resultados estranhos também são obtidos com outras classificações bit a bit e com classificações hash e array. Tais resultados incomuns são facilmente explicados pelo fato de que o tempo de preparação dos dados antes da classificação desses métodos para dados pequenos é maior que o próprio tempo de classificação. Obviamente, ao medir intervalos de tempo tão pequenos (nanossegundos), a influência de vários erros na lei exibida é muito maior do que na tabela anterior. Portanto, as leis acabaram sendo muito aproximadas, geralmente "com uma tendência" a valores exagerados. O último é parcialmente explicado pelo fato de que, ao trabalhar com dados pequenos, o próprio tempo de classificação se torna comparável ao tempo de chamar a função de classificação e várias operações auxiliares necessárias para medir o tempo. O programa tenta subtrair a sobrecarga nomeada da saída, mas acaba sendo feita aproximadamente. Com tudo isso, atrevo-me a supor que, comparando os resultados para diferentes tipos de dados e levando em consideração os comentários feitos, às vezes você pode fazer suposições que não estão muito longe da precisão.

Em conclusão, outra tabela que mostra quantos métodos de teste diferentes são necessários para classificar memória adicional. Obviamente, esse valor depende do sistema. Nos meus testes, como já escrevi, esse é o x86-64, GCC. A letra T significa o tamanho do tipo em bytes (o comprimento da string não está incluído neste tamanho: para linhas C é o tamanho do ponteiro, para linhas C ++ é o tamanho do descritor, 32 bytes para x86-64 GCC), a letra L é o meio o comprimento do tipo em bytes (para números é T e para cadeias é o comprimento médio da cadeia), a letra A pode ser 1 ou 0 - este é o alinhamento com a borda de 64 bits e a letra M é o alinhamento do alocador de memória padrão (supõe-se alinha a um limite de 32 bytes). O símbolo ^* significa que os dados para esse tipo de classificação foram obtidos apenas com base na análise da leitura do campo VmRSS em / proc / PID / status (o campo mencionado é o tamanho do programa de processo).


É claro que existem outros métodos de classificação, tanto primitivos quanto rápidos. A biblioteca de reforço possui algoritmos paralelos que permitem tirar vantagem da presença de núcleos de processador adicionais no sistema. Você também pode usar o container self-order boost :: container :: flat_multiset em vez de std :: multiset, mas funciona muito lentamente.

Aproveito a oportunidade para fazer alguns comentários sobre a biblioteca boost em geral. Eu recomendo não passar. Mesmo os recursos que estão na biblioteca padrão em impulso, como regra, são melhor implementados e, às vezes (como expressões regulares, por exemplo) são muito melhores. Se falamos de contêineres, eles são notoriamente maiores, e aqueles que coincidem com os contêineres às vezes são um pouco mais rápidos e geralmente têm pequenas, mas boas melhorias. O Boost verifica os tipos mais detalhadamente, o que às vezes pode ajudar na detecção de erros quase ilusórios que geralmente não se manifestam, mas, em algumas circunstâncias, podem ser ativados inesperadamente. As desvantagens do aumento incluem mensagens incondicionalmente completamente ilegíveis e enormes em volume sobre erros de compilação em muitas construções desta biblioteca - isso, embora em menor grau, se aplica à biblioteca padrão. Chegou a hora dos desenvolvedores de C ++ fazerem algo sobre isso.

Todos os arquivos com testes e outros materiais relacionados podem ser obtidos no meu repositório . Se alguém estiver interessado em dados de origem brutos, você pode obtê-los aqui (1,4 MB). Ficarei feliz em quaisquer comentários, críticas e acréscimos.