Nagy számok közelről · 3 perc olvasás
Egymilliárd rekord között harminc vizsgálat is elég lehet
Egymilliárd rendezett rekord között egy adott kulcsot legfeljebb harminc rekord megvizsgálásával is meg lehet találni, vagy ki lehet zárni a jelenlétét. A gyorsaság ára a megfelelő adatszerkezet. Egy rendezetlen lista vagy egy lassú háttértár egészen más gyakorlati eredményt ad.
Ebben a cikkben
A középső elem után a tartomány fele elhagyható
A saját modellben különböző egész kulcsok szerint növekvő sorrendbe rendezett tömbünk van. Bármely sorszámú rekordot közvetlenül elérhetünk. Megnézzük a tartomány középső elemét: ha azonos a keresett kulccsal, készen vagyunk; ha kisebb, a jobb oldali részben folytatjuk; ha nagyobb, a bal oldalin. Az elhagyott félben a rendezettség miatt biztosan nincs a keresett kulcs.
Egy rekordvizsgálatba most a középső kulcs elővételét és a keresett értékkel való összevetését értjük. Egy konkrét program ehhez több processzorműveletet vagy feltételvizsgálatot használhat. A harmincas szám tehát az algoritmus lépéseit számolja; a másodpercben mért futási időhöz további adatok kellenek.
Ezerszer több adat tíz további lépést kér
A szokásos középsőelem-vizsgálat legrosszabb esetében n elemhez ⌊log₂ n⌋ + 1 lépés kell, ha n legalább 1. Egymilliónál ez 20, egymilliárdnál 30. A közelítést a kettes hatványok is mutatják: 2¹⁹ = 524 288, 2²⁰ = 1 048 576; 2²⁹ = 536 870 912, 2³⁰ = 1 073 741 824.
A pontos lépéshatárhoz az utolsó elem vizsgálata is hozzátartozik. Például pontosan 2²⁰ elemes tömbnél a szokásos algoritmus legrosszabb esetben 21 vizsgálatot végez, ezért a logaritmust nem érdemes gondolkodás nélkül lefelé kerekíteni. A milliós és milliárdos példánkban a fenti 20 és 30 helyes felső határ.
Mit nyerünk az egyesével haladáshoz képest?
Ha a milliárd rekord rendezetlen, és további indexünk nincs, a legegyszerűbb keresés egyesével végignézi őket. Hiányzó kulcsnál mind az egymilliárdot ellenőrzi. Ha a keresett elem biztosan szerepel, és mindegyik pozíció azonos valószínű, az átlagos vizsgálatszám (1 000 000 000 + 1) / 2 = 500 000 000,5.
A rendezett állapotot viszont elő kell állítani és karban kell tartani. Egyetlen alkalmi keresés kedvéért egy nagy lista teljes rendezése sokkal több munka lehet, mint az egyszeri végigolvasás. Sok ismétlődő keresésnél a rendezés vagy az index felépítésének költsége megoszlik a lekérdezések között. A feladatok egész sorát kell mérlegelni.
A gyors keresés nem tesz minden műveletet harminclépésessé
Új elem helyét bináris kereséssel gyorsan megtalálhatjuk egy rendezett tömbben, de a beillesztéshez sok későbbi elemet el kell tolni. A Python bisect dokumentációja külön hangsúlyozza a logaritmikus helykeresés és a lineáris beszúrás eltérő költségét. Folyamatosan változó adatokhoz ezért más adatszerkezet is indokolt lehet.
Ha egy teljes értéktartomány összes rekordját kérjük, a tartomány elejét és végét gyorsan megtalálhatjuk, de a találatokat még ki is kell olvasni. Egymillió visszaadott rekord egymillió rekordnyi kimenetet jelent. Ugyanezért egy gyors kulcskeresésből a teljes riport vagy export sebességére sem lehet közvetlenül következtetni.
Mit kell ellenőrizni a nagy ígéret előtt?
Nézd meg, valóban a keresett kulcs szerint rendezettek-e az adatok, és ugyanazt az összehasonlítási szabályt használja-e a keresés. Szövegeknél például a kis- és nagybetű, illetve a rendezési szabály is számíthat. Egyetlen rosszul elhelyezett rekord is megsértheti azt a feltételt, amely alapján a keresés fél tartományokat hagy el.
A közvetlen hozzáférés szintén feltétel. Láncolt listán a középső elemhez eljutás önmagában sok lépés, háttértáron a szétszórt olvasások késleltetése lehet jelentős. A harminc vizsgálat ezért pontos algoritmikus állítás a leírt tömbre. Használható teljesítménybecsléssé az adatméret, az adatszerkezet és a hozzáférési költség együtt teszi.
A példák és a források
A számpéldák saját, szemléltető feladatok; a megadott feltételezésekből és képletekből újraszámolhatók. Valós vállalkozásra, országos statisztikára vagy jövőbeli eredményre nem vonatkoznak.
Forrásellenőrzés: 2026-11-09. A hivatkozások a fogalmakat és a módszert támasztják alá; a példaszámítások a cikk részei.
Négy kérdés a cikkhez
A válaszokból kiderül, melyik összefüggést érted már, és melyik részt érdemes újraolvasnod. A válaszokat és a pontszámot nem mentjük.
