Akár 7-10-szeres gyorsulást ígér a grep új kiadása

Szerszám

A grep karbantartók nevében Jim Meyering ma bejelentette, hogy elérhető a GNU grep 2.17-es kiadása. Figyelemreméltó változás, hogy a felhasználó akár 7-10-szeres gyorsulást is tapasztalhat az eszköz használata közben. A bejelentés szerint az ilyen mérvű gyorsulás nem nevezhető mindennapinak olyan eszköz esetén mint a grep. A változások közt említhető, hogy régóta nyugdíjba készülő "--mmap" opció végleg eltűnt.

Részletek a bejelentésben.

( locsemege v | 2014. 02. 19., sze – 00:24 )


rpm -q grep
grep-2.17-1.fc20.x86_64

Úgy látom, a linkelt bejegyzésben is 2.17 a verziószám, nem pedig 2.7. Javítsd, kérlek!

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

( gee v | 2014. 02. 19., sze – 01:53 )

És ezt vajon hogyan sikerült?

Gondolom nem csak annyi történt, hogy megnyomták az XT elején a turbo gombot :-)

( bucko | 2014. 02. 19., sze – 05:39 )

Ejnye & bejnye!
Figyelmetlenségedet ezennel csúsztatásnak minősítem, max. a bejelentőre háríthatod.
Mintha kimaradt volna a lényeg: in a multibyte locale.
Egy ilyen régi cuccost, mint a grep ilyen mértékben gyorsítani számomra csak annyit tesz, hogy eddig rosszul volt megírva.

(Töprengés: Mi a rossebnek kell gigabájtokat multibájtosan greppelni?)

Jajjdehogyisnem! A nyelv változik. Az "akár" manapság leggyakrabban a reklámokban fordul elő. Reklám == törvényes hazugság. A kör bezárult!

Magyarázat. A grep nem multibyte feldolgozásra készült. Aztán belerakták. Most, hogy belenéztem a commit szövegébe, a (fejlesztőkre) vonatkozó megjegyzésem megerősítést nyert.

Megoldottak egy profilozási problémát és feltalálták a karakterkonverziót. Királyság. Így rosszindulatúan (?) az "akár 7-10-szeres gyorsulást" olvassuk már úgy, hogy "nem mindig olyan lassú". És még CPU függő is. :(

Úgy gondolom, hogy neked továbbra is értelmezési problémád van. Ha nem és valóban technikai, akkor írd meg a GNU grep listára.

A "lassú" ranthoz érdemes lenne egy elérhető grep implementációkat összehasonlító teszted készítened, mert az állításaid így csak lógnak a levegőben. Én egy ilyen teszttel felszerelve írnék a helyedben a fejlesztőknek.

--
trey @ gépház

Azért nem ártana, ha kifejtenéd. Pl. "Szerintem te ÍGY érted, de ÚGY kellene értelmezn!" Hátha akkor érteném én is mire gondolsz.

Beszélgessünk!
- Lassú a Trabantod! A helyedben nem hencegnék vele.
- Dehogy lassú! Mutasd a Ferrarid!
Ebből a szövegből
- Nem következik, hogy gyors a Trabantod.
- Igazam van, mert tényleg lassú.
- Nincs Ferrarim, de akkor is lassú.
- Nem kell Ferrarit vennem, hogy igazam legyen.
- Ferrari nélkül is el tudom dönteni, hogy a Trabant lassú.

Egyik topicban állítottam, hogy big endian processzoron sokkal gyorsabb karakteres feldolgozásokat lehet írni. Ott és akkor én voltam a hülye és nem értettem semmihez. Itt viszont egy NAGY GREP FEJLESZTŐ írja, hogy 3-7x gyorsabb a CPU függvényében. Hogy is van ez?

That allows the matcher to search in buffer mode, rather than having to extract/case-convert/search each line separately. - Ezt a technikát úgy 15 évvel ezelőtt "találtam fel". (Először a világon, egyedül, elengedett kézzel! :))) A feldolgozási idő 1/24 arányban csökkent. Aprócska különbség, hogy a feledat megoldásához nem volt elég az "akár", mert véges idő állt rendelkezésre. Pontosabban az addig 100k rekordot 2 óra alatt feldolgozó programot kellett átalakítani 1,2M rekord feldolgozására úgy, hogy akár 4-5 futás is beleférjen a 24 órába.

Szóval hidd el, tudom miről beszélek, annak ellenére, hogy nem ötletelek a grep levlistán! És nem is tenném, mert nem grep-et szoktam írni, hanem jóval komplexebb feldolgozásokat.

Ez egy igazan kulturalt hozzaszolas volt ismet!
Neha azon gongonkodom hogy mi a f@sznak jovok a hup-ra, mert tisztan latszik hogy meg az uzemeltetoknek is komoly mentalis problemajuk van otthon!

Ha teged nem erdekel hogy O mit gondol, akkor ot miert kellene hogy erdekelje hogy te mit gondolsz???
Komolyan mondom ez nem is igaz.

Blikk/Borsonline == hup!

Jópofi vagy, csak morzézni nem tudsz. :)
bit 0: van jel - nincs jel
bit 1: rövid - hosszú
00 = rövid szünet (két jel között)
01 = rövid jel (pont)
10 = hosszú szünet (két betű között)
11 = hosszú jel(vonás)
SOS=01 00 01 00 01 10 11 00 11 00 11 10 01 00 01 00 01
NULL érték nincs, mert nem storage, hanem stream ;)

"Egy ilyen régi cuccost, mint a grep ilyen mértékben gyorsítani számomra csak annyit tesz, hogy eddig rosszul volt megírva."

... meglehet, hogy az egyik fejlesztőnek február elején a tyúkszemére esett egy "Algoritmusok és adatszerkezetek" című könyv :D

-fs-
Az olyan tárgyakat, amik képesek az mc futtatására, munkaeszköznek nevezzük.
/usr/lib/libasound.so --gágágágá --lilaliba

Egy nagy büdös francokat erős. Van egy halom jól-rosszul használható izé, ami többé-kevésbé használható módon megpróbálja elmaszatolni az alapproblémát, mégpedig azt, hogy legyen valami jól definiált interface az egyes rendszerek között és ezzel egy 40 éves agysérülést okozva az IT-nak. Aztán ezt azzal próbálják bemagyarázni, hogy "de a juniksz teksztben erős!!!4444"

Aki dolgozott már különféle nyelvterületekről származó adatokat, az érti ezt a problémát. A beszűkültebb meg elrendezi annyival, hogy a hülye gyökér miért nem ezt vagy azt a formátumot használta.

Juniksz teksztben erős? Aham, próbálj meg mondjuk egy TSV-t egy dátumot tartalmazó oszlop alapján rendezni.

----------------
Lvl86 Troll, "hobbifejlesztő" - Think Wishfully™

Ha a dátum mező normális formátumú, akkor nem nehéz a feladat - át kell forgatni %Y%m%d formára, aztán mehet a numerikus sort - az más kérdés, hogy a legtöbb nyelvi környezetben valami idióta okból nem a nagy - kisebb - még kisebb egység a normál sorrend a dátumnál...

Szerencsére a modern IT régóta megtalálta erre a megoldást! Az egészet betöltöd egy jól hordozható formátumba. Javaslom a COleDateTime VARIANT ojjektumot. Ezt OLEDB és java segítségével áttöltheted egy egy Oracle adatbázisba. Utána már csak egy select.

Alternatív megoldás lehet, hogy tisztában vagy a dátum, az nls, a bájt mibenlétével, és - csakis az előbbiek után - ha még mindig valami nem világos, akkor man sort.

Igaz, egy amerikai nő azért perelt, mert a mikrójának a használati utasítása nem említette, hogy macskát nem szabad szárítani benne. Nos, man sort sem írja le, hogy a vegyes kínai és magyar szavakat miként tudod ciril abc szerint rendezni. Szerintem, ha már rájöttél erre a hiányosságra - pereljél!

Juniksz teksztben erős? Aham, próbálj meg mondjuk egy TSV-t egy dátumot tartalmazó oszlop alapján rendezni.
Nem fogom "megpróbálni"! Több mint 20 éve csinálom, sok-sok millió adattsorral. Nekem működik.

:)
Ez nem karakteres feldolgozás. A való világban ezt szinoníma és egyéb szótárakkal oldják meg. Ilyenről a grep esetén szó sincs.
Pl. a "magyar" karakterkészletben szerepel az ä, Ä és a ß. Az első összehasonlítás (rendezés) szempontjából megfelel a magyar nyelvtan szerinti a-á egyezésnek. A második pedig ss kettős karakterré írandó át, mivel a németek már régen "betiltották". Rendezés szempontjából megfelel az s karakternek. Ugyanakkor az 1 byte hosszú kódkészletnél símán át kell írni s karakterré. Ez a kényszer.
Viszont a több karakterből álló hangok esetén sok esetben szótárakat kell használni - így az inkább nyelvészkedés.

Szerintem a google-t. :D
Azért írtam idézőjelbe, mert a pontos jogi és akadémiai kontextust nem ismerem. A forrás a wiki helyett apám, aki anyanyelvi szint felett beszéli a németet(is).
Valójában a tudathasadáshoz elegendő a http://www.fussball.de/ oldalra ellátogatni. Kis papírkávál 2 oszlopba: fussball jobbra vonás, fußball balra vonás, osztán a statisztika győz. :)

Öööö... miért is? Az egyetlen negatív, lekezelő stílusú hozzászólás. Azt indokolja, hogy miért nem lehet/érdemes megcsinálni valamit, ami pár sor kód, és jelentős gyorsuláshoz vezet. Remélem ezentúl a mostani gyorsító patch-eket is visszacsinálod a magad által fordított grep-ben hogy újra lassabb legyen! :)

OK, akkor árnyaljuk a képet. Az ott vitatott nagy gyorsítás azokra az esetekre vonatkozik, amikor a grep nem reguláris kifejezést keres, hanem egy fix string-et. Ezekre az esetekre meg ott van az fgrep.

Szóval adott kettő, már létező tool, az egyik a grep ami reguláris kifejezéseket keres, és a másik az fgrep ami fix sztringeket. Most pedig azt mondják az emberek abban a szálban, hogy optimalizáljuk a grep-et azokra az esetekre amikor fix sztringeket keresünk, méghozzá úgy hogy a fix sztringet árírjuk egy olyan reguláris kifejezésre amin a grep gyorsabb. Van ennek értelme? Miért nem hívjuk meg az fgrep-et akkor már? A legtöbb grep implementációban úgyis közös a bináris.

Valamint ez egy kicsit szembemegy az eredeti filozófiával miszerint az grep és az fgrep különböző dolgokat csinálnak.

Egyedül akkor van haszna, ha a mintát nem lehet előre tudni, és lehet fix sztring is, vagy reguláris kifejezés, de még ekkor is inkább ellenőrizni kellene, hogy mi a minta és aztán grep-et vagy fgrep-et hívni, ha már optimalizálunk.

> Most pedig azt mondják az emberek abban a szálban, hogy optimalizáljuk a grep-et azokra az esetekre amikor fix sztringeket keresünk, méghozzá úgy hogy a fix sztringet árírjuk egy olyan reguláris kifejezésre amin a grep gyorsabb. Van ennek értelme? Miért nem hívjuk meg az fgrep-et akkor már?

Emlékeim szerint épp arról szól a thread, hogy akkor az fgrep-et hívjuk meg, vagyis használjuk a már létező gyorsabb algoritmust.

Tök mindegy, hogy a sima grep mellett milyen más progik is vannak. Ha a grep azt ígéri, hogy valamit megtesz, és azt meg is teszi, és pár sor plusz kód segítségével azt sokkal gyorsabban tudja megtenni (rájön hogy hoppá a már létező fgrep algoritmus is jó), akkor tegye már meg!

> Egyedül akkor van haszna, ha a mintát nem lehet előre tudni, és lehet fix sztring is

Előfordulhat szkriptben is, hogy nem tudni előre, a minta tartalmaz-e speciális karaktereket. De szerintem legalább ennyire jogos érv az is, hogy ha én kézzel gépelek be egy parancsot, akkor ne nekem kézzel kelljen azt az f betűt is odabiggyesztenem (esetleg a parancs végiggépelése után, mert akkor jut eszembe hogy sima szóra kerestem rá), ne az én felelősségem legyen hogy megmondjam a gépnek hogy sokkal gyorsabb legyen, hanem legyen ő magától sokkal gyorsabb.

Emlékeim szerint épp arról szól a thread, hogy akkor az fgrep-et hívjuk meg, vagyis használjuk a már létező gyorsabb algoritmust.

Nem arról szól. Az eredeti patch sem arról szól egyébként, nem arról, hogy a 'fix' mintát átírja arra, hogy '[fF][iI][xX]' ha a user használja a -i kapcsolót. Ezt egyébként nem is minden locale-ben lehet megtenni.
http://git.savannah.gnu.org/gitweb/?p=grep.git;a=commit;h=97318f5e59a1e…

Drepper azt mondja, hogy ehelyett a hekkelés helyett használjuk az fgrep-et. Ízlés dolga, én nem engedtem volna be ezt a kommitot, mert szerintem hekkelés, és minden ilyen speciális eset csak elbonyolítja a kódot. De nem én tartom karban a grepet persze.

Egyébként szerintem bikeshed az egész, kb. kurvára mindegy.

ne az én felelősségem legyen hogy megmondjam a gépnek hogy sokkal gyorsabb legyen,

Igen, mert te a felhasználó szempontjából nézed a dolgot. Drepper meg a fejlesztő szempontjából, vagyis nem akarja szétcseszni a kódot csak azért, mert egy ritka use-case, amire van is megoldás (fgrep), gyorsabb lesz.

Aha, tehát az fgrep egy visszafelé kompatibilitás miatt meghagyott szörnyűség, s illenék grep -F parancsot használni. Amúgy épp ezt szoktam tenni. Lehet, korábban olvastam ezt a manualban, ezt csináltam, csak már elfelejtettem, hogy miért. :)

tr '[:lower:]' '[:upper:]' <<<locsemege
LOCSEMEGE

Szerintem másról beszélünk. Te a '[fF][iI][xX]' kapcsán a két új patch egyikéről. Én egy régi bugról, ahol nincs is patch, és a 2. komment leírja hogy már van speciális mágia - ha van, akkor ugyan miért lenne elítélendő ha a sima grep is mágiázna és fgrep-re váltana? -, valamint a 4. komment vége javasolja is hogy ezt kéne csinálni. Pár plusz kódsor és hirtelen egy bizonyos use-case sokkal gyorsabb lenne. Mire Drepper bácsi azt mondja hogy LFS.

> Igen, mert te a felhasználó szempontjából nézed a dolgot. Drepper meg a fejlesztő szempontjából, vagyis nem akarja szétcseszni a kódot csak azért, mert egy ritka use-case, amire van is megoldás (fgrep), gyorsabb lesz.

Nem hinném, hogy ritka use-case (sőt, szerintem kifejezetten nem), a kódot nem szétcseszni kéne hanem egy jól elkülönített, átlátható, dokumentált, egyszerű kódrészlet kezelné a speciális esetet (valszeg már eleve rakat speciális eset van, nem ez lenne az első speckó "hackelés").

Teljesen igazad van abban, hogy én fejlesztőként is a felhasználó szempontjából nézem a dolgokat, köszönöm, jól esett hogy észrevetted :), ez valóban így van, büszke vagyok rá, és szerintem minden fejlesztőnek el kellene jutnia idáig, sőt ha valamit, akkor ezt kellene nagyon erősen hangsúlyozni mindenféle programozó suliban/könyvben.

Szerintem másról beszélünk

Lehet.

Teljesen igazad van abban, hogy én fejlesztőként is a felhasználó szempontjából nézem a dolgokat, köszönöm, jól esett hogy észrevetted :), ez valóban így van, büszke vagyok rá, és szerintem minden fejlesztőnek el kellene jutnia idáig, sőt ha valamit, akkor ezt kellene nagyon erősen hangsúlyozni mindenféle programozó suliban/könyvben.

A felhasználó általában nem tudja, hogy az amit akar az milyen következményekkel jár a távolabbi jövőre nézni, ami a kód karbantarthatóságát illeti. A fejlesztő felelőssége nem szétcseszni a kódot.

> Abban szerintem egyetérthetünk, hogy általánosságban optimalizációkkal simán szét lehet cseszni a kódot, sőt, azokkal lehet csak igazán.

Ez egy túl általános megfogalmazás ahhoz, hogy egyet tudjak érteni vele. Gány kódolással lehet szétcseszni a kódot, és lehet optimalizálni elegánsan, tisztán, áttekinthetően. Nem a kód szépségéért írunk kódot, hanem a megoldandó problémának alárendelve.

Ebben a konkrét esetben én úgy látom azért, hogy a helyzet a következő. Van egy nagy kódbázis, aki egyébként kifele kb mindenhol azt mutogatja magáról, hogy konzisztens. Legalábbis nekem az, hogy van grep -F, grep -E, meg egrep és fgrep, amik ugyanarra a grep binárisra mutatnak, bizony azt kommunikálja, hogy kb tökmindegy, hogyan használom, mert ugyanaz a progi. Láttam már párszor a manját, talán rémlik is valami magyarázkodás, de hogy én spec. tuti betudtam annak, hogy ja, 75ben még biztos ez volt sysv5-ön, backward compatibility haleluja. Namost ha ebben a kódban, ami belül egyébként is kénytelen támaszkodni arra, hogy algoritmusok között válogasson belül (a fenti kezelése miatt minimum, de mint a fentebbi beszélgetés mutatja, vannak még ilyen esetek), és nincs egy olyan, jól elhatárolható kódrészlet, ami ezeket a válogatásokat tartja egy helyen, akkor azt a kódot egy ilyennel már nem lehet szétcseszni, mert már szét van cseszve :) És lehet, hogy amikor a régi izéket egyesítették, akkor illett volna refaktorálni, nem mutogatni a buta userre most :)

Szerintem a fix sztring szűrése grep-pel (és nem fgrep-pel!) egyáltalán nem ritka use-case. Szerintem ez a tipikus parancssoros használat, simán 50% felett. De a figyelmetlen rendszergazdák (a többség) simán script-ben is ezt hívja még biztosan fix szűrő-sztring esetén is. A kód elbonyolítása azért elég vicces kifogás.

if ( is_regexp_fix(regex) )
{
     algo = FIX_FILTER;
}
else
{
     algo = REGEX_FILTER;
}

Woááá, nagyon bonyolult és átláthatatlan... Az igaz, hogy lehet átláthatatlanul is megírni, mint ezt a Hello world!-öt.

Szerintem a fix sztring szűrése grep-pel (és nem fgrep-pel!) egyáltalán nem ritka use-case

Még az is kell, hogy legyen -i kapcsoló, meg le kell ellenőrizni, hogy milyen locale-ben vagy. És nem két külön algoritmust kell meghívni, hanem újra kell írni a mintát. Megnézted te azt a patchet?

http://git.savannah.gnu.org/gitweb/?p=grep.git;a=commit;h=97318f5e59a1e…

Woááá, nagyon bonyolult és átláthatatlan.

Ja, tényleg. Nem is tudtam, hogy ilyen egyszerű a grep forráskódja.

Nem néztem meg. Szép forráskódot írni lehetséges. Láttam már olyanokat, akik ilyet tudnak. Nem sokat, de láttam. Nem állítom, hogy a patch egyszerű. De azt igen, hogy meg lehet úgy írni ezt a funkciót, hogy a forrás átlátható marad. Még akkor is, ha a locale-t és a -i kapcsolót is le kell ellenőrizni. Én is fejlesztek szoftvert, és nem fogadom el egyik kollégámtól se, hogy azért legyen rossz a felhasználónak (figyeljen oda ilyen -F kapcsolókra), hogy a fejlesztőnek jó legyen. Nem tudom, hogy mennyire fogalmazzak erősen, ezért ide írom kétféleképpen:
1) Nem szerencsés hozzáállás a fejlesztő részéről, ha elvárja a felhasználótól, hogy az optimális felhasználás érdekében olvasson kézikönyv oldalakat és figyeljen a használatnál, ha ő is megcsinálhatja a szoftverben ennek a megoldását.
2) Az ilyen fejlesztő lusta, tohonya disznó és menjen inkább céllövöldésnek. Az ilyeneket fogja először falhoz állítani a forradalom.

A fejlesztők vannak a felhasználókért. Szerintem.

Csináltam egy kávét és közben jól felidegesítettem magam ezen a hozzáálláson. A grep fejlesztői évente 50x látják ezt a kódrészletet. A felhasználók naponta világ szinten 10^8 alkalommal használják rosszul (-F nélkül). Ez _nagyon_ gáz.

A barátaimnak és a kollégáimnak rendszeresen mondom: Azért, hogy a fejlesztőnek jobb legyen, a gyakran használt programoknak nem kellene sokkal több energiát elfogyasztani, mint ami indokolt. Belegondoltatok már, hogy ha egy lusta fejlesztő ír egy rossz algoritmust, indokolatlanul használ egy újabb absztrakciós szintet, nem oldja meg, hogy a lusta, buta felhasználók helyett a program gondolkodjon (mint itt), akkor egy általánosan használt programnál (mint itt) ez napi szinten irdatlan mennyiségű elektromos áramot használ el világszinten! Egy-egy tehetségtele vagy lusta fejlesztő és fák százezrei halnak meg hiába, több gramm urán ég ki feleslegesen! Nem viccelek. Szeretem az optimalizálást. Írjunk jó programokat!

Azt hittem a .sig-emet linkeled a Hello world okan :-) 


#!/bin/ksh
Z='21N16I25C25E30, 40M30E33E25T15U!';IFS=' ABCDEFGHIJKLMNOPQRSTUVWXYZ ';
set -- $Z;for i;{ [[ $i = ? ]]&&print $i&&break;[[ $i = ??? ]]&&j=$i&&i=${i%?};
typeset -i40 i=8#$i;print -n ${i#???};[[ "$j" = ??? ]]&&print -n "${j#??} "&&j=;
typeset +i i;};IFS=' 0123456789 ';set -- $Z;for i;{ [[ $i = , ]]&&i=2;
[[ $i = ?? ]]||typeset -l i;j="$j $i";typeset +l i;};print "$j"

Az olvashatosag okan tordelve, amugy az egesz egy (illetve a she-bangen kivul egy) sor.

> Szóval adott kettő, már létező tool, az egyik a grep ami reguláris kifejezéseket keres, és a másik az fgrep ami fix sztringeket.

> A legtöbb grep implementációban úgyis közös a bináris. 


$ ls -l /bin/fgrep
lrwxrwxrwx 1 root root 4 Dec  7  2010 /bin/fgrep -> grep
$ lsb_release -d
Description:    CentOS release 5.10 (Final)

( uid_16313 | 2014. 02. 19., sze – 14:22 )

Èn mindig örülök annak, ha nem új feature-ökröl szól a hír, hanem optimalizációról.

--
robyboy

"Gondolkozni nehéz, ezért legtöbben ítélnek." - Márai Sándor

( wince | 2014. 02. 19., sze – 14:57 )

Ez konkrétan milyen folyamatot fog felgyorsítani? Boot?

Biztosan nem ismered az "okoskodo" szó jelentését. Kérlek nézz utána az értelmező szótárban! (A helyes írásmódjának is!)
Ez a bumeráng bosszúja volt. :)

Szóval körmönfontan alapos és tényfeltáró hozzászólásod alapján nem derül ki miben okoskodok. Kevésbé szakmai fóumokon, ha a cikk tévedést - itt értelemzavaró elírást tartalmaz - másképp működik. Ott csak annnyit írnak, hogy köszi, bocsi, javítottam. Itt meg kiderült, hogy én nem értettem. Biztosan ez lehet a huszárkodás. :)

A cikk semmilyen elírást sem tartalmaz. Szerinted tartalmaz elírást. A cikk max. nem fejti részletesen a témát, hanem egy linket utat az eredeti bejelentésre - itt ez ugyanis nem csak szokás, hanem követelmény (mármint hogy legyen link a forrásra, ellentétben sok "szakmai" oldallal) -, amely linken az olvasó elolvassa a részleteket. Ja, új vagy errefelé, ezért neked elmondom, hogy én feltételezem, hogy _mindig_ elolvassa mindenki a linkelt cikkeket.

És valóban, amit művelsz, az szerintem szőrszálhasogatás. Ezért is skippelem. További jó rugózást.

--
trey @ gépház

( mrev | 2014. 02. 19., sze – 17:23 )

"a felhasználó akár 7-10-szeres gyorsulást is tapasztalhat az eszköz használata közben"

Matematikus szemmel nézve az ilyen állítás semmit sem jelent. Leírom, miért.

Bármilyen kombinatorikus algoritmuson könnyen lehet olyan "javítást" eszközölni, amire elmondható a fentihez hasonló állítás. Vegyük pl. a qsort javítását, a "javított" algoritmus a következő:

1) Ellenőrzöm, hogy a sorozat rendezett-e, ha eleve rendezett, akkor kész.

2) Ha nem eleve rendezett, akkor alkalmazom a qsortot.

Namost ez egyrészt minden sorozatra jól működik, másrészt _létezik_ olyan eset, amikor gyorsabb a qsortnál. Ha mondjuk feltételezem, hogy a sorozat egyszerű végigolvasása 10-szer gyorsabb, mint a tényleges rendezés, akkor igaz az állítás, miszerint a felhasználó akár 10-szeres gyorsulást is tapasztalhat.

Tehát az "akár" szó esetünkben ugyanazzal a módosító értelemmel bír, mint amit a reklámokból ismerünk (akár 75%-kal kellemesebb érzést biztosító egészségügyi papír), hogy annyira azért nem kell komolyan hinni a dologban. Ezzel szemben egy olyan állítás, hogy az algoritmus _átlagosan_ 1%-kal javult, az súlyos dolog volna.
--
ulysses.co.hu

Átlagfelhasználó szemmel az ilyen állítás sokat ér. Leírom, hogy miért. A mai világban a szoftver egy olyan kalap szar valami, aminél már annak is örül az ember, ha a következő verzió nem lett rosszabb, vagy lassabb mint az előző volt. Ha pedig azt olvassa az átlagfelhasználó, hogy a szoftver _akár_ gyorsabb is _lehet_, akkor örül, mint a majom a farkának.

Sajnos olyan világban élünk, hogy már ennek is lehet örülni.

--
trey @ gépház

( egmont | 2014. 02. 22., szo – 10:36 )

* Noteworthy changes in release 2.18 (2014-02-20) [stable]

** Bug fixes

grep no longer mishandles patterns like [^^-~] in unibyte locales.
[bug introduced in grep-2.8]

grep -i in a multibyte, non-UTF8 locale could be up to 200 times slower
than in 2.16. [bug introduced in grep-2.17]