Daraxtlar ro'yxati - Conc-tree list

A daraxt daraxti ^[1][2] elementlar ketma-ketligini saqlaydigan va amortizatsiya qilingan ma'lumotlar tuzilmasi O (1) operatsiyalarni qo'shish va oldindan tayyorlash, O (log n) vaqtni qo'shish va olib tashlash va O (log n) vaqtni birlashtirish. Ushbu ma'lumotlar tuzilishi, masalan, funktsional vazifa parallel va ma'lumotlarga parallel dasturlash uchun juda mos keladi va shunga o'xshash asimptotik murakkablikka ega bo'lgan boshqa ma'lumotlar tuzilmalari bilan taqqoslaganda nisbatan sodda.^[1] Daraxtlar ketma-ket chapdan o'ngga takrorlash tartibini talab qilmaydigan ma'lumotlarga parallel operatsiyalar samaradorligini oshirish uchun ishlab chiqilgan,^[3] va ma'lumotlarning keraksiz nusxalaridan saqlanish orqali ushbu operatsiyalardagi doimiy omillarni yaxshilash.^[2] Ortogonal ravishda ular funktsional uslubda ma'lumotlarni samarali to'plash uchun ishlatiladi parallel parallel algoritmlar, ma'lumotlar ro'yxatini qisqartirishning amalga oshirilishi sifatida.^[4] Conc-list - bu parallel dasturiy ta'minot funktsional kamchiliklari, va dastlab tomonidan kiritilgan Qal'a tili.

Amaliyotlar

Daraxtning asosiy ishlashi birlashma. Daraxt daraxtlari quyidagi asosiy ma'lumotlar turlari bo'yicha ishlaydi:

xususiyat Kons[T] {  def chap: Kons[T]  def to'g'ri: Kons[T]  def Daraja: Int  def hajmi: Int}ish sinf Bo'sh[T] uzaytiradi Kons[T] {  def Daraja = 0  def hajmi = 0}ish sinf Yagona[T](elem: T) uzaytiradi Kons[T] {  def Daraja = 0  def hajmi = 1}ish sinf <>[T](chap: Kons[T], to'g'ri: Kons[T]) uzaytiradi Kons[T] {  val Daraja = 1 + matematik.maksimal(chap.Daraja, to'g'ri.Daraja)  val hajmi = chap.hajmi + to'g'ri.hajmi}

The <> turi ichki tugunlarni ifodalaydi va talaffuz qilinadi kons, ilhomlangan :: (the kamchiliklari turi) funktsional ro'yxatlarda, ketma-ket dasturlash uchun ishlatiladi.

O (log n) vaqtidagi birlashma, keyinchalik har qanday ikkita birodar daraxtlar orasidagi darajalarning (ya'ni balandliklarning) farqi bir xil yoki kamroq bo'lishini ta'minlash orqali ishlaydi. AVL daraxtlari. Ushbu o'zgarmas narsa daraxtning balandligi (ildizdan biron bir barggacha bo'lgan eng uzun yo'lning uzunligi) har doim daraxt tarkibidagi elementlar soni bo'yicha logaritmik bo'lishini ta'minlaydi. Birlashtirish quyidagi tarzda amalga oshiriladi:

def konkret(xs: Kons[T], ys: Kons[T]) {  val farq = ys.Daraja - xs.Daraja  agar (matematik.abs(farq) <= 1) yangi <>(xs, ys)  boshqa agar (farq < -1) {    agar (xs.chap.Daraja >= xs.to'g'ri.Daraja) {      val nr = konkret(xs.to'g'ri, ys)      yangi <>(xs.chap, nr)    } boshqa {      val nrr = konkret(xs.to'g'ri.to'g'ri, ys)      agar (nrr.Daraja == xs.Daraja - 3) {        val nr = yangi <>(xs.to'g'ri.chap, nrr)        yangi <>(xs.chap, nr)      } boshqa {        val nl = yangi <>(xs.chap, xs.to'g'ri.chap)        yangi <>(nl, nrr)      }    }  } boshqa {    // nosimmetrik holat  }}

Amortizatsiya qilingan O (1) vaqt qo'shimchalariga (yoki oldindan) yangi ichki tugun turini kiritish orqali erishiladi Qo'shishva uning yordamida balandligi qat'iyan kamayib, daraxtlarning logaritmik uzunlikdagi ro'yxatini kodlash mumkin. Har bir Qo'shish tugun ap quyidagi invariantlarni qondirishi kerak:

1. darajasi ap.left.right darajasidan har doim qat'iy kattaroqdir to'g'ri.

2. Daraxt to'g'ri hech qachon o'z ichiga olmaydi Qo'shish tugunlar (ya'ni u normalangan shaklda, faqat tarkibidan tuzilgan <>, Yagona va Bo'sh).

Ushbu invariantlar yordamida qo'shilish ikkilik sonlarni qo'shishda izomorfdir - bir xil balandlikdagi ikkita qo'shni daraxt doimiy vaqt bilan bog'lanishi mumkin, ko'pi bilan logaritmik tashish operatsiyalari. Bu quyidagi rasmda aks ettirilgan, bu erda element ikkilik raqamga mos keladigan daraxt daraxtiga qo'shiladi:

Daraxt qo'shimchalari ishlashi

Ushbu ikkilik raqamning ifodasi shunga o'xshash sof funktsional tasodifiy kirish ro'yxatlari Okasaki tomonidan,^[5] tasodifiy kirish ro'yxatlari barcha daraxtlarning bo'lishini talab qiladigan farq bilan to'liq ikkilik daraxtlar, ammo daraxtzorlar yanada qulayroq va faqat muvozanatli daraxtlarni talab qiladi. Ushbu qulayroq invariantlar daraxtzorlarga logaritmik vaqt birikmasini saqlashga imkon beradi, tasodifiy kirish ro'yxatlari esa faqat O (n) biriktirishga imkon beradi.

Quyida an qo'shib qo'ying eng yomon usul O (log n) vaqt va amortizatsiya qilingan O (1) vaqt:

ish sinf Qo'shish[T](chap: Kons[T], to'g'ri: Kons[T]) uzaytiradi Kons[T] {  val Daraja = 1 + matematik.maksimal(chap.Daraja, to'g'ri.Daraja)  val hajmi = chap.hajmi + to'g'ri.hajmi}xususiy def qo'shib qo'ying[T](xs: Qo'shish[T], ys: Kons[T]) =  agar (xs.to'g'ri.Daraja > ys.Daraja) yangi Qo'shish(xs, ys)  boshqa {    val zs = yangi <>(xs.to'g'ri, ys)    xs.chap o'yin {      ish ws @ Qo'shish(_, _) => qo'shib qo'ying(ws, zs)      ish ws => agar (ws.Daraja <= xs.Daraja) konkret(ws, zs) boshqa yangi Qo'shish(ws, zs)    }  }}

Shu tarzda qurilgan daraxt daraxti hech qachon O (log n) dan oshmaydi. Qo'shish tugunlari va normal holatga qaytarilishi mumkin (faqat ulardan biri ishlatiladi) <>, Yagona va Bo'sh tugunlarni) O (log n) vaqtida.

Ushbu operatsiyalarning batafsil namoyishi bilan onlayn manbalarda tanishishingiz mumkin,^[6][7] yoki asl daraxt qog'ozida.^[1] Ushbu asosiy operatsiyalar eng yomon holatdagi O (1) ni qo'llab-quvvatlash uchun kengaytirilishi mumkinligi ko'rsatildi deque operatsiyalar,^[2] barcha operatsiyalarning doimiy omillarini oshirish hisobiga O (log n) biriktirish vaqtini chegaralangan holda ushlab turganda.

Adabiyotlar