abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
dnes 16:24 | Nová verze

Byla vydána Mageia 5.1. Jedná se o první opravné vydání verze 5, jež vyšla v červnu loňského roku (zprávička). Uživatelům verze 5 nepřináší opravné vydání nic nového, samozřejmě pokud pravidelně aktualizují. Vydání obsahuje všechny aktualizace za posledního téměř půldruhého roku. Mageia 5.1 obsahuje LibreOffice 4.4.7, Linux 4.4.32, KDE4 4.14.5 nebo GNOME 3.14.3.

Ladislav Hagara | Komentářů: 0
dnes 13:42 | Pozvánky

V Praze probíhá konference Internet a Technologie 16.2, volné pokračování jarní konference sdružení CZ.NIC. Konferenci lze sledovat online na YouTube. K dispozici je také archiv předchozích konferencí.

Ladislav Hagara | Komentářů: 0
včera 22:44 | Komunita

Joinup informuje, že Mnichov používá open source groupware Kolab. V srpnu byl dokončen dvouletý přechod na toto řešení. V provozu je asi 60 000 poštovních schránek. Nejenom Kolabu se věnoval Georg Greve ve své přednášce Open Source: the future for the European institutions (SlideShare) na konferenci DIGITEC 2016, jež proběhla v úterý 29. listopadu v Bruselu. Videozáznam přednášek z hlavního sálu je ke zhlédnutí na Livestreamu.

Ladislav Hagara | Komentářů: 12
včera 15:30 | Zajímavý projekt

Společnost Jolla oznámila v příspěvku Case study: Sailfish Watch na svém blogu, že naportovala Sailfish OS na chytré hodinky. Využila a inspirovala se otevřeným operačním systémem pro chytré hodinky AsteroidOS. Použita je knihovna libhybris. Ukázka ovládání hodinek na YouTube.

Ladislav Hagara | Komentářů: 8
včera 14:15 | Nová verze

Byla vydána verze 7.1.0 skriptovacího jazyka PHP používaného zejména k vývoji dynamických webových stránek. Jedná se o první stabilní verzi nejnovější větvě 7.1. Přehled novinek v dokumentaci. Podrobnosti v ChangeLogu. K dispozici je také příručka pro přechod z PHP 7.0.x na PHP 7.1.x.

Ladislav Hagara | Komentářů: 2
včera 12:55 | Nová verze

Google Chrome 55 byl prohlášen za stabilní. Nejnovější stabilní verze 55.0.2883.75 tohoto webového prohlížeče přináší řadu oprav a vylepšení (YouTube). Opraveno bylo také 36 bezpečnostních chyb. Mariusz Mlynski si například vydělal 22 500 dolarů za 3 nahlášené chyby (Universal XSS in Blink).

Ladislav Hagara | Komentářů: 4
včera 11:55 | Pozvánky

Máte rádi svobodný software a hardware nebo se o nich chcete něco dozvědět? Přijďte na 135. sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.

xkucf03 | Komentářů: 0
včera 00:10 | Nová verze

Byla vydána verze 3.2 svobodného systému pro detekci a prevenci průniků a monitorování bezpečnosti počítačových sítí Suricata. Z novinek lze zmínit například podporu protokolů DNP3 a CIP/ENIP, vylepšenou podporu TLS a samozřejmě také aktualizovanou dokumentaci.

Ladislav Hagara | Komentářů: 0
1.12. 21:00 | Nová verze

Byla vydána beta verze Linux Mintu 18.1 s kódovým jménem Serena. Na blogu Linux Mintu jsou hned dvě oznámení. První o vydání Linux Mintu s prostředím MATE a druhé o vydání Linux Mintu s prostředím Cinnamon. Stejným způsobem jsou rozděleny také poznámky k vydání (MATE, Cinnamon) a přehled novinek s náhledy (MATE, Cinnamon). Linux Mint 18.1 bude podporován až do roku 2021.

Ladislav Hagara | Komentářů: 0
1.12. 16:42 | Nová verze

Byl vydán Devuan Jessie 1.0 Beta 2. Jedná se o druhou beta verzi forku Debianu bez systemd představeného v listopadu 2014 (zprávička). První beta verze byla vydána v dubnu letošního roku (zprávička). Jedna z posledních přednášek věnovaných Devuanu proběhla v listopadu na konferenci FSCONS 2016 (YouTube, pdf).

Ladislav Hagara | Komentářů: 0
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 764 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

Dotaz: Jak funguje lexikografické třídění?

26.4.2006 13:20 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Jak funguje lexikografické třídění?
Přečteno: 1122×
Zdravím,

mam programátorský dotaz. Jak funguje lexikografické třídění řetězců? Vzpomínám si, že se to třídí nějak odzadu. Jedná se o adresní třídící algoritmus, ale nějak se nemohu na internetu dopátrat nějaké ukázky. Heslo lexicographics sorting nějak nezabírá. Ve skriptech co mám k dispozici je to jen trochu naznačeno a já bych to potřeboval trošku podrobněji.

Stačil by mi třeba odkaz na nějaký dobře napsaný (rozumněj okomentovaný) zdrojový kód.

Odpovědi

26.4.2006 13:21 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Dotaz směřuje na algoritmus lex. třídění. Zejména pak na variantu s lineární složitostí. Jak je samotné lex. setřídění zadefinováno je mi jasné... díky.
26.4.2006 14:04 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Dotazu moc nerozumím.

Třídící algoritmus můžeš snad volit jaký chceš. Jde akorát o to, co to znamená lexikograficky porovnat dvě slova. Pokud je slovo předponou druhého slova, je lexikograficky menší. Není-li tomu tak, existuje pozice, na které se liší. Vezmi první takovou pozici a porovnej odpovídající znaky. Lexikografické pořadí pak určí uspořádání na těch znacích.

Pokud mají slova neomezenou délku a mohou být jakákoli, nemůžeš nikdy dostat algoritmus s lineární složitostí.
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
26.4.2006 14:19 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Jenže to bych musel použít některý z asociativních třídících algoritmů, které nemají lineární složitost. Jde mi tedy o tento konkrétní algoritmus (tzv. přihrádkové lexikografické třídění).

K té lineární složitosti - skutečně to tak je, čtu to tady ve skriptech od Dr. Snášela. Vtip je v tom, že se třídí odkazy (pointery), ne celé řetězce. Pak je složitost algoritmu skutečně lineární (i když jsou slova neomezené na délce)... O(L + m) kde L je součet všech délek řetězců a m je konstanta.
26.4.2006 14:28 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Pak je složitost algoritmu skutečně lineární (i když jsou slova neomezené na délce)... O(L + m) kde L je součet všech délek řetězců a m je konstanta.

To je klasický příklad zavádějící formulace. Podobným způsobem byste totiž snadno došel k závěru, že každý algoritmus je (přinejhorším) lineární, pouze stačí vhodně zvolit, vůči čemu má být lineární… :-)

26.4.2006 17:11 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
U třídících algoritmů se časová složitost váže k počtu tříděných elementů. V tomto případě je to L, což je součet délek vstupních řetězců. Toto zjednodušení nijak nenarušuje celkový výsledek, a tedy že je to algoritmus s lineární složitostí, protože díky tomu, jak je složitost nadefinována (já použil např. O notaci), je naprosto korektní. Je to jen násobek dvou čísel, platí:

O(n*c) = O(n)

Předpokládáme pochopitelně třídění konečných řetězců.

Dalším prvkem je m, což je konstanta (v tomto případě celkový počet znaků abecedy/univerza). Tato konstanta představuje časovou náročnost finálního zřetězení výsledku tohoto asociativního algoritmu.

Takže dost dobře nechápu, co Vám na mé formulaci nesedí. Podle mě je to v naprostém pořádku.
26.4.2006 17:49 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
U třídících algoritmů se časová složitost váže k počtu tříděných elementů. V tomto případě je to L, což je součet délek vstupních řetězců.

Tak to tedy není. Nezlobte se na mne, ale počet řazených elementů je počet řazených řetězců. Neřadíte znaky, řadíte řetězce (tím spíš, že jste se minule sám zmiňoval o tom, že ve skutečnosti nebudete manipulovat se samotnými řetězci, ale pouze s pointery na ně).

Je to jen násobek dvou čísel, platí: O(n*c) = O(n)
Tak především součin a ne násobek - a to souvisí s tím zamlžováním, o kterém jsem mluvil, ono totiž O(kn) je ve skutečnosti něco podstatně jiného než O(n). Prohlášením nepohodlných kritérií rozsahu problému za konstanty a vhodnou volbou parametru, vůči němuž budeme časovou složitost vyjadřovat, lze prohlásit za lineární jakýkoli algoritmus… Pokud má mít ale takové tvrzení nenulovou informační hodnotu, musí být jasně řečeno, vůči kterému parametru je to lineární, jaké základní operace považujete za konstatní v čase a které parametry rozsahu problému považujete za konstanty.
26.4.2006 18:03 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Prohlásit to můžu, protože jsem předpokládal na začátku, že řetězce budou konečné. Konečné číslo (průměrnou délku řetězce) mohu považovat za konstantu. A když je to konstanta, pak platí toto (vizte "Multiplication by a constant").

Nemohu si pomoci, ale pořád se mi zdá, že stavíte na vodě. Nechci se nějak sáhodlouze dohadovat, rád uznám chybu, ale prostě ji nevidím. Určitě bych asi měl lépe specifikovat, které operace považuji za konstatní v čase, ale to je tak vše. Co považuji za konstantu jsem už napsal...
26.4.2006 18:12 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Já jsem teda měl pocit, že O-čko pochází z analýzy, takže to odkazování bude nejspíše zbytečné :-). Řekl bych, že zmatek do toho zavádíš ty. Vstupy (délky) řetězců sice vždy budou konečné, ale žádnou konstantou omezené nejsou. Přirozených čísel je taky nekonečně mnoho, ale žádné není nekonečné.

Když mluvíš o složitosti algoritmu, musíš říct vůči čemu tu složitost počítáš. Když se mluví o třídících algoritmech, tak pokud není uvedeno jinak, implicitně se myslí počet tříděných prvků (v našem případě řetězců).
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
26.4.2006 18:20 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Ale vždyť já to napsal! L = n*c, tedy O(L*m), což je O(n*c*m). To c není žádná omezující podmínka, ale dá se chápat jako průměrná délka řetezce (přes všechny vstupní řetězce). To je přece předem dané, nic to neomezuje. No a n je přece počet vstupů (řetězců).
26.4.2006 18:24 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Teďka na to koukám, já to vlastně nenapsal, nicméně je zřejmé, že když L je celkový součet délek, tak se to dá rozdělit na tento součin...
26.4.2006 18:58 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Obávám se, že v tom sám nemáte úplně jasno. Původně jste napsal O(L+m), teď tvrdíte že O(Lm), to je docela podstatný rozdíl, nemyslíte? Celý problém je v neoprávněném zanedbávání parametrů, které považujete za nepodstatné, ale které se do časové náročnosti promítají a zanedbat je nemůžete.
26.4.2006 20:15 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Má to být O(n*c+m), to byl překlep.

Bylo nerozumné zde prezentovat složitost algoritmu, aniž bych ho zde popsal. Bohužel ho tu mám rozepsaný na dvě strany a jak jsem se zběžně díval, tak lexicographical sorting je popsaný snad jedině v Knuthově třetím díle jeho ságy, a na tu bohužel odkaz nenaleznu. Tam také bude zřejmě uvedeno (z této knihy skripta čerpají), že je složitost lineární a hlavně proč: O(l_total + m). Asi nemá cenu obhajovat žádné stanovisko, když nejsou známy fakta.
26.4.2006 20:35 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Pořád mi nerozumíte: nejde o to, že bych vám nevěřil, že ten algoritmus má časovou složitost O(nk+m), to vám samozřejmě věřím, to bude mít ostatně nejspíš i algoritmus, který jsem vám tu popsal hned na začátku. Jde čistě o to, že je nesmysl říct bez dalšího upřesnění lineární nebo dokonce tvrdit, že O(kn) je totéž co O(n).
26.4.2006 20:43 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
O algoritmu mohu prohlásit, že má (přinejhorším) lineární složitost vzhledem k nějakému vstupu. U té ekvivalence jsem uvedl, že je to konstanta... Začíná fotbal :-)
26.4.2006 20:46 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Není to konstanta, je to jeden z parametrů, na kterých časová náročnost závisí. Můžete ho sice formálně prohlásit za konstantu, ale to už byste pak klidně mohl udělat i s tím n.
26.4.2006 18:21 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
To o té analýze jsem nějak nepochopil :-D
26.4.2006 19:05 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Mám dojem, že Michal Kubeček vystudoval matematickou analýzu...
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
26.4.2006 14:08 Kníže Ignor | skóre: 19 | blog: stoupa
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
jinak lexikografický se řekne lexicographical
Jestli máš zálohu mého blogu, tak mi ji pošli. Nějak jsem si ho smazal :-)
26.4.2006 14:13 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Možná by mohlo jít pro algoritmus, který se někdy používá pro řazení většího počtu záznamů s relativně malým počtem různých hodnot klíče. Představte si např., že budete mít za úkol seřadit větší počet čtyřciferných čísel. V prvním kroku je roztřídíte do deseti "přihrádek" podle poslední číslice, ve druhé je rozdtřídíte podle předposlední (ale s tím, že procházíte postupně jednotlivé přihrádky, aby v rámci nového rozřazení bylo zachováno pořadí podle poslední číslice), ve třetím podle třetí odzadu atd. Na konci budete mít seznam seřazený správně. Podobný algoritmus by bylo možné aplikovat i na řetězce, za předpokladu, že máte pevně danou jejich maximální délku (a ta není příliš velká). Pouze pak musíte dávat pozor, že zde neřadíte podle posledního (předposledního apod.) znaku, ale podle znaku na konkrétní pozici od začátku řetězce (začínáte od maximální), a na to, že musíte zvlášť zatřídit řetězce, kde příslušný znak není (protože jsou kratší). Doufám, že jsem to moc nezamotal.
26.4.2006 23:13 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Je to tak, tohle je ono. Jinak s tím parametrem máte naprostou pravdu, proč jste to nenapsal přímo? Pořád mi nebylo jasné, proč jste psal, že O(kn) není O(n), ale už chápu - myslel jste případ, kdy k není konstanta, ale (závislý) parametr. Nebylo to z toho zřejmé a já furt omýlal to svoje...
Martin Tůma avatar 27.4.2006 01:02 Martin Tůma | skóre: 38 | blog: RTFM | Praha
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?

Tohle je ale právě princip níže odkazovanýho radix-sortu. Pro třídění řetězců různé délky pak lze využít zobecněného radix-sortu. Popis algoritmu nalezneš v: Hudec: Programovací tecniky, ČVUT 2004. Složitost algoritmu je O(n + L), kde L je součet délek všech řazených slov.

Každý má právo na můj názor!
27.4.2006 14:54 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Pak je divný, proč to tu mám uvedený jako jiný algoritmus (Radix sort je hned v další kapitole). Princip je ale opravdu stejný, pořád jsem tam hledal nějaký rozdíl.
26.4.2006 14:39 Jiří Veselský | skóre: 30 | blog: Jirkovo | Ostrava
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?

Podle toho, co tady doposud zaznělo, předpokládám, že vám jde o skupinu algoritmů, kterým se říká radixsort.

26.4.2006 17:28 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Radixsort jsem neměl na mysli, přesto děkuji.
27.4.2006 14:56 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Prosím ještě o jednu radu ohledně složitosti. Uvažujme jednoduchý algoritmus přihrádkového třídění (ala spočítej výskyty znaků). Pro vstup n (počet znaků) z abecedy o m znacích je jeho časová složitost vzhledem k zařazování do "přihrádek" O(m + n). Doufám, že jsem to napsal správně a nic nechybí ;-)

Dále se praví, že je to algoritmus s lineární složitostí, ale pouze pokud m << n (je výrazně menší než n). Jak může mít algoritmus lineární složitost jen v některých případech? Vždyť i když bude prvků abecedy třeba milion, pořád s přibývajícím n poroste čas lineárně.
27.4.2006 15:13 Lukáš Zapletal | skóre: 42 | blog: lzapův svět | Olomouc
Rozbalit Rozbalit vše Re: Jak funguje lexikografické třídění?
Je jasné, že pokud bude znaků abecedy moc, bude to neefektivní. Ale pořád tam vidím lineární závislost mezi složitostí a počtem vstupujících znaků...

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.