Dinamik dizi - Dynamic array

Dinamik bir dizinin sonuna geometrik genişletme kullanılarak birkaç değer eklenir. Gri hücreler, genişletme için ayrılmış alanı gösterir. Çoğu ekleme hızlıdır (sabit zaman), bazıları ise yeniden ayırma ihtiyacı nedeniyle yavaştır (Θ (n) kaplumbağalarla etiketlenmiş zaman). mantıksal boyut ve kapasite son dizinin

İçinde bilgisayar Bilimi, bir dinamik dizi, büyütülebilir dizi, yeniden boyutlandırılabilir dizi, dinamik tablo, değiştirilebilir diziveya dizi listesi bir rasgele erişim, değişken boyutlu liste veri yapısı bu, öğelerin eklenmesine veya kaldırılmasına izin verir. Birçok modern ana programlama dilinde standart kitaplıklar ile sağlanır. Dinamik diziler statik bir sınırın üstesinden gelir diziler tahsisatta belirtilmesi gereken sabit bir kapasiteye sahip olan.

Dinamik bir dizi ile aynı şey değildir dinamik olarak tahsis edilmiş dizi, bir dizi dizi tahsis edildiğinde boyutu sabittir, ancak dinamik bir dizi böyle bir sabit boyutlu diziyi arka uç olarak kullanabilir.[1]

Sınırlı boyutlu dinamik diziler ve kapasite

Basit bir dinamik dizi, tipik olarak hemen gereken öğelerin sayısından daha büyük olan sabit boyutlu bir dizi tahsis edilerek oluşturulabilir. Dinamik dizinin öğeleri, temeldeki dizinin başlangıcında bitişik olarak depolanır ve temeldeki dizinin sonuna doğru kalan konumlar ayrılır veya kullanılmaz. Öğeler dinamik bir dizinin sonuna eklenebilir. sabit zaman ayrılmış alanı kullanarak, bu alan tamamen tüketilene kadar. Tüm alan tüketildiğinde ve ek bir öğe ekleneceği zaman, temeldeki sabit boyutlu dizinin boyutunun artırılması gerekir. Tipik olarak yeniden boyutlandırma pahalıdır çünkü yeni bir temel dizi tahsis etmeyi ve orijinal diziden her bir öğeyi kopyalamayı içerir. Yeniden boyutlandırma gerekmediğinden, öğeler dinamik bir dizinin sonundan sabit zamanda kaldırılabilir. Dinamik dizi içeriği tarafından kullanılan eleman sayısı, mantıksal boyut veya boyut, temeldeki dizinin boyutu dinamik dizinin boyutu olarak adlandırılırken kapasite veya fiziksel boyut, bu, verilerin yerini değiştirmeden mümkün olan maksimum boyuttur.[2]

Sabit boyutlu bir dizi, maksimum mantıksal boyutun sabit olduğu (örneğin spesifikasyona göre) veya dizi ayrılmadan önce hesaplanabildiği uygulamalarda yeterli olacaktır. Aşağıdaki durumlarda dinamik bir dizi tercih edilebilir:

  • dizi ayrılmadan önce maksimum mantıksal boyut bilinmiyor veya hesaplanması zor
  • bir spesifikasyon tarafından verilen maksimum mantıksal boyutun değişme olasılığı olduğu düşünülmektedir
  • Dinamik bir diziyi yeniden boyutlandırmanın amortize edilmiş maliyeti, performansı veya yanıt verebilirliği önemli ölçüde etkilemez

Geometrik genişleme ve amorti edilmiş maliyet

Birçok kez yeniden boyutlandırma maliyetinden kaçınmak için dinamik diziler, boyut olarak iki katına çıkarılması gibi büyük miktarda yeniden boyutlandırılır ve ayrılan alanı gelecekteki genişletmeler için kullanır. Sonuna bir eleman ekleme işlemi şu şekilde çalışabilir:

işlevi insertEnd(dynarray a, element e)    Eğer (a.boyut == a.kapasite)        // a'yı mevcut kapasitesinin iki katına yeniden boyutlandırın:        a.kapasite ← a.kapasite * 2         // (içeriği buradan yeni hafıza konumuna kopyalayın)    a[a.boyut] ← e    a.boyut ← a.boyut + 1

Gibi n elemanlar eklenir, kapasiteler bir geometrik ilerleme. Diziyi herhangi bir sabit orantı ile genişletmek a eklemeyi sağlar n elementler alır Ö(n) toplam süre, yani her ekleme işlemi amortisman sabit zaman. Birçok dinamik dizi, boyutu, kapasitenin% 30'u gibi belirli bir eşiğin altına düşerse, temeldeki depolamanın bir kısmını serbest bırakır. Bu eşik kesinlikle 1 / 'den küçük olmalıdıra sağlamak için histerezis (tekrar tekrar büyümeyi ve küçülmeyi önlemek için sabit bir bant sağlayın) ve amortize edilmiş sabit maliyetle karışık ekleme ve çıkarma sıralarını destekler.

Dinamik diziler, öğretirken yaygın bir örnektir amortisman analizi.[3][4]

Büyüme faktörü

Dinamik dizi için büyüme faktörü, bir uzay-zaman değiş tokuşu ve bellek ayırıcının kendisinde kullanılan algoritmalar dahil olmak üzere çeşitli faktörlere bağlıdır. Büyüme faktörü için a, ekleme işlemi başına ortalama süre hakkında a/(a−1), boşa harcanan hücrelerin sayısı yukarıda (a−1)n[kaynak belirtilmeli ]. Bellek ayırıcı bir ilk uyum tahsisi algoritma, ardından büyüme faktörü değerleri a = 2 önemli miktarda bellek hala kullanılabilir olsa bile dinamik dizi genişletmenin belleğin tükenmesine neden olabilir.[5] İdeal büyüme faktörü değerleriyle ilgili çeşitli tartışmalar yapıldı. altın Oran 1.5 değerinin yanı sıra.[6] Ancak birçok ders kitabı, a = 2 basitlik ve analiz amaçları için.[3][4]

Aşağıda birkaç popüler uygulama tarafından kullanılan büyüme faktörleri verilmiştir:

UygulamaBüyüme faktörü (a)
Java Dizi Listesi[1]1.5 (3/2)
Python PyListObject[7]~ 1.125 (n + n >> 3)
Microsoft Visual C ++ 2013[8]1.5 (3/2)
G ++ 5.2.0[5]2
Clang 3.6[5]2
Facebook çılgınlığı / FBVector[9]1.5 (3/2)
Pas Vec[10]2

Verim

Liste veri yapılarının karşılaştırılması
Bağlantılı listeDiziDinamik diziDengeli ağaçRastgele erişim listesiHashed dizi ağacı
EndekslemeΘ (n)Θ (1)Θ (1)Θ (günlük n)Θ (günlük n)[11]Θ (1)
Ekle / sil başlangıçtaΘ (1)YokΘ (n)Θ (günlük n)Θ (1)Θ (n)
Ekle / sil sonundaΘ (1) en son eleman biliniyor;
Θ (n) en son ne zaman öğe bilinmiyor		YokΘ (1) amortismanΘ (günlük n)Yok [11]Θ (1) amortisman
Ekle / sil ortadaarama süresi + Θ (1)[12][13]YokΘ (n)Θ (günlük n)Yok [11]Θ (n)
Boş alan (ortalama)Θ (n)0Θ (n)[14]Θ (n)Θ (n)Θ (√n)

Dinamik dizi, öğe eklemek ve kaldırmak için yeni işlemlerin eklenmesiyle bir diziye benzer bir performansa sahiptir:

  • Değeri belirli bir endekste alma veya ayarlama (sabit süre)
  • Sırayla öğeler üzerinde yineleme (doğrusal zaman, iyi önbellek performansı)
  • Dizinin ortasına bir öğe ekleme veya silme (doğrusal zaman)
  • Dizinin sonuna bir öğe ekleme veya silme (sabit amortisman süresi)

Dinamik diziler, iyi de dahil olmak üzere dizilerin birçok avantajından yararlanır. referans yeri ve veri önbelleği kullanım, kompaktlık (düşük bellek kullanımı) ve rasgele erişim. Genellikle boyut ve kapasite hakkında bilgi depolamak için yalnızca küçük bir sabit ek yüke sahiptirler. Bu, dinamik dizileri oluşturmak için çekici bir araç haline getirir önbellek -arkadaş canlısı veri yapıları. Bununla birlikte, referans semantiğini zorlayan Python veya Java gibi dillerde, dinamik dizi genellikle gerçek verileri depolamayacaktır, bunun yerine Referanslar hafızanın diğer alanlarında bulunan verilere. Bu durumda, dizideki öğelere sırayla erişmek aslında birden çok bitişik olmayan bellek alanına erişimi içerecektir, bu nedenle bu veri yapısının önbellek dostu olmasının birçok avantajı kaybolur.

Nazaran bağlantılı listeler dinamik diziler daha hızlı indekslemeye (doğrusal zamana karşı sabit zamana karşı) ve tipik olarak daha hızlı referans yerelliği nedeniyle daha hızlı yinelemeye sahiptir; bununla birlikte, dinamik dizilerin rastgele bir konuma yerleştirilmesi veya silinmesi için doğrusal zaman gerekir, çünkü takip eden tüm öğelerin taşınması gerekir, oysa bağlantılı listeler bunu sabit zamanda yapabilir. Bu dezavantaj, boşluk tamponu ve katmanlı vektör altında tartışılan varyantlar Varyantlar altında. Ayrıca, oldukça parçalanmış bellek bölgesinde, büyük bir dinamik dizi için bitişik alan bulmak pahalı veya imkansız olabilir, oysa bağlantılı listeler tüm veri yapısının bitişik olarak depolanmasını gerektirmez.

Bir dengeli ağaç hem dinamik dizilerin hem de bağlantılı listelerin tüm işlemlerini makul ölçüde verimli bir şekilde sağlarken bir listeyi depolayabilir, ancak hem sondaki ekleme hem de liste üzerindeki yineleme, bitişik olmayan depolama nedeniyle teoride ve pratikte dinamik bir diziden daha yavaştır. ağaç geçişi / manipülasyon ek yükü.

Varyantlar

Boşluk tamponları dinamik dizilere benzer, ancak aynı rasgele konumun yakınında kümelenmiş verimli ekleme ve silme işlemlerine izin verir. Biraz deque uygulamalar kullanır dizi dizileri, sadece bir uç yerine her iki uçta da amorti edilmiş sabit zamanlı ekleme / çıkarmaya izin verir.

Goodrich[15] adlı dinamik bir dizi algoritması sundu katmanlı vektörler O (n1 / k) dizinin herhangi bir yerinden ekleme ve silme performansı ve O (k) get ve set, burada k ≥ 2 sabit bir parametredir.

Hashed dizi ağacı (HAT), Sitarski tarafından 1996 yılında yayınlanan bir dinamik dizi algoritmasıdır.[16] Hashed dizi ağacı israf sırası n1/2 depolama alanı miktarı, burada n, dizideki öğe sayısıdır. Algoritma, karma bir dizi ağacının sonuna bir dizi nesne eklerken O (1) amortisman performansına sahiptir.

1999 tarihli bir makalede,[17] Brodnik vd. sadece n'yi boşa harcayan katmanlı bir dinamik dizi veri yapısını tanımlayın1/2 için alan n zamanın herhangi bir noktasında elemanlar ve operasyonların amortize edilmiş sabit zaman olarak kalması için herhangi bir dinamik dizinin bu kadar alanı boşa harcaması gerektiğini gösteren daha düşük bir sınırı kanıtlarlar. Ek olarak, tamponun büyütülmesi ve küçülmesinin sadece amorti etmekle kalmayıp, aynı zamanda en kötü durumda sabit süreyi de amorti ettiği bir varyant sunarlar.

Bagwell (2002)[18] dinamik bir dizi uygulamaya uyarlanabilen VList algoritmasını sundu.

Dil desteği

C ++ 's std :: vektör ve Pas, paslanma 's std :: vec :: Vec dinamik dizilerin uygulamalarıdır. Dizi Listesi[19] ile verilen sınıflar Java API ve .NET Framework.[20]

Genel Liste <> .NET Framework 2.0 sürümüyle sağlanan sınıf da dinamik dizilerle uygulanır. Smalltalk 's OrderedCollection dinamik bir başlangıç ​​ve bitiş indeksine sahip dinamik bir dizidir, birinci elemanın da O (1) kaldırılmasını sağlar.

Python 's liste veri türü uygulaması dinamik bir dizidir.

Delphi ve D Dinamik dizileri dilin çekirdeğine uygulayın.

Ada 's Ada.Containers.Vectors genel paket, belirli bir alt tür için dinamik dizi uygulaması sağlar.

Gibi birçok komut dosyası dili Perl ve Yakut yerleşik olarak dinamik diziler sunar ilkel veri türü.

Çeşitli platformlar arası çerçeve, dinamik dizi uygulamaları sağlar. C, dahil olmak üzere CFArray ve CFMutableArray içinde Çekirdek Vakfı, ve GArray ve GPtrArray içinde GLib.

Ortak Lisp yerleşik yapılandırmaya izin vererek yeniden boyutlandırılabilir vektörler için temel bir destek sağlar dizi olarak yazın ayarlanabilir ve yerleştirme yeri doldurma işaretçisi.

Referanslar

  1. ^ a b Örneğin bkz. OpenJDK 6'dan java.util.ArrayList sınıfının kaynak kodu.
  2. ^ Lambert, Kenneth Alfred (2009), "Fiziksel boyut ve mantıksal boyut", Python'un Temelleri: İlk Programlardan Veri Yapılarına, Cengage Learning, s. 510, ISBN  978-1423902188
  3. ^ a b Goodrich, Michael T.; Tamassia, Roberto (2002), "1.5.2 Genişletilebilir Dizi Uygulamasını Analiz Etmek", Algoritma Tasarımı: Temeller, Analizler ve İnternet Örnekleri, Wiley, s. 39–41.
  4. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "17.4 Dinamik tablolar". Algoritmalara Giriş (2. baskı). MIT Press ve McGraw-Hill. s. 416–424. ISBN  0-262-03293-7.
  5. ^ a b c "C ++ STL vektörü: tanım, büyüme faktörü, üye fonksiyonları". Arşivlenen orijinal 2015-08-06 tarihinde. Alındı 2015-08-05.
  6. ^ "vektör büyüme faktörü 1,5". comp.lang.c ++. denetlenir. Google Toplulukları.
  7. ^ Nesne uygulamasını listeleyin github.com/python/cpython/ adresinden, 2020-03-23 ​​alındı.
  8. ^ Brais, Hadi. "C ++ STL Vektörünün Kesilmesi: Bölüm 3 - Kapasite ve Boyut". Mikromistralar. Alındı 2015-08-05.
  9. ^ "facebook / çılgınlık". GitHub. Alındı 2015-08-05.
  10. ^ "pas-dil / pas". GitHub. Alındı 2020-06-09.
  11. ^ a b c Chris Okasaki (1995). "Tamamen İşlevsel Rastgele Erişim Listeleri". Yedinci Uluslararası Fonksiyonel Programlama Dilleri ve Bilgisayar Mimarisi Konferansı Bildirileri: 86–95. doi:10.1145/224164.224187.
  12. ^ 1. Gün Açılış Konuşması - Bjarne Stroustrup: C ++ 11 Stili -de Yerli 2012 açık channel9.msdn.com 45. dakikadan veya 44. folyodan
  13. ^ Sayı hesaplama: Neden ASLA kodunuzda bağlantılı liste kullanmamalısınız? -de kjellkod.wordpress.com
  14. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Optimal Zaman ve Mekanda Yeniden Boyutlandırılabilir Diziler (Teknik Rapor CS-99-09) (PDF), Bilgisayar Bilimleri Bölümü, Waterloo Üniversitesi
  15. ^ Goodrich, Michael T.; Kloss II, John G. (1999), "Katmanlı Vektörler: Sıralamaya Dayalı Diziler için Verimli Dinamik Diziler", Algoritmalar ve Veri Yapıları Çalıştayı, Bilgisayar Bilimleri Ders Notları, 1663: 205–216, doi:10.1007/3-540-48447-7_21, ISBN  978-3-540-66279-2
  16. ^ Sitarski, Edward (Eylül 1996), "HAT'ler: Hashing uygulanmış dizi ağaçları" Algoritma Yolu Dr. Dobb's Journal, 21 (11)
  17. ^ Brodnik, Andrej; Carlsson, Svante; Sedgewick, Robert; Munro, JI; Demaine, ED (1999), Optimum Zaman ve Uzayda Yeniden Boyutlandırılabilir Diziler (PDF) (Teknik Rapor CS-99-09), Bilgisayar Bilimleri Bölümü, Waterloo Üniversitesi
  18. ^ Bagwell, Phil (2002), Hızlı Fonksiyonel Listeler, Karma Listeler, Deques ve Değişken Uzunluk Dizileri, EPFL
  19. ^ Javadoc üzerinde Dizi Listesi
  20. ^ ArrayList Sınıfı

Dış bağlantılar