Talk:Boyer-Moore string search: Difference between revisions
Content added Content deleted
(→Emacs Lisp incorrect?: character compoarison counts?) |
|||
| Line 18: | Line 18: | ||
::: And... my simplistic tests suggest that the performance advantages of the full Boyer-Moore algorithm are significant (performance improvement greater than a factor of 2) in at least some example cases. So, the emacs lisp implementation should probably be marked as incorrect. (But that leaves us with the question of how to determine whether an arbitrary implementation in an arbitrary programming language is correct -- this isn't about the correctness of the result, it's about the relative performance of the implementation.) |
::: And... my simplistic tests suggest that the performance advantages of the full Boyer-Moore algorithm are significant (performance improvement greater than a factor of 2) in at least some example cases. So, the emacs lisp implementation should probably be marked as incorrect. (But that leaves us with the question of how to determine whether an arbitrary implementation in an arbitrary programming language is correct -- this isn't about the correctness of the result, it's about the relative performance of the implementation.) |
||
::: Near as I can tell, to properly judge implementations, we would have to work out search patterns which give us adequate code coverage (like 'ctcat') and ask for a display of some relevant intermediate results. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 17:54, 19 July 2022 (UTC) |
::: Near as I can tell, to properly judge implementations, we would have to work out search patterns which give us adequate code coverage (like 'ctcat') and ask for a display of some relevant intermediate results. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 17:54, 19 July 2022 (UTC) |
||
::::What do you think about the character comparison counts as shown by Julia/Phix, as a proof/measure of correctness? --[[User:Petelomax|Pete Lomax]] ([[User talk:Petelomax|talk]]) 16:23, 21 July 2022 (UTC) |
|||