Soru Scala'da Array ve List arasındaki fark


Hangi durumlarda Array (Buffer) ve List (Buffer) kullanmalıyım. Bildiğim tek bir fark, dizilerin değişken olmaması ve listelerin kovaryant olması. Peki performans ve diğer bazı özellikler hakkında ne düşünüyorsunuz?


104
2018-04-26 11:03


Menşei




Cevaplar:


Ölümsüz Yapıları

Scala List Scala'da böyle temel bir yapı olan, değişmez bir özyinelemeli veri yapısıdır. Array (aslında bu değişken - değişmez analog arasında Array olduğu IndexedSeq).

Java arkaplanından geliyorsanız, o zaman açık olan paraleldir. LinkedList üzerinde ArrayList. Eski genellikle sadece olan listeler için kullanılır geçilen (ve boyutu önceden bilinmemektedir), ikincisi ise bilinen bir boyuta (veya maksimum boyuta) sahip olan veya hızlı rastgele erişim önemli.

Değişebilir yapılar

ListBuffer a'ya sabit zamanlı bir dönüşüm sağlar List kullanmak için sebep sadece ListBuffer Böyle bir dönüşüm gerekirse.

Bir scala Array bir Java dizisi ile JVM üzerinde uygulanmalıdır ve dolayısıyla Array[Int] çok daha fazla performans gösterebilir ( int[]) bir List[Int] (Scala'nın en yeni versiyonlarını kullanmıyorsanız, @specialized özellik).

Ancak, bence kullanımı ArrayScala'daki s en az düzeyde tutulmalıdır çünkü gerçekten gerekli ilkel türüyle dizinizin gerçekten desteklenip desteklenmeyeceğine karar vermek için başlık altında neler olup bittiğini bilmeniz gerektiği gibi hissettirirsiniz veya bir sarıcı türü olarak kutulanabilir.


124
2018-04-26 11:17



ayrıca bkz stackoverflow.com/questions/3213368/... ve stackoverflow.com/questions/2481149/...  Diziler için "eşittir" tanımı, aynı diziye başvurmalarıdır. - oluies


Zaten yayınlanan cevaplara ek olarak, bazı özellikler burada.

Bir süre Array[A] kelimenin tam anlamıyla bir Java dizisidir List[A] değişmez bir veri yapısıdır. Nil (boş liste) veya bir çift oluşur (A, List[A]).

Performans farklılıkları

                          Array  List
Access the ith element    O(1)   O(i)
Delete the ith element    O(n)   O(i)
Insert an element at i    O(n)   O(i)
Reverse                   O(n)   O(n)
Concatenate (length m,n)  O(n+m) O(n)
Count the elements        O(1)   O(n)

Bellek farklılıkları

                          Array  List
Get the first i elements  O(i)   O(i)
Drop the first i elements O(n-i) O(1)
Insert an element at i    O(n)   O(i)
Reverse                   O(n)   O(n)
Concatenate (length m,n)  O(n+m) O(n)

Hızlı rastgele erişime ihtiyacınız yoksa veya öğeleri saymanız gerekmedikçe, List birinden daha iyidir Array.


111
2018-04-26 12:44



Bu Os listeyi kopyalamak için zaman ayırmak zorunda mı? Testi böyle yaptığınızı varsayalım: list = list.drop(i). Ya da, kaputun arkasında biraz sihir var mı?
Bu, gerektiğinde kopyalama listelerini ve dizileri hesaba katar. Gibi şeyler unutmayın drop Asla düşmeyen listenin bir kısmını kopyalamaya gerek yoktur. Örneğin. (x::xs).drop(1) tam olarak xsdeğil, bir "kopyası" xs. - Apocalisp
Bu asimptotiklerin Scala ile hiçbir ilgisi yoktur. C'deki aynı veri yapısı, tam olarak sabit faktörlere kadar hızlı olacaktır. - Apocalisp
@Apocalisp Bir referansınız var mı veya bu bilgileri hangi koşullar altında belirlediniz? - Phil
@Phil Bunlar asimtotiktir, ölçüm değildir. Her koşulda doğru tutacaklar. - Apocalisp


Bir Dizi değişkendir, yani her indeksin değerlerini değiştirebilirken, bir Liste (varsayılan olarak) değişmezdir, yani her değişiklik yaptığınızda yeni bir liste oluşturulur. Çoğu durumda, değişmez veri tipleri ile çalışmak daha "işlevsel" bir stildir ve muhtemelen bir Liste gibi yapıları kullanmayı denemeniz gerekir. yield, foreach, match ve benzeri

Performans karakteristiği için, bir Array elemanlara rasgele erişimle daha hızlıdır, oysa yeni öğeler için önpending (ekleme) yapılırken bir Liste daha hızlıdır. Onları tekrarlamak karşılaştırılabilir.


15
2018-04-26 11:19



ListBuffer değişebilir - oxbow_lakes
@leonm - apoller, OP'nin sadece Buffer sınıfları hakkında sorduğunu sanmıştım, onların da "normal" olanları sorduklarını fark ettim! - oxbow_lakes
ArrayBuffer'in yalnızca nesneyi (ortalama olarak iki kez) yeni bir diziye kopyalaması gerektiğinde, listeler bir Listeye (veya bir ListBuffer öğesine öğe eklemek) eklemek yerine bir ArrayBuffer'a eklemek genellikle daha hızlıdır. . İki kopya genellikle tek bir nesne oluşturma işleminden daha hızlıdır, bu yüzden ArrayBuffer eki genellikle List prepend'i vurur. - Rex Kerr
@oxbow_lakes hayır endişe :-) - leonm
dizi, listeden çok daha hızlı çalışır iterate over, önbellek yüzünden - Bin