MBOX-Line: From arnt at gulbrandsen.priv.no  Wed Dec 20 11:43:57 2006
To: imap-protocol@u.washington.edu
From: Arnt Gulbrandsen <arnt@gulbrandsen.priv.no>
Date: Fri Jun  8 12:34:38 2018
Subject: [Imap-protocol] Searching
In-Reply-To: <alpine.OSX.0.81.0612201018450.10225@pangtzu.panda.com>
References: <1166603479.22214.298.camel@hurina>
	<alpine.OSX.0.81.0612201018450.10225@pangtzu.panda.com>
Message-ID: <rBtlBkn+facAYdHBwRiNTg.md5@libertango.oryx.com>

Mark Crispin writes:
> If you are worried about performance, I suggest that you look into one 
> of the optimizing algorithms for fast search.  UW and Cyrus use a 
> Boyer-Moore fast search which is quite a bit faster than the 
> straightforward linear search.

Boyer-Moore is k*O(n) with an impressive k. People want k*O(log n) these 
days, if possible with an impressive k.

Arnt

