Talk:Boyer-Moore string search: Difference between revisions

Content added Content deleted

Inline

Revision as of 03:03, 6 July 2022

I am not sure if this is intended to be a task.

I also am not sure how this algorithm's performance fairs against the caching mechanisms of recent machines. (Other than branch prediction issues, boyer-moore is probably not penalized by caching implementations -- unlike tree search algorithms which experience poor cache locality -- but there might be some minimum search string length necessary to see significant gains from this approach, especially in uncached contexts.) --Rdm (talk) 01:13, 6 July 2022 (UTC)

For strings I do not know, but variants of this algorithm are commonly used to search DNA databases. See for example this video: https://www.coursera.org/lecture/dna-sequencing/lecture-boyer-moore-putting-it-all-together-GuaWm --Wherrera (talk) 03:03, 6 July 2022 (UTC)

Revision as of 01:13, 6 July 2022 (view source) Rdm (talk \| contribs) (Created page with "I am not sure if this is intended to be a task. I also am not sure how this algorithm's performance fairs against the caching mechanisms of recent machines. (Other than bran...")		Revision as of 03:03, 6 July 2022 (view source) Wherrera (talk \| contribs) mNo edit summary Newer edit →
Line 2:		Line 2:

	I also am not sure how this algorithm's performance fairs against the caching mechanisms of recent machines. (Other than branch prediction issues, boyer-moore is probably not penalized by caching implementations -- unlike tree search algorithms which experience poor cache locality -- but there might be some minimum search string length necessary to see significant gains from this approach, especially in uncached contexts.) --[[User:Rdm\|Rdm]] ([[User talk:Rdm\|talk]]) 01:13, 6 July 2022 (UTC)		I also am not sure how this algorithm's performance fairs against the caching mechanisms of recent machines. (Other than branch prediction issues, boyer-moore is probably not penalized by caching implementations -- unlike tree search algorithms which experience poor cache locality -- but there might be some minimum search string length necessary to see significant gains from this approach, especially in uncached contexts.) --[[User:Rdm\|Rdm]] ([[User talk:Rdm\|talk]]) 01:13, 6 July 2022 (UTC)


			For strings I do not know, but variants of this algorithm are commonly used to search DNA databases. See for example this video: https://www.coursera.org/lecture/dna-sequencing/lecture-boyer-moore-putting-it-all-together-GuaWm --[[User:Wherrera\|Wherrera]] ([[User talk:Wherrera\|talk]]) 03:03, 6 July 2022 (UTC)