What's the fastest Phobos-way of doing either

    x ~= y; // append
    x = x.uniq; // remove duplicates

or

    x = (x ~ y).uniq; // append and remove duplicates in one go

provided that

    T[] x, y;

?

Both variants are wrong because uniq needs sorted ranges.

Probably you need something like that:

x = x.chain(y).sort.uniq.array;

On Friday, 1 May 2015 at 19:08:51 UTC, Per Nordlöw wrote:
> What's the fastest Phobos-way of doing either
>
>     x ~= y; // append
>     x = x.uniq; // remove duplicates
>
> or
>
>     x = (x ~ y).uniq; // append and remove duplicates in one go
>
> provided that
>
>     T[] x, y;
>
> ?

If x is already sorted

x = x.completeSort(y).uniq.array;

On Friday, 1 May 2015 at 19:30:08 UTC, Ilya Yaroshenko wrote:
> Both variants are wrong because uniq needs sorted ranges.
>
> Probably you need something like that:
>
> x = x.chain(y).sort.uniq.array;
>
> On Friday, 1 May 2015 at 19:08:51 UTC, Per Nordlöw wrote:
>> What's the fastest Phobos-way of doing either
>>
>>    x ~= y; // append
>>    x = x.uniq; // remove duplicates
>>
>> or
>>
>>    x = (x ~ y).uniq; // append and remove duplicates in one go
>>
>> provided that
>>
>>    T[] x, y;
>>
>> ?

fix:

	completeSort(x.assumeSorted, y);
	x = x.chain(y).uniq.array;

or

	completeSort(x.assumeSorted, y.uniq.array);
	x ~= y;


On Friday, 1 May 2015 at 19:34:20 UTC, Ilya Yaroshenko wrote:
> If x is already sorted
>
> x = x.completeSort(y).uniq.array;
>
> On Friday, 1 May 2015 at 19:30:08 UTC, Ilya Yaroshenko wrote:
>> Both variants are wrong because uniq needs sorted ranges.
>>
>> Probably you need something like that:
>>
>> x = x.chain(y).sort.uniq.array;
>>
>> On Friday, 1 May 2015 at 19:08:51 UTC, Per Nordlöw wrote:
>>> What's the fastest Phobos-way of doing either
>>>
>>>   x ~= y; // append
>>>   x = x.uniq; // remove duplicates
>>>
>>> or
>>>
>>>   x = (x ~ y).uniq; // append and remove duplicates in one go
>>>
>>> provided that
>>>
>>>   T[] x, y;
>>>
>>> ?

fix:

 	completeSort(x.assumeSorted, y);
 	x = x.chain(y).uniq.array;

 or  (was fixed)

        y = y.sort().uniq.array;
 	completeSort(x.assumeSorted, y);
 	x ~= y;

On Friday, 1 May 2015 at 19:30:08 UTC, Ilya Yaroshenko wrote:
> Probably you need something like that:
>
> x = x.chain(y).sort.uniq.array;

You're right:

    import std.stdio, std.algorithm, std.range;
    auto x = [11, 3, 2, 4, 5, 1];
    auto y = [0, 3, 10, 2, 4, 5, 1];
    writeln(x.chain(y).uniq);
    writeln(x.chain(y).sort.uniq);

outputs

    [11, 3, 2, 4, 5, 1, 0, 3, 10, 2, 4, 5, 1]
    [0, 1, 2, 3, 4, 5, 10, 11]

so why doesn't

http://dlang.org/phobos/std_algorithm_iteration.html#.uniq

say anything about need for sortness!? I expected D to be strict here and SortedRange as input to uniq.

On 05/01/2015 03:41 PM, "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow@gmail.com>" wrote:

> so why doesn't
>
> http://dlang.org/phobos/std_algorithm_iteration.html#.uniq
>
> say anything about need for sortness!?

It is about the uniqueness of consecutive elements. It says "unique consecutive elements".

Ali

On Friday, 1 May 2015 at 22:47:17 UTC, Ali Çehreli wrote:
> It is about the uniqueness of consecutive elements. It says "unique consecutive elements".
>
> Ali

Ah.

Then I guess that if input is SortedRange then SortedRange should be returned.

Thanks.

On 05/01/2015 06:39 PM, "Per =?UTF-8?B?Tm9yZGzDtnci?= <per.nordlow@gmail.com>" wrote:> On Friday, 1 May 2015 at 22:47:17 UTC, Ali Çehreli wrote:
>> It is about the uniqueness of consecutive elements. It says "unique
>> consecutive elements".
>>
>> Ali
>
> Ah.
>
> Then I guess that if input is SortedRange then SortedRange should be
> returned.

Interesting idea. I have defined a simple algorithm below to see how it could work (my skipped() function instead of uniq()).

import std.stdio;
import std.range;
import std.algorithm;
import std.exception;

struct Skipper(R)
{
    R range;

    this(R range)
    {
        enforce(range.length % 2 == 0,
                "This example requires even number of elements");
        this.range = range;
    }

    @property bool empty() { return range.empty; }
    @property auto front() { return range.front; }

    void popFront()
    {
        range.popFront();
        range.popFront();
    }
}

auto skipped(R)(R range)
{
    import std.traits;

    static if (isInstanceOf!(SortedRange, R)) {
        // Nice! Let's add an .assumeSorted at the end
        return Skipper!R(range).assumeSorted;

    } else {
        return Skipper!R(range);
    }
}

void use(R)(R range)
{
    pragma(msg, R);
    writeln(range);
    writeln();
}

void main()
{
    auto a = [ 1, 2, 3, 4, 5, 6 ];

    use(a.skipped);
    use(a.assumeSorted.skipped);
}

Prints at compile time:

Skipper!(int[])
SortedRange!(Skipper!(SortedRange!(int[], "a < b")), "a < b")

Prints at run time:

[1, 3, 5]

[1, 3, 5]


One issue is that many standard algorithms could benefit from this as well. Should it be only for SortedRange? What about user defined types... What if I wanted MyCoolRange to be appended automatically as .myCoolRange. Could there we standard mechanism to support any range type?

Maybe the answer is a helper mixin that defines a template specialization for SortedRange!(R2, Func) instead of my 'static if' solution. (I was too impatient to get that syntax right. :) )

Ali

On Friday, 1 May 2015 at 19:30:08 UTC, Ilya Yaroshenko wrote:
> Both variants are wrong because uniq needs sorted ranges.
>
> Probably you need something like that:
>
> x = x.chain(y).sort.uniq.array;

Interesting.

Is

    x = x.chain(y).sort

faster than

    x ~= y;
    x.sort;

?

If so why?