www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Gotcha with photos' documentation

reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
Recently I stumbled upon a small issue in dlang's docs.
I wanted to look up uniq in std.algorithm. Started from 
https://dlang.org/phobos/std_algorithm.html and clicked uniq, no
problem, all good. But my code did not work. After some debugging
I saw, that for some inputs uniq just did not work. I clicked around
some more in the online docs and finally arrived at https://dlang.org
/phobos/std_algorithm_iteration.html which also lists uniq at the
beginning of the page and mentions (only there) that the input needs to
be sorted.
With that all was back to good :)

Would it make sense to mention this prerequisite also at the main 
documentation of uniq 
(https://dlang.org/phobos/std_algorithm_iteration.html#uniq)

Kind regards,
Christian
Dec 08 2022
next sibling parent "H. S. Teoh" <hsteoh qfbox.info> writes:
On Thu, Dec 08, 2022 at 09:15:45PM +0100, Christian Köstlin via
Digitalmars-d-learn wrote:

 Recently I stumbled upon a small issue in dlang's docs.
 I wanted to look up uniq in std.algorithm. Started from
 https://dlang.org/phobos/std_algorithm.html and clicked uniq, no
 problem, all good. But my code did not work. After some debugging
 I saw, that for some inputs uniq just did not work. I clicked around
 some more in the online docs and finally arrived at https://dlang.org
 /phobos/std_algorithm_iteration.html which also lists uniq at the
 beginning of the page and mentions (only there) that the input needs to
 be sorted.
 With that all was back to good :)
 
 Would it make sense to mention this prerequisite also at the main
 documentation of uniq
 (https://dlang.org/phobos/std_algorithm_iteration.html#uniq)


[...]

Technically, .uniq can be used with a custom predicate for collapsing
adjacent equivalent items, which can be useful on non-sorted ranges
sometimes.

OTOH, it's true that the most common use case for .uniq is on sorted
ranges.  The docs do say that it iterates "unique *consecutive*
elements" (emphasis mine), but I guess this is easy to miss.  I'll see
if I can reword this to be more explicit.


T

-- 
Spaghetti code may be tangly, but lasagna code is just cheesy.
Dec 08 2022
prev sibling parent reply "H. S. Teoh" <hsteoh qfbox.info> writes:
On Thu, Dec 08, 2022 at 05:21:52PM -0800, H. S. Teoh via Digitalmars-d-learn
wrote:
[...]

 I'll see if I can reword this to be more explicit.


[...]

https://github.com/dlang/phobos/pull/8646


T

-- 
Don't modify spaghetti code unless you can eat the consequences.
Dec 08 2022
parent reply =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
On 09.12.22 02:27, H. S. Teoh wrote:

 On Thu, Dec 08, 2022 at 05:21:52PM -0800, H. S. Teoh via Digitalmars-d-learn
wrote:
 [...]

 I'll see if I can reword this to be more explicit.


 [...]
 
 https://github.com/dlang/phobos/pull/8646
 
 
 T
 


Thanks a lot ...
that was fast.

Is there also an implementation that works on non sorted ranges?


Kind regards,
Christian
Dec 09 2022
parent reply "H. S. Teoh" <hsteoh qfbox.info> writes:
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

-- 
Fact is stranger than fiction.
Dec 09 2022
parent =?UTF-8?Q?Christian_K=c3=b6stlin?= <christian.koestlin gmail.com> writes:
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
Dec 09 2022