Re: [Boost-users] non-deterministic state diagram

Subject: Re: [Boost-users] non-deterministic state diagram
From: Mike Marchywka (marchywka_at_[hidden])
Date: 2008-10-24 06:28:01

> Date: Fri, 24 Oct 2008 01:26:51 +0000
> From: mavdzee_at_[hidden]
> To: boost-users_at_[hidden]
> 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_at_[hidden]
> 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_102008