Kesirli kaskad - Fractional cascading - Wikipedia

Yilda Kompyuter fanlari, kasrli kaskad ning ketma-ketligini tezlashtirish uchun usuldir ikkilik qidiruvlar tegishli ma'lumotlar tuzilmalari ketma-ketligidagi bir xil qiymat uchun. Ketma-ketlikdagi birinchi ikkilik qidirish, ikkilik izlash uchun standart bo'lgani kabi, logaritmik vaqtni oladi, ammo ketma-ketlikdagi ketma-ket qidiruvlar tezroq bo'ladi. Fraksiyonel kaskadning asl nusxasi, tomonidan ikki hujjatda kiritilgan Chazelle va Gibalar 1986 yilda (Chazelle & Guibas 1986a; Chazelle & Guibas 1986b ), kelib chiqishi kaskadli g'oyani birlashtirdi oraliq qidirish ma'lumotlar tuzilmalari Lueker (1978) va Uillard (1978), kelib chiqqan fraksiyonel namuna olish g'oyasi bilan Shazelle (1983). Keyinchalik mualliflar fraksiyonel kaskadning yanada murakkab shakllarini joriy qildilar, bu ma'lumotlar tuzilishini saqlashga imkon beradi, chunki ma'lumotlar diskret qo'shish va o'chirish hodisalari ketma-ketligi bilan o'zgaradi.

Misol

Kesirli kaskadning oddiy misoli sifatida quyidagi muammoni ko'rib chiqing. Biz kirish to'plami sifatida berilgan k buyurtma qilingan ro'yxatlar L_men umumiy uzunligi Σ | bo'ladigan sonlarning soniL_men| barcha ro'yxatlar nva ularni qayta ishlashi kerak, shunda biz so'rovlar qiymatini ikkilik izlashimiz mumkin q har birida k ro'yxatlar. Masalan, bilan k = 4 va n = 17,

L₁ = 24, 64, 65, 80, 93

L₂ = 23, 25, 26

L₃ = 13, 44, 62, 66

L₄ = 11, 35, 46, 79, 81

Ushbu qidiruv muammosining eng oddiy echimi - bu har bir ro'yxatni alohida saqlashdir. Agar shunday qilsak, bo'sh joy O (n), ammo so'rovni bajarish vaqti O (k log (n/k)), chunki har birida alohida ikkilik qidiruvni amalga oshirishimiz kerak k ro'yxatlar. Ushbu tuzilmani so'rash uchun eng yomon holat har birida sodir bo'ladi k ro'yxatlar teng o'lchamga ega n/k, shuning uchun har biri k so'rovda ishtirok etgan ikkilik qidiruv O vaqtini oladi (log (n/k)).

Ikkinchi echim ko'proq joy hisobiga tezroq so'rovlarni o'tkazishga imkon beradi: barchasini birlashtirishimiz mumkin k bitta katta ro'yxatga kiritilgan Lva har bir element bilan bog'laning x ning L qidirish natijalarining ro'yxati x kichik ro'yxatlarning har birida L_men. Agar biz ushbu birlashtirilgan ro'yxatning elementini quyidagicha tavsiflasak x[a,b,v,d] qaerda x raqamli qiymat va a, b, vva d kamida keyingi elementning pozitsiyalari (birinchi raqam 0 pozitsiyasiga ega) x asl kirish ro'yxatlarining har birida (yoki agar bunday element mavjud bo'lmasa, ro'yxat tugaganidan keyingi holat)

L = 11[0,0,0,0], 13[0,0,0,1], 23[0,0,1,1], 24[0,1,1,1], 25[1,1,1,1], 26[1,2,1,1],

35[1,3,1,1], 44[1,3,1,2], 46[1,3,2,2], 62[1,3,2,3], 64[1,3,3,3], 65[2,3,3,3],

66[3,3,3,3], 79[3,3,4,3], 80[3,3,4,4], 81[4,3,4,4], 93[4,3,4,5]

Ushbu birlashtirilgan echim O (log) vaqtida so'rov o'tkazishga imkon beradi n + k): shunchaki qidirish q yilda L va keyin elementda saqlangan natijalar haqida xabar bering x ushbu qidiruv natijasida topilgan. Masalan, agar q = 50, qidirilmoqda q yilda L 62-bandni topadi [1,3,2,3], natijadan natijalarni qaytaramiz L₁[1] = 64, L₂[3] (buni ko'rsatuvchi bayroq qiymati q oxiridan o'tdi L₂), L₃[2] = 62 va L₄[3] = 79. Ammo, bu echim kosmik murakkablikda yuqori jazo to'laydi: u O (kn) har biri sifatida n elementlar L ro'yxatini saqlashi kerak k Qidiruv natijalari.

Fraksiyonel kaskad, xuddi shu qidirish muammosini vaqt va makon chegaralari bilan har ikki dunyoning eng yaxshisiga javob beradigan tarzda hal qilishga imkon beradi: so'rov vaqti O (jurnal n + k) va bo'sh joy O (nFraksiyonel kaskadli echim ro'yxatlarning yangi ketma-ketligini saqlashdir M_men. Ushbu ketma-ketlikdagi yakuniy ro'yxat, M_k, ga teng L_k; har bir oldingi ro'yxat M_men birlashish natijasida hosil bo'ladi L_men har bir ikkinchi element bilan M_men+1. Har bir element bilan x ushbu birlashtirilgan ro'yxatda biz ikkita raqamni saqlaymiz: qidirish natijasida paydo bo'lgan pozitsiya x yilda L_men va qidirishdan kelib chiqadigan pozitsiya x yilda M_men+1. Yuqoridagi ma'lumotlar uchun bu bizga quyidagi ro'yxatlarni beradi:

M₁ = 24[0, 1], 25[1, 1], 35[1, 3], 64[1, 5], 65[2, 5], 79[3, 5], 80[3, 6], 93[4, 6]

M₂ = 23[0, 1], 25[1, 1], 26[2, 1], 35[3, 1], 62[3, 3], 79[3, 5]

M₃ = 13[0, 1], 35[1, 1], 44[1, 2], 62[2, 3], 66[3, 3], 79[4, 3]

M₄ = 11[0, 0], 35[1, 0], 46[2, 0], 79[3, 0], 81[4, 0]

Biz ushbu tuzilishda so'rovni bajarishni xohlaymiz deylik q = 50. Dastlab biz standart ikkilik qidiruvni amalga oshiramiz q yilda M₁, qiymatini topish 64[1,5]. 64-dagi "1" [1,5], bizga qidirish kerakligini aytadi q yilda L₁ qaytishi kerak L₁[1] = 64. "5" 64[1,5] bizga taxminiy joylashishini aytadi q yilda M₂ 5-pozitsiya. Aniqrog'i, ikkilik qidirish q yilda M₂ yoki 5-pozitsiyada 79 [3,5] qiymatini, yoki 62 [3,3] qiymatini bir pog'ona oldinroq qaytaradi. Taqqoslash orqali q 62 ga, va uning kichikligini ko'rib, to'g'ri qidiruv natijasi ekanligini aniqladik M₂ 62 ga teng [3,3]. 62-dagi birinchi "3" [3,3] bizga qidirish kerakligini aytadi q yilda L₂ qaytishi kerak L₂[3], degan ma'noni anglatuvchi bayroq qiymati q ro'yxat oxiridan o'tgan L₂. 62-dagi ikkinchi "3" [3,3] bizga taxminiy joylashishini aytadi q yilda M₃ bu pozitsiya 3. Aniqrog'i, ikkilik qidirish q yilda M₃ yoki 62 [2,3] qiymatini 3-pozitsiyada yoki 44 [1,2] qiymatini bir pog'ona oldinroq qaytaradi. Taqqoslash q 44 qiymatining kichikligi bizga to'g'ri qidiruv natijasi ekanligini ko'rsatadi M₃ 62 ga teng [2,3]. 62-dagi "2" [2,3] bizga qidirish kerakligini aytadi q yilda L₃ qaytishi kerak L₃[2] = 62, 62-dagi "3" esa [2,3] bizni qidirish natijasi ekanligini aytadi q yilda M₄ ham M₄[3] = 79 [3,0] yoki M₄[2] = 46 [2,0]; taqqoslash q 46 bilan to'g'ri natijaning 79 [3,0] ekanligini va qidirish natijasini ko'rsatmoqda q yilda L₄ bu L₄[3] = 79. Shunday qilib, biz topdik q to'rt ro'yxatimizning har birida, bitta ro'yxatda ikkilik qidiruvni amalga oshirish orqali M₁ ketma-ket ro'yxatlarning har birida bitta taqqoslash.

Umuman olganda, ushbu turdagi har qanday ma'lumotlar tuzilishi uchun biz ikkilik qidiruvni amalga oshirib, so'rovni bajaramiz q yilda M₁va natijada olingan qiymatdan o'rnini aniqlash q yilda L₁. Keyin, har biri uchun men > 1, biz ma'lum bo'lgan pozitsiyadan foydalanamiz q yilda M_men o'z o'rnini topish uchun M_men+1. Holati bilan bog'liq qiymat q yilda M_men holatiga ishora qiladi M_men+1 bu ikkilik qidirishning to'g'ri natijasi q yilda M_men+1 yoki bu to'g'ri natijadan bir qadam narida, shuning uchun qadam qo'ying men ga men + 1 faqat bitta taqqoslashni talab qiladi. Shunday qilib, so'rov uchun umumiy vaqt O (log n + k).

Bizning misolimizda fraksiyonel kaskadli ro'yxatlarda jami 25 ta element mavjud, bu dastlabki kiritilgan ma'lumotdan ikki baravar kamroq. M_men ushbu ma'lumotlar tarkibida ko'pi bilan

${ displaystyle | L_ {i} | + { frac {1} {2}} | L_ {i + 1} | + { frac {1} {4}} | L_ {i + 2} | + cdots + { frac {1} {2 ^ {j}}} | L_ {i + j} | + cdots,}$

induksiya bilan osonlikcha isbotlanishi mumkin. Shuning uchun ma'lumotlar strukturasining umumiy hajmi maksimal darajada

${ displaystyle sum | M_ {i} | = sum | L_ {i} | chap (1 + { frac {1} {2}} + { frac {1} {4}} + cdots o'ng) leq 2n = O (n),}$

bir xil kirish ro'yxatidan kelib tushgan hissalarni umumiy hajmga qayta guruhlash orqali ko'rish mumkin L_men bir-biri bilan birga.

Umumiy muammo

Umuman olganda, kasrli kaskad a bilan boshlanadi katalog grafigi, a yo'naltirilgan grafik unda har biri tepalik buyurtma qilingan ro'yxat bilan etiketlanadi. Ushbu ma'lumotlar tarkibidagi so'rov a dan iborat yo'l grafada va so'rov qiymati q; ma'lumotlar strukturasi pozitsiyasini belgilashi kerak q yo'lning tepalari bilan bog'liq har bir buyurtma qilingan ro'yxatlarda. Yuqoridagi oddiy misol uchun katalog grafigining o'zi to'rtta tugundan iborat yo'l. So'nggi qismdagi so'qmoqlar natijalariga javoban yo'lning keyingi tepalari dinamik ravishda aniqlanishi mumkin.

Ushbu turdagi so'rovlarni bajarish uchun har bir tepalik maksimal darajada bo'lgan grafik uchun d kiruvchi va ko'pi bilan d bir oz doimiy uchun chiquvchi qirralar d, har bir tepalik bilan bog'langan ro'yxatlar vertexning har bir chiqadigan qo'shnisidan elementlarning bir qismi bilan ko'paytiriladi; kasr 1 / dan kichikroq bo'lishi kerakd, shuning uchun barcha ro'yxatlar ko'paytiriladigan umumiy miqdor kirish hajmida chiziqli bo'lib qoladi. Har bir kengaytirilgan ro'yxatdagi har bir element o'zi bilan shu vertikalda saqlanadigan kengaytirilmagan ro'yxatdagi va chiqayotgan qo'shni ro'yxatlarning har biridagi joyni saqlaydi. Yuqoridagi oddiy misolda, d = 1, va biz har bir ro'yxatni qo'shni elementlarning 1/2 qismi bilan ko'paytirdik.

Ushbu ma'lumotlar tuzilmasidagi so'rov, so'rov yo'lining birinchi uchi bilan bog'liq bo'lgan kengaytirilgan ro'yxatdagi standart ikkilik qidiruvdan va yo'lning har bir ketma-ket tepasida oddiyroq qidiruvlardan iborat. Agar 1 /r har bir qo'shni elementning ro'yxatlarini ko'paytirish uchun elementlarning bir qismi ishlatiladi, keyin har bir ketma-ket so'rov natijalarini eng ko'p topish mumkin r So'rovda saqlangan pozitsiyaning qadamlari oldingi yo'l vertexidan kelib chiqadi va shuning uchun doimiy ravishda to'liq ikkilik qidiruvni amalga oshirmasdan topish mumkin.

Dinamik kasrli kaskad

Yilda dinamik kasrli kaskad, katalog grafasining har bir tugunida saqlanadigan ro'yxat dinamik ravishda o'zgarishi mumkin, ro'yxat elementlari kiritilgan va o'chirilgan yangilanishlar ketma-ketligi bilan. Bu ma'lumotlar tuzilishi uchun bir nechta qiyinchiliklarni keltirib chiqaradi.

Birinchidan, katalog grafigi tuguniga biror narsa kiritilganda yoki o'chirilganda, u shu tugun bilan bog'langan kengaytirilgan ro'yxat ichiga joylashtirilishi kerak va katalog grafigining boshqa tugunlariga o'zgarishlar tarqalishiga olib kelishi mumkin. Kattalashtirilgan ro'yxatlarni massivlarda saqlash o'rniga, ular ikkilik qidiruv daraxtlari sifatida saqlanishi kerak, shunda ushbu o'zgarishlar samarali ravishda boshqarilishi mumkin va shu bilan birga kengaytirilgan ro'yxatlarni ikkilik izlashga imkon beradi.

Ikkinchidan, qo'shish yoki o'chirish katalog grafigining qo'shni tugunlariga uzatiladigan tugun bilan bog'liq bo'lgan ro'yxatning pastki qismini o'zgartirishi mumkin. Dinamik sozlamalarda ushbu kichik to'plamni har bir narsada tanlab olish endi mumkin emas dkimdir uchun ro'yxatning birinchi o'rni d, chunki ushbu yangilanish har bir yangilanishdan keyin juda keskin o'zgaradi. Aksincha, yaqindan bog'liq bo'lgan texnik B daraxtlari 1 / dan kichik bo'lishi kafolatlangan ma'lumotlarning bir qismini tanlashga imkon beradid, tanlangan elementlarning to'liq ro'yxatda bir-biridan doimiy ravishda bir-biridan ajratib turilishi kafolatlangan va tugun bilan bog'langan kengaytirilgan ro'yxatga qo'shilishi yoki o'chirilishi o'zgarishlarning boshqa tugunlarga tarqalishiga olib keladigan operatsiyalarning bir qismi. 1 / dan kamd. Shu tarzda, ma'lumotlarning tugunlar o'rtasida taqsimlanishi so'rov algoritmining tezkor bo'lishi uchun zarur bo'lgan xususiyatlarni qondiradi, shu bilan birga ma'lumotlar qo'shish yoki o'chirish bo'yicha ikkilik qidiruv daraxti operatsiyalarining o'rtacha soni doimiy bo'lishiga kafolat beradi.

Uchinchidan, va eng tanqidiy jihatdan har bir element uchun statik kasrli kaskadli ma'lumotlar tarkibi saqlanib qoladi x katalog grafasining har bir tugunidagi kattalashtirilgan ro'yxatning, qidirish paytida olinadigan natijalar indeksining x ushbu tugundan kirish elementlari orasida va qo'shni tugunlarda saqlangan kengaytirilgan ro'yxatlar orasida. Biroq, ushbu ma'lumotni dinamik sharoitda saqlash juda qimmatga tushadi. Bitta qiymatni kiritish yoki o'chirish x cheklanmagan miqdordagi boshqa qiymatlarda saqlanadigan indekslarning o'zgarishiga olib kelishi mumkin. Buning o'rniga kasrli kaskadning dinamik versiyalari har bir tugun uchun bir nechta ma'lumotlar tuzilishini saqlaydi:

• Tugmaning kattalashtirilgan ro'yxatidagi elementlarning kichik tamsayılarga xaritasi, shunday qilib kengaytirilgan ro'yxatdagi pozitsiyalarni tartiblash butun sonlarning taqqoslash tartibiga teng bo'ladi va teskari xarita yana ro'yxat elementlariga. Ning texnikasi Dietz (1982) ushbu raqamlashni samarali saqlashga imkon beradi.
• A kabi ma'lumotlar strukturasini qidiradigan butun son van Emde Boas daraxti tugunning kirish ro'yxati bilan bog'liq raqamlar uchun. Ushbu tuzilma va elementlardan to butun songacha xaritalash orqali har bir element uchun samarali topish mumkin x kengaytirilgan ro'yxat, qidirishda topiladigan element x kirish ro'yxatida.
• Katalog grafasidagi har bir qo'shni tugun uchun qo'shni tugundan tarqaladigan ma'lumotlar to'plami bilan bog'liq bo'lgan raqamlar uchun ma'lumotlar tuzilishini qidiradigan o'xshash son. Ushbu tuzilma va elementlardan to butun songacha xaritalash orqali har bir element uchun samarali topish mumkin x kengaytirilgan ro'yxat, joylashgan joyning doimiy sonidagi pozitsiya x qo'shni tugun bilan bog'langan kengaytirilgan ro'yxatda.

Ushbu ma'lumotlar tuzilmalari O (log) vaqtida dinamik kasrli kaskadni bajarishga imkon beradin) qo'shish yoki o'chirish uchun va ketma-ketligi k ikkilik qidiruv uzunlik yo'lidan keyin k O vaqtida bajariladigan katalog grafikasida (logn + k log logn).

Ilovalar

Nuqta to'plamining qavariq qatlamlari, yarim tekislik oralig'idagi hisobot uchun samarali kasrli ma'lumotlar strukturasining bir qismi.

Fraksiyonel kaskadning odatiy dasturlarini o'z ichiga oladi oraliq qidirish ma'lumotlar tuzilmalari hisoblash geometriyasi. Masalan, ning muammosini ko'rib chiqing yarim tekislik oraliq hisobot: ya'ni sobit to'plamini kesib o'tish n so'rov bilan ishora qiladi yarim tekislik va chorrahadagi barcha nuqtalarni sanab o'ting. Muammo shundaki, ushbu turdagi so'rovga kesishma kattaligi jihatidan samarali javob beradigan tarzda fikrlarni tuzish kerak. h. Shu maqsadda ishlatilishi mumkin bo'lgan tuzilmalardan biri qavariq qatlamlar kirish nuqtasi to'plamining uyasi qavariq ko'pburchaklar dan iborat qavariq korpus nuqta to'plami va qolgan nuqtalarning rekursiv tuzilgan konveks qatlamlari. Bir qatlam ichida, so'rov yarim tekisligi ichidagi nuqtalarni so'rov yarmida joylashgan ko'pburchak tepalikka olib boruvchi, qavariq ko'pburchak chekka yonbag'rlarining tartiblangan ketma-ketligi orasida yarim tekislik chegara chizig'i moyilligini ikkilik izlash orqali topish mumkin. - samolyot va uning chegarasidan uzoqda, keyin ketma-ket qidirish so'rov yarim tekisligi ichidagi boshqa barcha tepaliklarni topish uchun ko'pburchak qirralari bo'ylab. Yarim tekislik oralig'idagi hisobotning butun muammosi ushbu qidiruv protsedurasini tashqi qatlamdan boshlab takrorlash va yarim so'rov oralig'idan ajratilgan qatlamga etib borguncha ichkariga qarab davom etish yo'li bilan hal qilinishi mumkin. Fraksiyonel kaskad, har bir qatlamda ko'pburchak chekka yonbag'rlari ketma-ketligi orasida ketma-ket ikkilik izlanishlarni tezlashtiradi va bu bo'shliq bilan bog'liq muammo uchun ma'lumotlar tuzilishiga olib keladi (n) va so'rov vaqti O (logn + h). Ma'lumotlar tarkibi O vaqt ichida tuzilishi mumkin (n jurnaln) ning algoritmi bilan Shazelle (1985). Bizning misolimizda bo'lgani kabi, ushbu dastur ro'yxatlarning ketma-ket ketma-ketligidagi ikkilik izlanishlarni o'z ichiga oladi (qavariq qatlamlarning ichki qatori), shuning uchun katalog grafigi shunchaki yo'l.

Geometrik ma'lumotlar tuzilmalarida kasrli kaskadning yana bir qo'llanilishi nuqta joylashuvi monotonli bo'linmada, ya'ni tekislikning ko'pburchaklarga bo'linishi, shunday qilib har qanday vertikal chiziq har qanday ko'pburchakni eng ko'p ikki nuqtada kesib o'tadi. Sifatida Edelsbrunner, Gibas va Stolfi (1986) ko'rsatdiki, ushbu muammoni bo'linma bo'ylab chapdan o'ngga cho'zilgan ko'pburchak yo'llar ketma-ketligini topish va so'rovlar nuqtasi ustida joylashgan ushbu yo'llarning eng pastini izlash orqali hal qilish mumkin. So'rov nuqtasi yo'llardan birida yuqorida yoki pastda bo'lishini sinab ko'rish, ikkilik qidiruv muammosi sifatida echilishi mumkin, yo'l vertikallarining x koordinatalari orasidagi nuqtalarning x koordinatasini qidirib, qaysi yo'l chekkasi yuqoridan yoki pastdan bo'lishi mumkinligini aniqlash uchun. so'rov nuqtasi. Shunday qilib, har bir nuqta joylashish so'rovini yo'llarning o'rtasida ikkilik qidiruvning tashqi qatlami sifatida hal qilish mumkin, uning har bir bosqichi o'zi tepaliklarning x koordinatalari o'rtasida ikkilik qidiruvni amalga oshiradi. Fraksiyonel kaskad yordamida ichki ikkilik qidirish vaqtini tezlashtirish uchun foydalanish mumkin, so'rov uchun umumiy vaqtni O ga kamaytiradi (logn) bo'shliqli ma'lumotlar tuzilmasi yordamida O (n). Ushbu dasturda katalog grafigi tashqi ikkilik qidiruvning mumkin bo'lgan qidiruv ketma-ketliklarini aks ettiruvchi daraxtdir.

Hisoblash geometriyasidan tashqari, Lakshman va Stiliadis (1998) va Buddhikot, Suri va Valdvogel (1999) ma'lumotlar tuzilmalarini loyihalashda tezkor kaskadni qo'llash paketlarni filtrlash yilda Internet routerlari. Gao va boshq. (2004) ma'lumotlarni tarqatish va olish uchun namuna sifatida kasrli kaskaddan foydalaning sensorli tarmoqlar.

Adabiyotlar