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
dd if=/dev/urandom | tr -c -d A-Za-z0-9_\\n | sed 10000q
: produção de 1000 linhas de texto aleatórias;\time mawk -f quick_sort.awk
: ordenação do input e medição do tempo que demorousort -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