Thread overview | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
March 25, 2015 C# to D | ||||
---|---|---|---|---|
| ||||
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. |
March 25, 2015 Re: C# to D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dennis Ritchie | 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
|
March 25, 2015 Re: C# to D | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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
|
March 25, 2015 Re: C# to D | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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 |
March 25, 2015 Re: C# to D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ali Çehreli | 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
|
March 25, 2015 Re: C# to D | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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 ); } |
March 25, 2015 Re: C# to D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dennis Ritchie | 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. |
March 25, 2015 Re: C# to D | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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 |
March 25, 2015 Re: C# to D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dennis Ritchie | 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
|
March 25, 2015 Re: C# to D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ivan Kazmenko | 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 |
Copyright © 1999-2021 by the D Language Foundation