On 12/12/2016 03:49 AM, Bruno Haible wrote:
Part of the
problem appears to be that position-set merging, even with his latest proposed
changes, is O(N**2) where N is the pattern size....
I'm confused. Which code are you talking about?
I was referring to code with his proposed patch installed. 'delete' is
O(N); 'replace' calls 'delete' in a loop and is therefore O(N**2).
'epsclosure' calls 'replace' in a loop and so I suppose it is O(N**3). I
haven't looked into how likely the worst-case performance is, though.
So, the larger the two input files, the larger the relative time eaten by
'dfastate'. IMO this means the bottleneck is 'dfastate'.
Yes, there is a bottleneck there. I haven't had time yet to investigate
more.
