Hi,
Can you please tell how to rewrite this code to D?

using System;
using System.Linq;
class Sort
{
    static void Main()
    {
        int[] arr = { 7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1, 1, 1, 2, 2, 8, 5, 8, 8 };
        Console.WriteLine(string.Join(" ", arr.OrderByDescending(x => arr.Count(y => y == x)).ThenBy(x => x)));
        // prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 7 7 0
    }
}

I want to sort the array in descending order of the number of elements in ascending order of elements.

Dennis Ritchie:

>         int[] arr = { 7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1, 1, 1, 2, 2, 8, 5, 8, 8 };
>         Console.WriteLine(string.Join(" ", arr.OrderByDescending(x => arr.Count(y => y == x)).ThenBy(x => x)));
>         // prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 7 7 0

One solution:


void main() {
    import std.stdio, std.algorithm, std.typecons;

    auto arr = [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1, 1, 1, 2, 2, 8, 5, 8, 8];

    arr
    .schwartzSort!(x => tuple(-arr.count!(y => y == x), x))
    .writeln;
}


Bye,
bearophile

>     .schwartzSort!(x => tuple(-arr.count!(y => y == x), x))

But calling "count" for each item is not efficient (in both C# and D). If your array is largish, then you need a more efficient solution.

Bye,
bearophile

On 03/25/2015 12:01 PM, bearophile wrote:

> bearophile

Do you know the story about groupBy? I see it in the documentation but my git head does not have it:

  http://dlang.org/phobos/std_algorithm_iteration.html#.groupBy

Ali

Ali Çehreli:

> Do you know the story about groupBy?

It's a long messy story. Look for it with another name, like chunkBy or something like that.

Bye,
bearophile

On Wednesday, 25 March 2015 at 19:01:43 UTC, bearophile wrote:
> One solution:

Thanks.

On Wednesday, 25 March 2015 at 19:03:27 UTC, bearophile wrote:
> But calling "count" for each item is not efficient (in both C# and D). If your array is largish, then you need a more efficient solution.

A more effective solution for C ++:

#include <iostream>
#include <vector>
#include <range/v3/all.hpp>

int main() {
  using namespace ranges;

  auto rng = istream<int>( std::cin )
           | to_vector
           | action::sort
           | view::group_by( std::equal_to<int>() )
           | copy
           | action::stable_sort( []( const auto& e1, const auto& e2 ) { return distance( e1 ) < distance( e2 ); } );
  std::cout << ( rng );
}

On Wednesday, 25 March 2015 at 19:32:43 UTC, Dennis Ritchie wrote:
> On Wednesday, 25 March 2015 at 19:01:43 UTC, bearophile wrote:
>> One solution:
>
> Thanks.
>
> On Wednesday, 25 March 2015 at 19:03:27 UTC, bearophile wrote:
>> But calling "count" for each item is not efficient (in both C# and D). If your array is largish, then you need a more efficient solution.
>
> A more effective solution for C ++:
>
> #include <iostream>
> #include <vector>
> #include <range/v3/all.hpp>
>
> int main() {
>   using namespace ranges;
>
>   auto rng = istream<int>( std::cin )
>            | to_vector
>            | action::sort
>            | view::group_by( std::equal_to<int>() )
>            | copy
>            | action::stable_sort( []( const auto& e1, const auto& e2 ) { return distance( e1 ) < distance( e2 ); } );
>   std::cout << ( rng );
> }

Here is my take at it:

1. A more verbose comparison function:

-----
import std.algorithm, std.conv, std.range, std.stdio;
void main () {
    auto arr = [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1,
1, 1, 2, 2, 8, 5, 8, 8];
    arr.sort !((x, y) => arr.count (x) > arr.count (y) ||
        (arr.count (x) == arr.count (y) && x < y))
        .map !(to !(string))
        .join (" ")
        .writeln;
    // prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 0 7 7
}
-----

This surprised me by printing ...0 7 7 instead of ...7 0 0, which is plain wrong.  Reproducible in 2.066 and 2.067 on win32.  With -debug, it triggers an assertion in Phobos:

-----
core.exception.AssertError@c:\Tools\dmd\windows\bin\..\..\src\phobos\std\algorithm\sorting.d(900): Failed to sort range of type int[]
----------------
0x0041708D in _d_assert_msg
0x00416C2F in void rt.dmain2._d_run_main(int, char**, extern (C) int function(char[][])*).runAll()
0x00416B47 in _d_run_main
0x00416848 in main
0x76AD33CA in BaseThreadInitThunk
0x770C9ED2 in RtlInitializeExceptionChain
0x770C9EA5 in RtlInitializeExceptionChain
-----

Will file an issue soon.

2. As above, but use the other sorting algorithm:

-----
import std.algorithm, std.conv, std.range, std.stdio;
void main () {
    auto arr = [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1,
1, 1, 2, 2, 8, 5, 8, 8];
    arr.sort !((x, y) => arr.count (x) > arr.count (y) ||
        (arr.count (x) == arr.count (y) && x < y), SwapStrategy.stable)
        .map !(to !(string))
        .join (" ")
        .writeln;
    // prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 7 7 0
}
-----

All fine here.

3. Sort by comparing a transform of the data, for some reason disguised by the name schwartzSort:

-----
import std.algorithm, std.conv, std.range, std.stdio, std.typecons;
void main () {
    auto arr = [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1,
1, 1, 2, 2, 8, 5, 8, 8];
    arr.sort ()
        .schwartzSort !(x => tuple (-arr.count (x), x))
        .map !(to !(string))
        .join (' ')
        .writeln;
    // prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 7 7 0
}
-----

Similar to bearophile's solution.
(1) For me, the name of the function is obscure.  Something like sortBy would be a lot easier to find than schwartzSort.
(2) It does not offer multiple transforms (sort by this, then by that).  This seems doable as a Phobos enhancement.

4. Sort by a few binary predicates in one pass.

-----
import std.algorithm, std.conv, std.range, std.stdio;
void main () {
    auto arr = [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1,
1, 1, 2, 2, 8, 5, 8, 8];
    arr.multiSort !((a, b) => arr.count (a) > arr.count (b),
        (a, b) => a < b);
    arr.map !(to !(string))
        .join (' ')
        .writeln;
    // prints 1 1 1 1 1 3 3 3 3 3 5 5 5 5 8 8 8 2 2 7 7 0
}
-----

Two concerns here.
(1) It returns void instead of a sorted range, so can't be chained as the others.  This seems doable as a Phobos enhancement.  Or is there a reason not to?
(2) The documentation says it is more efficient than the first version in the number of comparisons (verbose lambda with plain sort) [1], but I don't get how it is possible: unless we know than (not pred1(a,b)) and (not !pred1(a,b)), we can not proceed by evaluating pred2(a,b).

Ivan Kazmenko.

On Wednesday, 25 March 2015 at 20:02:20 UTC, Ivan Kazmenko wrote:
> (2) The documentation says it is more efficient than the first version in the number of comparisons (verbose lambda with plain sort) [1], but I don't get how it is possible: unless we know than (not pred1(a,b)) and (not !pred1(a,b)), we can not proceed by evaluating pred2(a,b).

[1] http://dlang.org/phobos/std_algorithm_sorting.html#.multiSort

Dennis Ritchie:

> A more effective solution for C ++:
>
> #include <iostream>
> #include <vector>
> #include <range/v3/all.hpp>
>
> int main() {
>   using namespace ranges;
>
>   auto rng = istream<int>( std::cin )
>            | to_vector
>            | action::sort
>            | view::group_by( std::equal_to<int>() )
>            | copy
>            | action::stable_sort( []( const auto& e1, const auto& e2 ) { return distance( e1 ) < distance( e2 ); } );
>   std::cout << ( rng );
> }


This is still not very efficient (perhaps the last sorting has to be stable):

void main() {
    import std.stdio, std.algorithm, std.typecons, std.array;

    [7, 5, 7, 3, 3, 5, 3, 3, 0, 3, 1, 1, 5, 1, 1, 1, 2, 2, 8, 5, 8, 8]
    .sort()
    .groupBy!((a, b) => a == b)
    .map!array
    .array
    .sort!q{a.length > b.length}
    .joiner
    .writeln;
}


Bye,
bearophile

Ivan Kazmenko:

> (1) For me, the name of the function is obscure.  Something like sortBy would be a lot easier to find than schwartzSort.

I've asked to change the name of that function for years. But Andrei Alexandrescu is a adamantly against changing that pet name he has chosen. This is irrational behavour:
https://issues.dlang.org/show_bug.cgi?id=4909

There's lot of way to go for Phobos. And the only want to find holes, missed opportunities, sub-optimal performance spots, missing functions and features, and bad APIs and bad names is to actually try to use Phobos, like we are doing in this thread.

Bye,
bearophile