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? .