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

On 02/05/2016 04:35 PM, Xinok wrote:
> It's a cool trick but I would be surprised if this were actually faster.

That changes every few years. Last time I measured it was slower. -- Andrei

On 02/05/2016 04:42 PM, Xinok wrote:
> Very nice! I'm curious, to both you and Timon, how did you go about
> writing these and coming up with the solutions? I'm not sure if I could
> come up with these results myself and so quickly at that.

I was thinking the same exact things. -- Andrei

On 02/05/2016 07:59 PM, 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

I meant "is your function unstable". Double negation, but if you speak Russian those count as one :o). -- Andrei

On 02/04/2016 03:30 PM, Timon Gehr wrote:
> At most 6 comparisons, <=3 swaps, idempotent (optimal number of swaps):

What is the minimum number of comparisons? Thx! -- Andrei
P.S. The sythesized searcher is genius.

On 02/04/2016 03:30 PM, Timon Gehr wrote:
> At most 6 comparisons, <=3 swaps, idempotent (optimal number of swaps):

Oh, also: could you let that bad boy run and let it find anything that does idempotent partition in 6 compares and 0-7 swaps? Then slowly tighten the number of swaps until you find the best balance between number of swaps and code size. -- Andrei

On 02/06/2016 02:39 AM, Andrei Alexandrescu wrote:
> On 02/04/2016 03:30 PM, Timon Gehr wrote:
>> At most 6 comparisons, <=3 swaps, idempotent (optimal number of swaps):
>
> What is the minimum number of comparisons? Thx! -- Andrei

There is no partition algorithm that uses <= 5 comparisons in all cases.
(If that is what you're asking.)

> P.S. The sythesized searcher is genius.

Thanks!

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.

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.

On Saturday, 6 February 2016 at 07:06:27 UTC, 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

The code I used to check stability:
http://dpaste.dzfl.pl/2b950cb3e5d8

The "y" and "n" at end of lines are "yes"/"no", as in "stable"/"unstable".

On Friday, 5 February 2016 at 21:42:41 UTC, Xinok wrote:
> On Friday, 5 February 2016 at 15:13:56 UTC, tn wrote:
>> On Thursday, 4 February 2016 at 20:30:57 UTC, Timon Gehr wrote:
>>> At most 6 comparisons, <=3 swaps, idempotent (optimal number of swaps):
>>>
>>> ...
>>>
>>
>> Inspired by this, I made four other versions of the function that are shorter but make more swaps (at most 4, 6, 7 and 8 swaps respectively). Each makes 6 comparisons and should be idempotent.
>>
>> http://dpaste.dzfl.pl/1c53d8f432f7
>>
>> ...
>
> Very nice! I'm curious, to both you and Timon, how did you go about writing these and coming up with the solutions? I'm not sure if I could come up with these results myself and so quickly at that.

I basically just started from Timons solution and made is smaller by replacing branches by swaps. The outermost structure of Timons code looks like this:

  if (a[0] < a[1]) {
    do something 1
  } else {
    do something 2
  }

I replaced the above by

  if (a[0] < a[1]) {
    swap(a[0], a[1]);
  }
  do something 1

So adding one swap just about halved the size of the code. Now "do something 1" again has two branches:

  if (a[2] < a[3]) {
    do something 1.1
  } else {
    do something 1.2
  }

So we can do the same trick again and replace it by

  if (a[2] < a[3]) {
    swap(a[2], a[3]);
  }
  do something 1.1

And so on. (When doing subsequent swaps we also need to make sure to not break the conditions achieved by the previous swaps.)

However, the swap of a[0] and a[1] in the first replacement would break idempotence, so I also had to change which elements are compared (and swapped). So in my code we first compare a[0] and a[2], then a[1] and a[3], and so on.