How to speed up a CYK Algorithm in C++? -

i implement cyk algorithm in c/c++, available on various websites pseudo-code doesn't answer how implement efficiently. wrote version uses stl structures map , sets, it's slow. thinking improve implementation using binary operations, don't know how store table sets. lets have 8 symbols non terminals , 26 terminals. thinking using table of unsigned chars (2^8 -> 8 positions 0-1) storing information productions, don't know how store it.

could give me or clue?

you don't provide many details, simple implementation (even pseudo code) lot give hints.

from wikipedia:

let input string s consisting of n characters: a1 ... an. let

for can use simple string, or vector of chars

the grammar contain r nonterminal symbols r1 ... rr.

i store nonterminal symbols in array of bools std::array nonterminal {}; since yu have characters can initialize position corresponding char, true.

nonterminal[static_cast('c')] = true; same terminal , have fast mechanism.

this grammar contains subset rs set of start symbols. let p[n,n,r] array of booleans. initialize elements of p false. each = 1 n each unit production rj -> ai set p[i,1,j] = true each = 2 n -- length of span each j = 1 n-i+1 -- start of span each k = 1 i-1 -- partition of span each production ra -> rb rc if p[j,k,b] , p[j+k,i-k,c] set p[j,i,a] = true if of p[1,n,x] true (x iterated on set s, s indices rs) s member of language else s not member of language

the algorithm seems pretty straightforward after that. make sure not initialize temporary values inside tight loops , you'll fine.