[C#] Jak na konečný automat

C++, C#, Visual Basic, Delphi, Perl a ostatní

Moderátor: Moderátoři Živě.cz

Odeslat příspěvekod PiranhaGreg 28. 9. 2015 17:43

Ahoj, potřebuji získávat nějaká data z dost velkého binárního souboru. Problém je, že od něho nemám dokumentaci. Nechce se mi ale týden (ne-li víc) luštit jak je strukturovaný, když pak stejně potřebuju jen zlomek dat, které vím jak hledat.

Zároveň bych ale ty správný data potřeboval najít max v lineárním čase vzhledem k velikosti souboru. Napadlo mě tedy pořešit to přes (něco jako) konečný automat. Moje bezhlavá implementace je ale jaksi hodně dlouhá a celkově to tak nemůžu nechat. Navíc tam detekuju jen jednu ze čtyř sekvencí. Počítám, že když bych do toho tímto stylem chtěl přidat i ty zbývající, tak se upíšu.

Takže jak na to znovu a správně? :-) Nemusí to být nutně přes ten konečný automat, pokud vás napadne něco jinýho. Ale vstupem by měl být stále stream. Nahrávání celýho souboru do pole bytů bych se chtěl vyhnout. Jen pro představu, už tahle funkce mi tam najde 46 576 záznamů, kde průměrný název proměnný má 18 znaků a její obsah 174. Těch dalších typů záznamů bude ještě víc.
PiranhaGreg
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod pucmeloudek 29. 9. 2015 09:30

hledas nakej prefix nebo co? zkus to pro zacatek bez goto... a pak trochu slovne popsat, o co jde, se mi to nechce zpetne lustit z kodu.
pucmeloudek
Junior

Odeslat příspěvekod darm 29. 9. 2015 09:51

Co to je za typ dat? Na dolování něčeho podle regexpu bohatě stačí třeba grep.
darm
Junior

Odeslat příspěvekod gandor 29. 9. 2015 10:06

V principe ides spravne. Len ten kod je prasacky a budes mat problem ked budes vytahovat viac veci.
Stavovy automat bude vzdy viac kodu a to je v pohode, ale preco nemozu byt jeho jednotlive stavy triedy obsahujuce prechody a podobne? Definujem X tried (kazda pre jeden stav), ktora bude obsahovat svoju condition a aj svoje prechody (a akcie). Na zaklade toho mi vznikne pekny priehladny graf, ktory budes vediet relativne lahko extendovat.
Idealne je, aby dedili s jednej triedy, ktora bude definovat nejake pomocne veci (read byte zo streamu a podobne).

Regexp v binarnom subore nebude nejak velmi pouzitelny. Ale pokial su tahane data dostatocne strukturovane, tak by to mohlo zjednodusit vec. Urcite ale nie grep ktory vytahuje cely riadok (co je riadok v binarnom subore?) ale skvor nejaky "tradicny" regexp z "normalnych" jazykov....
gandor
Mírně pokročilý

Odeslat příspěvekod Nargon 29. 9. 2015 14:00

Tak jsem luštil ten tvůj kód. Z toho co jsem vysledoval, tak by to mělo odchytávat takovýto kód:
Kód: Vybrat vše
0x01 0x00 0x00 0x00 NazevPromene 0x0a 0x00 0x00 0x00 0x00 0x01 0x30 0x41 0x00 4ByteData1 4ByteData2 4ByteData3 4ByteData4 TextData 0x0a

S tím že "NazevPromene" a "TextData" jsou variabilní a předem neznámé délky.
Pak "NazevPromene" musí obsahovat jen znaky A-Z, a-z, 0-9, a podtržítko _, cokoliv jiného není povolené.
Data1 až Data4 jsou vždy o délce 4Byty.

Je to tak správně a je to vše? To abych nevymýšlel něco podle špatného zadání. Určitě se to dá nějakým způsobem optimalizovat. Ale než se nad tím zamyslím tak chci vědět že nebudu věnovat čas něčemu špatnému.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod PiranhaGreg 29. 9. 2015 21:27

Nargon píše:Tak jsem luštil ten tvůj kód. Z toho co jsem vysledoval, tak by to mělo odchytávat takovýto kód:
Kód: Vybrat vše
0x01 0x00 0x00 0x00 NazevPromene 0x0a 0x00 0x00 0x00 0x00 0x01 0x30 0x41 0x00 4ByteData1 4ByteData2 4ByteData3 4ByteData4 TextData 0x0a

S tím že "NazevPromene" a "TextData" jsou variabilní a předem neznámé délky.
Pak "NazevPromene" musí obsahovat jen znaky A-Z, a-z, 0-9, a podtržítko _, cokoliv jiného není povolené.
Data1 až Data4 jsou vždy o délce 4Byty.

Je to tak správně a je to vše? To abych nevymýšlel něco podle špatného zadání. Určitě se to dá nějakým způsobem optimalizovat. Ale než se nad tím zamyslím tak chci vědět že nebudu věnovat čas něčemu špatnému.

Jop, vysledoval jsi to správně (+ první znak u proměnné nesmí být číslo). Když to trochu rozvedu...

Počáteční sekvence 0x01 0x00 0x00 0x00 je vždycky před NazevPromenne, ale nemusí nutně značit, že tam ta proměnná bude. Jsou tam i nějaký jiný data, kde se tyhle sekvence také objevují. Proto hned tak přísně validuji, že se jedná o proměnnou, abych případně mohl zahlásit false positive a jet od začátku.

Dále název proměnné i případný text vždy končí tím 0x0a. Text může být v podstatě cokoliv, ale bývá tam hlavně windows-1250 a windows-1251.

Ta následující sekvence 4x 0x00 tam bohužel není vždy. Ještě jsou tam pro jiný typy (viz dále) tvary 0x02 0x00 0x00 0x00 a 0x07 0x00 0x00 0x00 (a možná ještě něco). I v tomhle místě je ale ještě potřeba detekovat počáteční sekvenci 0x01 0x00 ..., protože pořád není jistota, že jde o správný data :-] .

No a pak je tam konečně sekvence, která určuje typ proměnné. Tři nejdůležitější jsou tyto

0x01 0x20 0x40 0x00 = var int
0x01 0x20 0x41 0x00 = const int
0x01 0x30 0x41 0x00 = const string

ale časem tam chci mít ještě podporu pro float, RGB barvu a několik dalších, takže bych minimálně tuhle část potřeboval nějakou rozšiřitelnou.

Pak jsou tam různý custom hodnoty podle typu, ale to už je v pohodě, protože vím na čem jsem. Sekvence pak vždy končí čtveřicí 0xff 0xff 0xff 0xff.

Jinak chci ty data vracet průběžně jak to mám teď. Budu s tím dělat ještě nějaký čachry pomocí LINQ a ani je třeba nebudu potřebovat načíst všechny. V předpisu metody bude jako návratová hodnota nějaký předek či interface.

Ale spíš než funkční implementace mi stačí nějaké typy jak na to v úhlednějším stylu, ale abych zároveň zachoval rychlost, která je tu důležitá.

gandor píše:Regexp v binarnom subore nebude nejak velmi pouzitelny. Ale pokial su tahane data dostatocne strukturovane, tak by to mohlo zjednodusit vec. Urcite ale nie grep ktory vytahuje cely riadok (co je riadok v binarnom subore?) ale skvor nejaky "tradicny" regexp z "normalnych" jazykov....

No když jsem se těmi daty prokousával, tak jsem si na to nějaký Regex napsal. Např. na tu sekvenci, kterou hledám v mé prvotní implementaci funguje v Sublime Text docela dobře
Kód: Vybrat vše
(?s)\x01\x00\x00\x00([ -˙]*?)\x0a\x00{4}\x010A\x00(.{4}).{4}\x01\x00\x00\x00.{8}([ -˙]*?)\x0a˙˙˙˙

+ bych tam ještě musel dopsat nějaký validace. Min. v Sublime Text je to ale hodně pomalý, asi hodně hodně hodně těžko bych do toho regexu narval všechny ty hledaný sekvence a pak taky C# pracuje s UNICODE a nevím nevím, jak by se mu líbily ty binární data, který bych mu podstrčil jako string. Navíc bych to nejspíš zase musel celý nahrát do paměti.

Jinak jak jsi to myslel s těmi třídami a stavy? Co jsem si kreslil na papír cca stavovej automat, kterej odpovídá celýmu řešení, tak je tam těch stavů opravdu hodně. Na to asi tolik tříd definovat nebudu :mrgreen: .
PiranhaGreg
Mírně pokročilý
Uživatelský avatar

Odeslat příspěvekod Nargon 30. 9. 2015 05:35

Hmm, tak po vyzkoušení to odchytává trochu jiná data.
Kód: Vybrat vše
0x01 0x00 0x00 0x00 NazevPromene 0x0a 0x00 0x00 0x00 0x00 0x01 0x30 0x41 0x00 4ByteData1 4ByteData2 4ByteTrash 4ByteData3 4ByteData4 TextData 0x0a

Je tam navíc 4ByteTrash, holt 20 != 4*4 ale je to 20 = 5*4

Já jsem něco zkusil vyplodit, a kompletní kód máš tady: http://paste.ofcode.org/cW5iaUzFa2q4dwXhHSxSpn
a tu hlavní část dám i sem
Kód: Vybrat vše
    class StreamParser
    {
        int lastByte = -1;
        private ulong lastRead = ulong.MaxValue;
        private ulong last2Read = ulong.MaxValue;
        Stream s;

        Encoding windows1250 = Encoding.GetEncoding(1250);
     
        public StreamParser(Stream input)
        {
            s = input;
        }

        int ReadByte()
        {
            lastByte = s.ReadByte();
            last2Read = (last2Read << 8) | (lastRead >> 56); //bitová magie, vždy se o 1B posune a načte se další hodnota
            lastRead = (lastRead << 8) | (ulong)lastByte; //zpětně si pamatuje 16B dat, což stačí na identifikaci správné pozice
            return lastByte;
        }       

        Queue<byte> variable = null;
        string varName = null;
       
        public IEnumerable<VariableEntry> ReadData()
        {
            while (ReadByte() != -1)
            {
                if ((lastRead & 0xFFFFFFFF) == 0x01000000ul) variable = new Queue<byte>();

                if (variable != null)
                {
                    if (lastByte == 0x0a) { varName = windows1250.GetString(variable.ToArray()); variable = null; }
                    else variable.Enqueue((byte)lastByte);
                    continue;
                }

                if ((last2Read & 0xFF) == 0x0a)
                {
                    switch (lastRead)
                    {
                        case 0x0000000001204000ul:
                        case 0x0200000001204000ul:
                        case 0x0700000001204000ul: //spravna data var int                         

                        case 0x0000000001204100ul:
                        case 0x0200000001204100ul:
                        case 0x0700000001204100ul: //spravna data const int                         

                        case 0x0000000001304100ul:
                        case 0x0200000001304100ul:
                        case 0x0700000001304100ul: //spravna data const string
                            {
                                byte[] bytes = new byte[20];
                                s.Read(bytes, 0, 20);
                                Queue<byte> content = new Queue<byte>();
                                while (ReadByte() != -1)
                                {
                                    if (lastByte == 0x0a)
                                    {
                                        yield return new VariableEntry()
                                        {
                                            Name = varName,
                                            Content = windows1250.GetString(content.ToArray()),
                                            Type = BitConverter.ToInt32(bytes, 0),
                                            Valuel1 = BitConverter.ToInt32(bytes, 4),
                                            Valuel2 = BitConverter.ToInt32(bytes, 12),
                                            Valuel3 = BitConverter.ToInt32(bytes, 16),
                                        };
                                        break;
                                    }
                                    else content.Enqueue((byte)lastByte);
                                }
                                break;
                            }
                    }
                }
            }
            yield break;
        }
    }

Já jsem nepoužil stavový automat, ale šel jsem na to trochu jinak. Při načítání si tvořím malý buffer o velikosti 8+8B, který posouvám a je v něm zpětně uložených 16B dat, které stačí na identifikaci sekvence 0x0a 0x00 0x00 0x00 0x00 0x01 0x30 0x41 0x00. Navíc to není problém rozšířit, jen do switche přidat další sekvenci. Ikdyž tam už jsem ti zadal všechny možnosti co jsi tu napsal.
Není tam ta kontrola na název proměnné, aby to obsahovalo jen ty validní znaky a ani ten konec na 0xff 0xff 0xff 0xff, ale snad to není nutné. Ikdyž to tam půjde doplnit.

Jen tak ze zvědavosti. Můžeš vyzkoušet rychlost na tom tvém souboru v porovnání s tvým řešením? Celkem mě to zajímá. Lineární složitost tam stále je, ale neodhadnu zda ty binární operace jsou rychlejší než skoky mezi stavy nebo naopak.
Desktop: Ryzen 7 1800X (3.95GHz, 1.35V), Asus Crosshair VI Hero, 16GB DDR4 Ram (3200MHz), 128GB SSD + 3TB HDD, Nvidia GTX 1080
Notebook: Asus UL50VT 15.6" (SU7300@1.7GHz, 4GB ram, 500GB HDD, Intel GMA 4500MHD + nVidia G210M, dlouha vydrz cca 7+ hod)
Nargon
Moderátor

Odeslat příspěvekod xmisak 30. 9. 2015 07:46

Já to napsal v Céčku takto: :)
Skoro bych se vsadil, že efektivněji to napsat nejde ;) Troufl by si někdo napsat kód (v libovolném jím zvoleném jazyce), který poběží na stejném hardware v rychlejším čase?

Kód: Vybrat vše
#include <stdio.h>

#define BLOK 8192
#define MAX_SEARCH 100

char buf[BLOK+MAX_SEARCH];

int shoda(char *a,char *b,int n)
  {
  int i;
  for (i=0;i<n;i++)
    if (a[i]!=b[i]) return(0);
  return(1);
  }
 
int hledej(char *fn,char *co,int n)
  {
  FILE *f;
  int i,nacteno,zac,l=0;
 
  f=fopen(fn,"rb");
  zac=MAX_SEARCH;
  do {
    nacteno=fread(buf+MAX_SEARCH,1,BLOK,f);
   for (i=zac;i<nacteno;i++)
     if (shoda(buf+i,co,n)) return(l+i-MAX_SEARCH);
   for (i=0;i<MAX_SEARCH;i++) buf[i]=buf[i+BLOK];
   zac=1;
   l+=BLOK;
    } while (nacteno==BLOK);
  fclose(f);
  return(-1);
  }

int main()
  {
  char co[4]={'a','h','o','j'};
  printf("%d\n",hledej("data.txt",co,4));
  }


-- 30. 9. 2015 09:08 --

V gigabajtovém souboru s hledaným 9-bajtovým binárním řetězcem na konci mi hledání trvá 4,47 sekundy. Pravda, mám SSD disk.
xmisak
Kolemjdoucí

Odeslat příspěvekod pucmeloudek 30. 9. 2015 08:37

mno, resit primitivni algoritmus, kterej stejne vzdycky bude brzdit medium, ze kteryho se cte... ze vas to bavi :)

trocha literatury na algoritmy hledani substringu (kdyby to nebrzdil onen disk, jinak je to o houne)

http://www-igm.univ-mlv.fr/~lecroq/string/index.html

btw. v tom Ccku je na prvni pohled brutalne neoptimalni tohle:

for (i=0;i<MAX_SEARCH;i++) buf[i]=buf[i+BLOK]

kopirovat buffer fixni velikosti po jednotlivych byte, fuj...
pucmeloudek
Junior

Odeslat příspěvekod xmisak 30. 9. 2015 08:43

No já zde kopíruji 100 bajtů na každých 8192. I kdyby se tahle část použitím funkce přepsané do assembleru (která ve finále stejně dělá to samé) zrychlila třeba na polovinu, nebo na třetinu, na výsledný běh to bude mít zcela zanedbatelný vliv.

Ostatně, teď jsem to zkusil. Ten řádek jsem nahradil
memcpy(buf,buf+BLOK,MAX_SEARCH);
a čas zůstal s přesností na setinu sekundy stejný...

Jinak zcela souhlasím s tím, že celý ten problém je naprosto banální a triviální :)
xmisak
Kolemjdoucí

Odeslat příspěvekod pucmeloudek 30. 9. 2015 08:57

no mne slo jenom o to poukazat na to, jak zvraceny je psat vlastni tezce neoptimalni algoritmy, kdyz mam knihovni volani...

aneb zkratka byla sice delsi, ale zato horsi cesta :)

btw. ta nejsnazsi optimalizace celyho algoritmu je pouzit strchr na hledani mist, kde vubec ma smysl se zacit zabyvat nakym cyklem pres hledany retezec...
pucmeloudek
Junior

Odeslat příspěvekod gandor 30. 9. 2015 08:59

xmisak: Nedavaj taketo vyzvi, lebo ked sa vezmu mikrooptimalizacie do uvahy, tak ten kod je vyslovene pomaly ;) Samozrejme suhlasim s pucmeloudek a zameral by som sa na ine veci ako percenticka vykonu...

Pucmeloudek: K tym triedam - kazda by mala predstavovat urcity stav v ktorom som - citam cisla, citam text ktory je na konci niecim ohraniceny, atd atd. Tento postup nieje vykonnostne ani zdaleka najoptimalnejsi. Ale je optimalny z hladiska toho, ze lustim nieco a neviem co a neviem co sa s toho neskvor vykluje a potrebujem sa vediet rychlo zorientovat v kode a doplnit do neho lubovolne features.
Samozrejme nerobis novu triedu pre kazdu premennu - len pre kazdy "stav" (teraz citam premenna1 premenna2 premenna3 premenna4) vramci daneho streamu. V takom pripade vies pre kazdu cast si precitat len tolko dat, kolko potrebujes vtedy ked potrebujes.

Ale kedze si sa vybral uz Nargonovym riesenim, tak by som sa ho drzal - koniec koncov urcite pojde rychlejsie a da sa aj doplnat...
gandor
Mírně pokročilý

Odeslat příspěvekod xmisak 30. 9. 2015 10:37

gandor: Vysloveně pomalý kód? :) Uff, tak sem s konkrétními čísly! Napiš svoji verzi a na jednom stroji pak pusť tu moji a tu svoji, a pochlub se srovnáním ;)
pak můžeme posoudit, co je "vysloveně pomalé" a ne-"vysloveně pomalé" ;) ;)
Keckat od stolu je tak snadné... ;)
xmisak
Kolemjdoucí

Odeslat příspěvekod xmisak 30. 9. 2015 12:04

pucmeloudek: strchr přece hledá v null-terminated řetězci. Takže když budou vstupní data obsahovat nulu, hledání tam skončí. To je nám na nic. I bez ohledu na to bych se navíc vsadil, že tímhle vylepšením v reálu nezískáš prakticky nic.

Jinak, já bych ty vestavěné funkce až tak nepřeceňoval. Jak říkám: zkuste ty své moudré úvahy implementovat, a hned budeme vidět.
xmisak
Kolemjdoucí

Odeslat příspěvekod pucmeloudek 30. 9. 2015 12:33

no tak memchr, bozinku, jde o princip.
to, ze tezko neco clovek muze ziskat (protoze to visi na pomalym ctenim disku, todiz je to cela diskuze o houne), rikam od zacatku.
pucmeloudek
Junior

Odeslat příspěvekod gandor 1. 10. 2015 12:50

Ano vyslovene pomale z hladiska mikrooptimalizacii a ano pucmeloudek ma pravdu, lebo na tomto nezalezi - kedze brzda je HDD a nie algoritmus.

PS. moje riesenie s konecnym automatom je radovo pomalsie, ale je to stale jedno - citatelnost/mnozstvo chyb/extensibilita je v 99% pripadov stale dolezitejsia ako cisty vykon skriptu.

PPS.
1, memset bude vzdy maximalne rovnako rychle ako for-cyklus a nastavovanie hodnoty na 0. Ale vo vecsine pripadov bude rychlejsie, pretoze loop-unrolling (t.z. for-cyklus neprebehne v kazdom cykle test ci je na konci, ale len 1x za 8 resp. 16 resp X (podla velkosti unrollnuteho cyklu) podmienok.
Druha vec je, ked hardware dokaze vykonat viac instrukcii naraz - co moze mat podporu v compilery a teda memset dokaze naraz v 1 cykle nastavit napriklad 4 hodnoty na 0 a tvoj kod len 1 (lebo potom ide k porovnaniu)
2, porovnavanie na zhodu retazcov vs strcmp funguje znova velmi podobne. Maximalne bude rovnako rychle/pomale ale pravdepodobne bude existovat rychlejsia hw implementacia.
3, memcopy to iste co memset (posuvanie hodnot bufferov)
4, pouzivas fread - buffrovana verzia readovania. Nebuffrovana verzia read (linux only) je rychlejsia lebo nema buffer navyse - dalsia "mrhanie"
5, C podporuje register premenne - pri spravnom zvoleni vybranych premennych dostanem znova zanedbatelne vyssi vykon, lebo premenna je v pamati blizsie k procesoru a je tam teda vyssi access time.
6, este som ani nespomenul assembler a moznosti co mi ponuka v oblasti mikrooptimalizacii

No a potom uz existuju algoritmicke vylepsenia ktore by si nasiel tym, ze by si si nastudoval problematiku... Napriklad nemusis sa posuvat vzdy po jednom znaku a testovat cely text, ale napriklad hladas prve pismeno zhody, ak matchne posunies sa dalej. Ak dalsie pismeno sa zhoduje posunies sa dalej. Ak dalsie sa nezhoduje, nemusis sa vratit na zaciatok, ale mozes ist dalej v streame - ale toto plati len ak ziadne s precitanych pismen sa nezhodovalo s inym (t.z. nenajdes substring) akonahle existuje substring, musis sa vratit k nemu a testovat od neho. Tymto tiez ziskam malinky vykon navyse oproti tebe.
gandor
Mírně pokročilý


Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 0 návštevníků