Qulfsiz ma'lumotlar tuzilmalari. Bir vaqtning o'zida joylashgan xaritalar: ro'yxatni o'tkazib yuborish

Turli test topshiriqlarini bajarish sizning professional darajangizni tezda oshirishga yordam beradi degan fikr keng tarqalgan. Men o'zim ham, ular aytganidek, doimo oyoq osti bo'lishim uchun ba'zida qiyin test savolini qazib olishni va uni hal qilishni yaxshi ko'raman. Bir marta men kompaniyada amaliyot o'tash uchun tanlov topshirig'ini bajarayotganimda, muammo menga kulgili va qiziqarli bo'lib tuyuldi, uning qisqacha matni:

Tasavvur qiling-a, sizning xirillagan hamkasbingiz o'zining qiyin ishi haqida gapirish uchun keldi - u nafaqat butun sonlar to'plamini o'sish tartibida tartiblashi, balki L dan R gacha bo'lgan tartiblangan to'plamning barcha elementlarini chiqarishi kerak!
Siz bu elementar vazifa ekanligini va C# da yechim yozish uchun sizga o'n daqiqa vaqt ketishini aytdingiz. Xo'sh, yoki bir soat. Yoki ikkita. Yoki Alyonka shokoladi

To'plamda dublikatlarga ruxsat beriladi va elementlar soni 10^6 dan oshmaydi deb taxmin qilinadi.

Yechimni baholash bo'yicha bir nechta sharhlar mavjud:

Sizning kodingiz uchta dasturchi tomonidan baholanadi va sinovdan o'tkaziladi:
Bill sizning yechimingizni 10Kb dan katta bo'lmagan testlarda ishga tushiradi.

Stivenning testlarida so'rovlar soni 10^5 dan oshmaydi, qo'shish so'rovlari soni esa 100 dan oshmaydi.

Mark testlarida so'rovlar soni 10^5 dan oshmaydi.

Yechim juda qiziqarli bo'lishi mumkin, shuning uchun men uni tasvirlashni zarur deb o'yladim.

Yechim

Keling, mavhum xotiraga ega bo'lamiz.

Add(e) - elementni do'konga qo'shish va Range(l, r) - l dan r elementgacha bo'lak olishni belgilaymiz.

Arzimas saqlash opsiyasi quyidagicha bo'lishi mumkin:

Saqlashning asosi o'sish tartibida tartiblangan dinamik massiv bo'ladi.
Har bir qo'shish bilan ikkilik qidiruv elementni kiritish kerak bo'lgan joyni topadi.
Range(l, r) ni so‘rashda biz l dan r gacha bo‘lgan massivning bir bo‘lagini olamiz.

Keling, dinamik massivga asoslangan yondashuvning murakkabligini baholaylik.

C diapazoni(l, r) - tilim olish O(r - l) sifatida baholanishi mumkin.

C Add(e) - eng yomon holatda kiritish O(n) da ishlaydi, bu erda n - elementlar soni. n ~ 10^6 da kiritish qiyin bo'ladi. Quyida maqolada yaxshilangan saqlash opsiyasi taklif etiladi.

Manba kodining misolini ko'rish mumkin.

Skiplist

Skiplist - bu bir nechta bog'langan ro'yxatlarga asoslangan qidiruv daraxtlarining tasodifiy alternatividir. U 1989 yilda Uilyam Pugh tomonidan ixtiro qilingan. Qidiruv, qo'shish va o'chirish operatsiyalari logarifmik tasodifiy vaqtda amalga oshiriladi.

Ushbu ma'lumotlar tuzilmasi keng ma'lum emas (Aytgancha, bu haqda Habré-da juda ko'p sharhlar yozilgan), garchi u yaxshi asimptotik baholarga ega. Qiziq, men buni amalga oshirishni xohladim, ayniqsa, menda tegishli vazifa bor edi.

Aytaylik, bizda tartiblangan bir-biriga bog'langan ro'yxat bor:

Eng yomon holatda, qidiruv O(n) da amalga oshiriladi. Buni qanday tezlashtirish mumkin?

Muammo ustida ishlayotganimda tomosha qilgan videoma'ruzalardan birida Nyu-Yorkdagi ekspress chiziqlar haqida ajoyib misol bor edi:

Ekspress liniyalar ba'zi stantsiyalarni bog'laydi
Muntazam liniyalar barcha stantsiyalarni birlashtiradi
Umumiy tezyurar liniya stantsiyalari o'rtasida muntazam liniyalar mavjud

G'oya shunday: biz ulardagi ma'lum miqdordagi tugunlar bilan ma'lum miqdordagi darajalarni qo'shishimiz mumkin va darajalardagi tugunlar bir tekis taqsimlanishi kerak. Keling, yuqoridagi darajalarning har biri asosiy darajadagi elementlarning yarmini o'z ichiga olgan misolni ko'rib chiqaylik:

Misol ideal SkipListni ko'rsatadi, aslida hamma narsa o'xshash ko'rinadi, lekin biroz boshqacha :)

Qidirmoq

Qidiruv shu tarzda sodir bo'ladi. Aytaylik, biz 72-elementni qidirmoqdamiz:

Kiritmoq

Qo'shimcha bilan hamma narsa biroz murakkabroq. Elementni kiritish uchun biz uni eng past ro'yxatga qaerga qo'yish kerakligini tushunishimiz va shu bilan birga uni ma'lum miqdordagi yuqori darajalarga surishimiz kerak. Lekin har bir aniq elementni necha darajadan o'tkazish kerak?

Buni shunday hal qilish taklif etiladi: qo'yish paytida biz eng past darajaga yangi element qo'shamiz va tanga otishni boshlaymiz, u tushib ketguncha elementni keyingi yuqori darajaga suramiz.
Keling, elementni kiritishga harakat qilaylik - 67. Birinchidan, uni asosiy ro'yxatning qayeriga qo'shish kerakligini aniqlaymiz:

Men tanga ketma-ket ikki marta tushib ketgan deb taxmin qildim. Bu elementni ikki darajaga ko'tarish kerakligini anglatadi:

Indeks bo'yicha kirish

Indeks bo'yicha kirish uchun quyidagilarni bajarish tavsiya etiladi: har bir o'tishni uning ostida joylashgan tugunlar soni bilan belgilang:

Biz i-elementga kirishga erishganimizdan so'ng (Aytgancha, biz uni O(ln n) da olamiz), tilim qilish qiyin ko'rinmaydi.

Diapazonni (5, 7) topish kerak bo'lsin. Avval biz beshinchi indeksdagi elementni olamiz:

Va endi diapazon (5, 7):

Amalga oshirish haqida

SkipList tugunining shunday ko'rinishi uchun tabiiy dastur kabi ko'rinadi:

SkipListNode(
int Element;
SkipListNodeNext;
int kengligi;
}

Aslida, shunday qilingan.

Ammo C# da massiv o'z uzunligini ham saqlaydi va men buni iloji boricha kamroq xotirada qilishni xohlardim (ma'lum bo'lishicha, muammo sharoitida hamma narsa unchalik qattiq baholanmagan). Shu bilan birga, men SkipList va kengaytirilgan RB daraxtini amalga oshirish taxminan bir xil xotira hajmini egallashiga ishonch hosil qilishni xohladim.

Xotira sarfini qanday kamaytirish mumkinligi haqidagi javob kutilmaganda java.util.concurrent paketini sinchiklab tekshirilganda topildi.

2D skiplist

Bir o'lchovdagi barcha elementlarning bir-biriga bog'langan ro'yxati bo'lsin. Ikkinchisida pastki darajaga havolalar bilan o'tish uchun "ekspress chiziqlar" mavjud.

ListNode(
int Element;
ListNodeNext;
}
qator (
O'ng chiziq;
Lane Down;
ListNode tugunlari;
}

Insofsiz tanga

Xotira sarfini kamaytirish uchun siz "insofsiz" tangadan ham foydalanishingiz mumkin: elementni keyingi bosqichga surish ehtimolini kamaytiring. Uilyam Pughning maqolasi bir nechta surish ehtimoli qiymatlarining kesmasini ko'rib chiqdi. ½ va ¼ qiymatlarini hisobga olgan holda, amalda xotira sarfini kamaytirishda taxminan bir xil qidiruv vaqti olindi.

Tasodifiy sonlarni yaratish haqida bir oz

ConcurrentSkipListMap-ni o'rganib chiqib, tasodifiy raqamlar quyidagicha yaratilganligini payqadim:

int randomLevel() (
int x = randomSeed;
x ^= x<< 13;
x ^= x >>> 17;
randomSeed = x ^= x<< 5;
agar ((x & 0x80000001) != 0)
qaytish 0;
int darajasi = 1;
while (((x >>>= 1) & 1) != 0) ++daraja;
qaytish darajasi;
}

Ushbu maqolada XOR yordamida psevdor tasodifiy raqamlarni yaratish haqida ko'proq o'qishingiz mumkin. Men tezlikning o'sishini sezmadim, shuning uchun uni ishlatmadim.

Olingan omborning manbasiga qarashingiz mumkin.

Hammasini googlecode.com dan yuklab olish mumkin (Pagination loyihasi).

Testlar

Saqlashning uchta turi ishlatilgan:

ArrayBased (dinamik massiv)
SkipListBased (¼ parametrli SkipList)
RBTreeBased (qizil-qora daraxt: xuddi shunday vazifani bajargan do'stimning amalga oshirilishi).

10^6 elementni kiritish uchun uch turdagi sinovlar o'tkazildi:

Elementlar ortib borish tartibida tartiblangan
Elementlar kamayish tartibida tartiblangan
Tasodifiy elementlar

Sinovlar i5, 8 gb RAM, ssd va Windows 7 x64 o'rnatilgan mashinada o'tkazildi.
Natijalar:

	Massiv	RBTree	Oʻtkazib yuborish roʻyxati
Tasodifiy	127033 ms	1020 ms	1737 ms
Buyurtma qilingan	108 ms	457 ms	536 ms
Pastga qarab tartiblangan	256337 ms	358 ms	407 ms

Kutilgan natijalar. Element oxirida emas, balki boshqa joyga kiritilganda massivga kiritish eng sekin ekanligini ko'rishingiz mumkin. Shu bilan birga, SkipList RBTree ga qaraganda sekinroq.

O'lchovlar ham amalga oshirildi: har bir xotira xotiraga qancha 10 ^ 6 element kiritilgan bo'lsa. Biz studiya profilidan foydalandik; soddaligi uchun biz quyidagi kodni ishga tushirdik:

var saqlash = ...
uchun (var i = 0; i< 1000000; ++i)
saqlash.Add(i);

Natijalar:

	Massiv	RBTree	Oʻtkazib yuborish roʻyxati
Jami ajratilgan baytlar	8 389 066 bayt	24 000 060 bayt	23 985 598 bayt

Kutilgan natijalar ham mavjud: dinamik massivda saqlash eng kam xotira hajmini egalladi, SkipList va RBTree esa taxminan bir xil miqdorni egalladi.

"Alenka" bilan baxtli yakun

Shiqillagan hamkasb, topshiriq shartlariga ko'ra, menga shokolad barini tikib qo'ydi. Mening yechimim maksimal ball bilan qabul qilindi. Umid qilamanki, bu maqola kimgadir foydali bo'ladi. Agar sizda biron bir savol bo'lsa, men javob berishdan xursand bo'laman.

P.S.: SKB Konturda amaliyot o‘taganman. Bu bir xil savollarga javob bermaslik uchun =)

O'tkazib yuborish ro'yxatlari muvozanatli daraxtlar o'rniga ishlatilishi mumkin bo'lgan ma'lumotlar tuzilmasi. Balanslash algoritmi qat'iy emas, balki ehtimollik bo'lganligi sababli, o'tish ro'yxatiga elementni kiritish va o'chirish muvozanatli daraxtlarga qaraganda ancha oson va tezroq.

O'tkazib yuborish ro'yxatlari muvozanatli daraxtlarga ehtimoliy muqobildir. Ular tasodifiy sonlar generatori yordamida muvozanatlanadi. O'tkazib yuborish ro'yxatlarining eng yomon ishlashi yomon bo'lsa-da, buni izchil bajaradigan operatsiyalar ketma-ketligi yo'q (tasodifiy mos yozuvlar elementi bilan tezkor saralash kabi). Ushbu ma'lumotlar strukturasi sezilarli darajada nomutanosib bo'lib qolishi ehtimoldan yiroq emas (masalan, 250 dan ortiq elementdan iborat lug'at uchun kutilgan vaqtdan uch baravar ko'p qidirish imkoniyati millionda birdan kam).

Balansni aniq ta'minlashdan ko'ra, ma'lumotlar strukturasini ehtimollik bilan muvozanatlash osonroq. Ko'pgina vazifalar uchun o'tkazib yuborish ro'yxatlari daraxtlarga qaraganda ma'lumotlarning tabiiyroq ko'rinishidir. Algoritmlarni amalga oshirish osonroq va amalda muvozanatli daraxtlarga qaraganda tezroq bo'lib chiqadi. Bundan tashqari, o'tkazib yuborish ro'yxatlari xotirani juda tejaydi. Ular har bir element uchun o'rtacha 1,33 ko'rsatkich (yoki undan ham kamroq) uchun amalga oshirilishi mumkin va har bir element uchun qo'shimcha balans yoki ustuvor ma'lumotlarni saqlashni talab qilmaydi.

Bog'langan ro'yxatdagi elementni topish uchun uning har bir tugunini ko'rib chiqishimiz kerak:

Agar ro'yxat tartiblangan bo'lsa va har ikkinchi tugun qo'shimcha ravishda oldinda ikkita tugun ko'rsatgichni o'z ichiga olsa, biz ko'pi bilan qarashimiz kerak ⌈ n/2⌉ + 1 tugun (qaerda n- ro'yxat uzunligi):

Xuddi shunday, agar har to'rtinchi tugun oldinda to'rtta tugun ko'rsatgichni o'z ichiga olsa, u holda siz ⌈ dan ko'p bo'lmagan nuqtaga qarashingiz kerak bo'ladi. n/4⌉ + 2 tugun:

Agar har 2 i i tugunlar oldinga siljiydi, keyin skanerlanishi kerak bo'lgan tugunlar soni ⌈log 2 ga kamayadi n⌉ va strukturadagi ko'rsatkichlarning umumiy soni faqat ikki baravar ko'payadi:

Ushbu ma'lumotlar strukturasi tez qidirish uchun ishlatilishi mumkin, ammo tugunlarni kiritish va o'chirish sekin bo'ladi.

Oldingi elementlarga k ko'rsatgichni o'z ichiga olgan tugunni tugun deb ataymiz Daraja k . Agar har 2 i Tugun 2 ga ko'rsatgichni o'z ichiga oladi i tugunlar oldinga, keyin darajalar quyidagicha taqsimlanadi: tugunlarning 50% 1 daraja, 25% 2 daraja, 12,5% 3 daraja va boshqalar. Ammo tugun darajalari tasodifiy, bir xil nisbatda tanlansa nima bo'ladi? Masalan, bu kabi:

Indeks raqami i har bir tugun keyingi darajadagi tugunga bog'lanadi i yoki undan ko'p, aniq 2 emas i Oldinga bo'lgani kabi -1 tugun oldinga. Qo'shish va o'chirish faqat mahalliy o'zgarishlarni talab qiladi; tasodifiy tanlangan tugunning darajasi u kiritilganda hech qachon o'zgarmaydi. Agar darajadagi topshiriq muvaffaqiyatsiz bo'lsa, ishlash yomon bo'lishi mumkin, ammo biz bunday holatlar kamdan-kam ekanligini ko'rsatamiz. Ushbu ma'lumotlar tuzilmalari oraliq tugunlarni o'tkazib yuborish uchun qo'shimcha ko'rsatkichlar bilan bog'langan ro'yxatlar bo'lgani uchun men ularni chaqiraman qoldirilgan ro'yxatlar.

Operatsiyalar

Keling, bo'shliqlari bo'lgan ro'yxatlarda amalga oshirilgan lug'atdagi elementlarni qidirish, kiritish va o'chirish algoritmlarini tasvirlaylik. Operatsiya qidirmoq berilgan kalitning qiymatini qaytaradi yoki kalit topilmaganligi haqida signal beradi. Operatsiya qo'shimchalar kalitni yangi qiymat bilan bog'laydi (va agar ilgari bo'lmagan bo'lsa, kalit yaratadi). Operatsiya olib tashlash kalitni o'chiradi. Shuningdek, ushbu ma'lumotlar strukturasiga "minimal kalitni topish" yoki "keyingi kalitni topish" kabi qo'shimcha operatsiyalarni osongina qo'shishingiz mumkin.

Har bir ro'yxat elementi allaqachon mavjud bo'lgan elementlar sonidan qat'i nazar, darajasi yaratilganda tasodifiy tanlangan tugundir. Darajali tugun i o'z ichiga oladi i oldindagi turli elementlarga ko'rsatgichlar, 1 dan indekslangan i. Biz tugun darajasini tugunning o'zida saqlamasligimiz mumkin. Darajalar soni oldindan tanlangan konstanta bilan cheklangan MaxLevel. Qo'ng'iroq qilaylik ro'yxat darajasi ushbu ro'yxatdagi tugunning maksimal darajasi (agar ro'yxat bo'sh bo'lsa, u holda daraja 1 ga teng). Sarlavha ro'yxat (rasmlarda u chap tomonda) 1 dan darajagacha ko'rsatkichlarni o'z ichiga oladi MaxLevel. Agar ushbu darajadagi elementlar hali mavjud bo'lmasa, u holda ko'rsatkich qiymati maxsus NIL elementidir.

Initializatsiya

Keling, kaliti ro'yxatda paydo bo'lishi mumkin bo'lgan har qanday kalitdan kattaroq bo'lgan NIL elementini yarataylik. NIL elementi bo'shliqlar bilan barcha ro'yxatlarni tugatadi. Ro'yxat darajasi 1 va sarlavhadagi barcha ko'rsatkichlar NIL ga ishora qiladi.

Elementni qidiring

Eng yuqori darajadagi ko'rsatkichdan boshlab, biz izlayotgan elementdan katta bo'lmagan elementga murojaat qilguncha ko'rsatkichlar bo'ylab oldinga siljiymiz. Keyin biz bir darajaga tushamiz va yana bir xil qoidaga amal qilamiz. Agar biz 1-darajaga erishgan bo'lsak va oldinga bora olmasak, biz qidirayotgan elementning oldida turibmiz (agar u mavjud bo'lsa).

Qidirmoq(roʻyxat, qidiruv kaliti)
x:= ro'yxat → sarlavha
# tsiklning o'zgarmasligi: x→ kalit< searchKey
uchun i:= roʻyxat → daraja pastga 1 qil
esa x → oldinga [i] → tugma< searchKey qil
x:= x→oldinga[i]
#x→ tugma< searchKey ≤ x→forward→key
x:= x→ oldinga
agar x→ kalit = qidiruv tugmasi keyin qaytish x→qiymat
boshqa qaytish muvaffaqiyatsizlik

Elementni kiritish va o'chirish

Tugunni qo'shish yoki o'chirish uchun biz qo'shilgan (yoki olib tashlangan) elementdan oldin barcha elementlarni topish uchun qidiruv algoritmidan foydalanamiz, so'ngra tegishli ko'rsatkichlarni yangilaymiz:

Ushbu misolda biz 2-darajali elementni kiritdik.

Kiritmoq(roʻyxat, qidiruv kaliti, yangi qiymat)
mahalliy yangilash
x:= ro'yxat → sarlavha
uchun i:= roʻyxat → daraja pastga 1 qil
esa x → oldinga [i] → tugma< searchKey qil
x:= x→oldinga[i]
#x→ tugma< searchKey ≤ x→forward[i]→key
yangilash[i] := x
x:= x→ oldinga
agar x→ kalit = qidiruv tugmasi keyin x→value:= newValue
boshqa
lvl:= randomLevel()
agar lvl > ro‘yxat → daraja keyin
uchun i:= roʻyxat → daraja + 1 uchun lvl qil
yangilash[i] := roʻyxat → sarlavha
roʻyxat→daraja:= lvl
x:= makeNode(lvl, searchKey, qiymat)
uchun i:= 1 uchun Daraja qil
x→oldinga[i] := yangilash[i]→oldinga[i]
yangilash[i]→oldinga[i] := x

Oʻchirish(roʻyxat, qidiruv kaliti)
mahalliy yangilash
x:= ro'yxat → sarlavha
uchun i:= roʻyxat → daraja pastga 1 qil
esa x → oldinga [i] → tugma< searchKey qil
x:= x→oldinga[i]
yangilash[i] := x
x:= x→ oldinga
agar x→ kalit = qidiruv tugmasi keyin
uchun i:= 1 uchun roʻyxat → daraja qil
agar yangilash[i]→oldinga[i] ≠ x keyin tanaffus
yangilash[i]→oldinga[i] := x→oldinga[i]
bepul(x)
esa roʻyxat→daraja > 1 va ro'yxat → sarlavha → oldinga = NIL qil
roʻyxat→daraja:= roʻyxat→daraja – 1

Massiv elementlarni kiritishdan (yoki olib tashlashdan) oldin eslab qolish uchun ishlatiladi. yangilash. Element yangilash[i]- bu darajaning eng o'ng tuguniga ko'rsatgich i yoki undan yuqori, yangilanish joyining chap tomonida joylashganlardan.

Agar kiritilgan tugunning tasodifiy tanlangan darajasi butun ro'yxat darajasidan kattaroq bo'lsa (ya'ni, bunday darajadagi tugunlar hali bo'lmasa), biz ro'yxat darajasini oshiramiz va tegishli massiv elementlarini ishga tushiramiz. yangilash sarlavhaga ishora. Har bir o'chirishdan so'ng biz tugunni maksimal darajada o'chirib tashlaganimizni tekshiramiz va agar shunday bo'lsa, biz ro'yxat darajasini kamaytiramiz.

Darajali raqamni yaratish

Ilgari biz tugunlarning yarmi daraja ko'rsatkichini o'z ichiga olgan holda tugun darajalarining taqsimlanishini taqdim etdik i, shuningdek, daraja tuguniga ko'rsatgich ham mavjud edi i+1. Sehrli doimiy 1/2 dan qutulish uchun biz bilan belgilaymiz p darajali tugunlarning ulushi i, darajali tugunlarga ko'rsatgichni o'z ichiga oladi i+i. Yangi cho'qqi uchun daraja raqami quyidagi algoritm yordamida tasodifiy hosil bo'ladi:

tasodifiy daraja()
lvl:= 1
# random() tasodifiy sonni yarim oraliqda qaytaradi, uzunligi: " + uzunlik); ))

O'zingiz yaratish uchun quyidagi koddan foydalanishingiz mumkin asosiy skipper:

1) qiling boshlash Va oxiri o'tkazib yuborish ro'yxatining boshlanishi va oxirini ifodalash uchun.

2) Tugunlarni qo'shing va ko'rsatgichlarni keyingisiga tayinlang
Agar (tugun juft bo'lsa), keyingi ko'rsatkich bilan tezkor chiziqli ko'rsatkichni belgilang, aks holda keyingi tugunga faqat ko'rsatgichni tayinlang
Java kodi asosiy o'tkazib yuborish ro'yxati uchun (siz qo'shimcha funktsiyalarni qo'shishingiz mumkin):
Ommaviy sinf MyClass ( public static void main(String args) ( Skiplist skiplist=yangi Skiplist(); Tugun n1=yangi tugun(); Tugun n2=yangi tugun(); Tugun n3=yangi tugun(); Tugun n4=yangi tugun (); tugun n5=yangi tugun(); tugun n6=yangi tugun(); n1.setData(1); n2.setData(2); n3.setData(3); n4.setData(4); n5.setData (5); n6.setData(6); skiplist.insert(n1); skiplist.insert(n2); skiplist.insert(n3); skiplist.insert(n4); skiplist.insert(n5); skiplist.insert( n6); /*barcha tugunlarni chop etish*/ skiplist.display(); System.out.println(); /* faqat tezkor tarmoqli tugunni chop etish*/ skiplist.displayFast(); ) ) klassi tugun( xususiy int ma’lumotlari; xususiy tugun one_next; //keyingi tugunga ko‘rsatgichni o‘z ichiga oladi. Shaxsiy tugun two_next; //keyingi tugundan keyingi tugunga ko‘rsatgich public int getData() ( ma’lumotlarni qaytarish; ) public void setData(int data) ( this.data = data; ) public Tugun getOne_next() ( one_next; ) public void setOne_next(tugun one_next) ( this.one_next = one_next; ) public Node getTwo_next() ( return two_next; ) public void setTwo_next(tugun ikki_next) ( this.two_next = ikkita ) ) sinf Skiplist( Tugunni boshlash; // o'tkazib yuborish ro'yxati uchun start ko'rsatkichi Tugun boshi; Tugun temp_next; // oxirgi foydalanilgan tezkor tarmoqli tugunni saqlash uchun ko'rsatgich Tugun oxiri; // o'tkazib yuborish ro'yxatining oxiri int uzunligi; umumiy Skiplist())( start = new Node(); end=new Node(); length=0; temp_next=start; ) public void insert(tugun tugun)( /*oʻtkazib yuborish roʻyxati boʻsh boʻlsa */ if(length==0)( start.setOne_next ( tugun); node.setOne_next(end); temp_next.setTwo_next(end); head=start; length++; ) else( length++; Node temp=start.getOne_next(); Tugun oldingi=start; while(temp!= end) ( prev=temp; temp=temp.getOne_next(); ) /*juft tugunlar soni uchun tezkor chiziq ko‘rsatkichini qo‘shing*/ if(length%2==0)( prev.setOne_next(tugun); node.setOne_next(end) ) ; temp_next.setTwo_next(tugun); temp_next=tugun; node.setTwo_next(end); ) /*toq tugun sonida tezkor chiziqli ko‘rsatkich bo‘lmaydi*/ else(prev.setOne_next(tugun); node.setOne_next(end) ; ) ) ) ommaviy bekor displey())( System.out.println("--Oddiy o'tish--"); Tugun temp=start.getOne_next(); while(temp != end)( System.out.print( temp. getData()+"=>"); temp=temp.getOne_next(); ) ) public void displayFast())( System.out.println("--Fast Lane Traversal--"); Tugun temp=start.getTwo_next(); while(temp !=end)( System.out.print(temp) . getData()+"==>"); temp=temp.getTwo_next(); ) ) )
Xulosa:

Oddiy aylanib o'tish -

1 = > 2 = > 3 = > 4 = > 5 = > 6 = >

Trekni tez yo'naltirish -

2 == > 4 == > 6 == >

ConcurrentSkipListSet ni yaratganingizda, siz konstruktorga komparatorni o'tkazasiz.
Yangi ConcurrentSkipListSet<>(yangi ExampleComparator()); umumiy sinf ExampleComparator Comparatorni amalga oshiradi (//sizning ishorangiz)
Siz SkipListSet-ni odatdagi ro'yxat kabi harakatga keltiradigan taqqoslagichni yaratishingiz mumkin.

Men buni o'zimning amalga oshirishim deb da'vo qilmayman. Uni qayerdan topganimni eslay olmayman. Agar bilsangiz, menga xabar bering va men yangilayman. Bu men uchun yaxshi ishlaydi:
Umumiy sinf SkipList > Iterable-ni amalga oshiradi (tugun _head = yangi tugun<>(nol, 33); xususiy final Tasodifiy rand = yangi Tasodifiy(); private int _levels = 1; xususiy AtomicInteger hajmi = yangi AtomicInteger(0); ///
/// O'tkazib yuborish ro'yxatiga qiymat kiritadi. ///
public void insert(T value) ( // Yangi tugun darajasini aniqlang. Tasodifiy R sonini yarating. Birinchi 0-bitga duch kelgunimizcha // 1-bitlar soni tugun darajasidir. . / / R // 32-bit boʻlgani uchun daraja koʻpi bilan 32 boʻlishi mumkin. int level = 0; size.incrementAndGet(); for (int R = rand.nextInt(); (R & 1) == 1 ; R >>= 1) (daraja++; agar (daraja == _darajalar) ( _darajalar++; tanaffus; ) ) // Ushbu tugunni o‘tkazib yuborish ro‘yxatiga kiriting Tugun newNode = yangi tugun<>(qiymat, daraja + 1); Tugun cur = _bosh; for (int i = _levels - 1; i >= 0; i--) ( for (; cur.next[i] != null; cur = cur.next[i]) ( if (cur.next[i]) .getValue().compareTo(value) > 0) break; ) if (i<= level) { newNode.next[i] = cur.next[i]; cur.next[i] = newNode; } } } ///
/// O'tkazib yuborish ro'yxatida ma'lum bir qiymat mavjud yoki yo'qligini qaytaradi ///
umumiy boolean o'z ichiga oladi(T qiymati) (tugun cur = _bosh; for (int i = _levels - 1; i >= 0; i--) ( for (; cur.next[i] != null; cur = cur.next[i]) ( if (cur.next[i]) .getValue().compareTo(value) > 0) tanaffus, agar (cur.next[i].getValue().compareTo(value) == 0) rostni qaytaradi; ) ) falseni qaytaradi; ) ///
/// Muayyan qiymatning bitta hodisasini o'tkazib yuborish /// ro'yxatidan olib tashlashga urinish. Qiymat o'tkazib yuborish ro'yxatida topilgan yoki yo'qligini /// qaytaradi. ///
ommaviy boolean olib tashlash (T qiymati) (tugun cur = _bosh; mantiqiy topildi = noto'g'ri; for (int i = _levels - 1; i >= 0; i--) ( for (; cur.next[i] != null; cur = cur.next[i]) ( if (cur.next[i]) .getValue().compareTo(value) == 0) (topildi = rost; cur.next[i] = cur.next[i].next[i]; break; ) if (cur.next[i].getValue ().compareTo(value) > 0) break; ) ) if (topilgan) size.decrementAndGet(); qaytish topildi; ) @SuppressWarnings(( "xom turlar", "checked" )) @Ommaviy iteratorni bekor qilish iterator() ( qaytish new SkipListIterator(this, 0); ) public int size() ( return size.get(); ) public Double toArray() ( Double a = new Double; int i = 0; for (T t: this) ( a[i] = (Double) t; i++; ) return a; ) ) class Node > (ommaviy tugun Keyingisi; umumiy N qiymati; @SuppressWarnings("checked") umumiy tugun(N qiymat, int darajasi) ( this.value = value; next = new Node; ) public N getValue() ( return value; ) public Node getNext() (keyingi qaytish; ) umumiy tugun getNext(int level) ( keyingi qaytish; ) public void setNext(tugun keyingi) ( this.next = next; ) ) sinf SkipListIterator > Iteratorni amalga oshiradi (Oʻtkazib yuborish roʻyxati ro'yxat; Tugun oqim; int darajasi; ommaviy SkipListIterator(SkipList list, int level) ( this.list = list; this.current = list._head; this.level = level; ) public boolean hasNext() ( return current.getNext(level) != null; ) public E next() ( current = current.getNext(level); return current.getValue(); ) public void remove() funksiyasi UnsupportedOperationException ni chiqaradi (yangi UnsupportedOperationException(); ) ni oching)

@PoweredByRice tomonidan taqdim etilgan amalga oshirishdagi xatolik tuzatildi. Bu masofaviy tugun birinchi tugun bo'lgan holatlar uchun NPEni tashladi. Boshqa yangilanishlar nomi o'zgartirilgan o'zgaruvchilar nomlarini va o'tkazib yuborish ro'yxati tartibini teskari chop etishni o'z ichiga oladi.
Import java.util.Random; SkipableList interfeysi > ( int LEVELS = 5; mantiqiy o'chirish (T maqsad); bekor chop etish (); bekor kiritish (T ma'lumotlar); SkipNode qidiruv (T ma'lumotlari); ) SkipNode sinfi > ( N ma'lumot; @SuppressWarnings("belgilanmagan") SkipNode keyingi = (SkipNode ) yangi SkipNode; SkipNode(N data) ( this.data = data; ) void refreshAfterDelete(int level) ( SkipNode joriy = bu; while (joriy != null && current.getNext(level) != null) ( if (current.getNext(level).data == null) ( SkipNode voris = current.getNext(level).getNext(daraja); current.setNext(voris, daraja); qaytish; ) joriy = current.getNext(daraja); ) ) void setNext(SkipNode keyingi, int darajasi) ( this.next = next; ) SkipNode getNext(int level) ( qaytar this.next; ) SkipNode search(N data, int level, mantiqiy chop) ( if (chop etish) ( System.out.print("Qidiruv: " + data + " at "); chop etish(daraja); ) SkipNode natija = null; SkipNode joriy = this.getNext(daraja); while (joriy != null && current.data.compareTo(ma'lumotlar)< 1) { if (current.data.equals(data)) { result = current; break; } current = current.getNext(level); } return result; } void insert(SkipNodeskipNode, int darajasi) ( SkipNode joriy = this.getNext(daraja); agar (joriy == null) ( this.setNext(skipNode, level); return; ) if (skipNode.data.compareTo(current.data)< 1) { this.setNext(skipNode, level); skipNode.setNext(current, level); return; } while (current.getNext(level) != null && current.data.compareTo(skipNode.data) < 1 && current.getNext(level).data.compareTo(skipNode.data) < 1) { current = current.getNext(level); } SkipNodevoris = current.getNext(daraja); current.setNext(skipNode, level); skipNode.setNext(voris, daraja); ) void print(int level) ( System.out.print("level " + level + ": [ "); int length = 0; SkipNode joriy = this.getNext(daraja); while (joriy != null) (uzunlik++; System.out.print(current.data + " "); joriy = current.getNext(level); ) System.out.println("], uzunlik: " + uzunlik); ) ) umumiy sinf SkipList > SkipableListni amalga oshiradi (maxsus yakuniy SkipNode bosh = yangi SkipNode<>(null); xususiy final Tasodifiy rand = yangi Tasodifiy(); @Override public void insert(T data) ( SkipNode skipNode = yangi SkipNode<>(ma'lumotlar); uchun (int i = 0; i< LEVELS; i++) { if (rand.nextInt((int) Math.pow(2, i)) == 0) { //insert with prob = 1/(2^i) insert(skipNode, i); } } } @Override public boolean delete(T target) { System.out.println("Deleting " + target); SkipNodequrbon = qidiruv (maqsad, rost); agar (qurbon == null) false qaytaradi; qurbon.data = null; uchun (int i = 0; i< LEVELS; i++) { head.refreshAfterDelete(i); } System.out.println("deleted..."); return true; } @Override public SkipNodesearch(T data) ( search(data, true); ) @Override public void print() ( uchun (int i = LEVELS-1; i >= 0 ; i--) (head.print(i); ) System.out.println(); ) shaxsiy bekor kiritish (SkipNode SkipNode, int level) ( head.insert(SkipNode, level); ) xususiy SkipNode qidiruv (T ma'lumotlari, mantiqiy chop etish) ( SkipNode natija = null; uchun (int i = LEVELS-1; i >= 0; i--) ( if ((natija = head.search(maʼlumotlar, i, chop etish)) != null) ( if (chop etish) ( System.out.println) ("Topildi" + data.toString() + " darajasida " + i + ", shuning uchun to'xtatildi"); System.out.println(); ) break; ) ) natijani qaytarish; ) public static void main(String args) ( SkipList sl = yangi SkipList<>(); int ma'lumotlari = (4,2,7,0,9,1,3,7,3,4,5,6,0,2,8); for (int i: data) ( sl.insert(i); ) sl.print(); sl.search(4); sl.delete(4); System.out.println("10 qo'yish"); sl.insert(10); sl.print(); sl.search(10); ))

OʻTKAZISH buyurtmalar bilan ishlash jarayonini toʻliq avtomatlashtirish imkonini beruvchi MS SharePoint asosida buyurtmalar bajarilishini nazorat qilish tizimidir. Bu topshiriqlar bilan ishlashni tashkil qilish uchun puxta o'ylangan, tayyor echimdir. U barcha modullarning eng moslashuvchan konfiguratsiyasini ta'minlash imkoniyati tufayli yirik va geografik jihatdan taqsimlangan kompaniyalarda ham, o'rta kompaniyalar uchun ham ishlash uchun javob beradi.
SKIP tizimi Microsoft SharePoint platformasiga asoslangan bo'lib, u avtomatik ravishda Microsoft mahsulotlari, jumladan Microsoft Office bilan integratsiya qilinishi mumkinligini bildiradi.

Tizim funksionalligi

SKIP tizimi "qutili" yechim bo'lib, ushbu versiyada buyurtmalar bilan ishlashni avtomatlashtirish uchun zarur bo'lgan asosiy funktsiyalar to'plami mavjud:

Ko'rsatmalarni belgilash, bajarish, nazorat qilish;

Buyurtmaning bajarilishi holatini kuzatish;

Ichki ("bola") buyurtmalarni yaratish qobiliyati.

Rangli ko'rsatma bilan ko'rsatmalar ro'yxati

Shu bilan birga, taqdim etilgan funksionallik foydalanuvchiga tizim bilan ishlash uchun eng keng imkoniyatlarni taqdim etadigan tarzda amalga oshiriladi:

Buyurtmalarni kataloglashtirish (bitta buyurtma turli papkalarda joylashgan bo'lishi mumkin);

Buyurtmalar ro'yxatini filtrlash;

Buyurtmalar ro'yxatini MS Excelga eksport qilish;

Ishlash intizomi bo'yicha hisobotlar;

Buyurtmaning bajarilish vaqti va holatiga qarab buyurtmalarning rang ko'rsatilishi;

Buyurtma kartasiga istalgan formatdagi fayllarning ixtiyoriy sonini biriktirish imkoniyati;

Outlook kalendarlari bilan integratsiya;

Buyurtma bilan ishlashning topshirig'i va borishi haqida sozlanishi mumkin bo'lgan bildirishnomalar;

Ta'til yoki xizmat safarlarida xodimlarni almashtirish tizimi;

Muayyan davrga (uchrashuvlar, uchrashuvlar va boshqalar) ega bo'lgan tadbirlar uchun davriy buyurtmalar (yoki jadval bilan buyurtmalar) yaratish;

Gantt chartida buyurtmalarni bajarish muddatlarini ko'rsatish;

Va hokazo

Gantt diagrammasi bilan vazifalar ro'yxati

Buyurtma qilingan lug'at ADTni samarali amalga oshirish uchun qiziqarli ma'lumotlar strukturasi turi bu skip^cnucoK (o'tkazib yuborish ro'yxati). Ushbu ma'lumotlar strukturasi ob'ektlarni tasodifiy tartibda tartibga soladi:

shunday qilib, qidirish va yangilash o'rtacha 0(log n) vaqt ichida yakunlanadi, bu erda n - lug'at ob'ektlari soni. Qizig'i shundaki, bu erda qo'llaniladigan o'rtacha vaqt murakkabligi tushunchasi kirishdagi kalitlarning mumkin bo'lgan taqsimlanishiga bog'liq emas. Aksincha, u yangi ob'ektni qaerga qo'yish kerakligini hal qilish jarayonini osonlashtirish uchun kiritish jarayonini amalga oshirishda tasodifiy sonlar generatorlaridan foydalanish bilan belgilanadi. Bu holda bajarish vaqti kirish ob'ektlari sifatida ishlatiladigan har qanday tasodifiy raqamlarni kiritishning o'rtacha bajarilish vaqtiga teng bo'ladi.

Tasodifiy raqamlarni yaratish usullari ko'pchilik zamonaviy kompyuterlarga o'rnatilgan, chunki ular kompyuter o'yinlari, kriptografiya va kompyuter simulyatsiyalarida keng qo'llaniladi. Soxta tasodifiy sonlar generatorlari deb ataladigan ba'zi usullar, urug' deb ataladigan narsadan boshlab, ba'zi qonunlarga ko'ra raqamlarni psevdor tasodifiy tarzda hosil qiladi. Boshqa usullar "haqiqiy" tasodifiy sonlarni chiqarish uchun apparatdan foydalanadi. Ikkala holatda ham kompyuterda berilgan tahlilda tasodifiy sonlar uchun talablarga javob beradigan raqamlar mavjud.

Ma'lumotlar strukturasida va algoritm yaratishda tasodifiy sonlardan foydalanishning asosiy afzalligi natijada olingan tuzilmalar va usullarning soddaligi va ishonchliligidir. Shu tarzda, ikkilik qidiruv algoritmiga o'xshash logarifmik qidiruv vaqtining narxini ta'minlaydigan o'tkazib yuborish ro'yxati deb ataladigan oddiy tasodifiy ma'lumotlar strukturasini yaratish mumkin. Biroq, o'tkazib yuborish ro'yxatining kutilayotgan vaqt qiymati qidiruv jadvalidagi ikkilik qidiruvdan kattaroq bo'ladi. Boshqa tomondan, lug'atni yangilashda, o'tkazib yuborish ro'yxati qidirish jadvallariga qaraganda ancha tezroq.

D lug'at uchun o'tkazib yuborish ro'yxati S ro'yxatlar qatoridan iborat bo'lsin (iSo, S\, Si, Z/j). Har bir S\ roʻyxati kamaymaydigan tartibda tugmalar boʻyicha D lugʻat obʼyektlari toʻplamini hamda “-oo” va “+oo” sifatida yozilgan ikkita maxsus tugmachali obyektlarni saqlaydi, bunda “-oo” kamroq va “+oo” maʼnosini bildiradi. D da bo'lishi mumkin bo'lgan har qanday kalitdan ko'proq narsani anglatadi. Bundan tashqari, S dagi ro'yxatlar quyidagi talablarga javob beradi:

S 0 ro'yxati lug'atning har bir ob'ektini o'z ichiga oladi D (qo'shimcha ravishda "-oo" va "+oo" tugmachalari bilan maxsus ob'ektlar);

/ = 1, …, h – 1 uchun Si ro'yxatida ("-oo" va "+oo" dan tashqari) S t _ l ro'yxatidan tasodifiy yaratilgan ob'ektlar to'plami mavjud.

S h ro'yxatida faqat "-oo" va "+oo" mavjud.

Bunday o'tkazib yuborish ro'yxatiga misol rasmda ko'rsatilgan. 8.9, bu ro'yxat S ro'yxatini ro'yxat asosida ko'rsatadi va uning ustida S\, ..., S^ ro'yxatini ko'rsatadi. S ro'yxatning balandligini h deb belgilaymiz.

Guruch. 8.9. o'tkazib yuborish ro'yxati misoli

Intuitiv ravishda ro'yxatlar shu tarzda tuzilgan; shundaymi?/+/ kamida har ikkinchi ob'ektni o'z ichiga oladi 5/. Kiritish usulini ko'rib chiqishda ko'rsatilgandek, St+\ dagi ob'ektlar Si dagi ob'ektlardan tasodifiy tarzda tanlanadi, har bir tanlangan ob'ekt 5/ 1/2 ehtimol bilan 5/ + \ ga kiritiladi. Majoziy ma'noda, Si+1 dan ob'ektni joylashtirish yoki qo'ymaslik, uloqtirilgan tanganing qaysi tomoniga - bosh yoki dumga tushishiga qarab belgilanadi. Shunday qilib, S\ taxminan n/2 ob'ektni, S2 - n/4 va shunga mos ravishda Sj - taxminan n/2' ob'ektni o'z ichiga oladi deb taxmin qilishimiz mumkin. Boshqacha qilib aytganda, S ro'yxatining h balandligi logn haqida bo'lishi mumkin. Garchi, ob'ektlar sonini bir ro'yxatdan ikkinchisiga yarmiga qisqartirish aniq o'tkazib yuborish ro'yxati xususiyati ko'rinishidagi majburiy talab emas. Aksincha, tasodifiy tanlash muhimroqdir.

Ro'yxatlar va daraxtlarga nisbatan qo'llaniladigan pozitsion abstraktsiyadan foydalanib, biz o'tkazib yuborish ro'yxatini gorizontal ravishda darajalarga va vertikal ravishda minoralarga ajratilgan ikki o'lchovli pozitsiyalar to'plami sifatida tasavvur qilishimiz mumkin. Har bir daraja S ^ ro'yxati va har bir minora bir xil ob'ektni saqlaydigan va ro'yxatlarda bir-birining tepasida joylashgan pozitsiyalar to'plamidir. Oʻtkazib yuborish roʻyxatidagi oʻrinlarni quyidagi amallar yordamida bosib oʻtish mumkin:

after(/?): bir xil daraja yonidagi pozitsiyani qaytaradi; before(/?): p dan oldingi pozitsiyani bir xil darajada qaytaradi; below(/?): o'sha minorada p ostida joylashgan pozitsiyani qaytaradi; above(/?): Xuddi shu minoradagi p dan yuqoridagi holatni qaytaradi.

Agar so'ralgan pozitsiya mavjud bo'lmasa, yuqoridagi operatsiyalar null qaytishi kerakligini aniqlaylik. Tafsilotlarga kirmasdan, esda tutingki, o'tkazib yuborish ro'yxati bog'langan tuzilma yordamida osongina amalga oshirilishi mumkin, shunda o'tish usullari 0 (1) vaqtni talab qiladi (agar ro'yxatda p pozitsiyasi mavjud bo'lsa). Bunday bog'langan tuzilma ikki marta bog'langan h ro'yxatlar to'plami bo'lib, ular o'z navbatida ikki marta bog'langan ro'yxatlardir.

O'tkazib yuborish ro'yxati tuzilishi oddiy qidiruv algoritmlarini lug'atlarga qo'llash imkonini beradi. Aslida, barcha o'tkazib yuborish ro'yxatini qidirish algoritmlari juda oqlangan SkipSearch usuliga asoslangan bo'lib, u kalitni oladi va ob'ektni o'tish ro'yxatidagi S eng katta kaliti ("-oo" bo'lishi mumkin) dan kichik yoki teng bo'lgan holda topadi. ga k. Aytaylik, bizda kerakli kalit mavjud SkipSearch usuli o'tish ro'yxatida p ning o'rnini S o'tish ro'yxatining yuqori chap holatiga o'rnatadi. Ya'ni, p "-oo" tugmachasi bilan maxsus ob'ekt pozitsiyasiga o'rnatiladi. " S ^ da. Keyin quyidagilar amalga oshiriladi:

1) agar S.below(/?) null bo'lsa, qidiruv tugaydi - S dagi eng katta ob'ekt kerakli k kalitdan kichik yoki unga teng bo'lgan kalit quyida joylashgan darajada topiladi.Aks holda biz bir daraja pastga tushamiz. bu minora, sozlash p S.be \ow(p);

2) p pozitsiyasidan o'ngga (oldinga) o'tamiz, toki biz hozirgi darajadagi o'ta o'ng holatidamiz, bu erda keu(/?)< к. Такой шаг называется сканированием вперед (scan forward). Указанная позиция существует всегда, поскольку каждый уровень имеет специальные ключи «+оо» и «-оо». И на самом деле, после шага вправо по текущему уровню р может остаться на исходном месте. В любом случае после этого снова повторяется предыдущее действие.

Guruch. 8.10. O'tkazib yuborish ro'yxatida qidirishga misol. Kalitlarni qidirish paytida tekshirilgan 50 ta pozitsiya chiziqli belgi bilan ta'kidlangan

Kod fragmenti 8.4 o'tkazib yuborish ro'yxatini qidirish algoritmining tavsifini o'z ichiga oladi. Bunday usulga ega bo'lgan holda findElement(/:) operatsiyasini amalga oshirish oson. p^-SkipSearch(A;) operatsiyasi bajariladi va tenglik kaliti(p)~ k tekshiriladi. Agar ^ teng bo'lsa, /?.element qaytariladi. Aks holda, NO_SUCH_KEY signalli xabar qaytariladi.

SkipSearch(/:) algoritmi:

Kirish: qidiruv tugmasi.

Chiqish: ob'ekti eng katta kaliti k dan kichik yoki unga teng bo'lgan S dagi p pozitsiyasi.

Faraz qilaylik, p S ning yuqori chap pozitsiyasi (kamida ikkita darajadan iborat), pastda (p) * null do

r quyida(p) (pastga skanerlash) tugmasi (so'ng(p))< к do

p after(p) (oldinga skanerlash) p qaytsin

Kod parchasi 8.4. O'tkazib yuborish ro'yxatida qidirish algoritmi S

Ma'lum bo'lishicha, SkipSearch algoritmining taxminiy bajarilish vaqti 0 (log n) ga teng. Buni asoslashdan oldin, biz o'tkazib yuborish ro'yxatini yangilash usullarini amalga oshirishni taqdim etamiz