Vyhodnotenie contestu - o najlepsi isort

31.05.2003 12:16 | blackhole

Presli tri tyzdne od zadania contestu v ktorom bolo za ulohu nakodit co najmensi insert sort. Po pociatocnom vahani mi prisli riesenia od 4 sutaziacich (geordi,lll,pt,imap). Kazde jedno riesenie bolo ine,cimsi zaujimave.

Utriedene podla velkosti je poradie taketo:

1. imap - 25 B -
podarilo sa mu vdaka celkom originalnemu napadu urobit, cez rekurziu, najmensi sort. Myslim ze prekvapil vsetkych pretoze ja osobne som nedaval nadej ze niekto pojde pod 30 bajtov ;). Skoda ze to nedotiahol celkom do konca pretoze zavedenim instrukcie lodsl na iste miesto by usetril 4 bajty ktore by pouzil na cld,pusha a popa co cini zisk 1 bajt ;). Dalo by sa vsak polemizovat nad istou konstrukciou ktora ako upozornil pt robi z tohto algoritmu hybrid medzi isortom a bubble sortom,myslim si vsak ze je to viac isortovanejsi algoritmus ako bubblovanejsi takze som to uznal ;).

2. geordi - 31 B -
zo zaciatku vyzeralo ze to vyhra avsak nie ;). Zo zaciatku jeho riesenie nezvladalo pracu s +/- cislami avsak nakoniec to vyriesil.

3. pt - 36 B - jediny kto sa snazil ist podla volacich konvencii. V zadani som to sice neziadal ale dalo by sa povedat ze prave vdaka tomu je jeho riesenie najodolnejsie voci problemom ;). Zachovava povodne hodnoty v registroch, dodatocne nastavuje direct flag a vobec cim ma jeho riesenie zaujalo najviac je ze nepouzil instrukcie vacsie ako 2 bajty (cize ziadne konstane hodnoty v operandoch).

3. lll - 36 B -
jediny kto poslal riesenie v intel syntaxi. Bohuzial jeho riesenie mi nefungovalo tj .:
# nasm -f elf -o sort.o sort.asm
# cc -o isort isort.c sort.o
# ./isort 3 1 2
<vrati newline character>
#
Tak neviem ci robim chybu ja alebo urobil ju lll.

4. nejaky v92 - 44 B -
toto je skor len nesutazne ale v zadani som slubil ze vam o nom poviem. Je to skarede pretoze vtedy som nemal potuchy o moznostiach stringovych instrukcii...tymto by som sa chcel podakovat riesitelom ze mi ukazali ako ich pouzivat ;).

Na zaver sa chcem podakovat riesitelom za zaujimave riesenia a ze po pociatocnom vahani investovali svoj cas aenergiu do tejto sutaze v ktorej ukazali ze vedia co je insert sort a asembler ;).

PS:
co urobi:
xorl %ecx,%ecx
mul %ecx
?:

zdrojaky su dostupne na: www.hysteria.sk/v92/contest/isort

potom, ako sa vitaz ohlasi na bhole@blackhole.sk, dostane tricko blackhole a ak bude mat zaujem, tak aj shell na servery + neobmedzeny mail (nieco@blackhole.sk).

tesime sa na dalsie sutaze.v92