Gelen IT , spesifik olarak algoritmik bir atlama listesi ya da liste geçitler ya da atlama listesi a, veri yapısı göre, olasılıksal bağlı listeler paralel. İşlemlerinin çoğu, yüksek olasılıkla O (log n ) zamanında gerçekleştirilir; burada n , listede bulunan öğe sayısıdır.
Atlama listeleri tarafından icat edildi William Pugh ilk olarak 1989 yılında bir teknik raporda sunulan ve daha sonra 1990 yazar bir yayında sunulan, onun teknik rapor ile karşılaştırır içinde dengeli ikili arama ağaçları , yazıyor:
Atlama listeleri, birçok uygulama için tercih edilen uygulama yöntemi olarak dengeli ağaçların yerini alması muhtemel görünen olasılıksal bir veri yapısıdır. Atlama listesi algoritmaları, dengeli ağaçlarla aynı asimptotik beklenen zaman sınırlarına sahiptir ve daha basit, daha hızlıdır ve daha az yer kullanır.''
( Atlama listeleri , birçok uygulama için tercih edilen bir uygulama yöntemi olarak dengeli ağaçlardan (arama ikili dosyaları) daha iyi performans gösteren bir veri yapısıdır. Atlama listesi algoritmaları , dengeli şaftlarla aynı beklenen asimptotik karmaşıklığa sahiptir ve daha basit, daha hızlıdır ve daha az bellek kullanır)
Bir atlama listesi , sıralanmış bir bağlantılı listenin geliştirilmiş hali olarak sunulur . Listedeki aramanın birçok öğeyi "atlayabilmesi" ( İngilizce'yi atlamak için ) için rastgele eklenen ileriye dönük ek işaretçiler içerir .
Atlama listesi organize edilmektedir katmanları . En alttaki katman, yalnızca standart bir bağlantılı listedir . Her bir üst katman i +1, alt katmanlar 1,…, i'yi geçmek için bir “ hızlı şerit ”tir . i katmanında bulunan bir öğenin , i +1 katmanının bir parçası olma olasılığı p sabittir . Ortalama olarak, her öğe 1 / (1- p ) katmanlarında görünür ve en uzun öğe (genellikle diğerlerinden daha küçük bir kukla öğe) tüm katmanlarda görünür. Atlama listesi, O (log 1 / p n ) katmanlarını içerir; burada n , toplam öğe sayısıdır.
Aşağıdaki örnek, 4 katmanlı 10 öğe içeren bir atlama listesini göstermektedir:
couche 4 1 couche 3 1-----4---6 couche 2 1---3-4---6-----9 couche 1 1-2-3-4-5-6-7-8-9-10Arama, en üst katmandaki en küçük öğeyle başlar. Ziyaret edilen her katman için, aranan elemana eşit veya daha küçük olan son elemana ulaşana kadar bağlantılardan geçiyoruz . Yani, bu eleman istenen değerden kesinlikle düşükse, bir sonraki katmana dikey olarak ineriz. Her katmandaki adım sayısı beklentisi 1/ p'dir . Araştırmanın toplam maliyeti ; p'yi sabit olarak kabul edersek bu tutar .
Bu parametrenin p değeri ayarlanarak, arama süresi ile tüketilen bellek alanı arasında bir uzlaşma elde edilir. p = 0 için, atlama listesi standart bir bağlantılı listedir (yalnızca bir katman). p 1'e ne kadar yakınsa, o kadar fazla katman vardır.
Ekleme ve silme, bağlantılı bir listede olduğu gibi uygulanır, ancak "en iyi" öğelerin birden çok katmana eklenmesi ve silinmesi gerekir.
Onun tarafından olasılıksal doğası , bu veri yapısı yok değil vermek örneğin gibi kötü durumlarda aynı garantileri dengeli ağaçlar . Gerçekten de, rastgele düzenlemenin çok dengesiz bir yapı oluşturmuş olması pek olası değildir, ancak yine de mümkündür.
Aslında, bu listeler pratikte çok iyi çalışır ve uygulanmasının, deterministik ağaç yeniden dengeleme eşdeğerlerinden daha kolay olduğu söylenir. Gerçek uygulamalarda, zaman ve uzaydaki performanslarının B ağaçlarından daha düşük olduğunu ölçtük . Bu, önbelleklerdeki verilerin yakınlığı gibi sorunlardan kaynaklanmaktadır.
Deterministik atlama listelerinde atlanacak elemanlar rastgele değil deterministik bir şekilde seçilir.