Re: [gnugo-devel] get_next_move_from_list() speed optimization

[Arend Bayer]

Paul wrote:

> This patch replaces slow O(n) sorting of matched pattern list in
> get_next_move_from_list() with fast O(n) heap building and O(log n)
> heap popping in new functions pattern_list_build_heap() and
> pattern_list_get_next_pattern() called from get_next_move_from_list().
>
> - slow sorting in get_next_move_from_list() is replaced with heap sorting
> - new static functions pattern_list_build_heap() and
>   pattern_list_get_next_pattern() in `engine/owl.c'

Thanks for doing this. It has been on my mental TODO-list for about a
year now, but never got around to it...

Arend

> No regression changes.
>
> The speedup is quite large, maybe up to 3%.  The profiles below are on
> `nngs2.tst' and with connection reading patch applied.