benim öğrenme Haskell, Haskell makaleler listeleri performans farklılıkları ile ilgili bir kaç okudum ve (dil Ekle)'in diziler.

Bir öğrenci olduğum belli bile performans farkı düşünmeden listeleri kullanın. Geçenlerde ve çok sayıda veri yapısı kütüphaneleri Haskell mevcut bulunan soruşturma başlatıldı.

Birisi veri yapıları bilgisayar bilimi teorisi çok derin gitmeden Listeler, Diziler, Vektörler, seriler arasındaki farkı açıklayabilecek olan var mı?

Ayrıca, başka bir yerine bir veri yapısı kullanmak istiyorsunuz bazı ortak kalıpları vardır?

Ve yararlı olabilir kaçırdığım veri yapıları diğer formları vardır?

Teşekkürler.

Listeler Kaya

En kolay veri yapısı Haskell sıralı veri listesidir

 data [a] = a:[a] | []

Listeler ϴ(1) eksileri ve desen eşleştirme ver. Standart kütüphane, ve bu konuda başlangıcı, kodunuzu çöp gereken yararlı fonksiyonlar tam(foldr,,*map*8).. Listelerkalıcıçok güzel , nam-ı diğer tamamen işlevsel. Haskell listeleri "listeleri coinductive (diğer diller azmak Ara) öyle şeyler" gibi değil

ones :: [Integer]
ones = 1:ones

twos = map ( 1) ones

tenTwos = take 10 twos

harika iş. Sonsuz veri yapıları Kaya.

Haskell listeler çok zorunlu dil olarak kullanımına gibi bir arabirim (tembellik nedeniyle) bulunur. Bu yüzden, yaygın olarak kullanıldıkları anlaşılıyor.

Diğer taraftan

Listeler ile ilk sorun, onlara Endeksi (!!) ϴ(k) zaman, can sıkıcı bir durum alır. Ayrıca, ekler ama Haskell tembel değerlendirme modeli bu olursa eğer tamamen itfa edilmiş olarak kabul edilmesi anlamına gelir, yavaş sürebilir.

Listeler ile ikinci sorun, kötü veri konum. Gerçek işlemci bellek nesneleri birbirine yakın yerleştirilir zaman yüksek sabitler tabi. Yani, C std::vector daha hızlı "snoc" (nesneler koyarak sonunda) daha saf bağlantılı liste veri yapısı bildiğim kadarıyla, kesin olmamakla birlikte bir kalıcı veri yapısı çok daha samimi daha Haskell'ın listeler.

Listeler ile üçüncü sorun, zavallı yer avantajı var. Ekstra işaretçiler demet depolama (sabit faktörü) Yukarı itin.

Dizileri İşlevseldir

Data.Sequence dahili bazı güzel özellikleri var demektir finger trees (ben, bunu bilmek istemezsin biliyorum) dayanmaktadır

1. Tamamen işlevsel. Data.Sequence tamamen kalıcı bir veri yapısıdır.
2. Ağacın başında ve sonunda hızlı erişim lanet olsun. ϴ(1) (amorti) ilk veya son öğeyi almak veya ağaçlar eklemek için. Listeler en hızlı At, Data.Sequence sürekli yavaş en fazla.
3. ϴ(log n) dizisinin orta erişimi. Bu yeni diziler için değerleri ekleme içerir
4. Yüksek kalite API

Diğer taraftan, Data.Sequence veri için fazla bir şey yapmıyor mevkiinde sorun ve sadece sınırlı eserleri koleksiyonları (listeler daha az tembel olduğu için

Diziler kalbi zayıf olanlara göre değil

Diziler CS en önemli veri yapılarından biridir, ama onlar çok iyi tembel saf fonksiyonel bir dünya ile uyum. Diziler ϴ(1) mahallin sabit faktörler/koleksiyon orta erişim ve son derece iyi bir veri sağlar. Ancak, onlar çok iyi Haskell uyması beri, kullanmak için bir ağrı vardır. Aslında geçerli standart kütüphanede farklı dizi türleri çok sayıda vardır. Bu tamamen kalıcı diziler, IO monad için değişken diziler, ST monad için değişken diziler, yukarda ve un-kutulu versiyonları vardır. Daha fazla the haskell wiki kontrol edin

Vektör bir "İyi" Dizi

Data.Vector paket daha yüksek seviyede ve daha temiz API dizi iyilik, sağlar. Ne yaptığınızı bilmek sürece, eğer performans gibi bir dizi ihtiyacınız varsa bu kullanmanız gerekir. -Tabi ki, bazı uyarılar hala veri yapıları yok sadece saf tembel dilde güzel oyun gibi değişken bir dizi uygulamak. Yine de, bazen(1) O performans mı istiyorsun, ve Data.Vector kullanışlı bir paket verir.

Diğer seçenekler vardır

Eğer sen verimli sonuna eklemek için yeteneği ile listeler istiyorsanız, difference list kullanabilirsiniz. Listeler performans batırmak için en iyi örnek başlangıcı String gibi kenarları yumuşatılmış olan [Char] gelen eğilimindedir. Char listeler evimiz var, ama 20 kat C dizeleri daha yavaş sipariş çalıştırmak eğilimindedir, Data.Text ya da çok hızlı kullanmaktan çekinmeyin Data.ByteString. Şu an düşünmüyorum sırası yönelik diğer kütüphaneler vardır eminim.

Sonuç

Haskell listeleri sıralı bir koleksiyon ihtiyacım var � doğru veri yapısı. Listeler kullanımına, listeleri kolayca bu diğer veri yapıları ile toList fonksiyonları kullanarak herhangi bir ile kullanılabilir tüketen fonksiyonları gibi. Daha iyi bir dünyanın başlangıcı tam olarak kullanır ne gibi parametrik olurdu, ama şu anda [] standart kütüphane litre. Yani, listeler (neredeyse) her yerde kesinlikle Tamam.
Tamamen parametrik listenin en sürümleri (ve onları kullanmak için asil) alabilirsiniz

Prelude.map                --->  Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc    --->  Data.Foldable.foldr/foldl/etc
Prelude.sequence           --->  Data.Traversable.sequence
etc

Aslında Data.Traversable tanımlar daha fazla veya daha az herhangi bir şey karşısında evrensel bir API "liste" gibi.

İyi ve tam parametrik kod yazabilirsiniz ancak yine de, çoğumuz değildir ve her tarafa listesi kullanın. Eğer öğrenme ise, şiddetle de öneririm.

EDİT: asla Data.Vector vs Data.Sequence ne zaman kullanılacağını açıkladı. farkındayım yoruma Dayalı Diziler ve Vektörler son derece hızlı indeksleme ve Dilimleme işlemlerini sağlamak, ama temelde geçici () zorunlu veri yapıları vardır. Data.Sequence [] gibi saf fonksiyonel veri yapıları üretmek izin verimliyenieğer eski değerleri değiştirilmiş olsaydı eski değerleri değerleri.

  newList oldList = 7 : drop 5 oldList

eski listeyi değiştirmek değil, ve bunu kopyalamak zorunda değil. Eğer öyleyse oldList inanılmaz uzun değilse bile, bu "değişiklik" çok hızlı olacaktır. Benzer şekilde

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

3000 unsuru yerde newValue ile yeni bir dizi üretecek. Yine eski sırası yok, sadece yeni bir tane oluşturur. Ama, bu çok verimli bir şekilde, O(n sırası uzunluğu olduğu günlük(min(k,k-n)), k dizini sen değiştir. olması demektir

Cant kolayca Vectors Arrays ile yapıyoruz. Olabilirdeğiştirilmişama bu gerçek zorunlu değişiklik ve cant normal Haskell kodu yapılabilir. snoc cons gibi değişiklikler tüm vektör kopya var olun O(n) zaman Vector paketinde işlemleri anlamına gelir. Tek özel durum için bu kullanabilirsiniz kesilebilir sürüm (Vector.Mutable) içinde ST monad (veya IO) ve tüm değişiklikler sadece istediğiniz bir zorunlu dil. İşiniz bittiğinde, size "saf kod ile kullanmak istediğiniz değişmez yapısı dönüşmesi için vektör. freeze

Benim düşüncem eğer bir liste uygun değil Data.Sequence kullanarak varsayılan gerektiğidir. Eğer kullanım desen eğer ST/IO monadlar içinde son derece yüksek performans gerekiyorsa birçok değişiklik yapmak dahil, ya da değil, eğer sadece Data.Vector kullanın.

ST monad bu konuşma şaşkın bırakarak tüm: tüm saf hızlı sopa için bir neden daha güzel Data.Sequence.