www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - C# to D

reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
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.
Mar 25 2015
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Mar 25 2015
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
     .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
Mar 25 2015
prev sibling next sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Mar 25 2015
parent "bearophile" <bearophileHUGS lycos.com> writes:
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
Mar 25 2015
prev sibling parent reply "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
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 ); }
Mar 25 2015
next sibling parent reply "Ivan Kazmenko" <gassa mail.ru> writes:
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\algor thm\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.
Mar 25 2015
next sibling parent "Ivan Kazmenko" <gassa mail.ru> writes:
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
Mar 25 2015
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Mar 25 2015
parent "Ivan Kazmenko" <gassa mail.ru> writes:
On Wednesday, 25 March 2015 at 20:17:57 UTC, bearophile wrote:
 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.
On the bright side, the list under "Sorting" at the docs http://dlang.org/phobos/std_algorithm.html is short enough for the curious to just look at the entries and find it. The specific page http://dlang.org/phobos/std_algorithm_sorting.html does even contain a link explaining what that is, but I'd propose -"Sorts with the help of the Schwartzian transform." +"Sorts by key predicate with the help of the Schwartzian transform." or some similar wording.
Mar 25 2015
prev sibling parent "Ivan Kazmenko" <gassa mail.ru> writes:
On Wednesday, 25 March 2015 at 20:02:20 UTC, Ivan Kazmenko wrote:
 Will file an issue soon.
Here it is: https://issues.dlang.org/show_bug.cgi?id=14340 And another one, a 2.067 regression: https://issues.dlang.org/show_bug.cgi?id=14341
Mar 25 2015
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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
Mar 25 2015
parent reply "Ivan Kazmenko" <gassa mail.ru> writes:
On Wednesday, 25 March 2015 at 20:09:53 UTC, bearophile wrote:
 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
5. An efficient version would be to count the integers by using an associative array (or a redBlackTree for guaranteed upper bound) and then use these. It is O (n) time and memory spent in precalculation phase and O (n log n) time for sorting. Looks like there is no way to write that as a chain of transforms, but many optimizations do require manual labor. ----- 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]; int [int] counts; foreach (e; arr) { counts[e]++; } arr.multiSort !((a, b) => counts[a] > counts[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 } ----- Also, some of my previously posted codes do not compile under 2.066 or earlier unless you replace .join (' ') with .join (" ") there.
Mar 25 2015
next sibling parent "Dennis Ritchie" <dennis.ritchie mail.ru> writes:
On Wednesday, 25 March 2015 at 20:09:53 UTC, bearophile wrote:
 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;
 }
On Wednesday, 25 March 2015 at 20:53:43 UTC, Ivan Kazmenko wrote:
 5. An efficient version would be to count the integers by using 
 an associative array (or a redBlackTree for guaranteed upper 
 bound) and then use these.  It is O (n) time and memory spent 
 in precalculation phase and O (n log n) time for sorting.  
 Looks like there is no way to write that as a chain of 
 transforms, but many optimizations do require manual labor.

 -----
 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];
     int [int] counts;
     foreach (e; arr) {
         counts[e]++;
     }
     arr.multiSort !((a, b) => counts[a] > counts[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
 }
 -----
Thank you very much, Ivan and bearophile! On Wednesday, 25 March 2015 at 20:53:43 UTC, Ivan Kazmenko wrote:
 Also, some of my previously posted codes do not compile under 
 2.066 or earlier unless you replace .join (' ') with .join (" 
 ") there.
I have long been updated :)
Mar 25 2015
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Ivan Kazmenko:

     arr.map !(to !(string))
         .join (" ")
         .writeln;
I suggest to not put a space before the bang (!), because it's confusing for me. Also, "arr.map !(to !(string))" is better written "arr.map!text". But even better is to use the range formatting of writefln, avoiding the "map", "to", and "join", something like: writefln("%(%d %)", arr); Bye, bearophile
Mar 25 2015