муқаддима
Ман ин гузоришро ба забони англисӣ дар конфронси GopherCon Russia 2019 дар Маскав ва ба забони русӣ дар мулоқот дар Нижний Новгород додам. Мо дар бораи шохиси bitmap гап мезанем - камтар маъмул аз B-дарахт, вале на камтар ҷолиб. Мубодила баромадҳо дар конфронс ба забони англисӣ ва стенограммаҳои матнӣ ба забони русӣ.
Мо дида мебароем, ки индекси bitmap чӣ гуна кор мекунад, кай беҳтар аст, кай аз дигар индексҳо бадтар аст ва дар кадом ҳолатҳо он нисбат ба онҳо ба таври назаррас тезтар аст; Биёед бубинем, ки кадом DBMS-ҳои маъмул аллакай индексҳои bitmap доранд; Биёед кӯшиш кунем, ки дар Go худамонро нависем. Ва "барои шириниҳо" мо китобхонаҳои тайёрро барои эҷод кардани пойгоҳи махсуси фаврии худ истифода хоҳем кард.
Умедворам, ки асарҳои ман барои шумо муфид ва ҷолиб хоҳанд буд. Бирав!
Муқаддима
Салом ба ҳама! Соат шаши бегоҳ аст ва мо ҳама хеле хаста ҳастем. Вақти олӣ барои сӯҳбат дар бораи назарияи дилгиркунандаи индекси пойгоҳи додаҳо, дуруст? Парво накунед, ман дар ин ҷо ва он ҷо як-ду сатри рамзи сарчашма хоҳам дошт. 🙂
Ҳама шӯхӣ як сӯ, гузориш пур аз маълумот аст ва мо вақти зиёд надорем. Пас биёед оғоз кунем.
Имрӯз ман дар бораи чизҳои зерин гап мезанам:
- индексҳо чистанд;
- индекси bitmap чист;
- дар куҷо истифода мешавад ва дар куҷо НЕСТ ва чаро;
- татбиқи оддӣ дар Go ва каме мубориза бо компилятор;
- каме соддатар, аммо татбиқи хеле самараноктар дар Go assembler;
- "мушкилоти" индексҳои bitmap;
- татбиқи мавҷуда.
Пас, индексҳо чист?
Индекс як сохтори алоҳидаи додаҳост, ки мо ба ғайр аз маълумоти асосӣ нигоҳ медорем ва навсозӣ мекунем. Он барои суръат бахшидан ба ҷустуҷӯ истифода мешавад. Бидуни индексатсияҳо, ҷустуҷӯ гузаштани маълумотро пурра талаб мекунад (раванде, ки сканкунии пурра номида мешавад) ва ин раванд мураккабии алгоритмии хатӣ дорад. Аммо пойгоҳи додаҳо одатан миқдори зиёди маълумотро дар бар мегиранд ва мураккабии хаттӣ хеле суст аст. Идеалӣ, мо як логарифмӣ ё доимӣ мегирем.
Ин як мавзӯи бениҳоят мураккаб аст, ки пур аз нозукиҳо ва муомилот аст, аммо пас аз баррасии даҳсолаҳои таҳия ва таҳқиқоти пойгоҳи додаҳо, ман омодаам бигӯям, ки танҳо чанд равишҳои ба таври васеъ истифодашаванда барои эҷоди индексҳои пойгоҳи додаҳо мавҷуданд.
Равиши аввал ба таври иерархӣ кам кардани фазои ҷустуҷӯ, тақсим кардани фазои ҷустуҷӯ ба қисмҳои хурдтар аст.
Мо одатан ин корро бо истифода аз навъҳои гуногуни дарахтон мекунем. Мисол як қуттии калони маводҳо дар ҷевони шумо хоҳад буд, ки қуттиҳои хурдтари маводҳоро ба мавзӯъҳои гуногун тақсим мекунанд. Агар ба шумо мавод лозим бошад, шумо эҳтимол онҳоро дар қуттичае ҷустуҷӯ мекунед, ки дар он "Маводҳо" навишта шудааст, на қуттии "Кукиҳо", дуруст?
Усули дуюм ин аст, ки фавран интихоб кардани элемент ё гурӯҳи элементҳои дилхоҳ. Мо инро дар харитаҳои хэш ё индексҳои баръакс мекунем. Истифодаи харитаҳои хэш ба мисоли қаблӣ хеле монанд аст, аммо ба ҷои як қуттии қуттиҳо, шумо дар ҷевони худ як хӯшаи хурди ашёи ниҳоӣ доред.
Усули сеюм ин бартараф кардани зарурати ҷустуҷӯ мебошад. Мо инро бо истифода аз филтрҳои Блум ё филтрҳои коку анҷом медиҳем. Аввалинҳо фавран ҷавоб медиҳанд ва шуморо аз ҷустуҷӯ наҷот медиҳанд.
Рохи охирин пурра истифода бурдани тамоми куввае, ки аппаратураи хозиразамон ба мо медихад. Ин маҳз ҳамон чизест, ки мо дар индексҳои bitmap мекунем. Бале, ҳангоми истифодаи онҳо ба мо лозим меояд, ки баъзан тамоми индексро гузарем, аммо мо онро хеле самаранок иҷро мекунем.
Тавре ки ман гуфтам, мавзӯи индексҳои пойгоҳи додаҳо васеъ ва пур аз созиш аст. Ин маънои онро дорад, ки баъзан мо метавонем якчанд равишро дар як вақт истифода барем: агар мо бояд ҷустуҷӯро боз ҳам бештар суръат бахшем, ё ба мо лозим аст, ки ҳамаи намудҳои имконпазири ҷустуҷӯро фаро гирем.
Имрӯз ман дар бораи равиши камтар маълуми инҳо - индексҳои bitmap гап мезанам.
Ман кӣ ҳастам, ки дар ин мавзӯъ сухан гӯям?
Ман ҳамчун роҳбари гурӯҳ дар Badoo кор мекунам (шояд шумо бо маҳсулоти дигари мо, Bumble бештар шинос бошед). Мо аллакай дар саросари ҷаҳон зиёда аз 400 миллион корбар дорем ва хусусиятҳои зиёде дорем, ки мувофиқати беҳтаринро барои онҳо интихоб мекунанд. Мо инро бо истифода аз хидматҳои фармоишӣ, аз ҷумла индексҳои bitmap иҷро мекунем.
Пас, индекси bitmap чист?
Индексҳои bitmap, тавре ки аз ном бармеояд, барои амалӣ кардани индекси ҷустуҷӯ аз bitmap ё bitsets истифода мебаранд. Аз нигоҳи чашми парранда, ин шохис аз як ё якчанд чунин bitmaps иборат аст, ки ҳама гуна объектҳо (масалан одамон) ва хосиятҳо ё параметрҳои онҳо (синну сол, ранги чашм ва ғ.) ва алгоритме бо истифода аз амалиёти бит (ВА, Ё, НЕ) мебошад. ) барои ҷавоб додан ба дархости ҷустуҷӯ.
Ба мо гуфтанд, ки индексҳои битмап барои ҳолатҳое мувофиқанд ва хеле иҷрокунандаанд, ки ҷустуҷӯҳое мавҷуданд, ки дархостҳоро дар бисёр сутунҳои дараҷаи паст муттаҳид мекунанд (фикр кунед, ки "ранги чашм" ё "вазъи оилавӣ" дар муқоиса бо "масофа аз маркази шаҳр"). Аммо ман баъдтар нишон медиҳам, ки онҳо барои сутунҳои баландсифат низ хуб кор мекунанд.
Биёед соддатарин мисоли индекси bitmap-ро бубинем.
Тасаввур кунед, ки мо рӯйхати тарабхонаҳои Маскав дорем, ки дорои хосиятҳои дуӣ мебошанд:
- дар наздикии метро;
- таваққуфгоҳи хусусӣ вуҷуд дорад;
- айвон дорад (террас дорад);
- шумо метавонед мизро банд кунед (бандро қабул мекунад);
- муносиб барои гиёҳхорон (дӯстона гиёҳхорон);
- қимат (қимат).
Биёед ба ҳар як тарабхона рақами пайдарпайро аз 0 сар карда, хотираро барои 6 харита ҷудо кунем (якто барои ҳар як хусусият). Сипас, мо ин харитаҳоро вобаста ба он, ки тарабхона дорои ин амвол аст ё не, пур мекунем. Агар ресторани 4 айвон дошта бошад, пас бит № 4 дар "веранда дорад" ба 1 гузошта мешавад (агар айвон набошад, пас ба 0).
Ҳоло мо соддатарин индекси bitmap дорем ва мо метавонем онро барои посух додан ба саволҳои зерин истифода барем:
- "Ба ман тарабхонаҳои гиёҳхорро нишон диҳед";
- "Ба ман тарабхонаҳои арзонеро нишон диҳед, ки веранда доранд, ки дар он шумо метавонед миз захира кунед."
Чӣ хел? Биёед бубинем. Дархости аввал хеле содда аст. Ба мо танҳо лозим аст, ки харитаи "дӯстонаи гиёҳхорӣ" -ро бигирем ва онро ба рӯйхати тарабхонаҳое табдил диҳем, ки битҳои онҳо фош мешаванд.
Дархости дуюм каме мураккабтар аст. Ба мо лозим аст, ки битмап-и НЕСТ-ро дар харитаи "гаронбаҳо" истифода барем, то рӯйхати тарабхонаҳои арзонро ба даст орем, пас ВА он бо битмапи "метавонам мизро фармоиш диҳам" ва ва натиҷа бо битмап "веранда вуҷуд дорад". Харитаи натиҷавӣ рӯйхати муассисаҳоеро дар бар хоҳад гирифт, ки ба ҳамаи меъёрҳои мо мувофиқат мекунанд. Дар ин мисол, ин танҳо тарабхонаи "Юность" аст.
Дар ин ҷо назарияи зиёде вуҷуд дорад, аммо хавотир нашав, мо кодро ба зудӣ хоҳем дид.
Индексҳои bitmap дар куҷо истифода мешаванд?
Агар шумо индексҳои bitmap-ро Google кунед, 90% ҷавобҳо бо ин ё он роҳ ба Oracle DB алоқаманд хоҳанд буд. Аммо дигар DBMS низ эҳтимолан чунин чизи олиро дастгирӣ мекунанд, дуруст? На дарвоқеъ.
Биёед рӯйхати гумонбарони асосиро аз назар гузаронем.
MySQL ҳанӯз индексҳои bitmap-ро дастгирӣ намекунад, аммо пешниҳоде ҳаст, ки илова кардани ин интихобро пешниҳод мекунад ().
PostgreSQL индексҳои bitmap-ро пуштибонӣ намекунад, аммо харитаҳои оддӣ ва амалиёти битро барои муттаҳид кардани натиҷаҳои ҷустуҷӯ дар бисёр индексҳои дигар истифода мебарад.
Tarantool дорои индексҳои bitset мебошад ва ҷустуҷӯҳои оддии онҳоро дастгирӣ мекунад.
Redis дорои майдонҳои оддӣ мебошад) бе кобилияти чустучуи онхо.
MongoDB ҳанӯз индексҳои bitmap-ро дастгирӣ намекунад, аммо инчунин як пешниҳоде вуҷуд дорад, ки ин хосият илова карда шавад.
Elasticsearch харитаҳои bitmap-ро дар дохили худ истифода мебарад).
- Аммо дар хонаи мо хамсояи нав пайдо шуд: Пилоза. Ин як пойгоҳи нави ғайрирасмӣ аст, ки дар Go навишта шудааст. Он танҳо индексҳои bitmap-ро дар бар мегирад ва ҳама чизро ба онҳо асос медиҳад. Мо дар ин бора каме дертар гап мезанем.
Амалиёт дар Go
Аммо чаро индексҳои bitmap ин қадар кам истифода мешаванд? Пеш аз посух додан ба ин савол, ман мехоҳам ба шумо нишон диҳам, ки чӣ гуна индекси bitmap-и хеле содда дар Go татбиқ карда шавад.
Bitmaps аслан танҳо қисмҳои додаҳо мебошанд. Дар Go, биёед барои ин буридаҳои байтро истифода барем.
Мо як харитаи бит барои як хусусияти тарабхона дорем ва ҳар як бит дар битмап нишон медиҳад, ки оё тарабхонаи мушаххас ин амвол дорад ё не.
Ба мо ду вазифаи ёрирасон лозим мешавад. Яке барои пур кардани харитаҳои мо бо маълумоти тасодуфӣ истифода мешавад. Тасодуфан, аммо бо эҳтимолияти муайян, ки тарабхона дорои ҳар як молу мулк. Масалан, ман боварӣ дорам, ки дар Маскав тарабхонаҳо хеле каманд, ки шумо мизро фармоиш дода наметавонед ва ба назарам, тақрибан 20% муассисаҳо барои гиёҳхорӣ мувофиқанд.
Функсияи дуюм битмапро ба рӯйхати тарабхонаҳо табдил медиҳад.
Барои ҷавоб додан ба саволи "Ба ман тарабхонаҳои арзонеро нишон диҳед, ки майдонча доранд ва метавонанд фармоиш кунанд", ба мо ду амалиёти битӣ лозим аст: НЕ ва ВА.
Мо метавонем бо истифода аз оператори мураккабтар ВА НЕ, коди худро каме содда кунем.
Мо барои ҳар яке аз ин амалиётҳо вазифаҳо дорем. Ҳардуи онҳо аз буридаҳо мегузаранд, аз ҳар кадоми онҳо унсурҳои мувофиқро мегиранд, онҳоро бо амалиёти каме якҷоя мекунанд ва натиҷаро ба буридаи натиҷа медиҳанд.
Ва акнун мо метавонем харитаҳо ва функсияҳои худро барои посух додан ба дархости ҷустуҷӯ истифода барем.
Иҷрои он он қадар баланд нест, гарчанде ки функсияҳо хеле соддаанд ва мо ҳар дафъае, ки функсия даъват карда мешуд, як буридаи навро барнагардонда, пули зиёдеро сарфа кардем.
Пас аз як каме профилсозӣ бо pprof, ман пайхас кардам, ки компилятори Go як оптимизатсияи хеле содда, вале муҳимро аз даст додааст: функсияи inlining.
Гап дар сари он аст, ки компилятори Go аз ҳалқаҳое, ки аз буридаҳо мегузаранд, сахт метарсад ва аз функсияҳои дарунсохт, ки чунин ҳалқаҳоро дар бар мегиранд, қатъиян рад мекунад.
Аммо ман наметарсам ва ман метавонам компиляторро бо истифода аз goto ба ҷои ҳалқа фиреб диҳам, ба мисли рӯзҳои қадим.
Ва, тавре ки шумо мебинед, ҳоло компилятор функсияи моро бо хушнудӣ ба кор мебарад! Дар натича мо кариб 2 микросонияро сарфа мекунем. Бад не!
Камбудии дуюмро дидан осон аст, агар шумо ба натиҷаи васлкунӣ бодиққат назар кунед. Компилятор дар дохили ҳалқаи гармтарини мо чеки сарҳади буридаро илова кард. Гап дар он аст, ки Go забони бехатар аст, мураттиб метарсад, ки се далели ман (се бурида) андозаҳои гуногун доранд. Баъд аз ҳама, он гоҳ имкони назариявии пайдоиши ба истилоҳ буферӣ фаро мерасад.
Биёед компиляторро бо нишон додани он, ки ҳама буридаҳо як андозаанд, итминон диҳем. Мо метавонем инро тавассути илова кардани чеки оддӣ дар оғози функсияамон иҷро кунем.
Инро дида, компилятор бо хушҳолӣ чекро мегузаронад ва мо дар ниҳоят 500 наносонияро сарфа мекунем.
Буттаҳои калон
Хуб, мо тавонистем баъзе корҳоро аз татбиқи оддии худ фишурда кунем, аммо ин натиҷа воқеан назар ба сахтафзори ҷорӣ хеле бадтар аст.
Мо ҳама коре мекунем, ки амалиёти асосии бит аст ва протсессори мо онҳоро хеле самаранок иҷро мекунад. Аммо, мутаассифона, мо протсессори худро бо порчаҳои хеле хурди кор "таъзо" медиҳем. Функсияҳои мо амалҳоро дар асоси байт ба байт иҷро мекунанд. Мо метавонем ба осонӣ коди худро тағир диҳем, то бо қисмҳои 8-байтӣ бо истифода аз буридаи UInt64 кор кунем.
Тавре ки шумо мебинед, ин тағироти хурд барномаи моро ҳашт маротиба суръат бахшида, ҳаҷми партияро ҳашт маротиба зиёд кард. Фоидаро метавон гуфт, ки хаттӣ аст.
Амалиёт дар ассемблер
Аммо ин охир нест. Протсессорҳои мо метавонанд бо қисмҳои 16, 32 ва ҳатто 64 байт кор кунанд. Чунин амалиётҳои «васеъ»-ро як дастури чанд маълумот (SIMD; як дастур, маълумоти зиёд) меноманд ва раванди табдил додани код, ки ин гуна амалиётҳоро истифода мебарад, векторизатсия номида мешавад.
Мутаассифона, компилятори Go дар векторизатсия аз аъло нест. Дар айни замон, ягона роҳи векторизатсияи рамзи Go ин гирифтан ва гузоштани ин амалиётҳо бо истифода аз Go assembler мебошад.
Go assembler ҳайвони аҷиб аст. Шумо эҳтимол медонед, ки забони ассемблер чизест, ки ба меъмории компютере, ки шумо барои он менависед, сахт алоқаманд аст, аммо дар Go ин тавр нест. Go assembler бештар ба IRL (забони намояндагии мобайнӣ) ё забони мобайнӣ монанд аст: он амалан аз платформа мустақил аст. Роб Пайк бозии аъло нишон дод дар ин мавзӯъ чанд сол пеш дар GopherCon дар Денвер.
Илова бар ин, Go формати ғайриоддии Plan 9-ро истифода мебарад, ки аз форматҳои маъмулан қабулшудаи AT&T ва Intel фарқ мекунад.
Бо боварӣ метавон гуфт, ки бо даст навиштани Go assembler шавқовартарин нест.
Аммо, хушбахтона, аллакай ду асбоби сатҳи баланд мавҷуданд, ки ба мо дар навиштани Go assembler кӯмак мерасонанд: PeachPy ва avo. Ҳарду утилитаҳо ассемблери Go аз рамзи сатҳи болотар мутаносибан дар Python ва Go навишта шудаанд.
Ин утилитҳо чизҳоро ба монанди тақсимоти реестр, навиштани ҳалқаҳо содда мекунанд ва умуман раванди ворид шудан ба ҷаҳони барномасозии ассембҳоро дар Go содда мекунанд.
Мо avo-ро истифода мебарем, аз ин рӯ барномаҳои мо қариб барномаҳои Go муқаррарӣ хоҳанд буд.
Намунаи оддии барномаи avo чунин аст. Мо функсияи main() дорем, ки дар дохили худ функсияи Add()-ро муайян мекунад, ки маънои он илова кардани ду адад аст. Дар ин ҷо функсияҳои ёрирасон мавҷуданд, ки параметрҳоро аз рӯи ном гирифта, яке аз регистрҳои протсессори ройгон ва мувофиқро гиред. Ҳар як амалиёти протсессор дар avo вазифаи мувофиқ дорад, тавре ки дар ADDQ дида мешавад. Дар ниҳоят, мо функсияи ёрирасонро барои нигоҳ доштани арзиши натиҷа мебинем.
Бо занг задан gogener, мо барномаро дар avo иҷро мекунем ва дар натиҷа ду файл тавлид мешавад:
- add.s бо рамзи натиҷавӣ дар Go assembler;
- stub.go бо сарлавҳаҳои функсия барои пайваст кардани ду ҷаҳон: Бирав ва assembler.
Акнун, ки мо дидем, ки avo чӣ кор мекунад ва чӣ тавр, биёед ба вазифаҳои худ назар кунем. Ман версияҳои скалярӣ ва вектории (SIMD) функсияҳоро амалӣ кардам.
Биёед аввал версияҳои скаляриро дида бароем.
Тавре ки дар мисоли қаблӣ, мо реестри ройгон ва эътибори умумиро талаб мекунем, ба мо лозим нест, ки ҷубронҳо ва андозаҳоро барои далелҳо ҳисоб кунем. avo ҳамаи инро барои мо мекунад.
Мо барои беҳтар кардани кор ва фиреб додани компилятори Go тамғакоғазҳо ва goto (ё ҷаҳиш) -ро истифода мебурдем, аммо ҳоло мо онро аз аввал иҷро карда истодаем. Гап дар он аст, ки давраҳо мафҳуми сатҳи баландтаранд. Дар assembler, мо танҳо тамғакоғазҳо ва ҷаҳишҳо дорем.
Рамзи боқимонда бояд аллакай шинос ва фаҳмо бошад. Мо як ҳалқаро бо тамғакоғазҳо ва ҷаҳишҳо тақлид мекунем, як пораи хурди маълумотро аз ду буридаи худ мегирем, онҳоро бо амалиёти каме муттаҳид мекунем (Ва дар ин ҳолат НЕ) ва сипас натиҷаро ба буридаи натиҷавӣ мегузорем. Ҳама.
Рамзи охирини ассемблер чунин аст. Ба мо лозим набуд, ки ҷубронҳо ва андозаҳоро ҳисоб кунем (бо ранги сабз нишон дода шудааст) ё регистрҳои истифодашударо пайгирӣ кунем (бо ранги сурх нишон дода шудааст).
Агар мо иҷрои татбиқи забони ассемблерро бо иҷрои беҳтарин татбиқ дар Go муқоиса кунем, мо мебинем, ки он ҳамон аст. Ва ин интизор меравад. Дар ниҳоят, мо ҳеҷ чизи махсусе накардаем - мо танҳо он чизеро, ки компилятори Go иҷро мекард, такрор кардем.
Мутаассифона, мо наметавонем компиляторро маҷбур созем, ки функсияҳои мо, ки бо забони ассемблер навишта шудаанд, дохил шаванд. Дар айни замон компилятори Go чунин хусусият надорад, гарчанде ки муддати тӯлонӣ дархост барои илова кардани он вуҷуд дорад.
Аз ин рӯ, аз функсияҳои хурд дар забони ассемблер ягон фоида ба даст овардан ғайриимкон аст. Мо бояд ё вазифаҳои калон нависем, ё бастаи нави математика/битҳоро истифода барем ё забони ассемблерро гузарем.
Акнун биёед ба версияҳои вектории функсияҳои худ назар андозем.
Барои ин мисол, ман қарор додам, ки AVX2-ро истифода барам, бинобар ин мо амалиётҳоеро истифода хоҳем кард, ки дар қисмҳои 32-байтӣ кор мекунанд. Сохтори код ба версияи скалярӣ хеле монанд аст: параметрҳои боркунӣ, дархости феҳристи муштараки ройгон ва ғайра.
Як навоварӣ ин аст, ки амалиёти васеътари векторҳо регистрҳои махсуси васеъро истифода мебаранд. Дар мавриди қисмҳои 32-байтӣ, ин регистрҳо бо пешванди Y мебошанд. Аз ин рӯ, шумо функсияи YMM()-ро дар код мебинед. Агар ман AVX-512-ро бо қисмҳои 64-бит истифода мекардам, префикс Z хоҳад буд.
Навоварии дуввум ин аст, ки ман тасмим гирифтам, ки оптимизатсия бо номи unrolling ҳалқаро истифода барам, ки маънои ҳашт амалиёти ҳалқаро дастӣ пеш аз гузаштан ба оғози ҳалқаро дорад. Ин оптимизатсия шумораи филиалҳоро дар код кам мекунад ва аз рӯи шумораи реестрҳои ройгони дастрас маҳдуд аст.
Хуб, дар бораи иҷроиш чӣ гуфтан мумкин аст? Вай зебост! Мо нисбат ба беҳтарин ҳалли Go тақрибан ҳафт маротиба суръат гирифтем. Таъсирбахш, дуруст?
Аммо ҳатто ин татбиқро метавон бо истифода аз AVX-512, пешакӣ ё JIT (компилятори танҳо дар вақташ) барои ҷадвали дархост суръат дод. Аммо ин албатта як мавзӯи гузориши алоҳида аст.
Мушкилот бо индексҳои bitmap
Акнун, ки мо аллакай татбиқи оддии индекси bitmap дар Go ва як хеле самараноктар дар забони ассемблерро дида баромадем, биёед дар ниҳоят дар бораи он сӯҳбат кунем, ки чаро индексҳои bitmap ин қадар кам истифода мешаванд.
Дар ҳуҷҷатҳои кӯҳна се мушкилот бо индексҳои bitmap зикр шудаанд, аммо ҳуҷҷатҳои навтар ва ман баҳс мекунанд, ки онҳо дигар аҳамият надоранд. Мо ба хар кадоми ин проблемахо чукур намепардозем, балки ба онхо сатхй назар мекунем.
Проблемаи баланд бардош-тани кордонй
Ҳамин тавр, ба мо гуфта мешавад, ки индексҳои bitmap танҳо барои майдонҳои дорои кардиналияти паст, яъне онҳое, ки арзишҳои кам доранд (масалан, ҷинс ё ранги чашм) мувофиқанд ва сабаб дар он аст, ки тасвири маъмулии чунин майдонҳо (як бит барои як арзиш) дар сурати баланд будани кардиналӣ, он фазои аз ҳад зиёдро ишғол мекунад ва илова бар ин, ин индексҳои bitmap суст (кам) пур карда мешаванд.
Баъзан мо метавонем як намоиши дигарро истифода барем, масалан стандарти барои муаррифии рақамҳо. Аммо ин пайдоиши алгоритмҳои фишурдасозӣ буд, ки ҳама чизро тағир дод. Дар тӯли даҳсолаҳои охир, олимон ва муҳаққиқон шумораи зиёди алгоритмҳои фишурдасозиро барои bitmap таҳия карданд. Бартарии асосии онҳо дар он аст, ки барои иҷрои амалиёти бит зарурати кушодани харитаҳои бит вуҷуд надорад - мо метавонем амалиёти битро мустақиман дар харитаҳои фишурда иҷро кунем.
Ба наздикӣ, равишҳои гибридӣ ба монанди харитаҳои ғуррон пайдо шуданд. Онҳо ҳамзамон се намояндагии гуногунро барои bitmap истифода мебаранд - худи bitmap, массивҳо ва ба истилоҳ битҳо - ва мувозинати байни онҳо барои ба ҳадди аксар расонидани кор ва кам кардани истеъмоли хотира.
Шумо метавонед харитаҳои ғурронро дар барномаҳои маъмултарин пайдо кунед. Аллакай шумораи зиёди татбиқҳо барои забонҳои гуногуни барномасозӣ мавҷуданд, аз ҷумла зиёда аз се татбиқ барои Go.
Равиши дигаре, ки метавонад ба мо дар мубориза бо кардиналияти баланд кӯмак кунад, биннинг номида мешавад. Тасаввур кунед, ки шумо майдоне доред, ки баландии одамро ифода мекунад. Баландӣ рақами нуқтаи шинокунанда аст, аммо мо одамон дар ин бора фикр намекунем. Барои мо байни қадаш 185,2 см ва 185,3 см фарқият вуҷуд надорад.
Маълум мешавад, ки мо метавонем арзишҳои шабеҳро дар ҳудуди 1 см ба гурӯҳҳо гурӯҳбандӣ кунем.
Ва агар мо инчунин донем, ки хеле кам одамон аз 50 см кӯтоҳтар ва аз 250 см баландтаранд, пас мо метавонем як майдони дорои кардиналияти беохирро ба майдони дорои кардиналияти тақрибан 200 арзиш табдил диҳем.
Албатта, агар лозим бошад, мо метавонем баъдан филтркунии иловагӣ анҷом диҳем.
Мушкилоти фарохмаҷрои баланд
Мушкилоти навбатӣ бо индексҳои bitmap ин аст, ки навсозии онҳо метавонад хеле гарон бошад.
Пойгоҳи додаҳо бояд маълумотро навсозӣ кунанд, дар ҳоле ки эҳтимолан садҳо дархостҳои дигар маълумотро ҷустуҷӯ мекунанд. Ба мо қуфлҳо лозим аст, то аз мушкилот бо дастрасии ҳамзамон додаҳо ё дигар мушкилоти мубодила пешгирӣ кунем. Ва дар он ҷое, ки як қулфи калон вуҷуд дорад, мушкилот вуҷуд дорад - муноқишаи қулф, вақте ки ин қулф ба монеъа табдил меёбад.
Ин мушкилотро тавассути истифодаи sharding ё бо истифода аз индексҳои версиявӣ ҳал кардан ё бартараф кардан мумкин аст.
Sharding як чизи оддӣ ва маълум аст. Шумо метавонед индекси bitmap-ро мисли ҳама гуна маълумоти дигар тақсим кунед. Ба ҷои як қулфи калон, шумо як хӯшаи қулфҳои хурд мегиред ва ҳамин тавр аз ихтилофи қулфҳо халос мешавед.
Роҳи дуюми ҳалли мушкилот ин истифодаи индексҳои версиявӣ мебошад. Шумо метавонед як нусхаи индексро, ки шумо барои ҷустуҷӯ ё хондан истифода мекунед ва дигареро барои навиштан ё навсозӣ истифода баред, дошта бошед. Ва як маротиба дар як муддати муайян (масалан, як маротиба дар 100 мс ё 500 мс) шумо онҳоро такрор мекунед ва иваз мекунед. Албатта, ин равиш танҳо дар ҳолатҳое татбиқ мешавад, ки барномаи шумо метавонад индекси ҷустуҷӯи каме ақибмондаро идора кунад.
Ин ду равишро ҳамзамон истифода бурдан мумкин аст: шумо метавонед шохиси версияи тақсимшуда дошта бошед.
Саволҳои мураккабтар
Мушкилоти ниҳоӣ бо индексҳои bitmap дар он аст, ки ба мо мегӯянд, ки онҳо барои намудҳои мураккабтари дархостҳо, ба монанди дархостҳои span мувофиқ нестанд.
Воқеан, агар шумо дар ин бора фикр кунед, амалиёти битӣ ба монанди ВА, Ё ва ғайра барои пурсишҳои "Ба ман меҳмонхонаҳоеро нишон диҳед, ки нархи ҳуҷраҳо аз 200 то 300 доллар дар як шаб" чандон мувофиқ нестанд.
Ҳалли соддалавҳона ва хеле беақлона ин гирифтани натиҷаҳо барои ҳар як арзиши доллар ва муттаҳид кардани онҳо бо амалиёти битвазӣ OR хоҳад буд.
Як ҳалли каме беҳтар аст, ки истифодаи гурӯҳбандӣ. Масалан, дар гурӯҳҳои 50 доллар. Ин процесси моро 50 баробар метезонад.
Аммо мушкилот бо истифода аз намуди махсус барои ин намуди дархост сохташуда низ ба осонӣ ҳал карда мешавад. Дар мақолаҳои илмӣ онро харитаҳои рамзгузории диапазон меноманд.
Дар ин муаррифӣ, мо на танҳо як битро барои баъзе арзиш муқаррар мекунем (масалан, 200), балки ин арзиш ва ҳама чизро болотар таъин мекунем. 200 ва боло. Ҳамин барои 300: 300 ва болотар. Ва ғайра.
Бо истифода аз ин намояндагӣ, мо метавонем ба ин гуна дархости ҷустуҷӯ тавассути убури индекс ҳамагӣ ду маротиба ҷавоб диҳем. Аввалан, мо рӯйхати меҳмонхонаҳоеро мегирем, ки дар онҳо ҳуҷраи онҳо камтар ё 300 доллар арзиш дорад ва баъд аз он онҳоеро, ки арзиши ҳуҷра камтар ё 199 доллар аст, хориҷ мекунем. Тайёр.
Шумо ҳайрон мешавед, аммо ҳатто бо истифода аз индексҳои bitmap географӣ имконпазир аст. Маслиҳат ин аст, ки тасвири геометриро истифода баред, ки координатаи шуморо бо фигураи геометрӣ иҳота мекунад. Масалан, S2 аз Google. Рақам бояд имкон дошта бошад, ки дар шакли се ё зиёда хатҳои бурида, ки рақамгузорӣ карда мешаванд, нишон дода шавад. Бо ин роҳ, мо метавонем геологии худро ба якчанд пурсишҳо "қад-қади фосила" (қад-қади ин сатрҳои рақамӣ) табдил диҳем.
Ҳалли проблемаҳо
Умедворам, ки ман ба шумо каме таваҷҷӯҳ кардам ва шумо ҳоло дар арсенали худ як асбоби дигари муфид доред. Агар ба шумо ягон вақт лозим ояд, ки чунин коре кунед, шумо хоҳед донист, ки ба кадом роҳ назар кунед.
Бо вуҷуди ин, на ҳама вақт, сабр ва захираҳо барои аз сифр сохтани индексҳои bitmap доранд. Хусусан пешрафтатар, масалан, бо истифода аз SIMD.
Хушбахтона, якчанд ҳалли омода барои кӯмак ба шумо мавҷуданд.
Харитаҳои ғуррон
Аввалан, ҳамон китобхонаи битмапҳои ғуррон вуҷуд дорад, ки ман аллакай дар бораи он гуфта будам. Он дорои ҳама контейнерҳои зарурӣ ва амалиёти бит мебошад, ки ба шумо лозим меояд, ки индекси битмап-и мукаммалро созед.
Мутаассифона, дар айни замон, ҳеҷ яке аз татбиқҳои Go SIMD-ро истифода намебаранд, ки ин маънои онро дорад, ки татбиқи Go нисбат ба татбиқи C, масалан, камтар самараноктар аст.
Пилоза
Маҳсулоти дигаре, ки метавонад ба шумо кӯмак расонад, ин DBMS Pilosa мебошад, ки дар асл танҳо индексҳои bitmap дорад. Ин як ҳалли нисбатан нав аст, аммо он бо суръати баланд дилҳоро ба даст меорад.
Пилоса харитаҳои ғурронро дар дохили худ истифода мебарад ва ба шумо қобилияти истифодаи онҳоро медиҳад, ҳама чизҳоеро, ки ман дар боло гуфтам, содда ва шарҳ медиҳад: гурӯҳбандӣ, харитаҳои бо диапазон-рамзшуда, консепсияи майдон ва ғайра.
Биёед ба мисоли истифодаи Pilosa барои посух додан ба саволе, ки шумо аллакай бо он шинос ҳастед, зуд дида мебароем.
Намуна ба он чизе ки шумо қаблан дидаед, хеле монанд аст. Мо дар сервери Pilosa муштарӣ эҷод мекунем, индекс ва майдонҳои заруриро эҷод мекунем, сипас майдонҳои худро бо маълумоти тасодуфӣ бо эҳтимолият пур мекунем ва дар ниҳоят дархости шиносро иҷро мекунем.
Баъд аз ин, мо НЕСТ-ро дар майдони "гарон" истифода мебарем, пас натиҷаро (ё ВА онро) бо майдони "террас" ва майдони "заказҳо" буриш мекунем. Ва ниҳоят, мо натиҷаи ниҳоӣ мегирем.
Ман дар ҳақиқат умедворам, ки дар ояндаи наздик ин намуди нави индекс инчунин дар DBMS ба монанди MySQL ва PostgreSQL - индексҳои bitmap пайдо мешаванд.
хулоса
Агар шумо то ҳол хоб нарафтед, ташаккур. Ман маҷбур шудам, ки ба далели маҳдуд будани вақт ба бисёр мавзӯъҳо мухтасар сухан ронам, аммо умедворам, ки сӯҳбат муфид ва шояд ҳатто рӯҳбаландкунанда буд.
Индексҳои bitmap хубанд, ки дар бораи он огоҳ шавед, ҳатто агар шумо ҳоло ба онҳо ниёз надоред. Бигзор онҳо як абзори дигар дар қуттии асбобҳои шумо бошанд.
Мо ҳиллаҳои гуногуни иҷроишро барои Go ва чизҳоеро дида баромадем, ки компилятори Go ҳанӯз чандон хуб кор намекунад. Аммо ин барои донистани ҳар як барномасози Go комилан муфид аст.
Ин ҳама чизест, ки ман ба шумо гуфтан мехостам. Сипос!
Манбаъ: will.com