automate tuple creation

[H. S. Teoh]

On Fri, Jan 21, 2022 at 09:10:56AM +0000, forkit via Digitalmars-d-learn wrote:
[...]
> turns out the problem has nothing to do with appender...
> 
> It's actually this line:
> 
> if (!idArray.canFind(x)):
> 
> when i comment this out in the function below, the program does what I
> want in seconds.
> 
> only problem is, the ids are no longer unique (in the file)
[...]

Ah yes, the good ole O(N²) trap that new programmers often fall into.
:-)

Using .canFind on an array of generated IDs means scanning the entire
array every time you find a non-colliding ID. As the array grows, the
cost of doing this increases. The overall effect is O(N²) time
complexity, because you're continually scanning the array every time you
generate a new ID.

Use an AA instead, and performance should dramatically increase. I.e.,
instead of:

	size_t[] idArray;
	...
	if (!idArray.canFind(x)): // O(N) cost to scan array 

write:

	bool[size_t] idAA;
	...
	if (x in idAA) ...	// O(1) cost to look up an ID


T

-- 
VI = Visual Irritation