Implementação de classificação de biblioteca mais rápida do Haskell

Question

Implementação de classificação de biblioteca mais rápida do Haskell

#1 resposta do (6 votos)

5

Estou implementando um aplicativo no Haskell e, para classificação, uso a função de biblioteca Data.List.sort . No entanto, eu queria saber se essa é a implementação de classificação mais rápida na biblioteca padrão do Haskell (talvez as listas não sejam a melhor opção para classificação eficiente).

Eu encontrei alternativas diferentes, por exemplo classificação de pilha em matrizes , < href="http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Sequence.html#g:10"> classificar em sequências (mas a documentação não dizer que tipo de algoritmo é usado).

Minha pergunta é: qual é a implementação de classificação mais rápida (tipo de contêiner + função de classificação) fornecida pela biblioteca padrão do Haskell? Existe alguma página de documentação listando todas as funções de classificação da biblioteca e comparando-as com o desempenho?

EDITAR

Para fornecer mais contexto, estou executando um benchmark. Eu escrevi um programa simples em C, Java, Python e Haskell que

Lê strings de 1000000 (linhas) de um arquivo de texto.
Classifica as strings usando um algoritmo de classificação integrado (biblioteca).
Grava a lista classificada de strings em um arquivo.

Para cada implementação, eu apenas meço o tempo de classificação (deixando de fora o tempo necessário para o disco IO). Executando o benchmark no Ubuntu 12.04, recebo

C (gcc 4.6.3, qsort em char ** ): 0.890 s
Java (OpenJDK 64-Bit 1.7.0_09, Collections.sort() em java.util.LinkedList<String> ): 1.307 s
Python (Python 2.7.3, list.sort() ): 1.072 s
Haskell (GHC 7.4.1, Data.List.sort em [Data.ByteString.UTF8.ByteString] ): 11.864 s

Então, pergunto-me se existe outra função de biblioteca / tipo de dados no Haskell que possa fornecer um melhor desempenho.

haskell sorting

por Giorgio 23.12.2012 / 00:05

fonte

1 resposta

Tags haskell sorting

Qual é a diferença entre o recozimento quântico e o recozimento simulado? Visão geral do processo ágil que posso aplicar a uma inicialização

score 6 · Accepted Answer

O problema com Data.List.sort é que ele usa merge sort, que cria novas listas durante cada passagem. Então, muito tempo é gasto na alocação e liberação de memória.

Surpreendentemente, a AFAIK não possui uma biblioteca de classificação para matrizes mutáveis , que provavelmente serão mais rápidos. Então eu tentei criar um e colocá-lo no github: marray-sort . Ele precisa de testes rigorosos, polimento e otimização também, mas até agora parece ser significativamente mais rápido do que Data.List.sort .

Se você fizer algum experimento com ele, ficarei feliz em ver os resultados. Eu coloquei seu benchmark (ligeiramente modificado) em src-test / Test.hs por conveniência. Não se esqueça de compilar tudo com -O2 para acionar as otimizações necessárias do compilador.

Editar: Descobri agora que existe uma implementação se introsort para vetores mutáveis em algoritmos de vetores . De acordo com minhas medições, é um pouco mais rápido (5-10%) do que minha tentativa acima de MArray s Veja também: Como se classifica com Data.Vector.Generic.Mutable? .