Taksi va avtoto'ldirish dizayni: geohash, yaqin haydovchi va Trie takliflari
Qisqacha: Taksi xizmatida asosiy savol — "yo'lovchiga eng yaqin bo'sh haydovchi kim?". Buning uchun yer yuzi kataklarga bo'linadi (geohash yoki quadtree) va qidiruv faqat yaqin kataklarda bajariladi. Joylashuvlar soniyasiga yuz minglab yangilanadi, shuning uchun ular diskka emas, xotiradagi indeksga yoziladi. Avtoto'ldirishda esa har harf bosilganda takliflar kerak: Trie'ning har tugunida eng mashhur takliflar oldindan tayyorlab qo'yiladi.
Bu darsda
- Taksi va avtoto'ldirish uchun yozish va o'qish yukini formula bilan hisoblaysiz.
- Geohash qanday ishlashini brauzerda kodlab ko'rasiz va uning chegara muammosini tushuntirasiz.
- Joylashuv oqimi uchun ombor tanlaysiz: Postgres, PostGIS yoki xotiradagi geo indeks.
- Avtoto'ldirish uchun Trie'da top-k takliflarni oldindan hisoblashni narxi bilan solishtirasiz.
- O'zbek matnidagi apostrof qidiruvni qanday buzishini loyihadagi misolda ko'rasiz.
Oldin bilishingiz kerak: Dizayn: video va fayl saqlash, streaming, PostGIS va geo so'rovlar, Geolokatsiya, Trie (prefiks daraxti).
1. Nega bu kerak?
Dizayn: video va fayl saqlash darsida asosiy resurs trafik edi. Bu darsda ikki yangi turdagi masala: makon bo'yicha qidiruv va prefiks bo'yicha qidiruv. Ikkalasi ham oddiy indeks bilan yaxshi ishlamaydi.
Toshkentda taksi chaqirganingizni eslang. Ilova bir-ikki soniyada "haydovchi 3 daqiqada yetib keladi" deydi. Shu soniyalarda tizim minglab haydovchi ichidan sizga yaqinlarini topadi, ular bo'shligini tekshiradi va bittasini tanlaydi. Shu paytda har bir haydovchi telefoni har bir necha soniyada "men shu yerdaman" deb yuboradi.
Avtoto'ldirish ham kundalik narsa. Qidiruv qatoriga "tosh" deb yozasiz va darhol "toshkent", "toshkent metro" chiqadi. Har harf — yangi so'rov. Javob kechiksa, takliflar siz yozib bo'lganingizdan keyin chiqadi va foydasi qolmaydi.
Hayotiy o'xshatish: shahar xaritasi kvadratlarga bo'lingan, har kvadratning nomi bor. Do'stingiz "men B-7 dayman" desa, butun shaharni emas, faqat B-7 va qo'shni kvadratlarni qidirasiz. Geohash — shu kvadratlarning dunyo miqyosidagi tizimi.
2. Talablar va hisob-kitob
2.1 Nimani quramiz
Taksi — funksional talablar:
- Haydovchi joylashuvini muntazam yuboradi.
- Yo'lovchi uchun eng yaqin bo'sh haydovchilar topiladi.
- Buyurtma bitta haydovchiga beriladi (ikkitasiga emas).
Avtoto'ldirish — funksional talablar:
- Har harf bosilganda 5–10 ta taklif, mashhurligi bo'yicha.
- Kirill va lotin, turli apostroflar bilan yozilgan so'rov bir xil topilsin.
Nofunksional talablar:
- Haydovchini topish — bir soniyadan kam.
- Takliflar — har harfga 100 millisekunddan kam (foydalanuvchi yozish tezligi bilan).
- Joylashuv bir necha soniya eskirgan bo'lishi mumkin — bu qabul qilinadi.
Oxirgi band muhim. Joylashuv uchun kuchli izchillik kerak emas: haydovchining 4 soniya oldingi joyi ham yetarli aniq.
Ikkala masala bitta darsda bo'lishining sababi bor. Ikkalasida ham "qidiruv" so'zi oddiy WHERE nom = … emas. Taksida — "shu nuqtaga yaqin", avtoto'ldirishda — "shu harflar bilan boshlanadigan". Oddiy B-daraxt indeksi tenglik va oraliq bo'yicha yaxshi ishlaydi. Makon va prefiks uchun esa ma'lumotni shunday ko'rinishga keltirish kerakki, savol yana "oraliq" yoki "prefiks" ga aylansin. Geohash ham, Trie ham aynan shu ishni qiladi.
2.2 Raqamlar
Farazlar dars uchun, ular real kompaniya raqami emas. 500 ming faol haydovchi, har biri 4 soniyada bir marta joylashuv yuboradi (taxminan 50 bayt). Avtoto'ldirishda kuniga 10 million foydalanuvchi, har biri 5 marta qidiradi, har qidiruvda o'rtacha 4 harf.
// Farazlar dars uchun, real kompaniya raqami emas
const haydovchi = 500e3; // faol haydovchi
const davr = 4; // har necha soniyada joylashuv
const yozuvBayt = 50; // lat, lon, vaqt, id
const dau = 10e6; // avtoto'ldirish: kunlik foydalanuvchi
const qidiruv = 5; // kuniga qidiruv
const harf = 4; // har qidiruvda bosilgan harf
const yozuv = haydovchi / davr;
const mb = (b) => `${(b / 1e6).toFixed(1)} MB`;
console.log("joylashuv yozuvi/s:", `${(yozuv / 1e3).toFixed(1)} K`);
console.log("trafik:", `${mb(yozuv * yozuvBayt)}/s`);
console.log("geo indeks:", mb(haydovchi * yozuvBayt));
const avto = (dau * qidiruv * harf) / 86_400;
const k = (avto / 1e3).toFixed(1);
console.log("avtoto'ldirish so'rov/s:", `${k} K`);Konsolda:
joylashuv yozuvi/s: 125.0 K
trafik: 6.3 MB/s
geo indeks: 25.0 MB
avtoto'ldirish so'rov/s: 2.3 K| Kattalik | Formula | Natija |
|---|---|---|
| joylashuv yozuvlari/s | 500e3 / 4 |
125.0 K |
| joylashuv trafigi | 125e3 × 50 B |
6.3 MB/s |
| geo indeks (faqat oxirgi joy) | 500e3 × 50 B |
25.0 MB |
| avtoto'ldirish so'rov/s | 10e6 × 5 × 4 / 86400 |
2.3 K |
Bu raqamlar ikki kutilmagan xulosa beradi.
Birinchi: geo indeks kichik — atigi 25 MB. Har haydovchining faqat oxirgi joyi kerak, tarixi emas. 25 MB bitta jarayon xotirasiga bemalol sig'adi.
Ikkinchi: yozish oqimi katta — soniyasiga 125 ming. Har yozuvni diskka, tranzaksiya va WAL bilan yozish og'ir. Kurs tajribasida bitta 4 KB yozuv va fsync 16 ms olgan edi (Taxminiy hisob-kitob va latency raqamlari). Ya'ni joylashuv — "ko'p yoziladi, kichik, eskirishi mumkin" turidagi ma'lumot. Bunday ma'lumot xotirada yashaydi.
Avtoto'ldirishda esa 2.3 ming so'rov soniyasiga — o'rtacha. Bu katta emas, lekin har javobning kechikishi muhim.
Joylashuv trafigi esa kichik: 6.3 MB/s. Uni tarmoq bemalol ko'taradi. Muammo baytlarda emas, amallar sonida. Bu oldingi darsdagi videoning teskarisi: u yerda amallar kam, baytlar ko'p edi.
Bitta haydovchining 4 soniyada bir marta yozishi ham tanlangan son. Har soniyada yuborsa — yozuvlar to'rt barobar (500 ming/s), aniqlik esa biroz oshadi. Har 15 soniyada yuborsa — yozuvlar to'rt barobar kam, lekin shahar ichida 15 soniyada mashina 150–200 metr yuradi. Ba'zi ilovalar davrni moslashtiradi: haydovchi to'xtab tursa kamroq, yo'lovchi kutayotgan paytda tez-tez. Bu ham "qachon kerak emas" savoli: aniqlik faqat kerak bo'lgan paytda to'lanadi.
Tekshirib ko'ring: Hisob-kitobga ko'ra joylashuvlar 25 MB. Nega unda bitta Redis serveri hamma narsani hal qilmaydi?
Javob
Hajm bo'yicha hal qiladi, amallar bo'yicha — balki yo'q. Soniyasiga 125 ming yozuv va qidiruvlar bitta Redis'ning imkoniyatiga yaqinlashadi (rate limiter darsida bitta Redis bilan lokal o'lchov soniyasiga 13 mingga yaqin skript bergan edi, lekin u boshqa sharoitda olingan). Yana ikki sabab: bitta server — bitta uzilish nuqtasi, va xizmat bir nechta shaharda bo'lsa, hammasi bitta joyga yozmaydi. Tabiiy bo'lish kaliti — shahar: Toshkent haydovchilari bitta tugunda, Samarqand — boshqasida. Bitta yo'lovchi faqat o'z shahridagi haydovchini qidiradi.
3. Geohash: makonni satrga aylantirish
3.1 G'oya
Geohash — kenglik va uzunlikni bitta qisqa satrga aylantiradigan usul. Yer yuzi ikkiga bo'linadi: g'arb yoki sharq (bitta bit). Keyin janub yoki shimol (yana bitta bit). Shu tarzda navbat bilan bo'linaveradi. Har 5 bit bitta belgiga aylanadi (32 belgili alifbo). Satr qancha uzun bo'lsa, katak shuncha kichik.
Asosiy xususiyat: umumiy prefiks — yaqinlik. Ikki nuqtaning geohash'i bir xil boshlansa, ular bitta katakda. Demak makon bo'yicha qidiruv oddiy satr prefiksi bo'yicha qidiruvga aylanadi — bu esa oddiy indeks bilan ishlaydi.
3.2 Brauzerda kodlang
const BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz";
function geohash(lat, lon, uzunlik) {
let [latMin, latMax, lonMin, lonMax] = [-90, 90, -180, 180];
let hash = "";
let bit = 0;
let qiymat = 0;
let lonNavbat = true; // juft bitlar — uzunlik (lon)
while (hash.length < uzunlik) {
if (lonNavbat) {
const orta = (lonMin + lonMax) / 2;
if (lon >= orta) { qiymat = qiymat * 2 + 1; lonMin = orta; }
else { qiymat *= 2; lonMax = orta; }
} else {
const orta = (latMin + latMax) / 2;
if (lat >= orta) { qiymat = qiymat * 2 + 1; latMin = orta; }
else { qiymat *= 2; latMax = orta; }
}
lonNavbat = !lonNavbat;
if (++bit === 5) {
hash += BASE32[qiymat];
bit = 0;
qiymat = 0;
}
}
return hash;
}
const joylar = [
["Amir Temur xiyoboni", 41.3111, 69.2797],
["Chorsu bozori", 41.3268, 69.2341],
["yo'lovchi", 41.3115, 69.2801],
["Samarqand, Registon", 39.6547, 66.9758],
];
for (const [nom, lat, lon] of joylar) {
console.log(geohash(lat, lon, 7), nom);
}Konsolda:
tx3702r Amir Temur xiyoboni
tx35p7q Chorsu bozori
tx37088 yo'lovchi
trp9s4f Samarqand, RegistonNatijani o'qiymiz. Yo'lovchi va Amir Temur xiyoboni 50 metrcha masofada — ikkalasi tx370 bilan boshlanadi (5 ta umumiy belgi). Chorsu taxminan 4 km narida — faqat tx3 umumiy. Samarqand esa ikkinchi belgidayoq farq qiladi: tr. Koordinatalar taxminiy, faqat misol uchun olingan.
Katak o'lchami belgilar soniga bog'liq. Elasticsearch hujjatidagi jadval (ekvator uchun) shunday: 5 belgi — taxminan 4.9 km × 4.9 km, 6 belgi — taxminan 1.2 km × 0.6 km, 7 belgi — taxminan 153 m × 152 m. Taksi uchun odatda 6 belgili katak va uning qo'shnilari qidiriladi.
"Ekvator uchun" degan izohga e'tibor bering. Uzunlik gradusi qutbga yaqinlashgan sari qisqaradi. Uning uzunligi kenglikning kosinusiga ko'paytiriladi. Toshkent taxminan 41.3° shimoliy kenglikda, cos(41.3°) ≈ 0.75. Demak bu yerda 6 belgili katakning eni 1.2 × 0.75 ≈ 0.9 km ga tushadi, bo'yi esa o'zgarmaydi (0.6 km). Kataklar "kvadrat" emas va shaharga qarab o'lchami farq qiladi. Shu sabab katak o'lchamini jadvaldan ko'chirib emas, o'z shahringiz uchun hisoblab tanlang.
3.3 Chegara muammosi
Geohash'ning mashhur tuzog'i: ikki nuqta bir-biridan bir metr narida, lekin katak chegarasining ikki tomonida bo'lsa, ularning prefikslari umuman boshqacha bo'lishi mumkin. Prefiks yaqinlikni kafolatlaydi, lekin teskarisi to'g'ri emas: yaqinlik umumiy prefiksni kafolatlamaydi.
Shuning uchun qidiruv bitta katakda emas, katak va uning 8 ta qo'shnisida bajariladi. Keyin topilgan nomzodlar orasida haqiqiy masofa hisoblanadi va saralanadi. Geohash — tez filtr, masofa — aniq tekshiruv. Bu 2-mashqda.
Tekshirib ko'ring: Nega geohash'ni 12 belgigacha (bir necha santimetr) olib, eng aniq katakda qidirmaymiz?
Javob
Katak qancha kichik bo'lsa, unda haydovchi topilish ehtimoli shuncha kam. 150 metrlik katakda ko'pincha hech kim yo'q va qidiruv qo'shnilarga, keyin qo'shnilarning qo'shnilariga kengayib boradi — ko'p so'rov. Katta katakda esa nomzodlar juda ko'p va ularning hammasiga masofa hisoblash kerak. Katak o'lchami — qidiruv soni va nomzodlar soni orasidagi murosali tanlov (trade-off). Zich shahar markazida kichikroq, chekkada kattaroq katak qulay.
3.4 Quadtree va boshqa variantlar
Quadtree — makonni to'rtga bo'luvchi daraxt, lekin bo'linish zichlikka qarab: haydovchi ko'p joyda katak maydalanadi, bo'sh dalada katta qoladi. Geohash'da kataklar hamma joyda bir xil. Quadtree zichlikka yaxshi moslashadi, lekin daraxtni yangilash va bir nechta serverga bo'lish murakkabroq.
Sanoatda boshqa tizimlar ham bor: Uber'da ishlab chiqilgan olti burchakli kataklar tizimi H3 ochiq kutubxona sifatida mavjud, S2 kutubxonasi esa Google'ning geografik ma'lumotlarida sinalgan ierarxik kataklar tizimi. Hammasining g'oyasi bir xil: makonni ierarxik kataklarga bo'lib, katak ID'si bo'yicha indekslash.
4. Joylashuv qayerda yashaydi
4.1 Uch variant
| Variant | Yutuq | Narx |
|---|---|---|
| Postgres + PostGIS | aniq geo so'rovlar, tranzaksiya | soniyasiga 125 ming yozuv — og'ir |
| Redis GEO | xotirada, GEOSEARCH tayyor |
xotira chegarasi, tarix yo'q |
| o'z xotira indeksi | eng tez | o'zingiz yozasiz va bo'lasiz |
PostGIS'ni 27-qismda ko'rgansiz (PostGIS va geo so'rovlar): masofa, radius, indeks. U geo ma'lumotlar uchun ajoyib: manzillar, hududlar, sayohatlar tarixi. Lekin soniyasiga yuz minglab "oxirgi joyni yangila" uchun emas.
Redis'ning geo buyruqlari (GEOADD, GEOSEARCH) ichida geohash'ni ishlatadi va kalit — oddiy tartiblangan to'plam (sorted set). Hujjatga ko'ra kenglik va uzunlik bitlari aralashtirilib, 52 bitli butun songa aylanadi va shu son elementning bali (score) bo'ladi. Radius bo'yicha qidiruvda Redis aynan bizdagi usulni qo'llaydi: markaziy katak va uning atrofidagi 8 ta katak (hujjatdagi "1+8 maydon") ball oraliqlari bilan o'qiladi, keyin doiradan tashqaridagilar tashlanadi. Masofa haversine formulasi bilan hisoblanadi. Yer to'liq shar bo'lmagani uchun xato 0.5 foizgacha yetishi mumkin — taksi uchun bu sezilmaydi. 25 MB lik indeks uchun ideal joy. Narxi: Redis o'chsa, joylashuvlar yo'qoladi. Lekin bu ma'lumot 4 soniyada qayta tiklanadi — haydovchilar baribir yangisini yuboradi. Bu yerda yo'qotish arzon.
4.2 Ikki xil ma'lumot
Butun tizimni bitta rasmda ko'raylik:
flowchart LR
H[haydovchi ilovasi] -->|har 4 s| J[joylashuv servisi]
J --> G[(xotira: geo indeks)]
Y[yo'lovchi ilovasi] --> B[buyurtma servisi]
B -->|yaqinlar| G
B --> M[moslashtirish]
M -->|taklif| H
B --> P[(Postgres: buyurtma, sayohat)]Diagrammada ikki xil ombor bor. Chapdagi geo indeks tez-tez yoziladi va faqat oxirgi holatni biladi. O'ngdagi Postgres kam yoziladi, lekin hamma narsani eslab qoladi. Moslashtirish ikkalasini birlashtiradi: nomzodlarni indeksdan oladi, natijani bazaga yozadi.
Dizayndagi eng muhim qaror — ma'lumotni ikkiga ajratish:
- Jonli joylashuv — xotirada, faqat oxirgi qiymat, eskirishi mumkin.
- Sayohat va buyurtma — Postgres'da, tranzaksiya bilan, to'liq tarix.
Bu CQRS ning bir ko'rinishi: bir xil "haydovchi" haqida ikki model. Yozish oqimi va saqlash talablari shunchalik farq qiladiki, ularni bitta jadvalga qo'yish ikkalasini ham yomonlashtiradi.
4.3 Qachon geo indeks kerak emas
Hamma narsa 500 ming haydovchi farazidan kelib chiqdi. Kichik shaharni olaylik: 2 000 haydovchi, cho'qqida soniyasiga 10 ta buyurtma. Indekssiz, eng sodda yo'l — har buyurtmada hamma haydovchiga masofa hisoblash. Bu 2 000 × 10 = 20 000 ta haversine hisobi soniyasiga. Bitta formula — bir necha trigonometrik amal, oddiy protsessor uchun bu arzimas yuk.
Joylashuv yozuvlari ham kichik: 2 000 / 4 = 500 yozuv soniyasiga. Buni Postgres'ning oddiy jadvali ham ko'taradi, ayniqsa faqat oxirgi joy yangilansa. Demak bunday xizmatda geohash, alohida joylashuv servisi va Redis GEO — tasodifiy murakkablik. To'g'ri qadam: oddiy jadval va to'liq ko'rib chiqish, o'tish sharti esa raqam bilan yoziladi. Masalan, "nomzodni topish p99 bo'yicha 100 ms dan oshsa" yoki "haydovchilar 50 mingdan oshsa".
5. Moslashtirish: bitta buyurtma — bitta haydovchi
Yaqin haydovchilar topildi. Endi buyurtmani bittasiga berish kerak. Ikki yo'lovchi bir paytda bitta haydovchini so'rasa-chi? Bu flash sale darsidagi masalaga o'xshash: cheklangan resurs (bo'sh haydovchi) va parallel talab. Yechim — haydovchi holatini atomik o'zgartirish: "bo'sh bo'lsa band qil". Redis'da bitta skript, Postgres'da shartli UPDATE … WHERE holat = 'bosh'. Bu Taqsimlangan rate limiter darsidagi atomiklik bilan bir xil g'oya.
Haydovchi taklifni qabul qilmasligi ham mumkin. Shuning uchun band qilish muddatli bo'ladi: 15 soniyada javob bo'lmasa, haydovchi bo'shaydi va keyingisi so'raladi. Bu "taklif — qabul" oqimi ham holat mashinasi.
Moslashtirishda "eng yaqin" har doim "eng yaxshi" emas. Daryo yoki temir yo'lning narigi tomonidagi haydovchi to'g'ri chiziqda yaqin, yo'l bo'yicha esa uzoq. Shuning uchun nomzodlar avval to'g'ri chiziq masofasi bilan saralanadi (arzon), keyin eng yaxshi bir nechtasiga xarita xizmatidan yetib kelish vaqti so'raladi (qimmat). Ikki bosqichli filtr — news feed darsidagi "nomzodlar, keyin ranking" g'oyasining o'zi.
Bir nechta buyurtmani birga ko'rib chiqish ham mumkin: har bir soniyada yig'ilgan buyurtmalar va haydovchilar orasida umumiy kutish vaqtini kamaytiradigan juftlash. Bu yaxshiroq natija beradi, lekin har buyurtma bir soniyagacha kutadi va algoritm murakkab. Kichik xizmatda "birinchi kelgan — eng yaqinga" qoidasi yetadi.
6. Avtoto'ldirish
6.1 Trie va top-k
Trie (prefiks daraxti) — har tugun bitta harf, ildizdan tugungacha yo'l — prefiks (Trie (prefiks daraxti)). "tosh" prefiksiga mos so'zlarni topish uchun to'rt qadam pastga tushib, ostidagi butun daraxtni aylanish kerak. Daraxt katta bo'lsa — sekin.
Yechim: har tugunda eng mashhur k ta taklifni oldindan saqlash. So'rov paytida aylanish yo'q — prefiks tuguniga tushib, tayyor ro'yxatni olamiz. Narxi: xotira (har tugunda k ta havola) va yangilash (so'z mashhurligi o'zgarsa, ildizgacha bo'lgan yo'ldagi har tugun yangilanadi). Buni 3-mashqda ikkala usul bilan solishtirasiz.
Trie xotirasini ham hisoblash kerak. Faraz: 10 million noyob so'rov, o'rtacha 15 harf. Eng yomon holatda tugunlar soni 10e6 × 15 = 150 million. Amalda umumiy prefikslar tufayli ancha kam, lekin har tugunda yana k ta havola saqlansa, xotira tez o'sadi. Shuning uchun real tizimlar faqat yetarlicha mashhur so'rovlarni Trie'ga kiritadi va uni bir nechta serverga prefiks bo'yicha bo'ladi ("a–k" bir serverda, "l–z" boshqasida).
Ommaviy tizimlarda takliflar real vaqtda yangilanmaydi. Qidiruv jurnallari yig'iladi, mashhurlik soatiga yoki kuniga bir marta qayta hisoblanadi va yangi Trie quriladi. Bir necha soatlik eskirish takliflar uchun sezilmaydi. Bu yana bitta oxir-oqibat izchillik (eventual consistency) misoli.
6.2 Kechikish budjeti
Har harfga 100 ms dan kam. Ulardan tarmoq va brauzer katta qismini oladi. Server tomonida bir necha millisekund qoladi. Kurs tajribasidagi o'z mashinamiz raqamlari: Redis GET — 1.42 ms, Postgres SELECT 1 — 1.38 ms. Demak har harfga bitta so'rov server tomonda budjetga sig'adi, o'nta ketma-ket so'rov esa yo'q.
Mijoz tomonda ham ikki usul so'rovlarni kamaytiradi. Debounce — foydalanuvchi yozishni 100–200 ms to'xtatmaguncha so'ramaslik. Mijoz keshi — "tosh" uchun javob kelgan bo'lsa, "tosh" ni o'chirib qayta yozganda serverga bormaslik. Ikkalasini TanStack Query va debounce darslarida ko'rgansiz.
6.3 O'zbek matni: apostrof tuzog'i
Bu yerda kanonda haqiqiy topilma bor. vazifalar-api dagi qidiruv (27-qism) Postgres full-text'ning simple konfiguratsiyasini ishlatadi. O'lchovda ma'lum bo'ldi: simple tahlilchisi oddiy apostrofni so'z ajratuvchi deb biladi. "o'qish" so'zi o va qish ga bo'linib ketadi. Boshqa apostrof belgisi (Unicode'dagi U+02BB, tashqi ko'rinishi deyarli bir xil) esa harf hisoblanadi va shu belgi bilan yozilgan so'z bitta bo'lib qoladi.
Kanon yechimi — normallashtirish funksiyasi (uz_normal): hamma apostrof shakllari bitta belgiga, kirill lotinga, urg'uli harflar oddiyga. Bir xil funksiya ham saqlanadigan matnga, ham so'rovga qo'llanadi.
Juft misol:
- Yordam bergan joy: normallashtirish. kirillcha "ўқиш", oddiy apostrofli "o'qish" va U+02BB bilan yozilgani bitta so'zga aylanadi — foydalanuvchi qanday yozsa ham topadi.
- Ongli qabul qilingan narx: funksiya
IMMUTABLEdeb e'lon qilingan, aslida esaunaccentlug'atiga bog'liq. Lug'at yangilansa, indeksni qayta qurish kerak. Kanon buni izohda ochiq yozgan. Avtoto'ldirish Trie'si uchun xulosa: Trie'ga so'z qo'shishdan oldin va har so'rovda xuddi shu normallashtirish.
7. Loyiha qadami: jamoa qidiruvi
jamoa da geo yo'q — bu qismni loyihaga qo'llamaymiz, "maqsad emas" ro'yxatiga ham kiritish shart emas.
Avtoto'ldirish esa bor: vazifa qidiruvi va a'zo tanlash ("@ali" deb yozganda jamoa a'zolari). Qaror:
- Vazifa qidiruvi — kanondagi Postgres full-text va
pg_trgm(xatoli yozuvga chidamli), normallashtirish bilan. Jamoada minglab vazifa — Trie kerak emas. - A'zo tanlash — jamoa 3–15 kishi. Ro'yxat bir marta yuklanadi va brauzerda filtrlanadi. Server so'rovi yo'q.
- Trie va top-k keshi — "qachon kerak" sharti bilan: umumiy (jamoalararo) qidiruv paydo bo'lsa va so'rovlar soniyasiga yuzlab bo'lsa.
Bu tahlil loyihaga kod sifatida kiritilmadi — RFC'dagi "Qidiruv" bandiga qo'shiladi.
7.1 Uch savol
- Yutuq:
jamoaqidiruvi mavjud, testlangan kod bilan ishlaydi; yangi servis yo'q. - Narx:
ILIKEyoki trigram so'rovi Trie'dan sekinroq. Kichik jamoada bu millisekundlar. - Qachon kerak emas: Trie — so'rovlar ko'p va qisqa prefikslar mashhur bo'lganda kerak. Jamoa ichidagi qidiruvda ikkalasi ham yo'q.
8. Hujumchi nigohi
- Soxta joylashuv. Haydovchi ilovasi GPS'ni soxtalashtirib, aeroport yonida "turaman" deydi va qimmat buyurtmalarni oladi. Himoya: tezlik tekshiruvi (bir soniyada 5 km sakrash mumkin emas), qurilma signallari, shubhali naqshlarni kuzatish.
- Yo'lovchi maxfiyligi. Haydovchilar joylashuvi ilovada ko'rinadi, yo'lovchiniki esa faqat tayinlangan haydovchiga. Joylashuv tarixi — shaxsiy ma'lumot, saqlash muddati bilan (Ma'lumot saqlash muddati).
- Takliflar orqali sizish. Avtoto'ldirish boshqa foydalanuvchilarning qidiruvlaridan quriladi. Kimdir o'z ismi va telefonini qidirsa, u boshqalarga taklif bo'lib chiqmasligi kerak. Takliflarga faqat ko'p foydalanuvchi qidirgan so'rovlar kiradi (masalan, kamida 50 xil foydalanuvchi). Bu 31-qismdagi k-anonimlik g'oyasi.
9. Ko'p uchraydigan xatolar
9.1 Har joylashuvni Postgres'ga yozish
125 ming yozuv soniyasiga, har biri tranzaksiya bilan. Jonli joylashuv — xotirada, tarix — kerak bo'lsa, paket bilan.
9.2 Faqat bitta katakda qidirish
Chegara yonidagi haydovchi ko'rinmaydi. Katak va 8 ta qo'shni, keyin aniq masofa.
9.3 Koordinata farqini masofa deb olish
Kenglik va uzunlik gradusi har xil uzunlikda. Masofa haversine formulasi bilan yoki PostGIS orqali.
9.4 Takliflarni har so'rovda hisoblash
Daraxtni har harfda aylanish — sekin. Top-k tugunda tayyor turadi.
9.5 Normallashtirishni unutish
"o'qish" va U+02BB bilan yozilgan xuddi shu so'z har xil bo'lib qoladi. Bir xil funksiya — saqlashda ham, qidiruvda ham.
9.6 Katak o'lchamini ekvator jadvalidan olish
Jadvaldagi "6 belgi — 1.2 km" ekvator uchun. Toshkentda xuddi shu katakning eni taxminan 0.9 km, shimolroqdagi shaharlarda undan ham tor. Radius "1 km atrofida" deb hisoblangan qidiruv kutilgandan kamroq maydonni qamraydi va chekkadagi haydovchi tushib qoladi. Katak o'lchami o'z kengligingiz bilan hisoblanadi, oxirgi saralash esa baribir aniq masofa bilan.
10. Mashqlar
Mashqlar kurs/mashqlar/36/43-geo-qidiruv/ da. 2- va 3-mashq yechimlari Node 24.21.0 da tekshirilgan (biz ishga tushirdik).
1-mashq (oson): bo'shliqlarni to'ldiring
- Kenglik va uzunlikni prefiksli satrga aylantirish usuli —
- Faraz bo'yicha soniyadagi joylashuv yozuvlari, ming —
- Faqat oxirgi joylar saqlansa, geo indeks hajmi, MB —
- Chegara muammosi uchun katak va nechta qo'shni qidiriladi —
- Prefiks daraxti —
Yechim
- geohash — umumiy prefiks — bitta katak.
- 125 —
500e3 / 4; diskka emas, xotiraga. - 25 — 500 ming × 50 bayt; bitta jarayonga sig'adi.
- 8 — atrofdagi kataklar; keyin aniq masofa.
- Trie — har tugunda top-k takliflar keshi.
2-mashq (o'rta): eng yaqin bo'sh haydovchi
masofa(a, b) funksiyasini haversine formulasi bilan yozing (Yer radiusi 6371 km). Keyin engYaqin(yolovchi, haydovchilar, k) — faqat bo'sh (bosh: true) haydovchilardan masofa bo'yicha eng yaqin k tasi. Natijani kilometrda, ikki kasr bilan chiqaring.
Ishora: haversine: h = sin²(Δlat/2) + cos(lat1)·cos(lat2)·sin²(Δlon/2), masofa 2R·asin(√h); gradusni radianga — g × π / 180 (Math obyekti). Saralash — toSorted (Nusxa bilan o'zgartirish).
Yechim
const R = 6371; // Yer radiusi, km
function masofa(a, b) {
const rad = (g) => (g * Math.PI) / 180;
const dLat = rad(b.lat - a.lat);
const dLon = rad(b.lon - a.lon);
const kos = Math.cos(rad(a.lat)) * Math.cos(rad(b.lat));
const h = Math.sin(dLat / 2) ** 2 + kos * Math.sin(dLon / 2) ** 2;
return 2 * R * Math.asin(Math.sqrt(h));
}
function engYaqin(yolovchi, haydovchilar, k) {
return haydovchilar
.filter((h) => h.bosh)
.map((h) => ({ id: h.id, km: masofa(yolovchi, h) }))
.toSorted((x, y) => x.km - y.km)
.slice(0, k);
}
const yolovchi = { lat: 41.3115, lon: 69.2801 };
const haydovchilar = [
{ id: "H1", lat: 41.3111, lon: 69.2797, bosh: true },
{ id: "H2", lat: 41.3268, lon: 69.2341, bosh: true },
{ id: "H3", lat: 41.3150, lon: 69.2900, bosh: false },
{ id: "H4", lat: 41.2995, lon: 69.2401, bosh: true },
];
for (const n of engYaqin(yolovchi, haydovchilar, 2)) {
console.log(n.id, `${n.km.toFixed(2)} km`);
}Konsolda:
H1 0.06 km
H4 3.60 kmH3 yo'lovchiga ikkinchi eng yaqin, lekin u band — filtr uni chiqarib tashladi. H1 atigi 60 metrda. Haqiqiy tizimda bu funksiya hamma haydovchilarga emas, geohash qo'shni kataklaridan kelgan bir necha o'nta nomzodga qo'llanadi. Bundan ham aniqrog'i — yo'l bo'yicha masofa va tirbandlikni hisobga olgan yetib kelish vaqti, bu esa xarita xizmatining ishi.
3-mashq (qiyin): top-k keshli Trie
Trie yozing: har tugunda bolalar (Map), son (so'z tugasa — mashhurligi) va top (eng mashhur k ta so'z). qosh(ildiz, soz, son, k) so'zni qo'shadi va ildizdan shu so'zgacha yo'ldagi har tugunning top ro'yxatini yangilaydi. Solishtirish uchun aylanib(ildiz, prefiks, k) — prefiks tugunidan butun daraxtni aylanib top-k ni hisoblaydi va nechta tugun ko'rilganini qaytaradi. "tosh" prefiksi uchun ikkala natijani chiqaring.
Ishora: tenglikda so'zlar alifbo bo'yicha — a.soz.localeCompare(b.soz). Aylanish — rekursiv funksiya (Rekursiya asoslari).
Yechim
function tugun() {
return { bolalar: new Map(), son: 0, top: [] };
}
function qosh(ildiz, soz, son, k) {
let t = ildiz;
const yol = [ildiz];
for (const h of soz) {
if (!t.bolalar.has(h)) t.bolalar.set(h, tugun());
t = t.bolalar.get(h);
yol.push(t);
}
t.son += son;
for (const n of yol) { // yo'ldagi har tugunning top-k ro'yxati
const r = n.top.filter((x) => x.soz !== soz);
r.push({ soz, son: t.son });
r.sort((a, b) => b.son - a.son || a.soz.localeCompare(b.soz));
n.top = r.slice(0, k);
}
}
function aylanib(ildiz, prefiks, k) {
let t = ildiz;
for (const h of prefiks) {
t = t.bolalar.get(h);
if (!t) return { natija: [], korildi: 0 };
}
const hammasi = [];
let korildi = 0;
const yur = (n, s) => {
korildi++;
if (n.son > 0) hammasi.push({ soz: s, son: n.son });
for (const [h, b] of n.bolalar) yur(b, s + h);
};
yur(t, prefiks);
hammasi.sort((a, b) => b.son - a.son || a.soz.localeCompare(b.soz));
return { natija: hammasi.slice(0, k), korildi };
}
const ildiz = tugun();
const sorovlar = [
["toshkent", 900], ["toshkent metro", 400], ["tosh", 50],
["toshkent havo", 700], ["toyota", 300], ["tovuq sho'rva", 120],
];
for (const [s, n] of sorovlar) qosh(ildiz, s, n, 3);
const p = "tosh";
let t = ildiz;
for (const h of p) t = t.bolalar.get(h);
const a = aylanib(ildiz, p, 3);
console.log("keshdan:", t.top.map((x) => x.soz).join(" | "));
console.log("aylanib:", a.natija.map((x) => x.soz).join(" | "),
`(${a.korildi} tugun)`);Konsolda:
keshdan: toshkent | toshkent havo | toshkent metro
aylanib: toshkent | toshkent havo | toshkent metro (15 tugun)Natijalar bir xil, narxi har xil. Keshdan olishda "tosh" tuguniga to'rt qadam tushildi va tayyor ro'yxat olindi. Aylanishda 15 ta tugun ko'rildi — bu kichik misolda ham. Millionlab so'zli daraxtda qisqa prefiks ("t") ostida millionlab tugun bo'ladi, keshli tugunda esa baribir k ta element. Narx esa qo'shishda to'lanadi: har so'z qo'shilganda yo'ldagi hamma tugun saralanadi. Shuning uchun real tizimlar Trie'ni oflayn, jurnaldan bir marta quradi va so'rov paytida faqat o'qiydi.
11. Real ishda
- Uber, Bolt, Yandex Go kabi xizmatlar — makon indeksi, jonli joylashuv oqimi va moslashtirishning eng katta namunalari. Uber H3 kutubxonasini ochiq manba qilgan.
- Mahalliy loyihalar. Yetkazib berish, kuryer, kafe xaritasi — hammasida "eng yaqin" savoli bor. Ko'p hollarda PostGIS yoki Redis GEO yetadi, o'z indeksini yozish shart emas.
- Qidiruv. Avtoto'ldirish ko'pincha qidiruv tizimlari (Meilisearch, Typesense, Elasticsearch) ichida tayyor keladi (Qidiruv tizimlari qanday ishlaydi). O'zbek matni uchun normallashtirishni baribir o'zingiz sozlaysiz.
- Intervyu. "Uber loyihalang" savolida kutiladigan nuqtalar: joylashuv oqimi va uning hajmi, geohash yoki quadtree, chegara muammosi, atomik moslashtirish. "Typeahead loyihalang" savolida — Trie, top-k keshi, oflayn qurish va debounce.
Xulosa
- Joylashuv — ko'p yoziladigan (125 ming/s), kichik (25 MB) va eskirishi mumkin bo'lgan ma'lumot: u xotirada, sayohatlar esa Postgres'da.
- Geohash makonni prefiksga aylantiradi; chegara muammosi uchun katak va 8 qo'shni, keyin aniq masofa.
- Kichik xizmatda (2 000 haydovchi) geo indeks kerak emas: soniyasiga 20 ming masofa hisobi va 500 yozuvni oddiy jadval ko'taradi; o'tish sharti raqam bilan yoziladi.
- Bitta haydovchini ikki buyurtmaga bermaslik — atomik "bo'sh bo'lsa band qil" va muddatli taklif.
- Avtoto'ldirish — Trie'da top-k oldindan; so'rov paytida aylanish yo'q, qurish esa oflayn.
- O'zbek matnida apostrof va kirill so'zni bo'lib yuboradi: bir xil normallashtirish saqlashda ham, so'rovda ham.
Keyingi dars: Dizayn: e-commerce flash sale va inventar — 10 ming dona tovarga million xaridor: ortiqcha sotishsiz va bazani yiqitmasdan. Bu 36-qismning yakuniy darsi.
Manbalar
- Elasticsearch — Geohash grid aggregation (katak o'lchamlari jadvali): https://www.elastic.co/docs/reference/aggregations/search-aggregations-bucket-geohashgrid-aggregation (tekshirildi, 2026-11)
- Redis — Geospatial (GEOADD, GEOSEARCH): https://redis.io/docs/latest/develop/data-types/geospatial/ (tekshirildi, 2026-11)
- Redis — GEOADD (52 bitli geohash, "1+8 maydon", haversine): https://redis.io/docs/latest/commands/geoadd/ (tekshirildi, 2026-11)
- Uber — H3: https://h3geo.org/ (tekshirildi, 2026-11)
- S2 Geometry: https://s2geometry.io/ (tekshirildi, 2026-11)
- PostGIS — Documentation: https://postgis.net/documentation/ (tekshirildi, 2026-11)
- Kurs tajribasi (IlmHamroh, 2026-11): latency raqamlari (o'z mashinamiz, median),
vazifalar-apiqidiruv migratsiyasi (uz_normal, apostrof topilmasi). Hisob-kitob farazlari va koordinatalar — dars uchun, taxminiy. Mashq yechimlari — biz ishga tushirdik (2026-11-09).
Izohlar · 0
Izoh yozish uchun kiring.