jeudi 29 novembre 2007

Fusionner 2 tableaux en les triant

Un peu d'algorithmique, ça fait toujours du bien... La question du jour était "Comment prendre 2 tableaux triés par ordre croissant (de tailles différentes éventuellement), et les fusionner en 1 seul tableau également trié ?". C'était une question d'algo, pas de code. Du coup, j'ai fait une petite fonction en Ruby, appelons la melt, qui fait ça (désolé pour le code pas indenté aujourd'hui, des balises récalcitrantes traînent dans le coin...).

def melt list1, list2
cur1 = 0
cur2 = 0
pt = 0
result = Array.new(list1.size+list2.size)

while ((cur1 < list1.size) and (cur2 < list2.size))
if (list1[cur1] < list2[cur2]) then
result[pt] = list1[cur1]
cur1 +=1
else
result[pt] = list2[cur2]
cur2 +=1
end
pt +=1
end

if cur1 < list1.size then
for i in (cur1...list1.size)
result[pt] = list1[i]
pt += 1
end
elsif cur2 < list2.size then
for i in (cur2...list2.size)
result[pt] = list2[i]
pt += 1
end
end

result

end


Alors c'est du classique qu'on voit à l'école avec les pitits curseurs qui se baladent, tout ça. Puis, par curiosité, j'ai voulu réécrire ce code en "vrai Ruby", soit :

def melt list1, list2
result = list1 + list2
result.sort!
end

Le gain de place me ferait presque rire si je ne m'étais pas tapé l'autre avant... Des méthodes préexistantes, un + sur des tableau : que demande le peuple ? Puis, histoire de rigoler, j'ai voulu comparer le temps d'exécution de chacun...

Time0 = Time.now
for i in (0...1000)
a = [1,2,6]
b = [0,3,6,12]
puts melt(a,b)
end
puts "Temps : #{Time.now - Time0} "


And the winner is................. VRAI RUBY !!!

Avec 0.469 s contre 0.515 s.

La différence n'est pas monstrueuse (mon algo est pas si moisi en fait... Contrairement à mon benchmark !), mais ça justifie le fait de ne surtout pas s'emm3rder d'essayer de faire les choses plus vite que le langage.

0 commentaires: