Return to Video

Mi a leggyorsabb módja könyvespolcod betűrendbe szedésének? – Chand John

  • 0:07 - 0:09
    Az egyetemi könyvtárban dolgozol.
  • 0:09 - 0:11
    Napod már a vége felé közeledik,
  • 0:11 - 0:18
    amikor hirtelen befut egy 1280
    különböző könyvből álló szállítmány.
  • 0:18 - 0:22
    A könyveket egy vonalban,
    egymás mellé rakják le,
  • 0:22 - 0:23
    de rendezetlen az egész,
  • 0:23 - 0:27
    és az automatikus
    osztályozó rendszer elromlott.
  • 0:27 - 0:30
    Ha ez még nem lenne elég,
    holnap tanítási nap,
  • 0:30 - 0:32
    így az első dolog reggel az lesz,
  • 0:32 - 0:37
    hogy tanulók tömegei fogják
    ezeket a könyveket keresni.
  • 0:37 - 0:39
    Hogyan tudod őket időben elrendezni?
  • 0:39 - 0:45
    Kezdhetnénk úgy, hogy az egyik végéről
    felveszed az első két könyvet.
  • 0:45 - 0:49
    Ha azok sorrendben vannak,
    hagyd úgy, ahogy voltak.
  • 0:49 - 0:51
    Máskülönben felcseréljük őket.
  • 0:51 - 0:53
    Majd jön a második, harmadik pár,
  • 0:53 - 0:55
    a folyamat ismétlődik.
  • 0:55 - 0:58
    Ezt egészen addig folytatod,
    amíg a sor végére érsz.
  • 0:58 - 1:01
    Lesz, hogy az utolsónak szánt
    könyv kerül a kezedbe,
  • 1:01 - 1:05
    és addig teszed a mögötte
    lévő könyvek után,
  • 1:05 - 1:09
    amíg oda nem érsz,
    ahová az tartozik, a végére.
  • 1:09 - 1:12
    Majd a folyamat újraindul, kezded elölről,
  • 1:12 - 1:16
    hogy az utolsó előtti könyv is
    helyére kerüljön,
  • 1:16 - 1:19
    ez addig megy, míg mindegyik rendben lesz.
  • 1:19 - 1:22
    Ezt a módszert
    buborékrendezésnek hívjuk.
  • 1:22 - 1:24
    Egyszerű, viszont lassú.
  • 1:24 - 1:29
    Első körben 1279-szer veted őket össze,
  • 1:29 - 1:34
    majd 1278-szer és így tovább,
  • 1:34 - 1:39
    összesen 818 560-szor csinálod meg.
  • 1:39 - 1:44
    Ha másodpercenként egyet vetnél össze,
    a folyamat kilenc napig tartana.
  • 1:44 - 1:49
    A másik módszer az lehetne,
    hogy az első két könyvvel kezdenél.
  • 1:49 - 1:54
    Majd hozzávennéd a harmadikat,
    és összevetnéd a második helyen lévővel.
  • 1:54 - 1:57
    Ha azt a második hely illeti meg,
    megcseréled őket,
  • 1:57 - 2:00
    majd az első helyen lévővel veted össze,
  • 2:00 - 2:02
    és ha kell, megint megcseréled.
  • 2:02 - 2:04
    Eddig sorba raktad az első három könyvet.
  • 2:04 - 2:08
    Adj hozzá mindig egy könyvet
    a már rendezettekhez,
  • 2:08 - 2:12
    vesd össze és cseréld meg
    az új könyvet az előtt lévővel,
  • 2:12 - 2:16
    amíg a sorba rakott könyvek között
    helyére nem kerül.
  • 2:16 - 2:18
    Ezt beszúrásos rendezésnek hívjuk.
  • 2:18 - 2:23
    A buborékrendezéssel ellentétben
    itt nem kell minden könyvet összevetni.
  • 2:23 - 2:27
    Arra számíthatunk,
    hogy átlagosan egy-egy könyvet
  • 2:27 - 2:29
    csak az előttük lévők
    felével kell összevetni.
  • 2:29 - 2:32
    Ebben az esetben az összevetések száma
  • 2:32 - 2:36
    409 280 lenne,
  • 2:36 - 2:38
    majdnem öt napig tartana.
  • 2:38 - 2:41
    Még mindig túl sokszor veted őket össze.
  • 2:41 - 2:43
    Íme, egy jobb ötlet:
  • 2:43 - 2:45
    Véletlenszerűen kiveszel egy könyvet.
  • 2:45 - 2:50
    Nevezd el válaszelemnek,
    és vessük össze mindegyik könyvvel.
  • 2:50 - 2:52
    Majd válaszd szét a sort úgy,
  • 2:52 - 2:56
    hogy a válaszelem
    előtti könyvek bal oldalra,
  • 2:56 - 2:59
    az utána következők pedig
    jobb oldalra mennek.
  • 2:59 - 3:00
    Rengeteg időt spóroltál,
  • 3:00 - 3:04
    hogy többet nem veted össze
    a baloldali könyveket
  • 3:04 - 3:07
    a jobboldaliakkal.
  • 3:07 - 3:10
    Most csak a baloldaliakat nézve,
  • 3:10 - 3:13
    újabb válaszelemet vehetsz ki,
  • 3:13 - 3:17
    és elkülönítheted az előtte
    és az utána jövő könyveket.
  • 3:17 - 3:20
    Addig osztasz további
    kisebb válaszelemekre,
  • 3:20 - 3:22
    amíg sok-sok kis válaszfal nem lesz,
  • 3:22 - 3:28
    melyek között más módszerrel,
    pl. beszúrásos rendezéssel rendet teszünk.
  • 3:28 - 3:33
    Egy-egy elválasztáshoz
    1280 összevetés kell.
  • 3:33 - 3:35
    Ha válaszelemeid egyenlő távolságra rakod,
  • 3:35 - 3:41
    ha minden tizedik könyvhöz
    teszünk egy válaszfalat, ami 128 darab,
  • 3:41 - 3:44
    úgy hét kör kell vagy 8960 másodperc.
  • 3:44 - 3:49
    A válaszfalak közötti rendezés
    egyenként 22 másodpercet venne igénybe.
  • 3:49 - 3:52
    Ezzel az ún. gyorsrendezéssel
    egészében véve
  • 3:52 - 3:55
    három órán belül
    sorba lehet rakni a könyveket.
  • 3:55 - 3:56
    De van hátulütője.
  • 3:56 - 4:00
    A válaszelemek aránytalanságával
    nem spórolnál semmit.
  • 4:00 - 4:01
    Szerencsére ez ritkán történik.
  • 4:01 - 4:05
    Ezért van, hogy a gyorsrendezés
    ma az egyik leghatékonyabb,
  • 4:05 - 4:07
    programozók által használt módszer.
  • 4:07 - 4:11
    Például ezzel rakják sorba ár szerint
    online boltok készletét,
  • 4:11 - 4:15
    vagy benzinkutakat listáznak ki
    egy adott helytől
  • 4:15 - 4:16
    távolság szerint.
  • 4:16 - 4:20
    Esetedben a rendezés után
    maradt még időd.
  • 4:20 - 4:23
    Csak egy újabb rázós nap a könyvtárban.
Title:
Mi a leggyorsabb módja könyvespolcod betűrendbe szedésének? – Chand John
Speaker:
Chand John
Description:

A teljes lecke megtekinthető itt: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

Az egyetemi könyvtárban dolgozol. Napod már a vége felé közeledik, amikor hirtelen befut egy 1280 darab könyvből álló szállítmány. A könyvek egyenes vonalban vannak, de rendezetlen az egész, és az automata osztályozó rendszer elromlott. Hogyan tudod leggyorsabban elrendezni őket? Chand John elmondja hogyan, és fényt derít arra is, hogyan segítenek az algoritmusok könyvtárosoknak és keresőmotoroknak az információk elrendezésének meggyorsításában.

Chand John leckéje, az animációt készítette Anton Trofimov.
more » « less
Video Language:
English
Team:
closed TED
Project:
TED-Ed
Duration:
04:39

  • Zsuzsa Viola

    Erre én anno magamtól rájöttem, úgy éreztem, így sokkal gyorsabb. Büszke vagyok magamra! :)

  • Ádám Kósa

    :) Akkor az előadás nem nagyon mondhatott újat.

  • Zsuzsa Viola

    Dehogynem. Nem tudtam, hogy külön nevük van ezeknek a módszereknek. Csak éreztem, hogy ez a módszer gyorsabb, de nem sejtettem, hogy ilyen mértékű a különbség. Egyébként számoknál is ez a helyzet, sorba rendezésnél, iskolákban gyakran volt ez a csökkenő-növekvő sorrendbe helyezés, ott is jól jött, bár igazán lényegessé nagy mennyiségű adatnál válik.

  • Zsuzsa Viola

    Amúgy van egy szerintem még egyszerűbb, ugye, a rövidítés titka a csoportba rendezés, és ezt is csináltam párszor, hogy az első betű alapján a könyv vagy az abc első harmadába esik, vagy a közepébe, vagy a végébe. Így máris van három csoport. Aztán ezeken a csoportokon belül érdemes a nyertes módszert alkalmazni, ez így szerintem még gyorsabb. Vagy még egy csoportosítással az eleje-vége elv szerint, és akkor 6 csoport van, amin belül gyorsan átlátható minden. Ez ugye a könyvek számától is függ, mikor mit célszerű.

  • Zsuzsa Viola

    3:27-nél nem igaz, hogy minden szétválasztáshoz 1280 összehasonlítás kell. Ez csak az elsőre igaz. Innentől a becsléses számítása is rossz. Ez a lényegen nem változtat, de matematikát szerető lelkemet zavarja.

  • Zsuzsa Viola

    Ja, és az én módszeremmel, abc első, második, harmadik harmada nem csak hogy egyszerre három csoportot hoznánk létre, hanem nagy számú könyv esetén jó eséllyel hasonló nagyságú csoportokat, amely gyorsítaná a folyamatot. Persze, lassan a könyvek is olyan elavulttá válnak, mint a hajdani kőtáblák. De ez nem az olvasás megszűnését jelenti, ez csupán egy olvasási módszer elavulása, ezt nem értik sokan.

  • Ádám Kósa

    Nem hinném elavulttá válnak a könyvek. Elég csak körbenézni, az viszont igaz, hogy luxuscikké váltak, de mikor nem voltak azok?

    Amúgy bevallom, én csak valami előadást kerestem, ami az algoritmusokról szólt. Mindenesetre igaz, lehetett belőle tanulni. Van bár sok könyvem, de még nem próbáltam betűrendbe rendezni őket.

  • Csaba Lóki

    Sziasztok! Legyetek szívesek a számokat/személyeket egyégesíteni. Csak átfuttottam, 2:40 környéként biztosan van ilyen. kapsz egy szállítmány könyvet, kiveszünk egyet véletlenszerűen stb.

  • Ádám Kósa

    Sziasztok!

    Úgy nézem, hogy 2:43-53, 3:56, 0:39, 0:45, 1:44-54-nél T/1 helyett lehetne E/2. Erre gondolsz, ugye, Csaba?

  • Csaba Lóki

    Szia, Ádám!
    Igen, erre. Lényeg, hogy egységes legyen. Köszönöm.

  • Zsuzsa Viola

    Ádám, akkor, ha te már megnézted, visszaadom neked, írd át, és aztán visszapasszoljuk.

  • Ádám Kósa

    Kész van.

Hungarian subtitles

Revisions

Our website uses cookies for analysis purposes.