bináris minta keresése

C/C++

Üdvözletem!

Gyakorlásképp írok magamnak egy programot és elakadtam az egyik függvény írásakkor:
egy bináris adathalmazban megkeresi a kívánt mintát és visszaköpi a találat helyét.

Ez lenne a cél, ennek ellenére sosem talál egyetlen egyezést sem. Azt láltom, hogy az összehasonlításnál van a baj, csak nem tudom micsoda. Mielőtt csámcsognátok rajta, azért használok long int típust, mert a fene tudja, ki mekkora területeket akar majd összehasonlítani. 


// =============================================================================
// BINBIN
// =============================================================================
// A `p_adat` memoriateruleten keresi a `p_minta` szekvenciat. Talalat eseten a
// visszateresi ertek az offset lesz, kulonben -1.

long int binbin( void *p_adat, long int adat_merete, void *p_minta, long int minta_merete )
{
    long int
        pozicio     = 0,
        egyezes     = 0;

    for( ; (pozicio < adat_merete) && (egyezes != minta_merete); pozicio++ )
    {
        egyezes = ((unsigned char *)(p_adat+pozicio) == (unsigned char *)(p_minta+egyezes))
                  ? egyezes + 1
                  : 0;
    }

    return (egyezes == minta_merete) ? pozicio - minta_merete
                                     : -1;
}
  • 2558 megtekintés

( apal v | 2010. 03. 28., v – 22:26 )

Ez kicsit nehezen erteheto, mire gondolsz. A binaris keresesnel a kovetkezot kell csinalni:
1/ veszel egy also es egy felso hatart a tombodben, ahol garantalod hogy a/ a minta benne van ebben az adott intervallumban b/ a tombod elemei rendezettek.
2/ megnezed hogy a mintad hogyan viszonyul az also es felso hatar kozott pont fe'luton levo" tombelemhez.
3/ ha kisebb annal, akkor az uj felso hatar lesz a fe'luton levo, ha nagyobb, akkor az uj also hatar lesz a feluton levo" elem
4/ goto 1, amig also hatar nem fog megegyezni a felso hatarral.
ez igy persze elegge pongyola, de kis korultekintessel konnyu megirni.

Erre gondolsz? A cimben bináris keresést irsz, de a vegen mar bináris adathalmazban keresel.

A sima ansi libc-ben van olyan hogy qsort() es bsearch(), nezd meg azokat es/vagy hasznald. A forraskodjuk elegge jol hasznalhato, legalabbis a qsort() alapjan en mar csinaltam ezt-azt.

Ha megis csak sima mintakereses kell, akkor nezegess ilyesmiket hogy strstr() vagy memchr().

( phaul | 2010. 03. 28., v – 22:42 )

Arra gondolsz hogy az adat amit keresel binaris, mint egyebkent minden adat. A binaris kereses teljesen mas. Amivel te akarsz foglalkozni az a minta illesztes/kereses.

[update]Ha jol ertem mit probalsz akkor az a "brute force", de mintha 1 ciklus hianyozna. Kulso ciklussal tolod a mintat elore, a belso meg nezi, hogy egyezik e. Ennel vannak jobb algoritmusok is gyebkent.[/update]
==
`Have some wine,' the March Hare said in an encouraging tone.
Alice looked all round the table, but there was nothing on it but tea.

( joco01 v | 2010. 03. 28., v – 22:47 )

Teljesen rosszul álltál neki. 2 ciklus kell. A külsőben iterálsz az adathalmazban 0-tól, de nem a teljes hosszon keresztül, hanem le kell vonni belőle a minta hosszát. A belső ciklusban a mintán iterálsz, ameddig egyezik, és ha végig egyezik, akkor return.

(Pl. ha a te kódoddal 12123 mintát keresel, 1212123 adatok között, eljutsz 1212-ig 4 hosszú egyezéssel, aztán 1 jön az adatban, 3 a mintában, ezért mindent eldobsz, és újrakezded 0-ról a keresést, és így nem fogod megtalálni)

És ha ennyire kell 4 gigabájton felül keresni, akkor inkább pl. makrózva csinálj belőle egy int-es és egy long int-es verziót, az esetek gyakorlatilag 100%-ában úgyis az int-es fog lefutni, nem éri meg belassítani egy irreális követelmény miatt.

--
joco voltam szevasz

( imp | 2010. 03. 29., h – 00:11 )

Teljesen rossz az összehasonlítás. Egyrészt a p_adat+1 == p_adat+2, vagyis egyhelyben jársz (mivel void*-ról van szó), másrészt memóriacímeket hasonlítasz össze, nem a mutatott terület tartalmát.


char* p=p_adat;
char* q=p_minta;
...
egyezes = *(p+pozicio) == *(q+pozicio) ? egyezes+1 : 0;

A p,q csak azért van, hogy ne kelljen *(((char*)p_adat)+pozicio) -t írni.

Másrészt az algoritmus se jó, aab -ben nem találja meg ab-t; vissza kéne léptetni a pozíciót annyival, amennyi egyezes eddig volt.

( meditor | 2010. 03. 29., h – 08:33 )

Elég sok mintaillesztő könyvtári fv van 'C'-ben is meglehetősen
hatékonyak. Használd ezeket, vagy, ha gyakorolni akarsz nézd meg
a forráskódjukat.

> Sol omnibus lucet.

( bimlas | 2010. 04. 03., szo – 11:52 )

Nos, végre volt egy kis időm. Az eredmény: 


long int binbin( void *adat, long int adat_merete, void *minta, long int minta_merete )
{
    unsigned int
        pozicio     = 0,
        egyezes     = 0;

    char
        *p_adat     = (char *) adat,
        *p_minta    = (char *) minta;

    for( pozicio  = 0;
         pozicio <= adat_merete-minta_merete;
         pozicio++ )
    {
        for( egyezes = 0;
             *(p_adat+pozicio+egyezes) == *(p_minta+egyezes);
             egyezes++ )
        {
            if( egyezes == minta_merete )
                return pozicio;
        }
    }

    return -1;
}

--
Azt akarom, hogy az emberek ne kényszerből tanuljanak, hanem azért, mert tudni akarnak.

( _jack_ | 2010. 04. 02., p – 21:22 )

Így már jobbnak tűnik. :)

Néhány észrevétel:

- Ha a 

[code]

BBCode-ot használod, megmarad a kód formázása, és olvashatóbb lesz. Azért nem a hozzászólásodra válaszoltam, hogy kijavíthasd ha akarod.

- Mint feljebb atal is írta, esetleg célszerűbb lehet a size_t használata a méretek megadásához.

- A p_adat és p_minta kezdeti értékadása C-ben jó, C++-ban viszont már explicit konverzió szükséges void*-ról char*-ra. Ha odaírod, később minden változtatás nélkül használhatod C++-ban is.

- A postfix ++ operátor ilyen használata már többször vezetett itt vitához. Nem hibás, de alapesetben kevésbé optimális kódot generálhat a fordító. Persze a fordító optimalizálhat, meg egyébként is kicsi az overheadje, de szerintem mégis rossz szokás így írni, ugyanis a postfix és a prefix változat szemantikailag alapvetően különböző dolgot jelöl. Ráadásul C++-ban nem primitív típusokra alkalmazva már tényleg problémát okozhat.

- Ha érdekelnek a mintaillesztési algoritmusok, van még miből válogatni:

  • Brute Force algoritmus (ilyen a te kódod is),
  • Knuth-Morris-Pratt algoritmus (talán ez a leggyakrabban implementált),
  • Boyer-Moore algoritmus,
  • Quick Search algoritmus,
  • Rabin-Karp algoritmus,
  • Dömölky-szűrő,
  • stb...

Köszi a BBCode-ot, próbáltam PRE tag-ek közé helyezni, de nem segített.

Ezt a size_t dolgot nem egészen értem, mindenesetre egy kis Google után azt látom, hogy nem lehet negatív értéke, ergo visszatérési értéknek nem jó. (Hogy jelzem a hibát, ha nem negatív számal?) Egyébként nem akarok 4 gigánál nagyobb terülleten keresni, csak mivel a függvény long int típusú (hogy lehessen negatív visszatérési érték is), gondoltam a méretek is legyenek ugyanilyen típusúak. Mindenesetre ezt a size_t típust melyik változóra kéne alkalmaznom?

A postfix inkrementálás miért baj? "rossz szokás így írni, ugyanis a postfix és a prefix változat szemantikailag alapvetően különböző dolgot jelöl" - ezért alkalmazom a postfixet, mert csak a ciklus után akarom növelni a változó értékét. Vagy félreértem, amit írtál? Kérlek fejtsd ki bővebben. És mit jelent az, hogy "ilyen használata" - a for ciklusban való használata a baj, vagy micsoda?

Köszönöm az építő jellegű válaszokat, de kérlek, kevesebb szakszóval fogalmazd meg a jövőben, mert a programozói szókészletem még nagyon kicsi. (El kéne olvasnom a K&R-C könyvet, de rossz szokás szerint azokat a részeket keresem ki a könyvekből, ami az adott feladathoz kapcsolódik)
--
Azt akarom, hogy az emberek ne kényszerből tanuljanak, hanem azért, mert tudni akarnak.

Na nézzük azt a ciklust: 


for (S1;S2;S4)
   S3

Ilyenkor az történik, hogy:
1. lefut S1
2. Kiértékelődik S2, ha false, akkor goto 5.
3. Lefut S3
4. Lefut S4, goto 2.
5.

Azaz teljesen mindegy, hogy S4-be postfix, vagy prefix operátort használsz.
Ennél fogva a prefixnek több értelme van. A fordító persze primitív típusoknál kioptimalizálhatja, de C++-ban, nem triviális esetekben már nem biztos.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

A size_t-visszatérési értékkel semmi gond nincs.
Annyira, hogy pl C++-ban a string::find-nak is ez a visszatérési típusa. Itt látható, hogy ha nincs találat, akkor a visszatérési érték: string::npos, ami a legnagyobb size_t érték (ami binárisan ugyanaz, mint az ugyanennyi biten tárolt előjeles -1).

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Bocs hogy csak most válaszolok, de hát Húsvét meg ilyesmi... :)

Ha már említetted a K&R könyvet, remélem az a változat van meg, amelyiknek az elején a C betű rózsaszín, és bele van írva, hogy "Az ANSI szerint szabványosított változat". Van ugyanis egy régebbi változat, aminek az elején világoskék C betű van, az már nagyon régi és elavult. Valamiért még mindig bele lehet futni a könyvesboltokban.

Ha jól látom, a size_t dolgot már megválaszolták.

Postfix inkrementálás: tr3w már leírta, hogy hogyan működik a ciklus (K&R: 3.5. alfejezet), és hogy nincs kapcsolat aközött, hogy prefix vagy postfix inkrementálást írsz, és aközött, hogy a ciklusmag végrehajtása előtt vagy után nő a ciklusváltozó értéke (mindig utána). Amúgy a K&R: 2.8. alfejezet leírja, hogy melyik inkrementálás mire van kitalálva, és hogy mi is az a szemantikai (jelentésbeli) különbség, amire utaltam. Ha elolvastad és megértetted, utána már könnyű lesz megérteni, hogy miért helyes, és miért nem ajánlott mégsem a postfix növelő/csökkentő operátor egyszál magában történő alkalmazása.

Vegyük pl. ezt: 


int i = 13;
int j = ++i - 4;

Végrehajtás után i=14, és j=10. Ha i++ szerepelt volna, akkor i=14 és j=9 lett volna a végeredmény. Azaz, az i régi értékével számoltunk volna a kifejezésben, az értéke mégis megnőtt volna. Tehát a prefix ++i esetén csak az új, megnövelt értékre van szükség, míg a postfix i++ esetben az új érték mellett a régi értékre is szükség van a teljes kifejezés értékének meghatározásához; a régi értéket csak a kifejezés kiértékelése után dobhatjuk el. Nagyjából tehát ezt csinálja a fordító a háttérben: 


j = ++i - 4;
/* Ez történik: */
i = i + 1;
j = i - 4;


j = i++ - 4;
/* Ez történik: */
int temp = i;
i = i + 1;
j = temp - 4;
/* temp a kifejezés után megsemmisül */

Most nézzük, mi történik, ha egy ciklusban a ciklusváltozót növeljük (vagy csökkentjük) a ciklusmag végrehajtása után: 


++i jelentése:
i = i + 1;

i++ jelentése:
int temp = i;
i = i + 1;
/* temp megsemmisül */

Tehát a ciklusváltozó növelését mindkét változat rendben elvégzi, csak postfix esetben a régi értéket teljesen feleslegesen eltároljuk, majd megsemmisítjük mivel nem volt rá szükség. A programozók nagy hányada ezért ilyen esetben inkább "++i"-t ír, mert az hatékonyabb. Mások azzal érvelnek, hogy az eredmény ugyanaz, a fordító pedig úgyis észreveszi hogy az inkrementálás nem egy nagyobb kifejezés része, ezért "kioptimalizálja" a kódból a régi érték eltárolását; és egyébként is, szerintük az, hogy "i++" logikusabb, mint az, hogy "++i". Szabadon eldöntheted, hogy melyik a szimpatikusabb.

C++ esetén már egészen más a helyzet, mert ott létre lehet hozni saját osztályokat (adattípusokat), és a saját osztályodhoz saját magad megírhatod az operátorokat, többek között a prefix és postfix növelő ill. csökkentő operátort is.

Bár még nem olvastam el a K&R-C idevágó részét, de mindenesetre nagyon köszönöm Neked is és tr3w-nak is a magyarázó leírást, örülök, hogy vannak ilyen lelkes 'tanárok' is a HUP-on - nem nyali, csak tényleg sokszor látok oneliner válaszokat. No, viszont most meglesem, mit mond a Biblia. :)

--
Azt akarom, hogy az emberek ne kényszerből tanuljanak, hanem azért, mert tudni akarnak.

Sosem értettem ezt a ++i, i++ vitát. Szerintem teljesen logikus, hogy nem a példádban leírt módon történik a postincrement verzió, hanem az alábbiak szerint:

j = i - 4;
i = i + 1;

azaz semmi szükség temp változóra. Most kipróbáltam gcc-vel, optimalizálás nélkül. Látható, hogy a műveletek sorrendjével variál, nem temp változóval.

int i = 13;
6: c7 45 fc 0d 00 00 00 movl $0xd,-0x4(%ebp)
j = ++i - 4;
d: 83 45 fc 01 addl $0x1,-0x4(%ebp)
11: 8b 45 fc mov -0x4(%ebp),%eax
14: 83 e8 04 sub $0x4,%eax
17: a3 00 00 00 00 mov %eax,0x0
j = i++ - 4;
1c: 8b 45 fc mov -0x4(%ebp),%eax
1f: 83 e8 04 sub $0x4,%eax
22: a3 00 00 00 00 mov %eax,0x0
27: 83 45 fc 01 addl $0x1,-0x4(%ebp)

--
Soli Deo Gloria

Ebben igazad van. Mivel a C nyelvben nincs operátor túlterhelés, csak a primitív típusokra vonatkozó beépített ++ és -- operátorokkal találkozhat a fordító, ezt pedig ki tudja használni a fordításkor. Két dolog miatt továbbra is fenntartom a véleményem arról, hogy nem ajánlanám a postfix formát önálló kifejezésként:

Az egyik dolog inkább elméleti jellegű. A prefix forma pontosabban kifejezi, hogy mit is szeretnénk csinálni. Persze ha a nyelvnek lenne valamilyen formális szemantikai definíciója, könnyen bizonyítható lenne, hogy a két forma hatása ebben a helyzetben ekvivalens. De olyan ez, mintha ahelyett, hogy 

i = 3

, azt írnád, hogy 

i = 1 + 2

. Itt ugyanaz a két utasítás hatása (C-ben!), és ha ezt a fordítóprogram képes megérteni, akkor ugyanazt a kódot is generálja, de ez implementációtól függő dolog. Ha a fordítót egy lusta ember írta volna, akkor egy az egyben leképezte volna gépi kódra a programozó bénaságát.

A másik dolog a C++-ra való későbbi átállás lehetősége. C++-ban az általad (vagyis a gcc által :) ) leírt optimalizálás csak a beépített primitív típusokra alkalmazható (általában már a standard könyvtári nemprimitív típusokra sem!).

És hogy honnan vettem ezt a temp-es módszert? A C++ a nemprimitív típusokra ilyesmit csinál - persze én int-et írtam, arra pont rossz példa.

Az i=1+2-es példa sántít, mert nem tudom, hogy a C szabvány hogyan rendelkezik, de a C++ szabvány előírja, hogy az ilyen kifejezések fordítási időben kiértékelődjenek. (Enélkül a template meta-programming nem is létezhetne. Sőt a C++0x-ben még bevezették a constexpr kulcsszót is.)

És igen, olvashatósági szempontból nagyon hasznos lehet.

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Igen, sikerült másodszor is rossz példát írnom, kösz a helyreigazítást. A dolog ideológiai hátterére koncentráltam, aztán hirtelen nem jutott eszembe jobb példa. Remélem, azért a lényeg átjött: mindig célszerű a lehető legpontosabban fogalmazni a kódban, és csak kivételes esetekben eltérni ettől és a fordítóra hagyni az optimalizációt. Ilyen kivételes eset pl. az olvashatóság fenntartása, ha megengedhető az esetleges pluszköltség amit okozhat.

Ez a C++0x dolog remélem hamar elterjed majd, mert egy csomó jóság van benne. Sajnos a concept-ek asszem nem, úgyhogy a template-ekkel lehet szívni továbbra is. :)

Conceptek nem, de static_assert igen, úgyhogy valamivel azért javul a helyzet...
Úgy tűnik, hogy hamarabb elterjed mint a C++98, mert a gcc, icc, és az msvc újabb verzióiban már most benne van jó pár feature. (Pl.: auto és lambda mindegyikben van.)

"...handing C++ to the average programmer seems roughly comparable to handing a loaded .45 to a chimpanzee." -- Ted Ts'o

Igazatok van, én a fenti példát csak C esetére értettem, C++ összetett típusnál nyilván lehet különbség.
És természetesen a pre- és postincrement csak önállóan használva felcserélhető, kifejezésben lényeges különbség van, ami a fenti példák különböző eredményében is látszik.
Az i = 1 + 2; írásmód is hasznos lehet, ha növeli az olvashatóságot (pl. 1 byte header plusz 2 byte adat esetén érthetőbb így írni), nem hiszem, hogy bármelyik mai fordító ezt nem fordítási időben számolná ki.

--
Soli Deo Gloria

( lzrd | 2010. 04. 02., p – 22:47 )

könyvjelző
--
unix -- több, mint kód. filozófia.
Life is feudal