C: Sorting Métodos de Análise

votos
7

Eu tenho um monte de diferentes algoritmos de ordenação que todos têm a seguinte assinatura:

void <METHOD>_sort_ints(int * array, const unsigned int ARRAY_LENGTH);

Há algum suites de teste para triagem que eu poderia usar para a finalidade de fazer comparações empíricas?

Publicado 27/08/2009 em 04:52
fonte usuário
Em outras línguas...                            


4 respostas

votos
10

Esta discussão detalhada , bem como a ligação a um grande número de páginas web relacionadas que são susceptíveis de encontrar útil, também descreve um conjunto útil de dados de entrada para testar algoritmos de classificação (ver a página vinculada por razões). resumindo:

  1. matriz totalmente reformulado aleatoriamente
  2. matriz já classificadas
  3. Já classificados em matriz ordem inversa
  4. matriz da serra de cadeia
  5. Disposição de elementos idênticos
  6. Já classificados matriz com permutações de N (N com de 0,1 a 10% do tamanho)
  7. matriz já classificados em ordem inversa com matriz permutações N
  8. Os dados que têm distribuição normal com chaves duplicadas (ou perto) (para triagem única estável)
  9. dados pseudo-aleatórios (valores diários de S & P500 ou outro índice para uma década pode ser um bom teste definido aqui, pois eles estão disponíveis a partir Yahoo.com)
Respondeu 02/09/2009 em 11:10
fonte usuário

votos
7

O estudo definitivo de classificação é Bob Sedgewick tese de doutorado 's. Mas há um monte de boas informações em seus livros de algoritmos, e esses são os dois primeiros lugares que eu iria procurar conjunto de testes e metodologia. Se você já teve um curso recente você vai saber mais do que eu; última vez que tive um curso, o melhor método era usar quicksort para baixo para partições de tamanho 12, em seguida, executar tipo de inserção em toda a matriz. Mas as respostas mudar tão rapidamente quanto o hardware.

Programação Perls livros de Jon Bentley tem algumas outras informações sobre a classificação.

Você pode rapidamente chicotear acima de um conjunto de testes contendo

  • inteiros aleatórios

  • inteiros ordenados

  • Reverter inteiros ordenados

  • inteiros ordenados, levemente perturbada

Se serve de memória, estes são os casos mais importantes para um algoritmo de ordenação.

Se você estiver olhando para classificar matrizes que não cabem no cache, você vai precisar para medir os efeitos de cache. valgrindé eficaz se lento.

Respondeu 27/08/2009 em 05:22
fonte usuário

votos
3

sortperf.py tem um conjunto bem selecionados de casos de teste de benchmark e foi usado para apoiar o ensaio encontrados aqui e fazer timsort o tipo em Python lo que há muitos anos. Note-se que, finalmente, Java pode estar se movendo para timsort também, graças a Josh Block (ver aqui), Então eu imagino que eles têm escrito a sua própria versão dos casos de teste de benchmark - no entanto, não pode facilmente encontrar uma referência a ele. (Timsort, um estábulo, adaptáveis, iterativa variante mergesort natural, é especialmente adequado para idiomas com a semântica de referência-a-objeto, como Python e Java, onde "o movimento de dados" é relativamente barato [[uma vez que todos que já sendo movido é referências aka ponteiros , não bolhas de tamanho ilimitado ;-)]], mas as comparações podem ser relativamente caro `pois não há limite superior para a complexidade de uma função de comparação - mas isso vale para qualquer idioma em que a classificação pode ser personalizado através de uma comparação personalizada ou function` chave-extracção).

Respondeu 06/09/2009 em 02:15
fonte usuário

votos
3

Este site mostra os vários algoritmos de ordenação utilizando quatro grupos: http://www.sorting-algorithms.com/

Além do grupo de quatro na resposta de Norman que pretende verificar os algoritmos de ordenação com coleção de números que têm algumas semelhanças nos números:

  • Todos os números inteiros são únicos
  • O mesmo número inteiro em toda a coleção
  • Poucas chaves únicas

Alterar o número de elementos na coleção também é uma boa prática verificar cada algoritmo com 1K, 1M, 1G etc, para ver quais são as implicações de memória desse algoritmo.

Respondeu 02/09/2009 em 10:51
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more