digitalmars.D.learn - sort error
- snow (9/9) Jun 28 2013 Hello there,
- bearophile (31/39) Jun 28 2013 If I replace your vector with a tuple (that defines automatically
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (19/27) Jun 28 2013 Yes, what is thrown is an Error. (Error and Exception are different
- snow (10/43) Jun 29 2013 I tried this now:
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (15/45) Jun 29 2013 Not knowing whether it applies to your case, the following is one almost...
- monarch_dodra (24/34) Jun 29 2013 This is the closes thing to what the OP wrote, but it is a *very*
- =?UTF-8?B?QWxpIMOHZWhyZWxp?= (4/7) Jun 29 2013 Agreed. The opCmp that I have written makes sense when there is a
- snow (5/57) Jun 29 2013 Thats a cool way, thanks. But the exception is still coming. Both
- monarch_dodra (7/29) Jun 29 2013 What do you mean "throw -1,0 or 1" ?
Hello there, Ive got the following code http://dpaste.dzfl.pl/e391a268 This code throws me a "Range Exception" in Algorithm.d. If I use a lower number of random vectors, like 100, the code terminates. Also, if I delete the template instruction like this : sort(individuals); I also don't get an exception. Does anybody know, why this is the case?
Jun 28 2013
"bearophile" <bearophileHUGS lycos.com> snow:http://dpaste.dzfl.pl/e391a268 This code throws me a "Range Exception" in Algorithm.d. If I use a lower number of random vectors, like 100, the code terminates. Also, if I delete the template instruction like this : sort(individuals); I also don't get an exception. Does anybody know, why this is the case?If I replace your vector with a tuple (that defines automatically a lexicographic opCmp) the problem seems to disappear: import std.stdio, std.random, std.array, std.algorithm, std.range, std.typecons; alias Vector3D = Tuple!(double,"x", double,"y", double,"z"); alias Individual = Vector3D[]; Vector3D getFitness(in ref Individual individual) pure nothrow { return individual[0]; } bool myComp(in Individual x, in Individual y) { return x.getFitness > y.getFitness; } Vector3D[] initializeRandomVectors(in uint count) { Vector3D[] result; foreach (immutable i; 0 .. count) result ~= Vector3D(uniform(0.0, 11.0), uniform(0.0, 11.0), uniform(0.0, 11.0)); return result; } Individual[] initializeRandomIndividuals() { return 1000.iota.map!(_ => 10.initializeRandomVectors).array; } void main() { auto individuals = initializeRandomIndividuals; individuals.sort!(myComp, SwapStrategy.stable); "finished".writeln; } Bye, bearophile
Jun 28 2013
On 06/28/2013 07:00 AM, snow wrote:> Hello there,Ive got the following code http://dpaste.dzfl.pl/e391a268 This code throws me a "Range Exception" in Algorithm.d. If I use a lower number of random vectors, like 100, the code terminates. Also, if I delete the template instruction like this : sort(individuals); I also don't get an exception.Yes, what is thrown is an Error. (Error and Exception are different hierarchies under Throwable.)Does anybody know, why this is the case?Your opCmp does not provide a complete ordering of objects: int opCmp(ref const Vector3D vec) { if (this.x > vec.x && this.y > vec.y && this.z > vec.z) return 1; if (this.x < vec.x && this.y < vec.y && this.z < vec.z) return -1; return 0; } According to that function, the following two values are neither less than nor greater than the other: // passes: assert(!(Vector3D(1, 2, 3) < Vector3D(2, 1, 3)) && !(Vector3D(1, 2, 3) > Vector3D(2, 1, 3))); Ali
Jun 28 2013
On Friday, 28 June 2013 at 17:07:22 UTC, Ali Çehreli wrote:On 06/28/2013 07:00 AM, snow wrote:> Hello there,I tried this now: int opCmp(ref const Vector3D vec) { if (this.x > vec.x && this.y > vec.y && this.z > vec.z) return 1; return -1; } this should be a total ordering, because a Vector is always greater or smaller, than another, but I still get the same exception.Ive got the following code http://dpaste.dzfl.pl/e391a268 This code throws me a "Range Exception" in Algorithm.d. If I use a lower number of random vectors, like 100, the code terminates. Also, if I delete the template instruction likethis :sort(individuals); I also don't get an exception.Yes, what is thrown is an Error. (Error and Exception are different hierarchies under Throwable.)Does anybody know, why this is the case?Your opCmp does not provide a complete ordering of objects: int opCmp(ref const Vector3D vec) { if (this.x > vec.x && this.y > vec.y && this.z > vec.z) return 1; if (this.x < vec.x && this.y < vec.y && this.z < vec.z) return -1; return 0; } According to that function, the following two values are neither less than nor greater than the other: // passes: assert(!(Vector3D(1, 2, 3) < Vector3D(2, 1, 3)) && !(Vector3D(1, 2, 3) > Vector3D(2, 1, 3))); Ali
Jun 29 2013
On 06/29/2013 05:46 AM, snow wrote:On Friday, 28 June 2013 at 17:07:22 UTC, Ali Çehreli wrote:Unfortunately, no. opCmp must return 0 when the values are considered equal.Your opCmp does not provide a complete ordering of objects: int opCmp(ref const Vector3D vec) { if (this.x > vec.x && this.y > vec.y && this.z > vec.z) return 1; if (this.x < vec.x && this.y < vec.y && this.z < vec.z) return -1; return 0; } According to that function, the following two values are neither less than nor greater than the other: // passes: assert(!(Vector3D(1, 2, 3) < Vector3D(2, 1, 3)) && !(Vector3D(1, 2, 3) > Vector3D(2, 1, 3))); AliI tried this now: int opCmp(ref const Vector3D vec) { if (this.x > vec.x && this.y > vec.y && this.z > vec.z) return 1; return -1; } this should be a total ordering,because a Vector is always greater or smaller, than another, but I still get the same exception.Not knowing whether it applies to your case, the following is one almost correct way of writing opCmp: int opCmp(ref const Vector3D vec) { return cast(int)(x != vec.x ? x - vec.x : (y != vec.y ? y - vec.y : z - vec.z)); } The reason I said "almost" is due to the usual floating point equality comparison warnings. Values that are supposed to be equal may not compare equal due to accumulated earlier floating point calculation errors. Ali
Jun 29 2013
On Saturday, 29 June 2013 at 14:20:05 UTC, Ali Çehreli wrote:
Not knowing whether it applies to your case, the following is
one almost correct way of writing opCmp:
int opCmp(ref const Vector3D vec) {
return cast(int)(x != vec.x
? x - vec.x
: (y != vec.y
? y - vec.y
: z - vec.z));
}
Ali
This is the closes thing to what the OP wrote, but it is a *very*
(IMO) strange way to sort 3D elements.
In basic English, it's:
Whoever has the smallest X, or, if tied,
Whoever has the smallest Y, or, if tied,
Whoever has the smallest Z
OP: Is this how you wanted to sort?
This is strange to me because ordering is (usually) tied to a
norm, where basically, opCmp returns whoever has the smallest
norm. Yet this ordering isn't really tied to any norm.
OP: Can you confirm how you want to sort? Usually, 3DVector are
sorted using any of Euclidian, Manhatan, Maximum or Minimum norm:
https://en.wikipedia.org/wiki/Norm_(mathematics)#Examples
If you can define a "norm" function, then opCmp becomes:
--------
int opCmp(in Vector3D iRhs)
{
auto nLhs = this.norm();
auto nRhs = iRhs.norm();
return (nLhs > nRhs) - (nLhs < nRhs);
}
--------
This is standard "boilerplate" opCmp. It avoids branching too.
Jun 29 2013
On 06/29/2013 07:52 AM, monarch_dodra wrote:This is strange to me because ordering is (usually) tied to a norm, where basically, opCmp returns whoever has the smallest norm. Yet this ordering isn't really tied to any norm.Agreed. The opCmp that I have written makes sense when there is a hierarchy between the members as in "hour, minute, second". Ali
Jun 29 2013
On Saturday, 29 June 2013 at 14:20:05 UTC, Ali Çehreli wrote:On 06/29/2013 05:46 AM, snow wrote:Thats a cool way, thanks. But the exception is still coming. Both solutions throw -1,0 or 1. So my first solution should work, too. Sure that the exception is coming, because of the compare function?On Friday, 28 June 2013 at 17:07:22 UTC, Ali Çehreli wrote:vec.z)Your opCmp does not provide a complete ordering of objects: int opCmp(ref const Vector3D vec) { if (this.x > vec.x && this.y > vec.y && this.z >vec.z)return 1; if (this.x < vec.x && this.y < vec.y && this.z <neither lessreturn -1; return 0; } According to that function, the following two values arevec.z)than nor greater than the other: // passes: assert(!(Vector3D(1, 2, 3) < Vector3D(2, 1, 3)) && !(Vector3D(1, 2, 3) > Vector3D(2, 1, 3))); AliI tried this now: int opCmp(ref const Vector3D vec) { if (this.x > vec.x && this.y > vec.y && this.z >return 1; return -1; } this should be a total ordering,Unfortunately, no. opCmp must return 0 when the values are considered equal.because a Vector is always greater or smaller, than another, but I still get the same exception.Not knowing whether it applies to your case, the following is one almost correct way of writing opCmp: int opCmp(ref const Vector3D vec) { return cast(int)(x != vec.x ? x - vec.x : (y != vec.y ? y - vec.y : z - vec.z)); } The reason I said "almost" is due to the usual floating point equality comparison warnings. Values that are supposed to be equal may not compare equal due to accumulated earlier floating point calculation errors. Ali
Jun 29 2013
On Saturday, 29 June 2013 at 14:54:13 UTC, snow wrote:On Saturday, 29 June 2013 at 14:20:05 UTC, Ali Çehreli wrote:Not for me, Ali's code works.Not knowing whether it applies to your case, the following is one almost correct way of writing opCmp: int opCmp(ref const Vector3D vec) { return cast(int)(x != vec.x ? x - vec.x : (y != vec.y ? y - vec.y : z - vec.z)); } The reason I said "almost" is due to the usual floating point equality comparison warnings. Values that are supposed to be equal may not compare equal due to accumulated earlier floating point calculation errors. AliThats a cool way, thanks. But the exception is still coming.Both solutions throw -1,0 or 1.What do you mean "throw -1,0 or 1" ?So my first solution should work, too. Sure that the exception is coming, because of the compare function?Your code throws an exception for me, ali's doesn't. The only difference is the compare function. So *pretty* much sure, yes. That said, in debug code, there *should* be an assert rather than a dumb range error. This requires an enhancement.
Jun 29 2013