On 09.12.22 19:55, H. S. Teoh wrote:
On Fri, Dec 09, 2022 at 12:51:27PM +0100, Christian Köstlin via
Digitalmars-d-learn wrote:
On 09.12.22 02:27, H. S. Teoh wrote:
[...]
https://github.com/dlang/phobos/pull/8646
[...]
Thanks a lot ...
that was fast.
It only took a minute to fix. :-D
Is there also an implementation that works on non sorted ranges?
[...]
Not as far as I know, because on a non-sorted range you'd have a much
higher time/space complexity. You could sort the range first, but
that's O(n log n) time and possibly O(n) space if you want to preserve
the original range.
Alternatively, you could use an AA to keep track of items already seen,
but that's also O(n) space in the worst case. Ostensibly it'd be O(n)
time as well, but that depends on your data set (some pathological cases
may trigger poorer AA performance). It will also trigger GC allocations.
Something along these lines:
auto noDuplicates(R)(R range)
if (isInputRange!R)
{
bool[ElementType!R] aa;
return range.filter!((e) {
if (e in aa)
return false;
aa[e] = true;
return true;
});
}
T
Thanks for the sketch ... sure ... for pathological cases all hope is
lost :).
Kind regards,
Christian
