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.