Grafiklarda qanday fikrlash kerak: Grafika nazariyasi va uning qo'llanmalariga tasviriy kirish

Grafika nazariyasini tushunish qiyin bo'lishi mumkin

Grafika nazariyasi kompyuter fanidagi eng muhim va qiziqarli yo'nalishlardan birini anglatadi. Ammo shu bilan birga bu eng noto'g'ri tushunilgan narsalardan biri (hech bo'lmaganda men uchun bu).

Grafiklarni tushunish, ishlatish va o'ylash bizni dasturchilarni yaxshiroq qiladi. Hech bo'lmaganda shunday deb o'ylashimiz kerak. Grafik - bu V qirralarning to'plami va E qirralarning to'plami bo'lib, G = (V, E) buyurtma qilingan juftlikdan iborat.

Grafika nazariyasini o'rganishga va ba'zi algoritmlarni amalga oshirishga harakat qilayotganda, men zerikkanligi sababli, muntazam ravishda qoqilib turardim.

Biror narsani tushunishning eng yaxshi usuli uning qo'llanilishini tushunishdir. Ushbu maqolada biz grafika nazariyasining turli xil amaliy dasturlarini namoyish qilmoqchimiz. Ammo bundan ham muhimi, ushbu ilovalarda batafsil rasmlar mavjud. Shunday qilib, ishga kirishish va sho'ng'in qilish.

Ushbu yondashuv juda tajribali (tajribali dasturchilar uchun) juda tuyulishi mumkin, ammo menga ishoning, u erda bo'lgan va grafika nazariyasini tushunishga harakat qilgan kishi kabi batafsil tushuntirish har doim qisqa ta'riflardan afzalroqdir.

Shunday qilib, agar siz "grafika nazariyasi va u haqida hamma narsani mutlaqo aqlga sig'maydigan nogironlar uchun darslik" izlayotgan bo'lsangiz, unda siz to'g'ri joyga keldingiz. Yoki hech bo'lmaganda umid qilaman. Shunday qilib, ishga kirishish va sho'ng'in qilish.

U Monte-Kristoni nazarda tutgan edi

Mundarija

  • Ogohlantirishlar
  • Konigsbergning ettita ko'prigi
  • Grafik namoyishi: Kirish
  • Graf vakili va ikkilik daraxtlar bilan tanishish (Airbnb misoli)
  • Grafik namoyishi: Outro
  • Twitter misol: tvitni etkazib berish muammosi
  • Grafik algoritmlari: kirish
  • Netflix va Amazon: teskari indeksli misol
  • Shikastlanishlar: DFS va BFS
  • Uber va eng qisqa yo'l muammosi (Dijkstraning algoritmi)

Ogohlantirishlar

1-QISM: Men CS, algoritmlar, ma'lumotlar tuzilmalari va ayniqsa grafika nazariyasi bo'yicha mutaxassis emasman. Men ushbu maqolada muhokama qilingan kompaniyalar uchun biron bir loyihada qatnashmayman. Muammolarni hal qilish yakuniy emas va ularni tubdan yaxshilash mumkin. Agar biron-bir muammo yoki biron bir asossiz narsani topsangiz, sharh qoldirishga xush kelibsiz. Agar siz yuqorida qayd etilgan kompaniyalardan birida ishlasangiz yoki tegishli dasturiy loyihalarda ishtirok etsangiz, iltimos, haqiqiy echim bilan javob bering (bu boshqalarga ham foydali bo'ladi). Qolganlarga sabrli kitobxon bo'ling, bu juda uzun maqol.

2-MAVZU: Ushbu maqola ma'lumotlar taqdim etiladigan uslubda bir oz farq qiladi. Ba'zan bu pastki mavzudan biroz xiralashgan bo'lib tuyulishi mumkin, ammo sabrli o'quvchilar oxir-oqibat katta rasmni to'liq tushunib olishadi.

DISCLAIMER 3: Ushbu maqola keng dasturchilar uchun mo'ljallangan. Maqsadli auditoriya sifatida yosh dasturchilar bo'lish bilan birga, bu tajribali mutaxassislar uchun ham qiziqarli bo'ladi.

Konigsbergning ettita ko'prigi

Men grafika nazariyasi kitoblarida muntazam ravishda duch keladigan narsalarni, Gonigsbergning ettita ko'prigi (haqiqatan ham aniq emas, lekin uni "qyonigsberg" deb talaffuz qilishingiz mumkin) haqida munozara qiladigan narsadan boshlaylik. Kaliningradda Pregolya daryosi bilan o'ralgan ikkita katta orolni va bir xil daryoga bo'lingan ikkita materik qismini bog'laydigan ettita ko'prik bor edi.

Bizning qiziqish doiramiz

18-asrda bu Konyigsberg (Prussiyaning bir qismi) deb nomlangan va yuqoridagi hududda ko'priklar ko'p bo'lgan. Muammo yoki shunchaki Königsberg ko'prigi bo'lgan miya tizeri barcha ettita ko'prikdan bir marta o'tib shahar bo'ylab yurish kerak edi. O'sha paytda ularda Internet yo'q edi, shuning uchun u ko'ngil ochar edi. Bu erda 18-asrdagi Konigsbergning ettita ko'prigi tasvirlangan.

Königsbergning ettita ko'prigi

Urunib ko'r. Har bir ko'prikdan faqat bir marta o'tib, shahar bo'ylab yurishingiz mumkinligini ko'ring.

  • Hech qanday kesilmagan ko'prik (lar) bo'lmasligi kerak.
  • Har bir ko'prikni bir necha marta kesib o'tish kerak emas.

Agar siz ushbu muammo bilan tanish bo'lsangiz, bilasizki, buni amalga oshirish mumkin emas. Garchi siz etarlicha astoydil harakat qilsangiz va hozir ham ko'proq urinib ko'rsangiz ham, oxirida taslim bo'lasiz.

Leonhard Eyler (Vikipediyadan olingan surat)

Ba'zan ro'za tutish oqilona. Eyler bu muammoni shunday hal qildi - u tezda taslim bo'ldi. Uni hal qilishga urinishning o'rniga, u har bir ko'prikdan bir martagina o'tib shahar bo'ylab yurishning iloji yo'qligini isbotlashga urinib ko'rdi.

Keling, Eyler qanday fikr yuritishini va echimni qanday topganini tushunishga harakat qilaylik (agar echim topilmasa, bu hali ham isbot talab qiladi). Bu juda qiyin masala, chunki bunday obro'li matematikning fikrlash jarayonidan o'tish - bu juda nohaqdir. (Knut va uning do'stlari o'z kitoblarini Leonhard Eylerga bag'ishladilar). Biz "Eyler singari o'ylashga" moyil bo'lamiz. Mumkin bo'lmagan narsalarni tasvirlashni boshlaylik.

To'rtta alohida joy, ikkita orol va materikning ikki qismi mavjud. Va ettita ko'prik. Orollarga yoki materikga ulangan ko'priklar soniga oid biron bir holat mavjudligini bilish qiziq (biz to'rtta aniq joyni nazarda tutish uchun “er” atamasidan foydalanamiz).

Ko'priklar soni

Bir qarashda qandaydir naqsh borga o'xshaydi. Har bir er bilan bog'langan toq sonli ko'priklar mavjud. Agar siz har bir ko'prikdan bir marta o'tishingiz kerak bo'lsa, unda siz 2 ta ko'prik bo'lsa, siz quruqlikka kirib, uni tark etishingiz mumkin.

2 ko'prik erlariga misollar

Yuqoridagi rasmlardan ko'rinib turibdiki, agar siz bitta ko'prikdan o'tib, quruqlikka kirsangiz, siz har doim ikkinchi ko'prikdan o'tib, erni tark etishingiz mumkin. Uchinchi ko'prik paydo bo'lganda, siz uning barcha ko'priklarini kesib o'tib, erni tark eta olmaysiz. Agar siz ushbu fikrni bitta bo'lak uchun umumlashtirishga harakat qilsangiz, siz ko'p sonli ko'priklar mavjud bo'lganda har doim erni tark etishingiz mumkinligini va toq sonli ko'priklar mavjud bo'lmasligini ko'rsata olasiz. t. Buni miyangizda sinab ko'ring!

Umumiy ko'priklar soni o'zgarishini va muammoni hal qiladimi yo'qmi, yangi ko'prik qo'shaylik.

Yangi ko'prikka e'tibor bering

Endi to'rtta er uchastkasini bog'laydigan ikkita (4 va 4) va ikkita toq (3 va 5) ko'priklar bor ekan, yangi ko'prik qo'shilishi bilan yangi marshrut chizamiz.

Qoyil

Yechish mumkinligini aniqlashda juft va toq sonli ko'priklarning soni muhim rol o'ynaganini ko'rdik. Mana bir savol. Ko'priklar soni muammoni hal qiladimi? Har doim bo'lishi kerakmi? Bunday emasligi ma'lum bo'ldi. Eyler shunday qildi. U ko'priklar soni muhimligini ko'rsatadigan usul topdi. Va yana qiziq tomoni shundaki, toq ulangan ko'priklarning soni bo'lgan erlar soni ham muhimdir. Aynan shu payt Eyler erlar va ko'priklarni biz grafik deb biladigan narsaga «aylantira» boshladi. Konigsberg ko'priklari muammosini aks ettiruvchi grafik qanday ko'rinishga ega (bizning "vaqtincha" qo'shilgan ko'prik u erda yo'qligini unutmang).

Chiziqlar biroz burishgan

Ta'kidlash kerak bo'lgan muhim narsa bu muammoni umumlashtirish / mavhumlashtirish. Har doim biron bir muammoni hal qilganda, eng muhimi, shunga o'xshash muammolarning echimini umumlashtirishdir. Ushbu vaziyatda Eylerning vazifasi kelajakda shunga o'xshash muammolarni, ya'ni dunyodagi barcha ko'priklarni hal qilish uchun ko'priklarni kesib o'tish muammosini umumlashtirish edi. Vizualizatsiya muammoni boshqa tomondan ko'rib chiqishga yordam beradi. Quyidagi grafikalar yuqorida ko'rsatilgan bitta Königsberg ko'prigi muammosining barcha turli xil ko'rinishlarini o'z ichiga oladi.

Ha, vizual grafikalar muammolarni tasvirlash uchun yaxshi tanlovdir. Ammo endi biz Konigsberg muammosini grafikalar yordamida qanday hal qilish mumkinligini aniqlashimiz kerak. Har bir doiradan chiqadigan chiziqlar soniga e'tibor bering. Ha, ularni tajribali mutaxassislar aytganidek nomlaylik, bundan keyin biz doira, uchlari va ularni bog'laydigan chiziqlar, chekkalarni chaqiramiz. Siz V uchun (vendetta?) Vertex, V chetiga E harflarini ko'rishingiz mumkin.

Keyingi muhim narsa - verteksning deb ataladigan darajasi, verteksga ulangan qirralarning soni. Yuqoridagi bizning misolimizda erlarga ulangan ko'priklarning soni grafik uchining darajalari bilan ifodalanishi mumkin.

Eyler o'z harakatida grafik (shahar) orqali har bir chetni (ko'prikni) kesib o'tish imkoniyati faqat tepaliklar (erlar) darajalariga bog'liqligini ko'rsatdi. Bu qirralardan iborat yo'l (uning sharafiga) Eyler yo'li deb ataladi. Eyler yo'lining uzunligi - qirralarning soni. Qattiq tilni o'rganishga tayyorlaning.

G (V, E) yo'naltirilmagan grafikning Eyler yo'li - bu shunday yo'lki, uning har bir qirrasi bir marta paydo bo'ladi. Agar Gda Eyler yo'li bo'lsa, u Eyler grafigi deb nomlanadi. [1]
Teorema. To'g'ri yo'naltirilmagan ulangan grafik, agar ikkita vertikal toq darajadagi yoki barcha uchlari teng darajadagi bo'lsa, bu Eyler grafigi hisoblanadi. Ikkinchi holda, grafikaning har bir Eyler yo'li - bu kontaktlarning zanglashiga olib keladi, va oldingi holatda, hech biri. [1]
Chapdagi rasmda ikkita vertikalning toq darajalari bor va barcha uchlari o'ngdagi rasmda g'alati darajaga ega

“Eyler yo'li” o'rniga “Eyler yo'li” dan shunchaki havolali kitoblar ta'rifiga mos kelish uchun foydalanganman. Agar siz Euler va Eulerian yo'llarini va Eyler grafigi va Eyler grafigini farq qiladigan kishini bilsangiz, ularga sharh qoldirishingizni aytib bering.

Avvalo, yuqoridagi ta'rif va teoremada yangi atamalarni aniqlab olaylik.

  • Yo'naltirilmagan grafik - chekkalar uchun ma'lum bir yo'nalishga ega bo'lmagan grafik.
  • Yo'naltirilgan grafik - chekkalari ma'lum yo'nalishga ega bo'lgan grafik.
  • Ulangan grafik - erishib bo'lmaydigan uchi bo'lmagan grafik. Har bir vertikal juftlik o'rtasida yo'l bo'lishi kerak.
  • Uzilgan grafik - erishib bo'lmaydigan uchlari mavjud bo'lgan grafik. Har bir vertikal juftlik o'rtasida yo'l yo'q.
  • Cheklangan grafik - tugallangan va tugagan sonli sonli grafik.
  • Cheksiz grafik - grafikning ma'lum bir yo'nalishda (yo'nalishlarda) oxiri cheksizgacha cho'zilgan grafik.

Kelgusi paragraflarda ushbu atamalarning ba'zilarini muhokama qilamiz.

Graflarni yo'naltirish va yo'naltirish mumkin, va bu grafiklarning qiziq xususiyatlaridan biridir. Siz yo'naltirilgan va yo'naltirilmagan grafikalar uchun mashhur Facebook va Twitter-ning misolini ko'rishingiz kerak. Facebook bilan do'stona aloqani osonlikcha boshqarib bo'lmaydigan grafik sifatida ko'rsatish mumkin, chunki agar Elis Bob bilan do'st bo'lsa, u holda Bob Alis bilan ham do'st bo'lishi kerak. Yo'nalish yo'q, ikkalasi ham bir-birlari bilan do'stdirlar.

Yo'naltirilmagan grafik

Shuningdek, "Patrik" deb belgilangan yoriqqa e'tibor bering, bu juda o'ziga xos (u erda do'stlar yo'q), chunki u erda hech qanday hodisa yo'q. Bu hali ham grafikning bir qismi, ammo bu holda biz bu grafik ulanmagan deb aytamiz, bu uzilgan grafikdir (xuddi "Jon", "Ashot" va "Bet" bilan birlashadi, chunki ular bir-biri bilan o'zaro bog'langan. lekin boshqalardan ajratilgan). Ulangan grafada cho'qqiga etib bo'lmaydigan uchlik mavjud emas, uning har bir juft uchi o'rtasida yo'l bo'lishi kerak.

Facebook misolidan farqli o'laroq, agar Elis Twitter-da Bobga ergashsa, bu Bobdan Elisning orqasidan yurishini talab qilmaydi. Shunday qilib, "ergashish" munosabati yo'naltiruvchi ko'rsatkichga ega bo'lishi kerak, bu vertex (foydalanuvchi) boshqa verteksga yo'naltirilgan qirraga ega (foydalanuvchi).

Endi cheklanmagan boshqarilmagan grafik nima ekanligini bilib, Euler grafigiga qaytaylik:

Xo'sh, nima uchun birinchi navbatda Königsberg ko'priklari muammosi va Eyler grafigini muhokama qildik? Xo'sh, unchalik zerikarli emas va muammoni tadqiq qilib, yuqorida ko'rsatilgan echim bilan biz quruq nazariy yondashuvdan qochib, grafiklar orqasidagi elementlarga tegdik (tepa, chekka, yo'naltirilgan, yo'naltirilmagan). Yo'q, biz Eyler grafikasi va yuqoridagi muammoni hal qilganimiz yo'q.

Endi biz grafiklarni kompyuter vakolatiga o'tishga harakat qilishimiz kerak, chunki bu biz uchun dasturchilar uchun qiziqish uyg'otadigan mavzu. Grafikani kompyuter dasturida aks ettirish orqali biz grafik yo'l (lar) ni kuzatish algoritmini ishlab chiqamiz va shuning uchun uning Eyler yo'li ekanligini aniqlaymiz. Undan oldin, Eyler grafigi uchun juda yaxshi dastur haqida o'ylashga harakat qiling (ko'priklarni aylanib o'tishdan tashqari).

Grafik namoyishi: Kirish

Endi bu juda qiyin vazifa, shuning uchun sabrli bo'ling. Arrays va bog'langan ro'yxatlar o'rtasidagi kurash esingizdami? Agar siz elementlarga tezkor kirishingiz kerak bo'lsa, massivlardan foydalaning, agar siz tez elementlarni kiritish / o'chirish va hokazolarga muhtoj bo'lsangiz, ro'yxatlardan foydalaning va hokazo. Men sizga "ro'yxatlarni qanday taqdim etish kerak" kabi narsalar bilan duch kelganingizga ishonmayman. Xo'sh, agar grafikalar mavjud bo'lsa, ularning haqiqiy vakili juda bezovta qiladi, chunki avval siz grafikni qanday aniq ko'rsatishni aniqlaysiz. Va menga ishoning, bunday qilishni xohlamaysiz. Yopishqoqlik ro'yxati, qo'shni matritsa, ehtimol chekka ro'yxatlar? Bir tanga tashlang.

Siz qattiq chayqalishingiz kerak, chunki biz daraxtdan boshlaymiz. Ikkilamchi daraxtni (yoki BT qisqasi) kamida bir marta ko'rgan bo'lsangiz kerak (quyida ikkilik izlash daraxti emas).

Faqat namuna

U vertikal va chekkadan iborat bo'lgani uchun, bu grafik. Ikkilik daraxti qanday aks ettirilganligini eslab qolishingiz mumkin (hech bo'lmaganda darsliklarda).

Ikkilik daraxtlar bilan yaxshi tanish bo'lgan odamlar uchun bu juda oddiy bo'lib tuyulishi mumkin, ammo men hali ham bir sahifada ekanligimizga ishonch hosil qilish uchun uni tasvirlashim kerak (biz hali ham psevdokod bilan shug'ullanayotganimizni unutmang).

Agar siz daraxtlar bilan tanish bo'lsangiz, yuqoridagi psevdokodni diqqat bilan o'qing, keyin quyidagi rasmdagi amallarni bajaring.

Ranglar shunchaki yorqin ingl

Ikkilik daraxti - bu har bir chap va o'ng bolalar tugunlari bo'lgan oddiy "to'plam". Ikkilik izlash daraxti juda foydali, chunki u tezkor kalitlarni qidirishga imkon beradigan bitta oddiy qoidani qo'llaydi. Ikkilamchi qidirish daraxtlari (BST) kalitlarini tartiblangan holda saqlaydi. Siz BT-ni xohlagan qoidangiz bilan amalga oshirishingiz mumkin (garchi u qoida asosida uning nomini o'zgartirishi mumkin, masalan, min-evap yoki maksimal-heap). BST uchun eng muhim kutish bu ikkilik qidiruv xususiyatini qondirishdir (ism shu erda paydo bo'ladi). Har bir tugunning kaliti chap pastki daraxtning kalitidan kattaroq va o'ng pastki daraxtning kalitidan kichik bo'lishi kerak.

Men BSTning qanday ishlashini tushunish uchun juda muhim bo'lgan "kattaroq" degan bayonga nisbatan juda qiziq bir narsani ta'kidlamoqchiman. Mulkni har doim "kattaroq yoki teng" ga o'zgartirsangiz, BST yangi tugunlarni kiritish paytida takroriy tugmachalarni saqlashi mumkin, aks holda u noyob tugmachalarga ega tugunlarni saqlab qoladi. Internetda ikkitomonlama qidirish daraxtlari haqida haqiqatan ham yaxshi maqolalarni topishingiz mumkin. Biz ikkitomonlama qidirish daraxtining to'liq bajarilishini ta'minlay olmaymiz, ammo moslik uchun biz bu erda oddiy ikkilik qidirish daraxtini tasvirlaymiz.

Graf vakili va ikkilik daraxtlar bilan tanishish (Airbnb misoli)

Daraxtlar juda foydali ma'lumotlar tuzilmasi. Siz o'zingizning loyihalaringizda noldan daraxt yasamagan bo'lishingiz mumkin. Ammo, ehtimol siz ulardan bexabar holda ham foydalangansiz. Keling, sun'iy, ammo qimmatli misolni ko'rib chiqaylik va "nima uchun avval ikkilik qidirish daraxtini ishlatish kerak" savoliga javob berishga harakat qilaylik.

Siz payqaganingizdek, ikkilik izlash daraxtida "qidirish" mavjud. Shunday qilib, tezkor qidiruvga muhtoj bo'lgan barcha narsalar ikkilik qidirish daraxtiga joylashtirilishi kerak. "Kerak" degani shart degani emas, dasturlashda yodda tutish kerak bo'lgan eng muhim narsa mos vositalar bilan muammoni hal qilishdir. Oddiy bog'langan ro'yxatni O (N) izlash bilan BSTga qaraganda (O (logN)) afzalroq bo'lgan holatlar ko'p.

Odatda biz BST ning kutubxonaviy qo'llanmasidan, ehtimol std :: set yoki std :: xaritadan C ++ da foydalanamiz. Biroq, ushbu o'quv qo'llanmada biz o'z g'ildiraklarimizni ixtiro qilishimiz mumkin. BSTlar deyarli har qanday umumiy maqsadli dasturlash tilidagi kutubxonada amalga oshiriladi. Siz ularni sevimli tilingizning tegishli hujjatlarida topishingiz mumkin. "Hayotiy misol" ga murojaat qilsak, biz hal qiladigan muammoni - Airbnb Home Search.

Airbnb uylarini qidirish haqida qisqacha ma'lumot

Qanday qilib ba'zi so'rovlar asosida uylarni iloji boricha tezroq filtrlar bilan qidiramiz. Bu qiyin ish. Agar biz Airbnb 4 million ro'yxatini saqlayotganini hisobga olsak, bu qiyinlashadi.

Shunday qilib, foydalanuvchilar uylarni qidirishda ma'lumotlar bazasida saqlangan 4 million yozuvga "tegishi" mumkin. Natijalar veb-saytning bosh sahifasida ko'rsatilgan "eng yaxshi ro'yxatlar" bilan cheklangan va foydalanuvchi millionlarni ro'yxatini ko'rish uchun deyarli hech qachon "etarlicha" qiziqtirmaydi. Menda Airbnb haqida hech qanday tahlil yo'q, ammo biz dasturlarda "taxminlar" deb nomlangan kuchli vositadan foydalanishimiz mumkin. Shunday qilib, bitta foydalanuvchi eng ko'p ~ 1K uyni ko'rib chiqish orqali yaxshi uy topadi deb taxmin qilamiz.

Bu erda eng muhim omil real vaqtda foydalanuvchilar soni hisoblanadi, chunki u ma'lumotlar tuzilmalari va ma'lumotlar bazalarini tanlashda va umuman loyihaning arxitekturasida farq qiladi. Ko'rinib turibdiki, agar 100 ta foydalanuvchi bo'lsa, biz umuman bezovta qilmasligimiz mumkin.

Aksincha, agar foydalanuvchilar soni va real vaqt rejimida foydalanuvchilar soni millionlab chegaradan oshsa, biz har bir qaror haqida oqilona o'ylashimiz kerak. "Har biri" aniq ishlatilgan, shuning uchun kompaniyalar xizmatlarni taqdim etishda ustunlikka intilayotib, eng yaxshisini yollashadi.

Google, Facebook, Airbnb, Netflix, Amazon, Twitter va boshqalar juda katta hajmdagi ma'lumotlar bilan shug'ullanishadi va har soniyada millionlab baytlarga millionlab real vaqtda foydalanuvchilarga to'g'ri muhandislarni yollashni boshlashdan iborat. Shuning uchun biz, dasturchilar, ushbu ma'lumotlar tuzilmalari, algoritmlar va mumkin bo'lgan intervyularda muammolarni hal qilish bilan kurashamiz, chunki ularga kerak bo'lgan narsa bu kabi katta muammolarni imkon qadar tez va samarali hal qilish qobiliyatiga ega bo'lgan muhandis.

Shunday qilib, foydalanish holati. Foydalanuvchi uy sahifasiga tashrif buyuradi (biz hali ham Airbnb haqida gaplashmoqdamiz) va uylarni eng yaxshi mos keladigan joyni qidirish uchun filtrlashga harakat qilmoqda. Ushbu muammoni qanday hal qilardik? (E'tibor bering, bu muammo orqada emas, shuning uchun biz uy tarmog'iga yoki http yoki Amazon EC2 orqali https yoki boshqa trafikka ahamiyat bermaymiz).

Avvalo, biz dasturchilar ro'yxatidagi eng kuchli vositalardan biri bilan tanish bo'lganligimiz sababli (abstraktsiyalar haqida emas, balki taxminlar haqida gaplashamiz), bir necha taxminlardan boshlaylik:

  • RAMga to'liq mos keladigan ma'lumotlar bilan ishlaymiz.
  • Bizning operativ xotiramiz etarlicha katta.

Kutish uchun etarlicha katta, hmm, qancha? Bu juda yaxshi savol. Haqiqiy ma'lumotlarni saqlash uchun qancha xotira talab qilinadi. Agar biz 4 million birlik ma'lumot bilan ishlayotgan bo'lsak (yana taxmin qilaman) va agar biz har bir birlik hajmini bilsak, kerakli xotiraning hajmini, ya'ni 4M * sizeof (one_unit) ni osongina olishimiz mumkin.

"Uy" ob'ekti va uning xususiyatlarini ko'rib chiqaylik. Aslida, hech bo'lmaganda muammoni hal qilishda qanday xususiyatlarga ega bo'lishini ko'rib chiqaylik ("uy" bu bizning jihozimiz). Biz uni ba'zi bir psevdokodda C ++ strukturasi sifatida namoyish etamiz. Siz uni MongoDB sxemasi ob'ekti yoki xohlagan narsangizga osongina o'zgartira olasiz. Biz shunchaki mulk nomlari va turlarini muhokama qilamiz (kosmik iqtisodiyot uchun bitfildlar yoki bitetslardan foydalanish haqida o'ylashga harakat qiling).

Yuqoridagi tuzilish mukammal emas (aniq) va ko'plab taxminlar va / yoki to'liq bo'lmagan qismlar mavjud. Men shunchaki Airbnb filtrlarini ko'rib chiqdim va qidiruv so'rovlarini qondirish uchun mavjud bo'lishi kerak bo'lgan mulk ro'yxatini tuzdim. Bu shunchaki bir misol.

Endi har bir AirbnbHome ob'ektini xotirada qancha bayt olishini hisoblashimiz kerak.

  • Uy nomi - bu ko'p tilli ismlar / sarlavhalarni qo'llab-quvvatlash uchun ishlatiladigan string, bu har bir belgi 2 baytni oladi (agar biz boshqa tilni ishlatmoqchi bo'lsak, belgilar hajmi bilan bezovta qilmasligimiz mumkin, lekin C ++ tilida 1 baytli belgi, va wchar 2). -qabul qilingan belgi). Airbnb-ning ro'yxatlariga qisqacha nazar tashlash, uyning nomi 100 belgidan iborat bo'lishi kerakligini taxmin qilishimizga imkon beradi (garchi asosan 100 emas, balki 50 atrofida), biz 100 belgini maksimal qiymat sifatida qabul qilamiz, bu esa ~ ga olib keladi. 200 bayt xotira. uint - 4 bayt, uchar - 1 bayt, ushort - 2 bayt (yana, bizning taxminlarimizda).
  • Rasmlar - Fotosuratlar Amazon S3 kabi ba'zi saqlash xizmatlarida yashaydi (men bilaman, bu taxmin Airbnb uchun to'g'ri bo'lishi mumkin, ammo yana Amazon S3 bu taxmin)
  • Fotosurat URL-lari - Bizda bu fotosurat URL-lari bor va URL-larda standart o'lchov chegarasi yo'qligini hisobga olsak, lekin taniqli 2083 belgidan iborat chegara mavjud bo'lsa, biz uni har qanday URL-ning maksimal hajmi sifatida olamiz. . Shunday qilib, har bir uyda o'rtacha 5 ta fotosurat mavjudligini hisobga olsak, bu ~ 10Kb gacha.
  • Fotosurat identifikatorlari - Keling, bu haqda qayta o'ylab ko'raylik. Odatda saqlash xizmatlari http (lar) kabi bir xil bazaviy URL-larga ega tarkibga xizmat qiladi: //s3.amazonaws.com/ / , ya'ni URL-larni qurish uchun umumiy naqsh mavjud va biz faqat haqiqiylarni saqlashimiz kerak. foto ID. Aytaylik, biz bir nechta noyob ID generatoridan foydalanamiz, u 20 baytlik noyob mag'lubiyat identifikatorini qaytaradi, bu erda fotosurat ob'ektlari va ma'lum bir fotosurat uchun URL manzili https://s3.amazonaws.com/some-know-bucket/. Bu bizga bo'shliqni tejashga imkon beradi, shuning uchun beshta fotosuratning simli identifikatorlarini saqlash uchun bizga 100 bayt xotira kifoya qiladi.
  • Xost identifikatori - Xuddi shu "hiyla" ni (yuqoridagi) host_id yordamida amalga oshirish mumkin, ya'ni uy egasi foydalanuvchi identifikatori 20 bayt xotirani oladi (aslida biz foydalanuvchilar uchun faqat integer identifikatoridan foydalanishimiz mumkin, ammo ba'zi MB tizimlari kabi MongoDB juda o'ziga xos noyob identifikator generatoriga ega, biz 20 bayt uzunlikdagi mag'lubiyat identifikatorini olamiz, chunki ba'zi bir "median" qiymati biroz o'zgargan holda deyarli har qanday MB tizimiga to'g'ri keladi. Mongo identifikatorining uzunligi 24 bayt). Va nihoyat, biz 8 baytli ob'ekt sifatida 32 bayt hajmdagi 32 bitgacha bo'lgan hajmni va 32 va 64 bit orasidagi o'lchamdagi bitsetni olamiz. Taxminlarni eslang. Biz ushbu misolda bitsetni har qanday xususiyatni ifodalaydigan, ammo bir nechta qiymatlarni olishga qodir bo'lgan, boshqacha qilib aytganda bir nechta tanlov katakchalarini ishlatadigan har qanday mulk uchun qo'lladik.
Airbnb uyi uchun qulayliklar

Yomonliklar - Har bir Airbnb uyi mavjud qulayliklar ro'yxatini saqlab turadi, masalan. "Temir", "yuvish vositasi", "televizor", "wifi", "ilgichlar", "tutun detektori" va hattoki "noutbuk uchun qulay ish maydoni" va boshqalar. 20 dan ortiq qulayliklar bo'lishi mumkin, biz Airbnb filtrlari sahifasida filtrlanadigan qulayliklar soni sababli 20 ga yopishamiz. Bitset, agar biz qulayliklarni to'g'ri buyurtma qilsak, bizga yaxshi joyni tejaydi. Masalan, agar uy yuqorida aytilgan barcha qulayliklarga ega bo'lsa (ekran rasmidagi tanlanganlarni ko'ring), biz bitsetda mos keladigan joyga birozgina o'rnatamiz.

Bitset atigi 20 bitdan foydalanib, 20 xil qiymatni tejashga imkon beradi

Masalan, uyda "yuvish vositasi" borligini tekshirish:

Yoki biroz professionalroq:

Kodni xohlaganingizcha yaxshilashingiz mumkin (va kompilyatsiya qilingan xatolarni tuzating). Biz shunchaki ushbu muammoli kontekstda bitsetsning g'oyasini ta'kidlamoqchimiz.

  • Uy qoidalari, uy turi - xuddi shunday g'oya (biz qulayliklar sohasida amalga oshirganmiz) "uy qoidalari", "uy turi" va boshqalar bilan bog'liq.
  • Mamlakat kodi, Shahar nomi - Nihoyat, mamlakat kodi va shahar nomi. Yuqoridagi kod sharhlarida aytib o'tilganidek (izohlarga qarang), biz geografik fazoviy so'rovlardan qochish uchun kenglik va uzunlikni saqlamaymiz (boshqa maqolaning mavzusi). Buning o'rniga, biz manzilni qidirishni qisqartirish uchun mamlakat kodi va shahar nomini saqlaymiz (soddaligi uchun ko'chalarni qoldiring, iltimos, meni kechiring). Mamlakat kodi 2 ta belgi, 3 ta belgi yoki 3 ta raqamdan iborat bo'lishi mumkin, biz raqamli tasvirni saqlaymiz va buning uchun ushortdan foydalanamiz. (Un) Yaxshiyamki, mamlakatlarga qaraganda ko'proq shaharlar ko'p, shuning uchun biz "shahar kodi" dan foydalana olmaymiz (garchi biz uni ichki foydalanish uchun yaratsak ham). Buning o'rniga biz shahar nomini va Taumatawhakatangihangakoauauotamateaturipukakapikimaungahoronukupokaiwhenuakitanatahu (85 harfli shahar) uchun o'rtacha 50 baytni saqlagan holda haqiqiy shahar nomini saqlaymiz. Biz qo'shimcha buoole o'zgaruvchisidan foydalansak, bu aniq shaharning uzunligini anglatadi (talaffuz qilmang). Shunday qilib, satrlar va vektorlarning ustki qismini yodda saqlang. Biz strukturaning yakuniy hajmiga qo'shimcha 32 baytni qo'shamiz (har holda). Biz 64 bitli tizimda ishlaymiz deb taxmin qilamiz, garchi biz int va qisqa uchun juda ixcham qiymatlarni tanlagan bo'lsak.

Shunday qilib, 420+ bayt, 32 bayt, 452 bayt va ba'zi birlaringiz shunchaki hizalanish omiliga e'tibor berishingiz mumkinligini hisobga olib, uni 500 baytga yig'amiz. Shunday qilib, har bir "uy" ob'ekti 500 baytni o'z ichiga oladi va barcha uy ro'yxatlari uchun (ro'yxatlar soni va uyning haqiqiy soni bilan bir nechta chalkash daqiqalar bo'lishi mumkin, agar menda biron bir xato bo'lsa, menga xabar bering), 500 bayt * 4 million = 1.86GB ~ 2GB. To'g'ri ko'rinadi. Strukturani yaratishda biz juda ko'p taxminlarni qildik, bu xotirani saqlashni arzonlashtirdi, men aslida 2 gigabaytdan ko'proq narsani kutgan edim va agar hisob-kitoblarda xato qilsam, menga xabar bering. Qanday bo'lmasin, oldinga siljiymiz, shuning uchun ushbu ma'lumotlar bilan nima qilsak ham, bizga kamida 2 GB xotira kerak bo'ladi. Agar zeriksangiz, u bilan shug'ullaning. Biz endi boshlaymiz.

Endi vazifaning eng qiyin qismi. Ushbu muammo uchun to'g'ri ma'lumotlar tuzilishini tanlash (ro'yxatlarni iloji boricha samarali ravishda filtrlash) eng qiyin ish emas. Ro'yxatlarni filtrlar bo'yicha qidirish eng qiyin vazifa (men uchun). Agar bitta qidirish kaliti bo'lsa (faqat bitta filtr), biz uni osongina echib olamiz. Aytaylik, foydalanuvchilar uchun yagona narsa bu narx, shuning uchun bizga kerak bo'lgan narsa AirbnbHome ob'ektlarini topishdir, bu esa narxlar berilgan doirada tushadi. Agar biz buning uchun ikkilik qidirish daraxtidan foydalansak, u qanday ko'rinishi mumkin.

Agar siz 4 million narsaning barchasini tasavvur qilsangiz, bu daraxt juda katta o'sadi. Aytgancha, xotira ustki qismi ham o'sadi, chunki biz ob'ektlarni saqlash uchun BST-dan foydalanganmiz. Har bir ota-ona tugunida chap va o'ng bolada ikkita qo'shimcha ko'rsatkich mavjud bo'lganligi sababli, har bir bola ko'rsatkichi uchun (64-bitli tizim) 8 tagacha qo'shimcha bayt qo'shiladi. 4 million tugun uchun bu ~ 62 Mb ni tashkil qiladi, bu 2Gb ob'ekt ma'lumotlariga qaraganda juda kichik bo'lib ko'rinadi, ammo bu biz osonlikcha «tashlab yuborish» uchun kerak bo'lgan narsa emas.

So'nggi rasmdagi daraxt shuni ko'rsatadiki, har qanday elementni O (logN) murakkabligida osongina topish mumkin. Agar siz tanish bo'lmagan bo'lsangiz yoki katta-katta chatlarda suhbat qilish uchun etarli darajada ishonchingiz komil bo'lmasa, biz buni quyida aniqlaymiz, aks holda murakkablik bo'limini o'tkazib yuboring.

Algoritmik murakkablik - Buni tezroq qilishga imkon bering, chunki kelgusi maqolada uzoq va batafsil tushuntirish beriladi: "Algoritmik murakkablik va dasturiy ta'minotning ishlashi: yo'qolgan qo'llanma". Ko'pgina holatlarda algoritm uchun katta O murakkabligini topish biroz oson. Bir narsani ta'kidlash kerakki, biz har doim ham eng yomon vaziyatni ko'rib chiqamiz, ya'ni algoritm ijobiy natija (muammoni hal qilish uchun) qiladigan maksimal operatsiyalar sonini hisobga olamiz.

Aytaylik, massivda tartiblanmagan tartibda 100 ta element mavjud. Elementni topish uchun qancha taqqoslash kerak edi (shuningdek, kerakli element etishmasligi mumkinligini hisobga olgan holda)? 100 ta taqqoslash kerak bo'ladi, chunki har bir elementning qiymatini biz qidirayotgan qiymat bilan taqqoslashimiz kerak. Element massivdagi birinchi element bo'lishi mumkinligiga (bitta taqqoslashga olib keladigan) qaramay, biz faqat eng yomon vaziyatni ko'rib chiqamiz (element yo'qolgan yoki massivning oxirgi o'rnida joylashgan).

Algoritmik murakkablikni “hisoblash” nuqtasi operatsiyalar soni va kiritish hajmi o'rtasida bog'liqlikni topishdir, masalan, massiv elementlari soni (agar uning kiritilishi) bo'lsa, yuqoridagi massiv 100 elementni tashkil qilgan va operatsiyalar soni 100 ga teng. 1423 gacha o'sadi, har qanday elementni topish bo'yicha operatsiyalar soni ham 1423 ga ko'tariladi (eng yomon holat). Shunday qilib, kirish va operatsiyalar soni orasidagi yupqa chiziq aniq bo'ladi, bu chiziqli deb ataladi, operatsiyalar soni qator kiritilishi oshgani sayin ko'payadi. O'sish. Bu murakkablikning muhim jihati, deymizki, ajratilmagan massivda elementni qidirish O (N) vaqtni oladi va uni topish jarayoni N operatsiyalari (yoki hatto N operatsiyalardan bir necha baravar ko'p vaqtgacha davom etadi) ta'kidlaydi. sifatida 3N). Boshqa tomondan, massivdagi har qanday elementga kirish doimiy vaqtni oladi, ya'ni O (1). Buning sababi qatorning tuzilishi. U bir-biriga zid ma'lumotlarning tuzilishi va bir xil turdagi elementlarni (mind JS massivlari) o'z ichiga oladi, shuning uchun ma'lum bir elementga "sakrash" faqat uning massivining birinchi elementiga nisbatan o'rnini hisoblashni talab qiladi.

Bir narsa juda aniq. Ikkilik izlash daraxti tugunlarni tartiblangan holda saqlaydi. Binar qidirish daraxtida elementni qidirishning algoritmik murakkabligi qanday bo'ladi? Elementni topish uchun talab qilinadigan operatsiyalar sonini hisoblashimiz kerak (yomon holatda).

Yuqoridagi rasmga qarang. Ildizni qidirishni boshlaganimizda, birinchi taqqoslash uchta holatga olib kelishi mumkin,

  1. Tugun topildi.
  2. Agar kerakli element tugun qiymatidan kichik bo'lsa, taqqoslash tugunning chap pastki daraxti uchun davom etadi
  3. Agar biz izlayotgan qiymat tugunning qiymatidan katta bo'lsa, taqqoslash tugunning pastki pastki daraxtiga nisbatan davom etadi.

Har bir qadamda biz ko'rib chiqilishi kerak bo'lgan tugunlarning hajmini yarmiga qisqartiramiz. BSTda elementni topish uchun zarur bo'lgan operatsiyalar soni (ya'ni taqqoslashlar) daraxtning balandligiga teng. Daraxtning balandligi - bu eng uzun yo'ldagi tugunlar soni. Bu holda bu 4. Va balandligi, ko'rsatilganidek, [taglik 2] logN + 1. Shunday qilib, qidiruvning murakkabligi O (logN + 1) = O (logN). Bu degani, 4 million tugun ichida biror narsani qidirish log4000000 = ~ 22 eng yomon holatda taqqoslashni talab qiladi.

Daraxtga qaytish - Ikkilik qidirish daraxtida elementga kirish vaqti O (logN). Nega hashtable-lardan foydalanmasligingiz kerak? Xesh-jadvallar doimiy kirish vaqtiga ega, bu esa hashtable-larni deyarli hamma joyda ishlatishni oqilona qiladi.

Ushbu muammoda biz muhim talabni hisobga olishimiz kerak. Biz qidiruvni amalga oshira olishimiz kerak, masalan. narxi 80 dan 162 dollargacha bo'lgan uylar. BST holatida barcha tugunlarni faqat daraxtning tartibsiz aylanishini va hisoblagichni ushlab turish orqali olish mumkin. Xesh-jadval uchun bu biroz qimmat, shuning uchun BST-larga yopishib olish maqsadga muvofiqdir.

Garchi hashtable jadvalini qayta ko'rib chiqishga olib keladigan yana bir nuqta bo'lsa-da. Zichlik. Narxlar "abadiy" ko'tarilmaydi, aksariyat uylar bir xil narx oralig'ida joylashgan. Ekran rasmiga qarang, histogram bizga narxlarning haqiqiy rasmini ko'rsatadi, millionlab uylar bir xil oraliqda (+/- $ 18 - $ 212), ular o'rtacha narxga ega. Oddiy qatorlar yaxshi rol o'ynashi mumkin. Massiv indeksini narx sifatida va uylarning ro'yxati sifatida qabul qilsak, biz har qanday narx oralig'iga doimiy (har doim, deyarli) qiymatiga kirishimiz mumkin. Bu qanday ko'rinishga ega (mavhum yo'l):

Xuddi xeshtabl singari, biz har bir uyga uning narxiga qarab kirmoqdamiz. Bir xil narxga ega bo'lgan barcha uylar alohida BST ostida guruhlangan. Agar yuqorida ko'rsatilgan ob'yekt o'rniga (AirbnbHome tuzilishi) o'rniga uy identifikatorini saqlasak, bu bizga biroz joy tejaydi. Mumkin bo'lgan stsenariy - barcha uylarning to'liq ob'ektlarini xeshtable xaritalashida uy identifikatorini uyning to'liq ob'ekti sifatida saqlash va uyning identifikatori bilan narxlarni belgilaydigan boshqa hashtable (yoki yaxshiroq, massiv) saqlash.

Shunday qilib, foydalanuvchilar narxlar oralig'ini talab qilganda, biz uy identifikatorlarini narxlar jadvalidan olamiz, natijalarni belgilangan o'lchamlarga ajratamiz (masalan, sahifalar joylashuvi, odatda bitta sahifada 10 dan 30 tagacha buyum ko'rsatilgan), har bir uydan foydalangan holda uyning to'liq buyumlarini olish ID.

Shunchaki boshqa narsani yodda tuting (bu haqda fonda o'ylang). BST uchun muvozanat juda muhim, chunki bu O (logN) daraxt operatsiyalarini bajarishning yagona kafolati. Elementlarni tartiblangan tartibda joylashtirganingizda BST muammosi yaqqol ko'rinib turibdi. Oxir oqibat, daraxt shunchaki bog'langan ro'yxatga aylanadi, bu aniq vaqtli ishlarga olib keladi. Buni hozir unuting, deylik, bizning barcha daraxtlarimiz mukammal muvozanatli. Yuqoridagi rasmga yana bir bor qarang. Har bir qator elementi katta daraxtni anglatadi. Agar biz rasmni quyidagicha o'zgartirsak nima bo'ladi:

Ko'proq grafikka o'xshaydi

Bu "yanada aniqroq" grafikka o'xshaydi. Ushbu rasm eng niqoblangan ma'lumotlar tuzilmalari va grafikalarni aks ettiradi, bizni keyingi qismga olib boradi.

Grafik namoyishi: Outro

Grafikalardagi yomon yangilik shundan iboratki, grafik tasvirlash uchun bitta aniq ta'rif yo'q. Shuning uchun siz kutubxonada std :: grafigini topa olmaysiz. Bizda BST deb nomlangan "maxsus" grafikani namoyish qilish imkoniyati mavjud edi. Gap shundaki, daraxt bu grafik, ammo grafika daraxt emas. So'nggi rasm shuni ko'rsatadiki, bizda bitta abstraktsiya ostida juda ko'p daraxtlar bor, "uylarga nisbatan narxlar" va ba'zi bir vertikal turlar "turlicha", narxlar faqat narx qiymatiga ega bo'lgan grafik tugunlar bo'lib, butun daraxtni anglatadi. ma'lum bir narxni qondiradigan uy identifikatorlari (uyning uchlari). Bu gibrid ma'lumotlar tuzilishiga o'xshaydi, biz darslik misollarida ko'rib chiqqan oddiy grafikka qaraganda.

Grafik tasvirlashning muhim jihati shundaki, grafik namoyishi uchun qat'iy va "de jure" tuzilishi mavjud emas (BSTlardan farqli o'laroq, chap va o'ngdagi bolalar ko'rsatkichlari bilan belgilangan tugunga asoslangan vakili, ammo siz BSTni bitta qator bilan ifodalashingiz mumkin. ). Siz grafikni o'zingiz xohlagan shaklda taqdim etishingiz mumkin (aniq bir muammoga eng qulay), asosiysi siz uni grafik sifatida “ko'rishingiz” dir. Va "grafikani ko'rish" deganda biz grafiklarga xos bo'lgan algoritmlarni qo'llashni nazarda tutamiz.

Archa daraxti haqida nima deyish mumkin, u grafikka o'xshaydi.

N-ary daraxt tugunini namoyish etish uchun birinchi narsa quyidagicha:

Ushbu struktura daraxtning bitta tugunini anglatadi. To'liq daraxt quyidagicha ko'rinadi:

Bu sinf root_ nomli bitta daraxt tugunining atrofida mavhumlikdir. Istalgan o'lchamdagi daraxtni barpo etish uchun bizga kerak bo'lgan narsa shu. Daraxtning boshlanishi bu. Yangi daraxt tugunini qo'shish uchun biz unga xotira ajratib, daraxtning ildiziga bu tugunni qo'shishimiz kerak.

Grafika juda kam farqli N-ary daraxtiga o'xshaydi. Uni aniqlashga harakat qiling.

Bu grafikami? Yo'q, ha, demoqchiman, lekin bu oldingi rasmdagi bir xil archa daraxti, biroz aylantirilgan. Bosh barmog'ining qoidasi sifatida, har qachon daraxtni ko'rsangiz (u olma daraxti, limon daraxti yoki ikkilik qidirish daraxti bo'lsa ham), u ham grafik ekanligiga amin bo'lishingiz mumkin. Shunday qilib, grafik tugun uchun tuzilmani (grafik uchida) tuzib, biz xuddi shu struktura bilan ishlashimiz mumkin:

Grafik tuzish uchun bu etarli emasmi? Xo'sh, yo'q. Va shuning uchun. Oldingi rasmlardagi ushbu ikkita grafikka qarang, farqni toping:

Ikkalasi ham grafikadir

Chap tarafdagi rasmdagi grafikda "kirish" uchun yagona nuqta yo'q (bu bitta daraxtdan ko'ra o'rmon), aksincha, o'ng rasmdagi grafikda etib bo'lmaydigan uchlari mavjud emas. Tanish ovozlar.

Har bir vertikal juftlik o'rtasida yo'l bor bo'lganda, grafik ulanadi. [Vikipediya]

Shubhasiz, "uylarga nisbatan narxlar" grafigi uchun har bir juftlik o'rtasida yo'l mavjud emas (agar rasmda aniq bo'lmasa, narxlar bir-biri bilan bog'liq emas deb taxmin qiling). Biz bitta GraphNode struktura bilan grafik tuzolmasligimizni ko'rsatadigan shunchaki bir misol, shunda biz bunday uzilgan grafikalar bilan ishlashimiz kerak bo'lgan holatlar mavjud. Ushbu sinfni ko'rib chiqing:

N-ary daraxti bitta tugun atrofida (ildiz tugunida) qurilganidek, ulangan grafik ham ildiz tuguniga qurilishi mumkin. Aytishlaricha, daraxtlar "ildiz otgan", ya'ni ularning boshlang'ich nuqtasi bor. Bog'langan grafik ildizli daraxt sifatida ifodalanishi mumkin (yana ikkita xususiyatga ega), bu allaqachon ravshan, ammo shuni yodda tutingki, haqiqiy tasvir algoritmdan algoritmgacha, muammolardan tortib ulangan grafik uchun farq qilishi mumkin. Biroq, grafiklarning tugunga asoslangan xususiyatlarini hisobga olgan holda, uzilgan grafikni quyidagicha ko'rsatish mumkin:

DFS / BFS kabi chizmalar uchun daraxtga o'xshash tasvirni ishlatish tabiiydir. Ko'p yordam beradi. Biroq, samarali yo'llarni qidirish kabi holatlar boshqacha ko'rinishni talab qiladi. Eyler grafigini eslaysizmi? Grafikning "eulerilligi" ni kuzatish uchun biz uning ichidagi Eyler yo'lini kuzatishimiz kerak. Bu har bir qirrani bittadan kesib o'tib, barcha vertikalarni ziyorat qilishni anglatadi va agar biz chizish tugaganida va biz burilmagan qirralarga ega bo'lsak, unda grafikda Eyler yo'li bo'lmaydi va shuning uchun Eyler grafigi emas.

Bundan ham tezroq usul mavjud, biz vertikallarning darajalarini (har bir vertex o'z darajasini saqlaydi) tekshirib ko'rishimiz mumkin va ta'rifda aytilganidek, agar grafda toq darajadagi qirralar bo'lsa va ularning ikkitasi bo'lmasa, u shunday emas. Eyler grafigi. Bunday tekshirishning murakkabligi O (| V |), bu erda | V | bu grafik uchlari sonidir. Tek (hatto) darajani tekshirishimiz mumkin, chunki O (1) ga toq / tenglik darajalarini tekshirish uchun yangi qirralarni joylashtiramiz. Chaqmoq tez. Hechqisi yo'q, biz shunchaki grafikni tomosha qilmoqchimiz. Quyida grafikning tasviri va yo'lni qaytaruvchi Trace () funktsiyasi mavjud.

Xatolarni yodda tuting, xatolar hamma joyda. Ushbu kod ko'plab taxminlarni o'z ichiga oladi, masalan, markalash, shuning uchun vertex orqali biz satr yorlig'ini tushunamiz. Siz xohlagan narsangiz uchun uni osongina yangilashingiz mumkin. Ushbu misol kontekstida muhim emas. Keyingi, nomlash. Izohlarda aytib o'tilganidek, VELOGraf Vertex Edge Label Only Graf uchun mo'ljallangan (men buni shunday qildim). Gap shundaki, ushbu grafik ko'rinishda vertex yorlig'ini shu uchi bilan bog'liq bo'lgan qirralarning xaritasi uchun jadval va bir qator uchlari (ma'lum bir chekka bilan bog'langan) va faqat Iz tomonidan ishlatiladigan bayroqni o'z ichiga olgan jadval mavjud. ) funktsiyasi. Trace () funktsiyasining bajarilishini ko'rib chiqing. U allaqachon o'tib ketgan chetni belgilash uchun chekka bayroqchasidan foydalanadi (bayroqlar har qanday Trace () chaqiruvidan keyin tiklanishi kerak).

Twitter misol: Tweet etkazib berish bilan bog'liq muammo

Bu erda biz Twitter izdoshlari grafigi uchun ishlatganimiz singari, yo'naltirilgan grafikalarda foydali bo'lishi mumkin bo'lgan qo'shilish matritsasi deb nomlangan yana bir rasm mavjud.

Yo'naltirilgan grafik

Ushbu Twitter misolida 8 ta vertikalar mavjud. Shunday qilib, biz ushbu grafikani namoyish qilishimiz kerak bo'lgan yagona narsa bu | V | x | V | kvadrat matritsa (| V | qatorlar soni va | V | ustunlar soni). Agar v-dan u-ga yo'naltirilgan chiziq bo'lsa, u holda [v] [u] matritsasi to'g'ri, aks holda bu noto'g'ri.

Twitter misol

Ko'rib turganingizdek, bu matritsa juda kam, uning tezkor kirishidir. Patrik Sponge Bobga ergashganligini bilish uchun ["Patrik"] ["Shimgich Bob"] matritsasining qiymatini tekshirishimiz kerak. Annning izdoshlari ro'yxatini olish uchun biz "Ann" ustunini to'liq saralaymiz (sarlavhasi sariq rangda). Sponge Bob tomonidan ta'qib qilinayotganlarni (g'alati tuyuladi) topish uchun biz "Sponge Bob" qatorini qayta ishlaymiz. Yopishqoqlik matritsasi yo'naltirilmagan grafikalar uchun ham ishlatilishi mumkin va agar 1-chi sozlamalar o'rniga v-dan u-gacha bo'lgan chekka bo'lsa, biz ikkala qiymatni 1-ga sozlashimiz kerak, masalan. adj_matrix [v] [u] = 1, adj_matrix [u] [v] = 1. yo'naltirilmagan grafikning qo'shilish matritsasi nosimmetrikdir.

Shuni yodda tutingki, nol va nolni ulashgan matritsada saqlash o'rniga, biz "foydali" narsalarni saqlashimiz mumkin, masalan, vazn. Eng yaxshi misollardan biri masofa haqidagi ma'lumotlarning joylari grafigi bo'lishi mumkin.

Yuqoridagi grafik Patrik, Sponge Bob va boshqalarning uylari orasidagi masofani (shuningdek, vaznli grafika sifatida ham tanilgan) anglatadi. Agar vertikal chiziqlar o'rtasida to'g'ridan-to'g'ri yo'nalish bo'lmasa, biz "cheksizlik" belgilarini qo'yamiz. Bu umuman marshrutlar mavjud emasligini anglatmaydi va shu bilan birga albatta yo'nalish bo'lishi kerak degani emas. Bu vertikal chiziqlar orasidagi marshrutni topish uchun algoritmni belgilashda aniqlanishi mumkin (vertikal chiziqlar va unga buralgan qirralarni saqlashning eng yaxshi usuli ham bor, bu hodisa matritsasi deb ataladi).

82000Tb. Fotosurat manbai

Tvitterning qo'shilish matritsasi yaxshi foydalanuvchiga aylangan bo'lsa ham, 300 millionga yaqin foydalanuvchilar (har oy faol foydalanuvchilar) uchun kvadrat matritsani 300 * 300 * 1 bayt (mantiqiy qiymatlarni saqlash) talab qiladi. Ya'ni, ~ 82000 Tb (Terabayt), bu 1024 * 82000 Gb. Xo'sh, uy klasteringiz haqida bilmayman, mening noutbukimda unchalik tezkor xotira yo'q. Bitsetsmi? BitBoard bizga ozgina yordam berishi mumkin va kerakli hajmni ~ 10000 Tbgacha kamaytirishi mumkin. Hali ham yo'l juda katta. Yuqorida ta'kidlab o'tilganidek, qo'shni matritsa juda kam. Bu bizni kerak bo'lgandan ko'proq joy sarflashga majbur qiladi. Shuning uchun vertikal vertikal hodisalar qirralarining ro'yxatidan foydalanish foydali bo'lishi mumkin. Gap shundaki, o'zaro bog'liqlik matritsasi bizga "ergashadigan" va "ergashmaydigan" ma'lumotlarni saqlashga imkon beradi, holbuki biz quyidagilar haqida ma'lumotni bilishimiz kerak:

Qo'shni bo'lish matritsasi va qo'shni ro'yxat

O'ng tarafdagi rasm qo'shni ro'yxat deb ataladi. Har bir ro'yxat grafadagi bir verteksning qo'shnilari to'plamini tavsiflaydi. Aytgancha, grafika taqdimotining qo'shni ro'yxat sifatida amalda bajarilishi yana farq qiladi (kulgili faktlar). Rasmda biz hashtable foydalanishni ta'kidladik, bu har qanday verteksning kirish imkoniyati O (1) bo'ladi, va qo'shni uchlari ro'yxatida biz bog'langan ro'yxatlardan vektorlarga og'ib, aniq ma'lumotlar tuzilishini aytmadik. . Tanlov siznikidir.

Gap shundaki, Patrik Lizni kuzatadimi yoki yo'qligini bilish uchun biz xeshtable (doimiy vaqt) ga kirishimiz va ro'yxatdagi barcha elementlarni har bir elementni "Liz" elementi bilan taqqoslashimiz kerak (chiziqli vaqt). Hozirgi vaqtda chiziqli vaqt unchalik yomon emas, chunki biz "Patrik" ga tutashgan faqat ma'lum miqdordagi qirralarni orqaga qaytarishimiz kerak. Fazoviy murakkablik haqida nima deyish mumkin, Twitter-dan foydalanish kerakmi? Xo'sh, bizga kamida 300 million xeshtable yozuvlari kerak, ularning har biri vektorga ishora qiladi (bog'langan ro'yxatlarning chap / o'ng ko'rsatkichlari xotiradan kattaroq bo'lmasligi uchun vektorni tanlash), qancha? Bu erda hech qanday statistika yo'q, faqat o'rtacha twitter izdoshlarining 707 (googled) topildi.

Shunday qilib, agar har bir hashtable yozuvi 707 foydalanuvchi identifikatorini (har biri og'irligi 8 baytni) tashkil etadi deb hisoblasak va hashtablning ustki qismi uning kalitlari, yana foydalanuvchi identifikatori, deb taxmin qilsak, hashtablning o'zi 300 millionni oladi * 8 bayt. Umuman olganda, bizda hashtable uchun 300 million * 8 bayt + 707 * 8 bayt, ya'ni 300 million * 8 * 707 * 8 bayt = ~ 12 Tb. O'zingizni yaxshi deb ayta olmayman, lekin ha, 10,000 Tb dan ham yaxshiroq.

Rostini aytsam, ushbu 12Tb o'rtacha sonmi yoki yo'qligini bilmayman. 32 Gb tezkor xotira bilan maxsus server mashinasiga taxminan 30 dollarni sarflayotganimni hisobga olsak, 12 Gb saqlash uchun kamida 385 bunday serverlar, shuningdek, ikkita nazorat serveri (ma'lumotlar tarqatilishini boshqarish uchun) talab qilinadi. Shunday qilib, bu menga $ 12K (har oyda) turadi.

Ma'lumotlar ko'paytirilishi kerakligi va har doim biror narsa noto'g'ri ketishi mumkinligini hisobga olsak, biz serverlar sonini uch baravar ko'paytiramiz va yana bir necha nazorat serverlarini qo'shamiz, aytaylik, bizga kamida 1500 server kerak bo'ladi, bu bizga qimmatga tushadi. Oyiga 45 dollar. Albatta, men uchun unchalik yaxshi emas, chunki bitta serverni ushlab turolmayman, lekin Twitter uchun qulay (bu haqiqiy Twitter serverlariga taqqoslanmaydi). Aytaylik, Twitter uchun juda yaxshi.

Endi biz bu yerdamisiz? Hozircha bu faqat izdoshlar haqidagi ma'lumotlar edi. Twitterdagi asosiy narsa nima? Aytmoqchimanki, texnik jihatdan uning eng katta muammosi nima? Bu tvitlarni tezkor etkazib berish deb aytsangiz, yolg'iz emassiz. Men buni albatta aniqlashtiraman. Va tez emas, lekin chaqmoq tez. Aytaylik, Patrik oziq-ovqat haqidagi fikrlari haqida tvit yozdi, barcha izdoshlari bu tvitni maqbul vaqt ichida olishlari kerak. U qancha vaqt oladi? Biz bu erda hech qanday taxmin qilmaymiz va biz xohlagan har qanday abstraktsiyadan foydalanamiz, ammo biz real dunyo ishlab chiqarish tizimlariga qiziqamiz, shuning uchun qazib olaylik. Odatda kimdir tvit qilganda odatda shunday bo'ladi.

Shunga qaramay, bitta tvitning barcha izdoshlariga qancha vaqt kerakligi haqida ko'p narsa bilmaymiz, ammo hammaga ochiq statistika har kuni 500 millionga yaqin tvit borligini aytadi. Har kuni!

Demak, yuqoridagi jarayon har kuni 500 million marta sodir bo'ladi. Men haqiqatan ham tvit tezligida hech narsa topolmayapman. Men tvitning barcha izdoshlariga etkazish uchun taxminan 5 soniya davomida biron bir narsani eslayman. Bir milliondan ortiq izdoshlari bo'lgan mashhur shaxslar "og'ir holatlarga" e'tibor bering. Ular plyaj uyidagi ajoyib nonushta haqida biron bir tvit yozishlari mumkin, ammo Twitter bu juda foydali tarkibni millionlab izdoshlarga etkazish uchun juda ko'p ter qiladi.

Tvitlarni etkazib berish muammosini hal qilish uchun biz izdoshlar jadvaliga ehtiyoj sezmaymiz, aksincha ularga kuzatuvchilar grafigi kerak. Oldingi grafik (hashtable va bir nechta ro'yxatlar bilan) bizga har qanday foydalanuvchi tomonidan ta'qib qilinadigan barcha foydalanuvchilarni samarali topishga imkon beradi. Ammo bu bizga bitta bitta foydalanuvchini kuzatayotgan barcha foydalanuvchilarni samarali topishga imkon bermaydi, bu holda biz barcha hashtable tugmachalarini skanerlashimiz kerak. Shuning uchun biz yana bir grafikni tuzishimiz kerak, bu biz izdoshlar uchun qurgan grafikka qarama-qarshi nosimmetrikdir. Ushbu yangi grafika yana barcha 300 million vertikallarni o'z ichiga olgan hashtable-dan iborat bo'lib, ularning har biri qo'shni uchlari ro'yxatiga ishora qiladi (tuzilishi bir xil bo'lib qoladi), ammo bu safar qo'shni uchlari ro'yxati izdoshlarni namoyish etadi.

Shunday qilib, ushbu rasmga asoslanib, har safar Liz biror narsani tvit qilganda, Sponge Bob va Enn bu tvitni o'z vaqtida ko'rishlari kerak. Buni amalga oshirishning odatiy usuli har bir foydalanuvchining vaqt jadvaliga alohida tuzilmalarni kiritishdir. Twitter'ning 300+ million foydalanuvchisi bo'lsa, biz kamida 300+ million vaqt jadvalini (har bir foydalanuvchi uchun) olishimiz mumkin. Asosan, har qachon foydalanuvchi tvit qilganda, biz foydalanuvchilarning izdoshlari ro'yxatini olishimiz va ularning vaqt jadvallarini yangilashimiz kerak (har biriga shu tvitni joylashtiring). Xronologiya bog'langan ro'yxat yoki muvozanatli daraxt shaklida taqdim etilishi mumkin (tugmali tugmalar shaklida tvitlar vaqtlari).

Bu shunchaki asosiy fikr, biz vaqt jadvalini aks ettirishdan tortib oldik va agar biz multitreadingdan foydalansak, haqiqatan ham etkazib berishni tezroq qilishimiz mumkin. Bu "og'ir holatlar" uchun juda muhimdir, chunki millionlab izdoshlar uchun oxiriga yaqinroq bo'lganlar ro'yxatning old tomoniga yaqinroq bo'lganlarga qaraganda kechroq qayta ishlanadi.

Quyidagi psevdokod ushbu ko'p qirrali etkazib berish g'oyasini yoritishga harakat qiladi:

Shunday qilib, har doim izdoshlar o'z vaqt jadvallarini yangilashganda, ular yangi tvitni olishadi.

Airbnb yoki Twitter-da biz aysbergning uchiga tegdik, deyish adolatli bo'ladi. Twitter, Google, Facebook, Amazon, Airbnb va boshqalar kabi murakkab tizimlarda bunday ajoyib natijalarga erishish uchun chinakam iqtidorli muhandislarning mashaqqatli mehnati talab etiladi. Ushbu maqolani o'qiyotganda shuni yodda tuting.

Twitter-ning tvitlarini etkazib berish muammosini namoyish etishning maqsadi grafiklardan foydalanishni o'z ichiga oladi, garchi biz biron bir algoritmni ishlatmagan bo'lsak ham, biz shunchaki grafikadan foydalanganmiz. Albatta, biz tvitlarni etkazish funktsiyasini soxtalashtirganmiz, ammo biz bu echimni izlash jarayonida paydo bo'lgan narsa.

Men "har qanday grafik algoritm" ni nazarda tutgan narsa bu ro'yxatdagi har qanday algoritm. Dasturchilarni yig'latishi uchun juda katta narsa bo'lgani uchun, grafik nazariyasi va grafik algoritmga oid ilovalar bir qarashda bir oz farq qiladi. Biz Airbnb uylarini va grafik tasvirlarni taqdim etishdan oldin samarali filtrlashni muhokama qildik va eng asosiy narsa uylarni bir nechta filtr tugmachalari yordamida samarali filtrlashning mumkin emasligi edi. Grafik algoritmlar yordamida bajarilishi mumkin bo'lgan biron bir narsa bormi? Biz aniq ayta olmaymiz, lekin hech bo'lmaganda harakat qilib ko'rishimiz mumkin. Agar har bir filtrni alohida vertex sifatida taqdim etsak nima bo'ladi?

Har bir filtr, hatto $ 10 dan $ 1000 gacha barcha narxlar, barcha shahar nomlari, mamlakat kodlari, qulayliklar (TV, Wi-Fi va boshqalar), kattalar soni va har bir raqam alohida grafik tepasida.

Airbnb filtrlaridan parcha

Agar biz ushbu "vertikal" vertikalarni, masalan, qulaylik filtrini ifoda etuvchi barcha uchlarga ulangan "qulayliklar" ni qo'shsak, ushbu vertikal to'plamni yanada do'stona qilishimiz mumkin.

Turlari bo'lgan Airbnb filtrlari

Endi, agar biz Airbnb uylarini vertikal sifatida ko'rsatsak va u uy filtrni qo'llab-quvvatlasa, har bir uyni "filtr" uchi bilan ulasak nima bo'ladi? uning imkoniyatlari)?

Xiralashgan ko'rinadi

Ushbu rasmning nozik o'zgarishi uni ikki tomonlama grafik deb nomlangan maxsus turdagi grafikaga o'xshatish ehtimoli ko'proq.

Buzilishlar soni paydo bo'lishi mumkin bo'lganidan ko'proq

Bipartitli grafik yoki shunchaki katta grafik - bu uchlari ikkita kesishgan va mustaqil to'plamlarga bo'linadigan grafik bo'lib, shunday qilib har bir qirraning uchi bir to'plamdagi boshqasini boshqasiga bog'laydi. - Vikipediya.

Bizning misolimizda to'plamlardan biri filtrlarni bildiradi (biz buni F bilan belgilaymiz), ikkinchisida (H bilan belgilanadigan) uylar. Masalan, agar $ 62 narxga ega bo'lgan 100 mingta uy bo'lsa, u holda "62 dollar" deb belgilangan narxning tepasida har bir uyning tepasida 100 mingta voqea sodir bo'ladi. Agar biz kosmik murakkablikning eng yomon holatini o'lchasak, ya'ni har bir uy filtrlarni qondiradigan barcha xususiyatlarga ega, shuning uchun saqlanadigan qirralarning umumiy miqdori 70,000 * 4 millionni tashkil qiladi. Agar biz har bir chetni ikkita idning juftligi sifatida ifodalasak: {filter_id; home_id} va agar biz identifikatorlarni qayta ko'rib chiqsak va filtrlar uchun 4 bayt (int) raqamli iddan va uylar uchun 8 bayt (uzun) iddan foydalansak, har bir chetidan kamida 12 bayt kerak bo'ladi. Shunday qilib, 70,000 * 4 million 12 bayt qiymatini saqlash uchun 3Tb xotira kerak bo'ladi. Hisoblashda kichik xato qildik, ko'ryapsizmi.

Airbnb (stats) da ishlaydigan 65 ming shahar mavjudligi sababli filtrlar soni 70,000 atrofida. Va yaxshi xabar shundaki, bitta uy bir nechta shaharda joylashtirilishi mumkin emas. Ya'ni, bizning shaharlar bilan birlashtirilgan qirralarning haqiqiy soni 4 million (har bir uy bitta shaharda joylashgan). Shunday qilib, biz 70k - 65k = 5 ming filtr uchun hisoblaymiz, bu bizga 5000 * 4 million * 12 bayt xotirani talab qiladi, bu esa 0.3 Tb dan kam. Juda yaxshi. Ammo bizga bu ikki tomonlama grafikani nima beradi? Ko'pincha veb-sayt / mobil so'rov bir nechta filtrlardan iborat bo'ladi, masalan:

uy_tip: "butun_ joy",
kattalar soni: 2,
narx_range_start: 56,
price_range_end: 80,
choyshablar soni: 2,
qulayliklar: ["tv", "wifi", "noutbuk uchun qulay ish maydoni"],
imkoniyatlar: ["sport zali"]

Bizga kerak bo'lgan narsa yuqorida joylashgan "filtr uchlari" ni topish va ushbu "filtr uchlari" ga yaqin bo'lgan barcha "uy uchlari" ni qayta ishlashdir. Bu bizni dahshatli mavzuga olib boradi.

Grafik algoritmlari: Kirish

Grafik yordamida bajarilgan har qanday ishlov berish "grafik algoritmi" deb tasniflanishi mumkin. Grafikning barcha uchlarini bosib chiqarish funktsiyasini amalga oshirishingiz va uni " 'vertex bosib chiqarish algoritmi" deb nomlashingiz mumkin. Ko'pchiligimiz darsliklarda keltirilgan grafik algoritmlardan qo'rqamiz (to'liq ro'yxatni bu erda ko'ring). Hipcroft-Karp algoritmi kabi ikkitomonlama grafikka mos keladigan algoritmni Airbnb uylarimizni filtrlash muammosiga qo'llashga harakat qilaylik.

Airbnb uylarining (H) va filtrlarning (F) ikkitomonlama grafigi berilgan, bunda H ning har bir elementida (vertexida) F ning qo'shni elementlari (vertex) bo'lishi mumkin (umumiy qirrani almashish). F to'plamidagi vertikallarga ulashgan vertikallardan tashkil topgan H to'plamini toping.

Muammoning ta'rifini chalkashtirib yuborish, ammo hozircha Hopcroft-Karp algoritmi bizning muammomizni hal qiladimi-yo'qligini aniq bilmaymiz. Sizni ishontirib aytamanki, ushbu sayohat bizga grafik algoritmlar ortidagi ko'plab muhim g'oyalarni o'rgatadi. Va safar juda qisqa emas, shuning uchun sabr qiling.

Hopcroft-Karp algoritmi kirish, ikkitomonlama grafik va chiqish sifatida ishlab chiqariladigan, maksimal kardinalga mos keladigan algoritmdir - ikkita qirralarning egri chizig'iga ega bo'lmagan xususiyat bilan iloji boricha qirralarning to'plami - Vikipediya.

Ushbu algoritm bilan tanish bo'lgan o'quvchilar allaqachon bu bizning muammoni hal etmasligini bilishadi, chunki mos kelishni talab qilish kerak, chunki ikkita qirralarning umumiy uchlari bo'lmasligi kerak.

Keling, bitta rasmni ko'rib chiqaylik, bu erda atigi 4 ta filtr va 8 ta uy bor (soddaligi uchun).

  • Uylar A dan H gacha bo'lgan harflar bilan belgilanadi, filtrlar tasodifiy tanlanadi.
  • Uyda A-ning narxi ($ 50) va 1 ta to'shak bor (bu narx uchun bizda bor).
  • A dan Hgacha bo'lgan barcha uylarda bir kecha uchun narx $ 50 va 1 krovat bor, ammo ularning ba'zilarida "Wi-Fi" va / yoki "TV" mavjud.

Shunday qilib, quyidagi rasmda to'rtta filtr mavjud bo'lgan uylarni so'rash uchun qaysi uylarga "qaytishimiz" kerakligi ko'rsatiladi (masalan, ular bir kecha uchun $ 50 turadi, ularda bitta to'shak, Wi-Fi va televizor mavjud). .

Muammoni hal qilish uchun bir xil filtr quyi qismiga tegishli bo'lgan uyning vertikal qismlariga olib keladigan umumiy vertikal uchlari kerak bo'ladi, Hopcroft-Karp algoritmi esa bunday chekkalarni umumiy so'nggi nuqtalar bilan yo'q qiladi va ikkala pastki qismdagi vertikallarga mos keladigan qirralarni keltirib chiqaradi.

Yuqoridagi rasmga qarang, biz uchun D va G uylari kerak, bu ikkala filtrning to'rtta qiymatini qondiradi. Bizga kerak bo'lgan narsa, umumiy nuqta bo'lgan barcha mos keladigan qirralarni olishdir.

Biz ushbu yondashuvning algoritmini ishlab chiqishimiz mumkin, ammo uni qayta ishlash vaqti foydalanuvchilar ehtiyojlariga mos kelmaydi (foydalanuvchilar = tezkor, hoziroq shu erda). Ehtimol, asosiy / tashqi tugmachalarni qoniqarli yozuvlar to'plamiga ega bo'lgan ma'lumotlar bazasi indekslari fayli kabi, bir nechta tartiblash tugmachalari bilan muvozanatli ikkilik qidirish daraxtini yaratish tezroq bo'lar edi.

Balanslangan ikkilik qidirish daraxtlari va ma'lumotlar bazasini indekslash alohida maqolada muhokama qilinadi, bu erda biz yana Airbnb uy filtrlash muammosiga qaytamiz.

Hopcroft-Karp algoritmi (va boshqa ko'p narsalar) ikkala DFS (Chuqurlik-Birinchi Qidiruv) va BFS (Kenglik-Birinchi Qidiruv) grafiklarining algoritmlariga asoslangan. Rostini aytadigan bo'lsak, bu erda Hopcroft-Karp algoritmini joriy qilishning sababi shoshilinch ravishda grafik shpallariga o'tishdir, bu esa chiroyli grafiklardan, ikkilik daraxtlardan boshlangan yaxshiroqdir.

Ikkilik daraxt shpallari haqiqatan ham go'zaldir, asosan ularning rekursivligi tufayli. Buyurtma, buyurtma va buyurtma deb nomlangan uchta asosiy travers mavjud (siz o'zingizning shaxsiy algoritmingiz bilan tanishishingiz mumkin). Agar siz bog'langan ro'yxatni bosib o'tgan bo'lsangiz, ularni tushunish oson. Bog'langan ro'yxatlarda siz hozirgi tugunning qiymatini chop etasiz (quyidagi kodda ko'rsatilgan element) va keyingi tugunga o'tasiz.

Deyarli bir xil narsa ikkilik daraxtlar bilan ishlaydi, siz tugun qiymatini bosib chiqarasiz (yoki boshqa nima qilishingiz kerak bo'lsa) va keyin keyingi tugunga o'tasiz, ammo bu holda chap va o'ngda "ikkita keyingi" tugun mavjud. Shunday qilib, chap va o'ng tugunlar uchun ham xuddi shunday qilishingiz kerak. Ammo bu erda uchta xil tanlov mavjud:

  • tugun qiymatini chop eting, so'ng chap tugunga o'ting, so'ngra o'ng tugunga o'ting yoki
  • chap tugunga o'ting, tugun qiymatini chop eting va keyin o'ng tugunga o'ting, yoki
  • chap tugunga o'ting, keyin o'ng tugunga o'ting va tugunning qiymatini yozing.
Oldindan buyurtma shpalini batafsil tekshirish

Shubhasiz, rekursiv funktsiyalar juda oqlangan ko'rinadi, ammo ular juda qimmat. Har safar biz biron bir funktsiyani rekursiv ravishda chaqirganda, biz mutlaqo "yangi" funktsiyani chaqiramiz (yuqoridagi rasmga qarang). Va "yangi" deganda, funktsiyalar va argumentlar uchun boshqa zaxira xotira maydoni "ajratilgan" bo'lishi kerak. Shuning uchun rekursiv qo'ng'iroqlar juda qimmat (qo'shimcha bo'sh joy ajratish va ko'p funktsional qo'ng'iroqlar) va xavfli (stack toshib ketishini yodda tuting) va shuning uchun iterativ dasturlardan foydalanish tavsiya etiladi. Kritik tizimlarning dasturiy vazifalarida (samolyotlar, NASA rullari va boshqalar) rekursiya mutlaqo taqiqlangan (statistika, tajriba yo'q, shunchaki mish-mishlarni aytib berish).

Netflix va Amazon: Inverted Index Misoli

Aytaylik, biz barcha Netflix filmlarini ikkilik qidiruv daraxti ichida saralash tugmachalari sifatida kino sarlavhalari bilan saqlamoqchimiz. Shunday qilib, har safar foydalanuvchi "Inter" kabi biror narsani yozganda, biz "Inter" dan boshlanadigan filmlar ro'yxatini qaytaramiz (masalan, "Yulduzlar", "Interceptor", "Uolter Uaytning so'roq qilinishi").

Endi biz "Inter" ni o'z ichiga olgan har bir filmni (nafaqat "Inter" bilan boshlanadigan filmlarni) qaytarib beradigan bo'lsak, yaxshi bo'ladi va bu ro'yxat kino reytingi yoki shu bilan bog'liq bo'lgan narsalar bo'yicha saralanadi. foydalanuvchi (dramadan ko'ra ko'proq trillerlar kabi). Ushbu misolning maqsadi BST-ga samarali so'rovlarni bajarishdir.

Odatdagidek, biz aysbergning qolgan qismini aniqlash uchun sovuq suvga chuqurroq sho'ng'iy olmaymiz. Asosan, biz qidiruv kalit so'zlari orqali tezkor qidiruvga muhtojmiz, so'ngra ba'zi bir kalit bo'yicha saralangan natijalar ro'yxatini olishimiz kerak, bu eng ehtimol filmning reytingi va / yoki foydalanuvchining shaxsiy ma'lumotlari asosida ichki reyting bo'lishi kerak. Iloji boricha KISK printsipiga sodiq qolishga harakat qilamiz (sodda qilib aytganda, Karl).

"KISK" yoki "buni sodda qilib aytaylik" yoki "soddaligi uchun", o'qituvchilar yozuvchilarini "abc" ni oson misolini va uning echimini psevdokodda olib borish orqali haqiqiy muammodan mavhum bo'lish va ko'pgina taxminlarni qilish uchun juda yaxshi bahona. hatto buvangizning noutbukida ishlaydi.

Ushbu muammoni Amazon-ning mahsulotlarini qidirishda osonlikcha qo'llash mumkin, chunki biz Amazonda ko'pincha qiziqishimizni tavsiflovchi matnni ("Grafik algoritmlari") kiritish orqali qidiramiz va mahsulot reytingi bo'yicha saralangan natijalarni olamiz. Men Amazonning qidiruv natijalarida shaxsiy natijalarni ko'rmadim. Ammo aminmanki, Amazon ham buni amalga oshiradi. Shunday qilib, ushbu subtopikning nomini o'zgartirish adolatli bo'ladi ...

Netflix va Amazon. Netflix filmlarga xizmat qiladi, Amazon mahsulotlarga xizmat qiladi, biz ularni "buyumlar" deb ataymiz, shuning uchun siz "buyum" ni o'qiganingizda Netflix-dagi film yoki Amazon-dagi har qanday "hayotiy" mahsulot haqida o'ylang.

Ko'pincha narsalar bilan ularning nomi va tavsifi tahlil qilinadi (biz faqat sarlavhaga yopishib olamiz), shuning uchun operator (odatda ma'lumotlar ma'murlari boshqaruv paneli orqali Netflix / Amazon ma'lumotlar bazasiga ma'lumotlar kiritayotgan). ma'lumotlar bazasida yangi element, uning nomi kalit so'zlarni ishlab chiqarish uchun ba'zi "ItemTitleProcessor" tomonidan qayta ishlanmoqda.

Eng yaxshi rasm emas, men bilaman (va yozuvim bor)

Har bir element o'z nomiga ega bo'lgan kalit so'z bilan bog'langan o'zining noyob identifikatoriga ega. Butun dunyo bo'ylab veb-saytlarni qidirishda qidiruv tizimlari shunday qiladi. Ular har bir hujjatning tarkibini tahlil qiladilar, tokenlar (so'zlar deb nomlangan kichik ob'ektlarga ajratadilar) va jadvalga qo'shadilar, bu erda har bir token (so'z) token «ko'rgan» hujjat identifikatoriga (veb-saytiga) joylashtiriladi.

Shunday qilib, "salom" ni qidirganingizda, qidiruv tizimi "salom" kalit so'ziga biriktirilgan barcha hujjatlarni keltiradi (haqiqat juda murakkab, chunki eng asosiysi qidirishning ahamiyati va shuning uchun Google Search juda ajoyib). Shunday qilib, Netflix / Amazon-ga o'xshash jadval shunga o'xshash ko'rinishi mumkin (yana elementlarni o'qiyotganda Filmlar yoki Mahsulotlar haqida o'ylang).

Inverted indeks

Hashtables, yana. Ha, biz ushbu teskari indeks uchun xesh-jadvalni saqlaymiz (xaritani tarkibdan saqlaydigan indeks tuzilishi - Vikipediya). Ushbu hashtable BST-ga kalit so'zni xaritada joylashtiradi. Nega BST? Chunki biz ularni tartiblangan holda saqlashni va bir vaqtning o'zida ularga xizmat ko'rsatishni istaymiz (buyurtma so'rovlariga javob bering), ketma-ket saralangan qismlarda (masalan, sahifada yozuv yordamida 100 ta element). BSTlarning kuchini ko'rsatadigan narsa emas. Aytaylik, biz ham qidiruv natijalarida tezkor qidiruvga ehtiyoj sezamiz, deylik, barcha uchta "film" ni "mashina" so'zi bilan qidirmoqchiman.

E'tibor bering, turli xil daraxtlarda bir-birini takrorlash yaxshi emas, chunki elementni odatda bir nechta kalit so'zlar bilan topish mumkin.

Biz quyidagicha belgilangan narsalar bilan ishlaymiz:

Har safar ma'lumotlar bazasiga yangi element kiritilganda, sarlavha qayta ishlanadi va elementga kalit so'zni xaritaga soladigan katta indeks jadvaliga qo'shiladi. Bitta kalit so'zni ulashadigan ko'plab narsalar bo'lishi mumkin, shuning uchun biz ularni BST-da reytinglari bo'yicha tartiblangan holda saqlaymiz.

Foydalanuvchilar biron bir kalit so'zni qidirishganda, ular reytinglari bo'yicha saralangan narsalarning ro'yxatini olishadi. Qanday qilib tartibli tartibda daraxtdan ro'yxatni olishimiz mumkin? Tartibsiz tartibni buzish orqali.

InOrderProducVector () dasturining bajarilishi qanday ko'rinishi mumkin:

Ammo, lekin ... Bizga avval eng yuqori baholangan buyumlar kerak va bizning tartibli shpallarimiz avval eng past baholangan mahsulotlarni ishlab chiqaradi. Bu uning tabiati tufayli. Tartibni aylantirish ishlari "pastdan yuqoriga", pastdan yuqorisiga. O'zimiz xohlagan narsani olish uchun, ya'ni ko'tarilish o'rniga ro'yxat bo'yicha kamayish tartibida, biz tartibda tartibda amalga oshirilayotgan aylanishlarni biroz yaqinroq ko'rib chiqishimiz kerak.

Biz chap tugunni bosib, so'ng tugunning qiymatini bosib, keyin o'ng tugunni bosib o'tamiz. Chapdagi eng ko'p tugun - bu eng kichik qiymatga ega tugun. Shunday qilib, birinchi navbatda dasturni to'g'ri tugun orqali o'tish uchun o'zgartirish bizni ro'yxatning kamayish tartibiga olib keladi. Biz buni boshqalar singari nomlaymiz, teskari tartibda aylanib o'tish.

Yuqoridagi kodni yangilaylik (bitta ro'yxatga kiriting). Ogohlantirish - oldinda xatolar!

Bo'ldi shu. Biz qidiruv natijalarini juda tezkor ravishda taqdim etamiz. Yuqorida aytib o'tilganidek, teskari indeksatsiya asosan Google kabi qidiruv tizimlarida qo'llaniladi. Garchi Google Search juda murakkab qidiruv tizimi bo'lsa-da, ammo qidiruv so'rovlarini hujjatlar bilan taqqoslash va natijalarga iloji boricha tezkor xizmat qilish uchun ba'zi sodda fikrlardan foydalanadi (juda zamonaviylashtirilgan usul).

Biz natijalarni tartiblangan holda berish uchun daraxt kesishmalaridan foydalanganmiz. Ushbu nuqtada, buyurtmadan oldingi / buyurtmadan oldingi shovqinlar etarlicha ko'proq bo'lib tuyulishi mumkin, ammo ba'zida boshqa turdagi shpallar kerak bo'ladi.

Keling, taniqli dasturiy intervyu savoliga, "Qanday qilib siz [ikkilik] daraxtning balandligini darajaga qarab chop etasiz?"

Shikastlanishlar: DFS va BFS

Agar siz ushbu muammoni bilmasangiz, daraxtni kesib o'tayotganda tugunlarni saqlash uchun foydalanishingiz mumkin bo'lgan ba'zi ma'lumotlarning tuzilishi haqida o'ylang. Agar biz daraxtni bosqichma-bosqich kesib o'tilishini yuqoridagi boshqalar bilan taqqoslasak (avval, keyin, tartibni buzgan holda), biz oxirida grafiklarning ikkita asosiy shpalini, ya'ni chuqurlik birinchi izlash (DFS) va kenglik - birinchi qidirish (BFS).

Eng chuqur tugunni qidirish chuqurligi, birinchi kenglik birinchi navbatda eng yaqin tugunlarni qidiradi.

  • Chuqurlikdan birinchi izlash - ko'proq harakatlar, kamroq fikrlar.
  • Nonni birinchi qidirish - uzoqroq yurishdan oldin atrofingizni yaxshilab ko'rib chiqing.

DFS oldindan, buyurtmadan keyingi tartibda buzilishlarga o'xshaydi. Daraxt tugunlarini bosqichma-bosqich bosib chiqarishni istasak, BFS bizga kerak.

Buni amalga oshirish uchun biz grafikning "darajasini" saqlash uchun "ota-ona darajasiga" saqlash uchun navbat (ma'lumotlarning tuzilishi) kerak bo'ladi. Oldingi rasmda navbatga qo'yilgan tugunlar ochiq ko'k rangda.

Asosan, bosqichma-bosqich o'tish, har bir darajadagi tugunlar navbatdan olinadi va har bir qabul qilingan tugunga tashrif buyurganimizda, biz o'z navbatida bolalarimizni (keyingi bosqich uchun) kiritishimiz kerak. Quyidagi kod BFS asosiy g'oyasini olish uchun etarli darajada sodda. Grafik ulangan deb taxmin qilinadi, garchi uni uzilgan grafiklarga qo'llash uchun o'zgartirish mumkin bo'lsa.

Asosiy g'oyani tugunga asoslangan ulangan grafik ko'rinishida ko'rsatish oson. Shuni yodda tutingki, grafika shpalining bajarilishi vakillikdan vakillikka qadar farq qiladi.

BFS va DFS grafik qidirish bilan bog'liq muammolarni hal qilishda muhim vositadir (ammo grafik qidiruv algoritmlari tonna mavjudligini unutmang). DFS nafis rekursiv tatbiqga ega bo'lsa-da, uni iterativ ravishda amalga oshirish maqsadga muvofiqdir. BFS-ni takrorlash uchun biz navbatdan foydalandik, DFS uchun sizga stack kerak bo'ladi. Grafikdagi eng mashhur muammolardan biri va shu bilan birga ushbu maqolada o'qiganingiz mumkin bo'lgan sabablaridan biri bu grafik tepalari orasidagi eng qisqa yo'lni topish muammodir. Va bu bizni so'nggi fikr tajribamizga olib boradi.

Uber va eng qisqa yo'l muammosi (Dijkstraning algoritmi)

50 million foydalanuvchisi va 7 million haydovchisi (manbai) bilan Uber faoliyati uchun eng muhim narsalardan biri bu haydovchilarni chavandozlarga samarali tarzda moslashdir. Muammo joylardan boshlanadi.

Orqa fonda foydalanuvchilarning millionlab so'rovlari ko'rib chiqilishi kerak, ularning har biri so'rovlarni yaqin yoki bir nechta (odatda ko'proq) haydovchilarga yuboradi. Foydalanuvchi so'rovini yaqin atrofdagi barcha drayverlarga yuborish osonroq va ba'zan yanada oqilona bo'lsa-da, ba'zi oldindan ishlov berish aslida yordam berishi mumkin.

Kiruvchi so'rovlarni qayta ishlash va foydalanuvchi koordinatalari asosida joylashuv zonasini topish, so'ngra eng yaqin koordinatali haydovchilarni topish bilan bir qatorda, biz haydash uchun to'g'ri haydovchini ham topishimiz kerak. Geografik fazoviy so'rovlarga yo'l qo'ymaslik uchun (hozirgi koordinatalarni foydalanuvchi koordinatalari bilan taqqoslab yaqin atrofdagi mashinalarni olib kelish), aytaylik, xaritada foydalanuvchi va yaqin atrofdagi bir nechta mashinalar bilan segment mavjud.

Shunga o'xshash narsa:

Avtomobildan foydalanuvchiga mumkin bo'lgan yo'llar sariq rangda. Muammo shundaki, avtomobil foydalanuvchiga etib borishi uchun minimal talab qilinadigan masofani hisoblash, boshqacha aytganda, ular orasidagi eng qisqa yo'lni topishdir. Bu Uber emas, balki Google Xaritalar haqida ko'proq ma'lumotga ega bo'lsa-da, biz ushbu aniq va soddalashtirilgan vaziyatda buni hal qilishga harakat qilamiz, chunki odatda bittadan ortiq haydovchi avtomobili mavjud va Uber eng yuqori reytingga ega bo'lgan eng yaqin mashinani hisoblashni xohlashi mumkin. foydalanuvchiga.

Ushbu rasm uchun uchta uchta mashina uchun foydalanuvchiga etib boradigan eng qisqa yo'lni hisoblash va qaysi avtomashinani jo'natish eng maqbul bo'lishini hisoblash degan ma'noni anglatadi. Ishlarni chindan ham sodda qilish uchun biz bu ishni bitta mashina bilan muhokama qilamiz. Bu erda foydalanuvchiga erishish mumkin bo'lgan ba'zi marshrutlar mavjud.

Foydalanuvchi bilan bog'lanish mumkin bo'lgan variantlar

Tugatishgacha, biz ushbu segmentni grafik sifatida taqdim etamiz:

Bu yo'naltirilmagan og'irlik grafigi (aniqroq bo'lishi uchun qirralarning o'lchami). B (mashina) va A (foydalanuvchi) vertikallari orasidagi eng qisqa yo'lni topish uchun, eng kam og'irliklari bilan qirralardan iborat yo'lni topishimiz kerak. Siz echimning versiyasini ishlab chiqishga tayyormiz. Biz Dijkstraning versiyasiga yopishib olamiz. Dijkstraning algoritmining quyidagi bosqichlari Vikipediyadan.

Biz boshlayotgan tugunni boshlang'ich tugun deb atasin. Y tugunining masofasi boshlang'ich tugundan Y.gacha bo'lgan masofaga teng bo'lsin. Dijkstraning algoritmi bir necha boshlang'ich masofani belgilaydi va ularni bosqichma-bosqich yaxshilashga harakat qiladi.

  1. Barcha tugunlarni ko'rinmaydigan qilib belgilang. Ko'zda tutilmagan to'plam deb nomlangan barcha ko'zda tutilmagan tugunlarning to'plamini yarating.
  2. Har bir tugunga dastlabki masofa qiymatini belgilang: boshlang'ich tugunimiz uchun nolga va boshqa tugunlarga cheksizlik. Dastlabki tugunni oqim sifatida o'rnating.
  3. Mavjud tugun uchun, uning barcha kutilmagan qo'shnilarini ko'rib chiqing va mavjud tugun orqali ularning taxminiy masofalarini hisoblang. Yangi hisoblangan boshlang'ich masofani joriy berilgan qiymat bilan taqqoslang va kichikini tayinlang. Masalan, agar hozirgi A tugun 6 masofa bilan belgilangan bo'lsa va uni B qo'shni bilan bog'laydigan chetning uzunligi 2 bo'lsa, u holda B dan A gacha bo'lgan masofa 6 + 2 = 8 bo'ladi. 8 dan katta masofani bosib keyin uni 8 ga o'zgartiring. Aks holda, joriy qiymatni saqlang.
  4. Biz hozirgi tugunning barcha qo'shnilarini hisobga olsak, mavjud tugunni tashrif buyurilgan deb belgilang va uni keraksiz to'plamdan olib tashlang. Tashrif buyurilgan tugun hech qachon boshqa tekshirilmaydi.
  5. Belgilangan tugun tashrif buyurilgan bo'lsa (ikkita aniq bir tugun o'rtasida marshrutni rejalashtirayotganda) yoki kutilmagan to'plamdagi tugunlar orasidagi eng kichik masofa cheksiz bo'lsa (to'liq chorrahani rejalashtirishda; boshlang'ich tugun o'rtasida hech qanday aloqa bo'lmaganda). va ko'rilmagan tugunlar), keyin to'xtating. Algoritm tugadi.
  6. Aks holda, eng kichik boshlang'ich masofa bilan belgilanadigan kutilmagan tugunni tanlang, uni yangi "joriy tugun" sifatida o'rnating va 3-bosqichga qayting.

Buni bizning misolimizga qo'llasak, B tugunidan (avtomobil) boshlang'ich tugun sifatida boshlaymiz. Dastlabki ikki bosqich uchun:

Bizning kutilmagan to'plamimiz barcha vertikallardan iborat. Shuningdek, rasmning chap tomonidagi jadvalga e'tibor bering. Barcha cho'qqilar uchun u verteksdan B va oldingi ("Old" belgi) barcha eng qisqa masofalarni o'z ichiga oladi. Masalan, B dan F gacha bo'lgan masofa 20 ga teng, oldingi uchi esa B dir.

Biz B tashrif buyurgan deb belgilaymiz va uni qo'shni F ga o'tkazamiz.

Endi biz F-ni tashrif buyurgan deb belgilaymiz va eng kichik boshlang'ich masofaga ega bo'lgan keyingi ko'rinmas tugunni tanlaymiz, bu G.dir. Shuningdek chap tomonidagi jadvalga e'tibor bering. Oldingi rasmli tugunlarda C, F va G allaqachon oldingi tugunlar bilan taqqoslanadigan masofalarni belgilab qo'ygan, ular yuqorida aytib o'tilgan tugunlarga olib keladi.

Algoritmda aytilganidek, agar maqsad tuguniga tashrif buyurilgan bo'lsa (bizning holatimizda bo'lgani kabi, ikkita aniq tugun o'rtasida marshrutni rejalashtirishda), biz to'xtashimiz mumkin. Shunday qilib, bizning keyingi qadamimiz quyidagi qiymatlar bilan algoritmni to'xtatadi.

Shunday qilib, biz B dan Agacha eng qisqa masofani va F va G tugunlari orqali o'tadigan yo'lni olamiz.

Bu haqiqatan ham Uber-da yuzaga kelishi mumkin bo'lgan muammolarning eng oddiy namunasidir, buni bizning aysbergga o'xshatib, biz aysbergning uchida turibmiz. Biroq, bu grafika nazariyasi va uning qo'llanilishining haqiqiy dunyosini o'rganishda yaxshi boshlang'ich. Men avval ushbu maqolada rejalashtirganlarimni to'liq bajarmadim, ammo yaqin kelajakda bu davom ettiriladi (shu bilan birga ma'lumotlar bazasini indeksatsiya qilish).

Grafiklar haqida gapirish uchun hali ko'p narsa bor (hali o'rganish kerak). Ushbu maqolani aysbergning yana bir uchi sifatida oling. Agar siz bu haqda uzoq vaqt o'qigan bo'lsangiz, siz albatta cookie-fayllariga loyiqsiz. Qarsaklar va baham ko'rishni unutmang. Rahmat.

Resurslar

[1] Sh. Hatto, G. hatto, grafik algoritmlari

Keyingi o'qish

R. Sedjevik, K. Ueyn, algoritmlar

T. Kormen, Ch. Leiserson, R. Rivest, C. Shtayn, Algoritmlarga kirish

Airbnb Engineering, AirbnbEng

Netflix Tech Blog, Netflix Technology Blog

Twitter muhandislik blogi

Uber muhandislik blogi