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.
