Halat (veri yapısı) - Rope (data structure)

"Hello_my_name_is_Simon" dizesi üzerine kurulmuş basit bir ip.

Gelen bilgisayar programlama , bir ip veya kordon , bir olan veri yapısı daha küçük oluşan dizeleri verimli depolamak ve çok uzun bir dize işlemek için kullanılır. Örneğin, bir metin düzenleme programı, düzenlenmekte olan metni temsil etmek için bir ip kullanabilir, böylece ekleme, silme ve rastgele erişim gibi işlemler verimli bir şekilde yapılabilir.

Açıklama

Halat, her yaprağın (uç düğüm) bir ip ve bir uzunluğu ("ağırlık" olarak da bilinir) tuttuğu ve ağacın daha yukarısındaki her düğümün sol alt ağacındaki tüm yaprakların uzunluklarının toplamını tuttuğu ikili bir ağaçtır. . İki çocuklu bir düğüm böylece tüm dizgiyi iki parçaya böler: sol alt ağaç dizenin ilk bölümünü depolar, sağ alt ağaç dizenin ikinci bölümünü depolar ve bir düğümün ağırlığı ilk bölümün uzunluğudur.

İp operasyonları için, düğümlerde depolanan dizelerin tipik tahribatsız durumda sabit değişmez nesneler olduğu varsayılır ve bazı yazma üzerine kopyalama davranışına izin verir . Yaprak düğümleri genellikle temel sabit uzunluklu dizeler olarak uygulanır ve artık ihtiyaç kalmadığında serbest bırakma için bir referans sayısı eklenir, ancak diğer çöp toplama yöntemleri de kullanılabilir.

Operasyonlar

Aşağıdaki tanımlarda N ipin uzunluğudur.

Ekle

Tanım:: yeni bir C ₁ ,…, C _i , S ' , C _{i + 1} ,…, C _m dizisi oluşturmak için, s dizesinde i konumunda başlayan S'Insert(i, S’) dizesini ekleyin .

Zaman karmaşıklığı: . ${\ displaystyle O (\ log N)}$

Bu işlem a Split() ve iki Concat() işlemle yapılabilir. Maliyet, üçünün toplamıdır.

Dizin

Şekil 2.1: Bir ipte indeks arama örneği.

Tanım:: iIndex(i) konumundaki karakteri döndür

Zaman karmaşıklığı: ${\ displaystyle O (\ log N)}$

Almak için i -inci karakter, bir başlar özyinelemeli kök düğümden arama:

function index(RopeNode node, integer i)
  if node.weight <= i and exists(node.right) then
    return index(node.right, i - node.weight)
  end
  
  if exists(node.left) then
    return index(node.left, i)
  end
  
  return node.string[i]
end

Örneğin i=10 , sağda gösterilen Şekil 2.1'deki karakteri bulmak için , kök düğümden (A) başlayın, 22'nin 10'dan büyük olduğunu ve bir sol çocuk olduğunu bulun, bu yüzden soldaki çocuğa (B) gidin. 9, 10'dan küçüktür, bu yüzden 10'dan 9'u çıkarın (ayrılıyor i=1 ) ve sağ çocuğa gidin (D). Sonra 6 1'den büyük olduğu ve sol çocuk olduğu için soldaki çocuğa (G) gidin. 2 1'den büyük ve sol çocuk var, o yüzden tekrar soldaki çocuğa git (J). Son olarak 2, 1'den büyüktür, ancak sol alt öğe yoktur, bu nedenle, "na" (yani "a") kısa dizesinin 1. dizinindeki karakter cevaptır.

Concat

Şekil 2.2: İki alt ipin tek bir ipte birleştirilmesi.

Tanım: S ₁ ve S ₂ olmak üzere Concat(S1, S2) iki halatı tek bir halata birleştirin.

Zaman karmaşıklığı: (veya kök ağırlığını hesaplama süresi) ${\ displaystyle O (1)}$${\ displaystyle O (\ log N)}$

Sabit zaman olan sol = S1 ve sağ = S2 ile yeni bir kök düğüm oluşturularak basitçe birleştirme yapılabilir . Ebeveyn düğümün ağırlığı sol çocuk uzunluğuna ayarlanmış S ₁ alacağını, ağaç dengeli ise, zaman. ${\ displaystyle O (\ log N)}$

İp işlemlerinin çoğu dengeli ağaçlar gerektirdiğinden, birleştirme işleminden sonra ağacın yeniden dengelenmesi gerekebilir.

Bölünmüş

Şekil 2.3: Bir ipi ikiye bölmek.

Tanım:: S dizgisini S ₁ ve S ₂ , S ₁ = C ₁ ,…, C _i ve S ₂ = C _{i + 1} ,…, C _{m olmak} üzere iki yeni diziye Split (i, S) bölün .

Zaman karmaşıklığı: ${\ displaystyle O (\ log N)}$

Ele alınması gereken iki durum vardır:

1. Bölme noktası bir dizenin sonundadır (yani bir yaprak düğümün son karakterinden sonra)
2. Bölme noktası, bir dizenin ortasındadır.

İkinci durum, iki yeni yaprak düğüm oluşturmak için diziyi bölünme noktasında bölerek ve ardından iki bileşen dizisinin ebeveyni olan yeni bir düğüm oluşturarak birinciye indirgenir.

Örneğin, Şekil 2.3'te gösterilen 22 karakterli ipi 11 uzunluğunda iki eşit bileşen halatına ayırmak için, alt seviyedeki K düğümünü bulmak için 12. karakteri sorgulayın . K ve G arasındaki bağlantıyı kaldırın . G'nin ebeveynine gidin ve K'nin ağırlığını D' nin ağırlığından çıkarın . Ağaçta yukarı çıkın ve 11. konumu geçen karakterleri kapsayan alt ağaçlara giden tüm sağ bağlantıları , ana düğümlerinden K'nin ağırlığını çıkararak kaldırın ( bu durumda yalnızca düğüm D ve A ). Son olarak, yeni öksüz K ve H düğümlerini bir araya getirerek ve sol düğüm K'nin uzunluğuna eşit ağırlığa sahip yeni bir ana P oluşturarak oluşturun .

İp işlemlerinin çoğu dengeli ağaçlar gerektirdiğinden, ağacın ayrıldıktan sonra yeniden dengelenmesi gerekebilir.

Silme

Tanım: Delete(i, j) : alt dize silmek C _i , ..., C _{i + j - 1} , den s yeni dize oluşturmak üzere C ₁ , ..., C _{i - 1} , C _{i + j} , ..., C _m .

Zaman karmaşıklığı: . ${\ displaystyle O (\ log N)}$

Bu işlem iki Split() ve bir Concat() işlemle yapılabilir. İlk olarak, ipi sırasıyla i- inci ve i + j -ci karakterlere bölerek üçe bölün , bu da silinecek dizeyi ayrı bir düğümde çıkarır. Ardından diğer iki düğümü birleştirin.

Bildiri

Tanım:: C _i ,…, C _{i + j - 1}Report(i, j) dizesini çıktılar .

Zaman karmaşıklığı: ${\ displaystyle O (j + \ log N)}$

Dize bildirmek için C _i , ..., C _{i + j - 1} , düğüm bulmak u içerdiğini C _i ve weight(u) >= j ve ardından çapraz T düğüm başlayan u . Çıkış Cı _i , ..., Cı- _{i + j, 1 -} Bir yaparak içinde sipariş geçişi arasında T düğümünde başlangıç u .

Monolitik dizilerle karşılaştırma

Avantajlar:

• Halatlar, işlemlerin zaman karmaşıklığına O (n) sahip olduğu monolitik dize dizilerine göre metnin çok daha hızlı eklenmesini ve silinmesini sağlar.
• Halatlar çalıştırıldığında O (n) ekstra bellek gerektirmez (diziler kopyalama işlemleri için buna ihtiyaç duyar).
• Halatlar, büyük bitişik bellek alanları gerektirmez.
• İşlemlerin yalnızca tahribatsız sürümleri kullanılırsa, halat kalıcı bir veri yapısıdır . Metin düzenleme programı örneği için bu, birden çok geri alma düzeyi için kolay bir desteğe yol açar .

Dezavantajları:

• Çalıştırılmadığında, esas olarak ana düğümleri depolamak için daha fazla genel alan kullanımı. Toplam belleğin ne kadarının bu kadar ek yük olduğu ve ne kadar uzun veri parçalarının dizeler olarak işlendiği arasında bir denge vardır. Yukarıdaki örnek şekillerdeki dizeler, modern mimariler için gerçekçi olmayan bir kısadır. Ek yük her zaman O (n) 'dır, ancak sabit keyfi olarak küçük yapılabilir.
• Ekstra depolama alanını yönetmek için süreyi artırın
• Kaynak kodunun artan karmaşıklığı; daha fazla hata riski

Bu tablo , ip ve halat uygulamalarının ham hızlarını değil , algoritmik özelliklerini karşılaştırmaktadır . Dizi tabanlı dizelerin ek yükü daha küçüktür, bu nedenle (örneğin) birleştirme ve bölme işlemleri küçük veri kümelerinde daha hızlıdır. Bununla birlikte, dizi tabanlı dizeler daha uzun dizeler için kullanıldığında, karakter eklemek ve silmek için zaman karmaşıklığı ve bellek kullanımı kabul edilemeyecek kadar büyük hale gelir. Buna karşılık, bir halat veri yapısı, veri boyutundan bağımsız olarak istikrarlı bir performansa sahiptir. Ayrıca, ipler ve diziler için uzay karmaşıklığının her ikisi de O (n) 'dir. Özetle, veriler büyük olduğunda ve sık sık değiştirildiğinde halatlar tercih edilir.

Ayrıca bakınız

• Sedir "neredeyse kurulduğu günden beri" ipleri kullanılan programlama ortamı,
• Model T enfilade 1970'lerin başlarından itibaren, benzer bir veri yapısı.
• Aynı konumun yakınında kümelenmiş verimli ekleme ve silme işlemlerine izin veren, metin düzenleyicilerde yaygın olarak kullanılan bir veri yapısı olan boşluk arabelleği
• Parça tablosu , metin düzenleyicilerde yaygın olarak kullanılan başka bir veri yapısı

Referanslar

Dış bağlantılar

• Boehm Çöp Toplayıcı kitaplığındaki halatların "C kabloları" uygulaması
• Halatlar için SGI C ++ spesifikasyonu (STLPort ve libstdc ++ tarafından desteklenir )
• C # için halatlar
• Common Lisp için ipler
• Java için Halatlar
• JavaScript için ipler
• Limbo için Halatlar
• Nim için halatlar
• OCaml için halatlar
• Python için pyropes
• Smalltalk için Halatlar
• Swift için SwiftRope
• Rust için "Ropey"