200-600x slower Dlang performance with nested foreach loop

[CraigDillabaugh]

On Tuesday, 26 January 2021 at 23:57:43 UTC, methonash wrote:
clip
>> That nested loop is an O(n^2) algorithm. Meaning it will slow 
>> down *very* quickly as the size of the array n increases.  You 
>> might want to think about how to improve this algorithm.
>
> Nice observation, and yes, this would typically be an O(n^2) 
> approach.
>
> However, due to subsetting the input dataset to unique strings 
> and then sorting in descending length, one might notice that 
> the inner foreach loop does not iterate over all of n, only on 
> the iterator value i+1 through the end of the array.
>
> Thus, I believe this would then become approximately O(n^2/2). 
> More precisely, it should be O( ( n^2 + n ) / 2 ).
>

But that is still O(n^2), you've only changed the constant.