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

Subject: Re: [Boost-users] non-deterministic state diagram
From: Mike Marchywka (marchywka_at_[hidden])
Date: 2008-10-26 22:08:19

> From: marchywka_at_[hidden]
> To: boost-users_at_[hidden]
> Subject: RE: [Boost-users] non-deterministic state diagram
> Date: Fri, 24 Oct 2008 06:28:01 -0400
>
>
>
>
>> 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?
>

Ok, no interest yet. Let's assume you have 1<>
>> 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

_________________________________________________________________
Want to read Hotmail messages in Outlook? The Wordsmiths show you how.
http://windowslive.com/connect/post/wedowindowslive.spaces.live.com-Blog-cns!20EE04FBC541789!167.entry?ocid=TXT_TAGLM_WL_hotmail_092008