Boost Users :
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
>> 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,
>> Boost-users mailing list
> Store, manage and share up to 5GB with Windows Live SkyDrive.
Want to read Hotmail messages in Outlook? The Wordsmiths show you how.
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net