Neden iki kodum çok farklı çalışıyor? (Haskell, Birleştirme Sıralaması)

Question

Birleştirme türü (Haskell) için bir kod yazıyordum.

İki listeyi siparişe göre birleştiren işlev hakkında bir sorum var.

(yani [1,4,7] [2,5,6] -> [1,2,4,5,6,7])

Bu orijinal kodudur. (Xs, ys parametreleri ve zs bir akümülatör olarak düzenlenmiştir.)

msort4 [] ys zs = zs ++ ys 
msort4 xs [] zs = zs ++ xs 
msort4 allx@(x:xs) ally@(y:ys) zs 
| x <= y = msort4 xs ally (zs ++ [x]) 
| otherwise = msort4 allx ys (zs ++ [y]) 

Bu İnternet'te bulduğum bir kod atıfta sonra yazdığı ikinci kodudur.

msort4 [] ys = ys 
msort4 xs [] = xs 
msort4 allx@(x:xs) ally@(y:ys) 
| x <= y = x :msort4 xs ally 
| otherwise = y : msort4 allx ys 

Sadece bu küçük farkla, kodum çok gelişti.

Yaklaşık 500 kelimelik bir listeyi sıralıyorum ve orijinal kodumun yaklaşık 2,5 saniyeye ihtiyacı var, ancak yeni olanı 0,4 saniye içinde ortalamasını sıralıyor.

Niçin benim gibi çok yavaş görünse de, çevrimiçi olanın çok daha hızlı olmasına rağmen, neden bu kadar yavaş olduğunu merak ediyorum. (Benimkinin daha hızlı olacağını düşündüm çünkü benimkinin ileri geri gitmesi gerekmiyor.)

Şimdiden teşekkürler.

Answer 1

prepending (:) bir listeye O (1), (++), n, sol listesinin bir uzunluğu O (n) zs büyük olsun tüm listeyi yana hareket ettirmek zorunda

her seferinde sadece bir eleman eklemek için [x]