Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!mx04.eternal-september.org!.POSTED!not-for-mail From: Jim Janney Newsgroups: comp.lang.java.programmer Subject: Re: SortedMap question? Date: Mon, 26 Nov 2012 12:45:59 -0700 Organization: nodded nimbly next his nose Lines: 19 Message-ID: References: <50b26f67$0$295$14726298@news.sunsite.dk> <50b28b1a$0$289$14726298@news.sunsite.dk> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: mx04.eternal-september.org; posting-host="75975abe3fe3503ca7350803ab98e478"; logging-data="26166"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19oabnEDaHJJ517lYc1YCjE" User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.3 (gnu/linux) Cancel-Lock: sha1:x+wiYUGs57mtjJW0R5JbZ09H9fA= sha1:G9KXTCTWIowpFU0omxetvxubCvg= Xref: csiph.com comp.lang.java.programmer:19983 Eric Sosman writes: > Or look at String#indexOf(String). Some fast algorithms > like Boyer-Moore have already been mentioned in this thread, yet > Java's own implementation uses a naive method that is linear at > best, super-linear if unlucky (I think it can be O(M*N), where M > and N are the lengths of the two Strings). If the naive method > were replaced by Boyer-Moore or Knuth-Morris-Pratt or some other > better-O() algorithm, would you expect performance to improve? Boyer-Moore and its descendants invest more time up front building the jump table, in return for faster searching once the table is built. That pays off if you're searching for the same pattern across a large volume of text. But for the common case where strings are relatively short, I'd expect the brute-force (not naive) approach to be the better choice. -- Jim Janney