Quais são algumas técnicas de análise exóticos?
https://stackoverflow.com/questions/940984
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu estive analisando históricos de mãos de poker para o ano passado e aprendi bastante coisa sobre a análise em geral.
Começamos com expressões regulares, mas rapidamente percebeu que não iria escalar facilmente. Nós pulamos línguas de Ruby para c ++ e, finalmente veio aos apertos que era o algorithim que tinha que mudar.
Pegamos boost :: Espírito e assisti a nossa velocidade aumentará dramaticamente em pedidos de mais de 10 vezes a nossa velocidade original. Em seguida, pulou para java e está usando antlr para criar gramáticas para cada site. Este é definitivamente o método mais rápido ainda e é muito completo que é bom porque você sabe exatamente onde você está, em termos de uma gramática 'completa'. Infelizmente, eu passei uma incrível quantidade de tempo que trabalham com estas gramáticas -. Eles trabalham muito muito bem, mas ainda não perfeitamente
De qualquer forma, o suficiente com o fundo para a questão em apreço - existem técnicas 'exóticos' ou menos conhecidos para analisar que eu não estou ciente de? Eu só sei de lexing / analisar uma gramática e o outro método regex / loop inferior.
Para aqueles de vocês que não estão familiarizados com históricos de mãos de poker eu vou postar um para que você pode dizer o que a estrutura é.
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
Estou bem ciente de outros métodos de recolha da informação (tais como screen-scraping e dll injeção), mas a necessidade de transformar o histórico de mãos em dados estruturados ainda está lá, então eu estou olhando apenas para métodos que agarrar a informações como regex / gramáticas ...
Eu acho que se eu não encontrar algo que eu vou reescrever nossas gramáticas com ocamllex / ocamlyacc.
update
fyi: velocidade regexen foi ~ 60 mãos / seg enquanto as gramáticas foram processando mais de 600 mãos / seg ... a mão inteira é transformada em xml depois os dados são tudo resolvido ... há entre 20-30 regexes necessário (na última contagem) para cada site que você deseja analisar .... cada site no lado da gramática tem a sua própria gramática com quantidades ímpios de regras lexer / analisador (mas é o tamanho do código ainda menor)
Eu tenho o livro dragão e tenho lido através dele - que rejeitou o meu interesse em utilizar o ocamllex / ocamlyacc .... velocidade é o nome do jogo aqui ..
Solução
Se você estiver olhando para maximizar a velocidade, então você pode fazer melhor usar OcamlYacc / FsYacc sobre ANTLR. OcamlYacc cria (1) analisadores LL, que normalmente têm melhor desempenho do que LL ANTLR-style (*) analisadores (alguém pode me corrija se eu estiver errado) . [Edit para adicionar:] parece que alguém me corrigiu: OCamlYacc produz LALR (1) analisadores. Eu não posso dizer com alguma confiança se analisadores OcamlYacc são mais rápidos que os analisadores ANTLR.
OCaml / F # são muito boas linguagens para a construção de uma DSL, e na minha opinião muito mais apropriado para o trabalho de Java, principalmente porque a sua ridiculamente fácil criar e atravessar um AST representada como uma estrutura de dados união. I recommed este tutorial que demonstra como analisar SQL em F #.
Outras dicas
Uma vez que você está procurando exótico, leia este artigo sobre de Vaughan Pratt Top Down Operador Precedência ...
Analisador combinators é um método muito popular de construção de analisadores em linguagens funcionais, como Haskell.
Você tem que se perguntar se o que você realmente quer fazer é brincar com analisadores (reconhecidamente divertido, e que eu mesmo prefiro) ou se você quiser realmente começar o trabalho feito em seu bot poker. Muito provavelmente, análise técnicas exóticas são um exagero para o que você precisa. Basta escolher uma linguagem rápida com algumas simples, fácil de usar analisadores. Você provavelmente deve ser capaz de processar 10k mãos / seg com reta C + flex. Ou, ocamllex + ocamlyacc deve ser mais do que suficiente. Se você tem que hadoopify seu código eu acho que você está fazendo algo errado. Rede de latência deve acabar por ser o seu verdadeiro gargalo, não analisar velocidade. Que tipo de máquina que você está executando isso em?
Outra alternativa é usar um gerador de analisador para gerar automaticamente uma tabela de análise e, em seguida, entregar otimização que, ou a mão otimização da NFA (você provavelmente não vai economizar muito, porém, e a troca no tempo programador provavelmente não vale a pena ). Combinator análise é provavelmente vai ser mais lento.
Em média, para uma determinada gramática LL potência equivalente será mais lento do que LALR. Em particular, se as mãos de poker são realmente parseable por um analisador LALR, então bisonte / byacc + Flex vai bater ANTLR mãos para baixo, cada vez. Estou pessoalmente muito feliz com menhir, embora seja uma cadela furiosa e meio para começar a trabalhar com godi + ocamlbuild.
- Nico
Leia o Livro Dragon: http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/ dp / 0201100886
Ele cobre análise léxica e sintática em profundidade (entre outros tópicos). Você pode usar isso para ajudar você a entender a "linguagem" que você está tentando analisar para determinar a melhor maneira de fazê-lo.
Wikipedia tem uma boa visão geral sobre os tipos de analisador, aqui: http://en.wikipedia.org/wiki/Parser
E uma comparação sobre ferramentas de gerador de analisador, aqui: http://en.wikipedia.org/wiki / Comparison_of_parser_generators
GLR é uma espécie de menos conhecido método que é interessante porque lida com ambiguidades de linguagem.
recursiva Descida de análise trabalho poder para você. É muito personalizável. Pode ser um pouco mais lento do que yacc / antlr, mas pode ser rápido o suficiente. A idéia básica: Você codificar cada regra gramatical como uma função
.Uma vez que você está falando sobre o uso OCaml para análise, esta página dá uma visão geral de diferentes opções de análise para esse idioma:
Parser geradores para a linguagem OCaml
Se você decidir se contentar com ocamlyacc (ou menhir), estes tutoriais pode ser um pouco mais fácil do que a referência manual:
