Gotcha with photos' documentation

Christian Köstlin christian.koestlin at gmail.com
Fri Dec 9 20:47:46 UTC 2022


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


More information about the Digitalmars-d-learn mailing list