digitalmars.D.learn - C# to D
- Dennis Ritchie (18/18) Mar 25 2015 Hi,
- bearophile (12/18) Mar 25 2015 One solution:
- bearophile (5/6) Mar 25 2015 But calling "count" for each item is not efficient (in both C#
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (5/6) Mar 25 2015 Do you know the story about groupBy? I see it in the documentation but
- bearophile (5/6) Mar 25 2015 It's a long messy story. Look for it with another name, like
- Dennis Ritchie (18/22) Mar 25 2015 Thanks.
- Ivan Kazmenko (94/116) Mar 25 2015 Here is my take at it:
- Ivan Kazmenko (2/7) Mar 25 2015 [1] http://dlang.org/phobos/std_algorithm_sorting.html#.multiSort
- bearophile (11/13) Mar 25 2015 I've asked to change the name of that function for years. But
- Ivan Kazmenko (12/23) Mar 25 2015 On the bright side, the list under "Sorting" at the docs
- Ivan Kazmenko (5/6) Mar 25 2015 Here it is:
- bearophile (17/32) Mar 25 2015 This is still not very efficient (perhaps the last sorting has to
- Ivan Kazmenko (27/62) Mar 25 2015 5. An efficient version would be to count the integers by using
- Dennis Ritchie (5/45) Mar 25 2015 Thank you very much, Ivan and bearophile!
- bearophile (9/12) Mar 25 2015 I suggest to not put a space before the bang (!), because it's
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
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
"bearophile" <bearophileHUGS lycos.com>
.schwartzSort!(x => tuple(-arr.count!(y => y == x), x))
and D). If your array is largish, then you need a more efficient
solution.
Bye,
bearophile
Mar 25 2015
On 03/25/2015 12:01 PM, bearophile wrote:bearophileDo you know the story about groupBy? I see it in the documentation but my git head does not have it: Ali
Mar 25 2015
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
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: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
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: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.One solution:Thanks. On Wednesday, 25 March 2015 at 19:03:27 UTC, bearophile wrote: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
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).
Mar 25 2015
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
On Wednesday, 25 March 2015 at 20:17:57 UTC, bearophile wrote:Ivan Kazmenko: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.(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.
Mar 25 2015
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
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
On Wednesday, 25 March 2015 at 20:09:53 UTC, bearophile wrote:Dennis Ritchie: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.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
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
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