Re: [Patch] Optimize _BFSExecutor in regex

[Tim Shen <timshen91 at gmail dot com>]

On Mon, Oct 7, 2013 at 7:12 AM, Jonathan Wakely <jwakely.gcc@gmail.com> wrote:
> On 6 October 2013 23:43, Tim Shen wrote:
>> Here's a simple piece of code
>> https://gist.github.com/innocentim/6849759 the reveals _BFSExecutor's
>> inefficiency. Some optimizations are here to reduce the unecessary
>> time complexity from O(n^2) to O(n).
>>
>> I'll do a bootstrap and full testing before committing.
>
> In the ChangeLog, please fix the spelling of "unnecessary".
>
> The constructor of _TodoList could be "explicit"
>
> Does _TodoList really need to derive from std::vector<_StateIdT> or
> could it just have a second member? I think there's no benefit to
> using inheritance here.
>
> _TodoList::__exists should be named _M_exists to follow the library
> coding standards.
>
> Shouldn't _TodoList::_M_empty() also set __exists[n] = false for all n?
>
> I think it's guaranteed that __exists[__u] is always in range, right?

Anyway, here's the patch. I intended to write something like a
Quine[1] as the testcase but gave up ;)

Thank you!

[1] http://en.wikipedia.org/wiki/Quine_(computing)

-- 
Tim Shen

Attachment: a.patch
Description: Binary data