On 02/06/2016 02:06 AM, Ivan Kazmenko wrote:
On Saturday, 6 February 2016 at 00:59:17 UTC, Andrei Alexandrescu wrote:
On 02/05/2016 06:36 AM, Ivan Kazmenko wrote:
Another interesting task would be to make the function stable, but I
don't see how it is possible with such flat structure.
Under what circumstances isn't your function unstable? -- Andrei
For example, if elements are "value | id", compared by value, then:
0|0, 0|1, 1|2, 0|3, 0|4
is transformed into
0|0, 0|1, 0|4, 0|3, 1|2
and 0|4 is now placed earlier than 0|3, which violates the stability
requirement.
Things can be reordered a bit, but it seems that no possible order
eliminates the need to remember a part of the history.
On the other hand, when we track our whole path in the decision tree
(e.g. at the leaves of Timon Gehr's tree of ifs), we have all
information to make the partition stable.
In any case, finding the shortest-code stable partition-of-5 algorithm
looks like a problem solvable by an automated searcher.
Yah. I think stability should be solved if there's a need/application
for it, e.g. is there a larger algorithm that would be stable if
partition5 were stable?
Regarding the speed, there are different use cases with different
requirements, for example:
1. Primitive types (cheap swap, cheap comparison).
2. Heavy structs A (expensive swap, cheap comparison - e.g., compare one
field of primitive type).
3. Heavy structs B (expensive swap, expensive comparison - e.g., call a
heavy external function).
4. Heavy classes (cheap swap - pointers only, expensive comparison).
So there's perhaps no single best solution.
Yah, good point. I should also add that more comparisons generally mean
more branching and more code. -- Andrei
