About me

About

2011-09-29

E por falar em ordenação...

E por falar em ordenação…

Um z80, lançado originalmente em 1976, ordenava 1000 números em 60s, usando o algoritmo selection sort, programado directamente em código máquina, com o processador dedicado a 100% à operação. Ou seja, aproveitando as potencialidades máximas do sistema.

Alguns anos mais tarde, vejamos o seguinte exercício:

  • CPU: Intel(R) Core(TM)2 Duo CPU T7250 @ 2.00GHz, mas fixado a 800MHz
  • sistema operativo linux 2.6.33.7 32 bits
  • 101 processos mas load average 0.00, i.e. máquina virtualmente sem carga
  • linguagem awk: interpretada, de “alto nível”
  • cenário: ordenação de strings de tamanho arbitrário
  • algoritmos: selection sort, insertion sort, heap sort, bubble sort, merge sort, quick sort

Execução:

dd if=/dev/urandom | tr -c -d A-Za-z0-9_\\n | sed 10000q | \time mawk -f quick_sort.awk | sort -c
  1. dd if=/dev/urandom | tr -c -d A-Za-z0-9_\\n | sed 10000q: produção de 1000 linhas de texto aleatórias;
  2. \time mawk -f quick_sort.awk: ordenação do input e medição do tempo que demorou
  3. sort -c: validação da correcção da ordenação

Algumas medições efectuadas, com os tempos sempre em segundos:

  • selection sort revisitado às 1000 linhas: 0.37;

  • Benchmark de 10k linhas (tempo em segundos):
    • bubble_sort.awk => 100.78
    • selection_sort.awk => 26.70
    • insert_sort.awk => 16.76
    • heap_sort.awk => 1.66
    • quick_sort.awk => 1.41
    • merge_sort.awk => 1.33

Agora algumas contas:

  • se o selection sort é O(n^2), significa que o tempo de execução num ambiente pode ser calculado derivando uma constante c;
  • assim: t=n^2/c; logo c=n^2/t;
  • como já temos n=1000 e t=26.70 no caso do selection sort, fica c=3745318;
  • qual o número de itens necessários para a ordenação demorar 60s? n^2=ct => n=sqrt(ct), sabemos c=3745318 e pretendemos t=60, logo n=14990;
  • testando:
    • dd if=/dev/urandom | tr -c -d A-Za-z0-9_\\n | sed 14990q | \time mawk -f selection_sort.awk |sort -c
    • Resultado: 63.87. Perfeito. :)

Estes resultados mostram uma coisa que por vezes é negligenciada: o hardware tem evoluído bastante mas a dimensão dos dados também. Se os algoritmos que processam os dados não forem eficientes, o novo hardware traz poucos ganhos em escala e pode acontecer a lentidação causada pelo crescimento dos dados ultrapassar os ganhos introduzidos pelo novo hardware.

Neste pequeno exemplo, uma ordenação de 1k números no velhinho spectrum corresponde a uma ordenação de 15k num portátil hoje em dia, em powersave :), mais coisa menos coisa. A comparação não foi 100% rigorosa (assembler vs awk, etc) mas tem o rigor suficiente para o que se demonstra.

Sem comentários:

Enviar um comentário