On Mon, Aug 10, 2015 at 04:43:01PM -0400, Paul Davis wrote: > it provides output indicating the logic decisions that lead to the > execution order.
I spent most of the day trying to convinve myself that I was overlooking something. But in the end the conclusion of all that work is this: * The algorithm used by Jack1 to determine the order of * running clients in each cycle is fundamentally flawed. The reason in mathematical terms is quite simple. Both the relations 'A feeds B' and its transitive closure 'A feeds B, maybe indirectly' define only a *partial order* on the set of clients. Now all classical sorting algorithms, including the merge sort used in this case, assume a *total order* of the set to be sorted, and may not produce the correct result if only a partial order is defined. It's easy to see this in a less abstract way. All classical sorting algos are designed to reduce the number of compare() calls. For example, if they find that a == b and a == c they will in most cases avoid testing b against c, since under total order it must be true that b == c. Now if a '0' return from the compare() function does not mean equality but rather 'not connected' things change. Using the example above, you *can not* conclude that b and c are not connected. So all it takes is a few unconnected clients or two or more independent chains to increase the probability that a classical sort algorithm will fail to produce a correct sequence. I actually worked out the example I posted yesterday with pencil and paper, including all the merge sorts. This produced exactly the results posted. So there is no bug in the current code, it is just the wrong algorithm. To find a linear sequence preserving the order of a partially ordered set you need what is known as 'topological sorting'. It's usually implemente using depth-first search (DFS) with post-order output. Ciao, -- FA A world of exhaustive, reliable metadata would be an utopia. It's also a pipe-dream, founded on self-delusion, nerd hubris and hysterically inflated market opportunities. (Cory Doctorow) _______________________________________________ Linux-audio-dev mailing list Linux-audio-dev@lists.linuxaudio.org http://lists.linuxaudio.org/listinfo/linux-audio-dev