On 8/18/14, 1:44 AM, Peter Alexander wrote:
> On Monday, 11 August 2014 at 03:29:56 UTC, Andrei Alexandrescu wrote:
>> [...] can be implemented generically for ranges that offer
>> front as a reference:
>>
>> bool sameFront(R1, R2)(R1 r1, R2 r2) {
>>   return &r1.front == &r2.front;
>> }
>
> This doesn't work for ranges that visit the same element twice, e.g.
>
> cycle(arr).take(arr.length + 1)
> [0, 0].map!(i => arr[i])

Correct. Though maybe that's a good thing - rotating a cycle is unlikely to produce something interesting.

> I suspect most ranges will have to implement the sameFront primitive
> manually, usually forwarding to the underlying range.

Only those that return rvalues from front.

> Related: most mutating algorithms won't work for these kinds of ranges,
> as we usually presume lvalue ranges never visit the same lvalue twice.
> Perhaps this needs to be mentioned on affected algorithms?

Looks like a benign effect to me.


Andrei

On Monday, 18 August 2014 at 05:27:11 UTC, Andrei Alexandrescu wrote:
> On 8/17/14, 9:06 AM, Fool wrote:
>>  http://dpaste.dzfl.pl/8fc83cb06de8
>
> Yah, it's a good option. Relevant code:
>
> if (right is whole)
> {
>     //writeln("case identical");
>     return tuple(right, whole.dropExactly(whole.length));
> }
>
> (Prolly it would be better to use "whole.sameHead(right)" instead of "right is whole". Also whole may not define length so the actual algo is just a tad different.)

A cleaned-up version is here: http://dpaste.dzfl.pl/a8c36a0c36d0


> Trouble is it takes O(n) for that trivial case and for what may be in all likelihood a useless return (iterate right all the way through the end and return the empty balance).

Yah, on the other hand you can only expect to get what you pay for.

The strategy that naturally arises from the basic algorithm is even worse. In the case at hand, it suggests executing n trivial swaps.


> Loosely related, Xinok wrote a nice piece on in-place merge: http://goo.gl/AS2P4A. A great use of rotateTail.

Thanks for that link. It's a nice writeup.

-- Fool

On 8/19/14, 12:32 PM, Fool wrote:
> On Monday, 18 August 2014 at 05:27:11 UTC, Andrei Alexandrescu wrote:
>> On 8/17/14, 9:06 AM, Fool wrote:
>>>  http://dpaste.dzfl.pl/8fc83cb06de8
>>
>> Yah, it's a good option. Relevant code:
>>
>> if (right is whole)
>> {
>>     //writeln("case identical");
>>     return tuple(right, whole.dropExactly(whole.length));
>> }
>>
>> (Prolly it would be better to use "whole.sameHead(right)" instead of
>> "right is whole". Also whole may not define length so the actual algo
>> is just a tad different.)
>
> A cleaned-up version is here: http://dpaste.dzfl.pl/a8c36a0c36d0

FWIW just added https://issues.dlang.org/show_bug.cgi?id=13335

Andrei

On Monday, 11 August 2014 at 14:45:09 UTC, Andrei Alexandrescu wrote:
> On 8/11/14, 2:11 AM, "Nordlöw" wrote:
>> On Monday, 11 August 2014 at 06:56:52 UTC, Dragos Carp wrote:
>>> bool sliceOf(T)(in T[] whole, in T[] slice)
>>> {
>>>    return whole.ptr <= slice.ptr &&
>>>        whole.ptr + slice.length <= whole.ptr + slice.length;
>>> }
>>
>> Shouldn't the function arguments of sliceOf be reversed to given a more
>> intuitive UCFS as
>>
>>     if (slice.sliceOf(whole) { ... }
>
> isSliceOf -> yum

While "sameHead" and "sameTail" *could* have a "good enough" generic implementation for ranges, there is absolutely no way to make "isSliceOf" or "overlap" work for a generic range.

That said, sameHead and sameTail is just the iterator equivalent of "first1 == first2" and "last1 == last2", which is used a lot with iterators. You rarely see operator "<" used with iterators though, so I have doubts about why those two functions (isSliceOf and overlap) would actually be of any use.

After having some fun with rotateTail and friends a draft implementation [2] is now available and ready for comments aiming at formal specification, algorithmics, and implementation details.

While most ideas were taken from [1], all mistakes are mine. Since this is my first D code, more or less, please take it with a grain of salt and don't hesitate to express the obvious.

Summary

The original recursive algorithm applicable to ForwardRange experienced another pass [B]. It was put out of contention by an iterative transcription [D] which turned out to be notably faster.

For bidirectional iterators, there is a beautiful reduction to three calls of the reverse function. It was not hard to come up with a corresponding version for BidirectionalRange [E].

Finally, I looked at a third approach which prefers moving to swapping. My implementation [C], however, does not seem to be competitive in practice.

Compared to their iterator analogues, the class of range based rotation algorithms considered comprise a certain amount of additional cost. Practice will show whether it is relevant. On the other hand it seems to me that this cost could be minimized if ranges were based on iterators.

At this point, I refrain from posting results of my biased performance tests. It is safe to assume that the implementation can be tuned based on profiling information.

All algorithms preliminarily handle degenerate cases as proposed by myself. I believe now that rotateTail(r, r) should return r.popFrontAll [A] if and only if it is not more expensive than returning some empty range. Is there a way to check whether r.popFrontExactly(r.walkLength) is O(1)?

Fool

--

[1] A. Stepanov: Rotate - Lecture 19. in Notes on Programming, 2007, pp.154--167
    URL http://www.stepanovpapers.com/notes.pdf

[2] http://dpaste.dzfl.pl/514a1ef77d0a

[A] popFrontAll, ll.47ff
[B] rotateTailRecursive, ll.75ff
[C] rotateTailCycle, ll.147ff
[D] rotateTail, ll.227ff, and rotateTailAux, ll.325ff
[E] rotateTail, ll.227ff, and rotateTailAux, ll.407ff

On Saturday, 23 August 2014 at 18:07:43 UTC, Fool wrote:
> [2] http://dpaste.dzfl.pl/514a1ef77d0a

The 'three reverses' algorihm could be actually improved. Updated code (along with additional unit tests and a strengthened assertion) is available at [3].

I compared this implementation to an iterator based C++ translation and std::rotate [4]. Considering C++ std::vector and D dynamic array, here are the results:

 compiler | algorithm                | execution time
----------+--------------------------+----------------
 clang++  | std::rotate              | 1.62s
 clang++  | my_rotate / std::reverse | 1.45s
 clang++  | my_rotate / my_reverse   | 0.58s
 ldc2     | rotateTail               | 1.64s
 g++      | std::rotate              | 0.57s
 g++      | my_rotate / std::reverse | 1.43s
 g++      | my_rotate / my_reverse   | 0.36s
 gdc      | rotateTail               | 0.38s

Here, my_reverse is an adaption of D's reverse for RandomAccessRange.

These results make me think that the implementation proposed for RandomAccessRange is not too bad. It needs to be investigated why, in this particular situation, ldc2 produces significantly slower code than gdc and clang.

System: GNU/Linux x86_64

Compiler versions:

clang version 3.4.2
LDC - the LLVM D compiler (0.14.0): based on DMD v2.065 and LLVM 3.4.2
g++ (GCC) 4.9.1
gdc (GCC) 4.9.1

Compiler flags:

clang++ -std=c++11 -O3 -march=native
ldc2 -O3 -mcpu=native -release -disable-boundscheck
g++ -std=c++11 -O3 -march=native
gdc -O3 -march=native -frelease -fno-bounds-check


[3] http://dpaste.dzfl.pl/b8e47941a007

[4] C++ translation of rotateTail for RandomAccessRange:

template <typename TIterator>
void my_reverse
(
   TIterator b,
   TIterator e
)
{
   auto steps = std::distance(b, e) / 2;

   if (steps)
   {
      auto l = b;
      auto r = std::prev(e);
      do
      {
         std::iter_swap(l, r);
         ++l;
         --r;
      } while (--steps);
   }
}

template <typename TIterator>
TIterator my_rotate
(
   TIterator b,
   TIterator m,
   TIterator e
)
{
   if (m == e) return b;
   if (b == m) return e;

//   my_reverse(b, m);
   std::reverse(b, m);

   auto s = std::next(b, std::distance(m, e));

//   my_reverse(b, e);
   std::reverse(b, e);
//   my_reverse(s, e);
   std::reverse(s, e);

   return s;
}

There was a bug in my C++ translation of rotateTail. The only significant change in execution time is marked below:

On Sunday, 24 August 2014 at 09:20:59 UTC, Fool wrote:
>  compiler | algorithm                | execution time
> ----------+--------------------------+----------------
>  clang++  | std::rotate              | 1.62s
>  clang++  | my_rotate / std::reverse | 1.44s
>  clang++  | my_rotate / my_reverse   | 0.38s <-
>  ldc2     | rotateTail               | 1.64s
>  g++      | std::rotate              | 0.57s
>  g++      | my_rotate / std::reverse | 1.43s
>  g++      | my_rotate / my_reverse   | 0.37s
>  gdc      | rotateTail               | 0.38s

The fixed implementation of my_rotate:

> template <typename TIterator>
> TIterator my_rotate
> (
>    TIterator b,
>    TIterator m,
>    TIterator e
> )
> {
>    if (m == e) return b;
>    if (b == m) return e;
>
> //   my_reverse(m, e); // <-
>    std::reverse(m, e); // <-
>
>    auto s = std::next(b, std::distance(m, e));
>
> //   my_reverse(b, e);
>    std::reverse(b, e);
> //   my_reverse(s, e);
>    std::reverse(s, e);
>
>    return s;
> }