Quali sono alcune tecniche di analisi esotici?
https://stackoverflow.com/questions/940984
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sono stato l'analisi di dati storici delle mani di poker per l'anno passato e ho imparato piuttosto un affare su analisi in generale.
Abbiamo iniziato con le regex ma presto resi conto che non sarebbe scalare facilmente. Abbiamo saltato lingue dal rubino al C ++ e, infine, è venuto alle prese che era l'algorithim che doveva cambiare.
Abbiamo raccolto boost :: Spirito e guardavamo la nostra velocità notevolmente lievitare per ordini di più di 10 volte la nostra velocità originale. Abbiamo poi saltato a Java e attualmente utilizzando ANTLR per creare grammatiche per ogni sito. Questo è sicuramente ancora il metodo più veloce ed è molto accurato che è bello perché si sa esattamente dove ti trovi, in termini di una grammatica 'completa'. Purtroppo, ho trascorso una quantità incredibile di tempo a lavorare con queste grammatiche -. Funzionano dannatamente bene, ma non ancora perfettamente
In ogni modo, basta con lo sfondo alla questione a portata di mano - ci sono tutte le tecniche 'esotiche' o meno noti per l'analisi che io non sono a conoscenza? So solo di lexing / parsing una grammatica e l'altro metodo di espressione regolare / ciclo inferiore.
Per quelli di voi che non hanno familiarità con la storia delle mani di poker vi posterò uno così si può dire quale sia la struttura sia.
Full Tilt Poker Game #12037626529: Table durrrr (heads up, deep) - $500/$1000 -
Pot Limit Omaha Hi - 2:00:48 ET - 2009/05/05
Seat 1: durrrr ($196,456.50)
Seat 2: Gus Hansen ($65,499)
durrrr posts the small blind of $500
Gus Hansen posts the big blind of $1,000
The button is in seat #1
*** HOLE CARDS ***
durrrr raises to $3,000
Gus Hansen raises to $9,000
durrrr calls $6,000
*** FLOP *** [3d 4d 7d]
Gus Hansen has 15 seconds left to act
Gus Hansen checks
durrrr checks
*** TURN *** [3d 4d 7d] [Jh]
Gus Hansen checks
durrrr checks
*** RIVER *** [3d 4d 7d Jh] [Ah]
Gus Hansen has 15 seconds left to act
Gus Hansen checks
durrrr has 15 seconds left to act
123stayfree (Observer): GUS I NOW BRING U LUCK
durrrr bets $7,600
Gus Hansen has 15 seconds left to act
Gus Hansen has requested TIME
Hernandez777 (Observer): Gus has the super-duper nuts
Gus Hansen calls $7,600
Podobed45 (Observer): fluuuuuuuuuush
*** SHOW DOWN ***
durrrr shows [Kc 3s Qd As] two pair, Aces and Threes
Gus Hansen mucks
durrrr wins the pot ($33,199.50) with two pair, Aces and Threes
*** SUMMARY ***
Total pot $33,200 | Rake $0.50
Board: [3d 4d 7d Jh Ah]
Seat 1: durrrr (small blind) collected ($33,199.50)
Seat 2: Gus Hansen (big blind) mucked
Sono ben consapevole di altri metodi di raccolta delle informazioni (come l'iniezione screen-scraping e dll), ma la necessità di trasformare la cronologia delle mani in dati strutturati è ancora lì quindi non vedo solo i metodi che afferrare il informazioni come ad esempio regex / grammatiche ...
Credo che se non trovo qualcosa che ho intenzione di riscrivere le nostre grammatiche con ocamllex / ocamlyacc.
Aggiorna
FYI: velocità regexen stato ~ 60 mani / sec, mentre le grammatiche sono stati elaborando 600+ mani / sec ... tutta la mano si trasforma in XML dopo che i dati sono tutto risolto ... ci sono tra 20-30 regex necessario (l'ultimo conteggio) per ogni sito che si desidera analizzare .... ogni sito sul lato di grammatica ha il proprio grammatica con quantità empi di regole lexer / parser (ma è la dimensione del codice ancora più piccolo)
Io ho il libro drago e sono stato la lettura attraverso di essa - che ha respinto il mio interesse nel usando il ocamllex / ocamlyacc .... velocità è il nome del gioco qui ..
Soluzione
Se stai cercando di massimizzare la velocità, allora si potrebbe fare meglio utilizzare OcamlYacc / FsYacc sopra ANTLR. OcamlYacc crea LL (1) parser, che in genere hanno prestazioni migliori rispetto LL-style ANTLR (*) parser (qualcuno può correggermi se sbaglio) . [Modifica per aggiungere:] sembra che qualcuno mi corresse: OCamlYacc produce LALR (1) parser. Non posso dire con certezza se parser OcamlYacc sono più veloci di parser ANTLR.
OCaml / F # sono molto buoni linguaggi per la costruzione di un DSL, e, a mio parere molto più appropriato per il lavoro di Java, soprattutto perché la sua ridicolmente facili da creare e esegue un movimento AST rappresentato come una struttura di dati unione. Io consiglio di questo esercitazione che dimostra come analizzare SQL in F #.
Altri suggerimenti
Dal momento che siete in cerca di esotico, di leggere questo articolo su Top Down Precedenza degli operatori di Vaughan Pratt ...
Parser combinatori è un metodo molto popolare di parser costruzione in linguaggi funzionali come Haskell.
È necessario chiedersi se ciò che si vuole veramente fare è giocare con i parser (certamente divertente, e quello che preferisco io) o se si desidera ottenere in realtà il lavoro fatto sul poker bot. Per lo più probabili, tecniche di parsing esotici sono eccessivo per quello che ti serve. Basta scegliere una lingua veloce con alcune semplici, facili da usare parser. Probabilmente si dovrebbe essere in grado di elaborare 10k mani / sec con dritto C + flex. Oppure, ocamllex + ocamlyacc dovrebbe essere più che sufficiente. Se dovete hadoopify il codice penso che stai facendo qualcosa di sbagliato. la latenza di rete dovrebbe finire per essere il tuo vero collo di bottiglia, non è l'analisi della velocità. Che tipo di macchina sono in esecuzione su questo?
Un'altra alternativa sta usando un generatore di parser per autogenerare un tavolo di analisi, e poi a mano ottimizzazione che, o la mano di ottimizzazione dalla NFA (probabilmente non farà risparmiare molto però, e il compromesso in tempo programmatore, probabilmente non vale la pena ). Combinator analisi è probabile che sarà più lento.
In media, per un dato grammatica LL potenza equivalente sarà più lento di LALR. In particolare, se le mani di poker sono in realtà leggibile dalla un parser LALR, quindi bisonte / byacc + flex sarà battere le mani ANTLR giù, ogni volta. Personalmente sono abbastanza contento menhir, anche se è una cagna infuria e mezzo per arrivare a lavorare con Godi + ocamlbuild.
- Nico
Leggi il Drago libro: http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/ dp / 0201100886
Si estende l'analisi lessicale e sintattica in profondità (tra gli altri argomenti). È possibile utilizzare questo per aiutare a comprendere il "linguaggio" si sta cercando di analizzare per determinare il modo migliore per andare su di esso.
Wikipedia ha una bella panoramica sui tipi di parser, qui: http://en.wikipedia.org/wiki/Parser
E un confronto sugli strumenti generatore di parser, qui: http://en.wikipedia.org/wiki / Comparison_of_parser_generators
GLR è un genere di metodo meno noto che è interessante perché si tratta con ambiguità linguistiche.
Recursive Descent Parsing potrebbe funzionare per voi. E 'molto personalizzabile. Può essere un po 'più lento di yacc / ANTLR, ma può essere abbastanza veloce. L'idea di base: si codifica ogni regola grammaticale in funzione
.Dal momento che si sta parlando con OCaml per l'analisi, la pagina offre una panoramica delle diverse opzioni di analisi per la lingua:
generatori analizzatore del linguaggio OCaml
Se si decide di accontentarsi di ocamlyacc (o menhir), queste esercitazioni possono essere un po 'più facile che il manuale di riferimento:
