uniq and array of enum members (That are all strings)

H. S. Teoh hsteoh at quickfur.ath.cx
Wed Jan 16 16:35:04 UTC 2019


On Wed, Jan 16, 2019 at 04:21:12PM +0000, bauss via Digitalmars-d-learn wrote:
> On Wednesday, 16 January 2019 at 16:12:28 UTC, H. S. Teoh wrote:
[...]
> > .uniq only works on adjacent identical elements.  You should sort
> > your array first.
> > 
> > If you need to preserve the original order but eliminate duplicates,
> > then you could use an AA to keep track of what has been seen. E.g.:
> > 
> > 	bool[string] seen;
> > 	auto b = a.filter!((e) {
> > 			if (e in seen) return false;
> > 			seen[e] = true;
> > 			return true;
> > 		});
[...]
> Sorting will not work in my case though because it's an enum of
> strings that are not sorted alphabetically.
> 
> Right now I'm doing it manually by a foreach in similar way you're
> using filter.
> 
> I just feel like that's an overkill for something so trivial.

It's not trivial. In order for the computer to know whether or not the
i'th element should be excluded, it needs to know what has come before
it. In the case of .uniq, this is easy because the assumption is that
identical elements are adjacent, so we only need to know what the
previous element was.  But in your case, we need to know elements that
were seen an arbitrary distance in the past.  So there must be some way
of answering the question "has the i'th element been seen x iterations
ago?".  So either you search backward until you find the element (very
inefficient: it will turn your algorithm into O(n^2)), or you need some
kind of lookup structure like an AA to remember what has been seen
before.


T

-- 
It is the quality rather than the quantity that matters. -- Lucius Annaeus Seneca


More information about the Digitalmars-d-learn mailing list