Date: Fri, 24 Oct 2008 01:26:51 +0000 From: mavdzee@yahoo.co.uk To: boost-users@lists.boost.org Subject: [Boost-users] non-deterministic state diagram
Hi,
I need to calculate the non-deterministic state diagram from raw data and was wondering how boost can hep me.
It may help to outline the naive approach. As a frequent advocate of re-inventing the wheel and "dirt level" programming, let me see if I can motivate the case for something simple like a 2D array of count_types ( unsigned ints) that gets updated as you record each transition ( indicies are "current" and "next" ) perhaps with running totals for both, leading to 3 int increments and some simple offset calculations per recorded transition. I guess if you need to calculate the float p on each iteration, divisions IIRC are still slow, you might consider some tricks here given a past result and incrementing numerator or denominator by 1 ( no idea what these may be). Now, if your state table is big compared to cache sizes, you could anticipate some thrashing and think about any ways to minimize this ( brute force LUT's are not always the fasted way to go ). For example, it may make sense to keep small count types and make carries exceptional events, allowing larger pieces of primary table to stay in lower level caches, especially if you expect pretty uniform P's. This should all code, and be easy to optimize with "tricks", pretty quickly but what dead ends does it stick you with?
More specific, I have many state transition sequences (lets say up to 100-thousand) that all start at state A, such as: A -> B -> D -> B -> E A -> D -> B -> C -> B A -> E -> D -> F -> D
Now I want to calculate the non-deterministic state diagram with a chance for each transition, and desirable in real-time. For example, for the raw data above, the transition for A -> B is 0.33.
My question is how boost can help me: * Which library is best to represent the state diagram? * Does the library help in calculation of the state diagram from raw data?
Thank you, Andrej
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
_________________________________________________________________ Store, manage and share up to 5GB with Windows Live SkyDrive. http://skydrive.live.com/welcome.aspx?provision=1?ocid=TXT_TAGLM_WL_skydrive...