Re: Failed to sort range
On Tuesday, 28 May 2013 at 20:43:32 UTC, Ali Çehreli wrote: On 05/28/2013 12:47 PM, Anthony Goins wrote: > sort!("a > This worked for me with the code at your link. I've noticed that too. The reason that works is because in that case it uses Tim Sort. Apparently, the Tim Sort algorithm does not expose the bugs that were in the code. Ali I believe the issues with opIndex and opSlice caused the bug. Now, those are fixed, and I guess it's safe to say that range interface is correct. Although, I remember a discussion in the NG about somewhat "standardized" testing facilities for ranges ( http://forum.dlang.org/thread/20130321130858.3ef4@unknown ). Precisely the semantic/runtime behavior, to supplement isSomeRange templates family. Do you, guys know, was there any activities on it?
Re: Failed to sort range
On 05/28/2013 12:47 PM, Anthony Goins wrote: > sort!("a > This worked for me with the code at your link. I've noticed that too. The reason that works is because in that case it uses Tim Sort. Apparently, the Tim Sort algorithm does not expose the bugs that were in the code. Ali
Re: Failed to sort range
On Tuesday, 28 May 2013 at 12:57:12 UTC, Sergei Nosov wrote: Hi! I'm trying to implement an array, which uses malloc to allocate memory. Also, I want to implement a random access range interface for it. That went pretty well, until I tried to sort it. Sorting function asserted "Failed to sort range of type Array!(int)." I've spent quite some time trying to figure out what's going on with no success. The implementation can be found at: https://gist.github.com/snosov1/5662471 I used DMD64 D Compiler v2.062 and LDC - the LLVM D compiler (trunk): based on DMD v2.062 and LLVM 3.2svn on Ubuntu. Phobos version was the one that came with the dmd compiler. Does anyone have any ideas what's wrong with the code I've provided? sort!("a
Re: Failed to sort range
On Tuesday, 28 May 2013 at 18:38:01 UTC, Ali Çehreli wrote: On 05/28/2013 11:31 AM, Ali Çehreli wrote: > @property Array!T opSlice(size_t i, size_t j) { > // ... > ret.front_ = i; > > I feel like the initialization of front_ above is not right either. > Imagine quick sort where we are slicing the right-hand side of a range > as [0..10], which has already been sliced before. Setting front_ to 0 > would be wrong because then opIndex would still be counting from the > beginning of the original elements. My explanation is wrong but I think there is still a bug. Imagine we are in the right-hand range that has been sliced as [10..$]. Now front_ is 10 and all is good: s[0] provides the arr[10] of the original array. Now imagine our slice again by [5..$]. s_further[0] should provide arr[15] of the original array but your setting front_ to 5 would unfortunately provide arr[5]. Ali Yes, exactly. I believe, the same fix should be applied here: front_ + i, front_ + j. It passes the sorting test. Thank you so much, Ali. Feels like to be back in school again.
Re: Failed to sort range
On 05/28/2013 11:31 AM, Ali Çehreli wrote: > @property Array!T opSlice(size_t i, size_t j) { > // ... > ret.front_ = i; > > I feel like the initialization of front_ above is not right either. > Imagine quick sort where we are slicing the right-hand side of a range > as [0..10], which has already been sliced before. Setting front_ to 0 > would be wrong because then opIndex would still be counting from the > beginning of the original elements. My explanation is wrong but I think there is still a bug. Imagine we are in the right-hand range that has been sliced as [10..$]. Now front_ is 10 and all is good: s[0] provides the arr[10] of the original array. Now imagine our slice again by [5..$]. s_further[0] should provide arr[15] of the original array but your setting front_ to 5 would unfortunately provide arr[5]. Ali
Re: Failed to sort range
On 05/28/2013 11:19 AM, Sergei Nosov wrote: > Do you mean it's a good idea > to separate storage and access (via range) to the container? Like > std.container's containers (heh) have nested Range struct? Yes, that is generally the right approach. Note that built-in arrays have a similar design which may not be obvious: The storage is in an array that is owned by the D runtime. (The exception is fixed-length arrays where the entire array may be on the stack.) Then, the elements are accessed by slices, which are ranges. Consuming the slice does not invalidate the consumed elements (as long as there are other accesses to those elements.) >> ref T opIndex(size_t idx) { >> return vec_[front_ + idx]; >> } >> >> It is a start but still not the solution. Sorry... :/ > > That's obviously a bug, thanks. But, yeah, not the last one =) @property Array!T opSlice(size_t i, size_t j) { // ... ret.front_ = i; I feel like the initialization of front_ above is not right either. Imagine quick sort where we are slicing the right-hand side of a range as [0..10], which has already been sliced before. Setting front_ to 0 would be wrong because then opIndex would still be counting from the beginning of the original elements. Ali
Re: Failed to sort range
Thx, Ali! 1) First, an observation: This Array design conflates the concepts of container and range. If there are actual elements that are being stored (as opposed to elements being generated), it is better tha a range merely provides access to those elements. popFront should consume the range, not the container. (Unless it is some special type of range with the responsibility of removing elements from the container.) I'm not sure I understand this correctly. Do you mean it's a good idea to separate storage and access (via range) to the container? Like std.container's containers (heh) have nested Range struct? 2) As a minor comment, "back" usually means the last element but your back_ has the meaning of one-past-the-last element. Yeah, that's probably a not-so-good name. 3) You have to rethink the indexing as well. opIndex indexes directly on vec_: ref T opIndex(size_t idx) { return vec_[idx]; } However, we may be on a slice which has already been sliced before (as is the case in quick sort, which SwapStrategy.unstable uses). So, I think opIndex should add front_ to idx: ref T opIndex(size_t idx) { return vec_[front_ + idx]; } It is a start but still not the solution. Sorry... :/ That's obviously a bug, thanks. But, yeah, not the last one =) I updated the gist. And also, replaced the malloc call with new. The behavior is the same.
Re: Failed to sort range
On 05/28/2013 05:57 AM, Sergei Nosov wrote: Hi! I'm trying to implement an array, which uses malloc to allocate memory. Also, I want to implement a random access range interface for it. That went pretty well, until I tried to sort it. Sorting function asserted "Failed to sort range of type Array!(int)." I've spent quite some time trying to figure out what's going on with no success. The implementation can be found at: https://gist.github.com/snosov1/5662471 I used DMD64 D Compiler v2.062 and LDC - the LLVM D compiler (trunk): based on DMD v2.062 and LLVM 3.2svn on Ubuntu. Phobos version was the one that came with the dmd compiler. Does anyone have any ideas what's wrong with the code I've provided? 1) First, an observation: This Array design conflates the concepts of container and range. If there are actual elements that are being stored (as opposed to elements being generated), it is better tha a range merely provides access to those elements. popFront should consume the range, not the container. (Unless it is some special type of range with the responsibility of removing elements from the container.) 2) As a minor comment, "back" usually means the last element but your back_ has the meaning of one-past-the-last element. 3) You have to rethink the indexing as well. opIndex indexes directly on vec_: ref T opIndex(size_t idx) { return vec_[idx]; } However, we may be on a slice which has already been sliced before (as is the case in quick sort, which SwapStrategy.unstable uses). So, I think opIndex should add front_ to idx: ref T opIndex(size_t idx) { return vec_[front_ + idx]; } It is a start but still not the solution. Sorry... :/ Ali
Re: Failed to sort range
On Tuesday, 28 May 2013 at 13:41:19 UTC, bearophile wrote: Sergei Nosov: That went pretty well, until I tried to sort it. Sorting function asserted "Failed to sort range of type Array!(int)." If you take a look a the implementation of Phobos sort, you see there is a recently added runtime test mostly meant to catch wrongly implemented comparison functions, like q{a <= b} instead of q{a < b}. Maybe that's the one that has fired. But I don't know why. Bye, bearophile I don't think that is the case, since I use the default comparison function for ints.
Re: Failed to sort range
Sergei Nosov: That went pretty well, until I tried to sort it. Sorting function asserted "Failed to sort range of type Array!(int)." If you take a look a the implementation of Phobos sort, you see there is a recently added runtime test mostly meant to catch wrongly implemented comparison functions, like q{a <= b} instead of q{a < b}. Maybe that's the one that has fired. But I don't know why. Bye, bearophile
Re: Failed to sort range
On Tuesday, 28 May 2013 at 12:57:12 UTC, Sergei Nosov wrote: Hi! I'm trying to implement an array, which uses malloc to allocate memory. Also, I want to implement a random access range interface for it. That went pretty well, until I tried to sort it. Sorting function asserted "Failed to sort range of type Array!(int)." I've spent quite some time trying to figure out what's going on with no success. The implementation can be found at: https://gist.github.com/snosov1/5662471 I used DMD64 D Compiler v2.062 and LDC - the LLVM D compiler (trunk): based on DMD v2.062 and LLVM 3.2svn on Ubuntu. Phobos version was the one that came with the dmd compiler. Does anyone have any ideas what's wrong with the code I've provided? Forgot to mention, that my hand-made sorting function (simply a copy-paste of some quicksort implementation that uses array indexing syntax) works just fine void qSort(alias less, Range)(Range A, int low, int high) { int i = low; int j = high; auto x = A[(low+high)/2]; do { while(less(A[i], x)) ++i; while(less(x, A[j])) --j; if(i <= j){ auto temp = A[i]; A[i] = A[j]; A[j] = temp; i++; j--; } } while(i < j); if(low < j) qSort!less(A, low, j); if(i < high) qSort!less(A, i, high); }
Failed to sort range
Hi! I'm trying to implement an array, which uses malloc to allocate memory. Also, I want to implement a random access range interface for it. That went pretty well, until I tried to sort it. Sorting function asserted "Failed to sort range of type Array!(int)." I've spent quite some time trying to figure out what's going on with no success. The implementation can be found at: https://gist.github.com/snosov1/5662471 I used DMD64 D Compiler v2.062 and LDC - the LLVM D compiler (trunk): based on DMD v2.062 and LLVM 3.2svn on Ubuntu. Phobos version was the one that came with the dmd compiler. Does anyone have any ideas what's wrong with the code I've provided?