Hát szóval találtam valamit. Persze most jó lenne, ha tudnám, hogy mi mennyi ideig tart egy prociban, és nem is sokat gyorsít, de szerintem működik. Eltolást, AND műveletet és 1 byte ellenőrzését vettem 1 lépésnek.
Nézzük 8 byte-ra, innen biztos általánosítani tudod. Számolni fogok valószínűségeket, két dolgot teszek fel:
- a következő 8 byte nem tartalmaz \0-t. Úgy is az az érdekes, amikor hosszú a string, akkor akarunk gyorsak lenni. Ha hamar megtaláljuk a \0-t, akkor örülönk.
- a bitek véletlenszerűek. Nyílván nem, de így tudunk számolni.
Az algoritmus:
Fogod a 8 byte-ot, eggyel ciklikusan eltolod (a bal részre a jobbról távozó byte jön be). Ezután AND-del összehasonlítod az eredeti 8 byte-tal (ha külön művelet lemásolni, akkor nem lesz jó a módszerem). Ezután megnézed a 0., 2., 4., 6. pozíciókat, hogy ott \0 áll-e. Ha végig nem, akkor ebben nem lesz \0. Ha igen, akkor ellenőrzöd a megfelelő két byte-ot.
P( a 4 vizsgálat során valahol \0-t látsz | nincs \0 bennük ) =
1 - P( a 4 vizsgálat során sehol sem látsz \0-t | nincs \0 bennük ) =
1 - P( 1 bytenál nem \0-t látsz | nem \0 )^4 =
1 - (1 - P(két véletlen bit AND műveletnél 0-t látsz)^8)^4 =
1 - (1-(3/4)^8)^4, ami kb. 0.344
Tehát az esetek harmadában lesz csak vak risztás. Egy vak riasztás 2 plusz vizsgálattal jár (nade lehet több vakriasztás is, úgyhogy vissza a matekhoz), nézzük pontosan a várható értéket:
6 művelet: egy eltolás, egy AND, plusz 4 vizsgálat.
plusz: 4*2* P( két véletlen bit AND műveletnél 0-t látsz) = 4*2*(3/4)^8 (magyaráznám a 2-es szorzót: két összehasonlítást kell néznünk)
Összesen: 6.8009
Ez várhatóan még mindig jobb, mint a 8 vizsgálat.
Számoltam több eltolással, de 8-nál több jött ki. Nincs még 16 byte-os rendszer? Ott repesztene.
Egy kis magyarázat. Használtam:
- feltételes valószínűséget
- várható érték linearitást
- elemi kombinatorikát
Bármelyikben szívesen segítek.
Még valami: Lehet, hogy az AND művelet után kapott 8 byte-os számot még egyszer el kellene tolni, most már 2 byte-tal, majd összehasonlítani (vagyis AND-elni) magával. Így csak 2 byte-ot kellene ellenőrizni, hogy \0-ák-e. Ez így még nem lenne gyors, mivel marad a 6 művelet + nagyobb szám várható értékben = kb. 8.773, mivel minden egyes vakriasztás esetén 4 byte-ot kell végig nézni. Javítási javaslat: vakriasztás esetén az első AND művelet után kapott számot lehetne vizsgálni, és nagy valószínűséggel (ez is feltételes lesz, na ezt nem volt kedvem számolni) 2 vizsgálattal meg lehet úszni a dolgot. Ez még gyors lehet, de 6 alá semmiképp sem tud menni.