yeah i did realise it must be a O(n^2) operation. Still trying to figure out how I can improve it. Since a contains operation will naturally be an O(n).
I'm wondering if there's other forms of optimizations i can do as well. On Mon, May 17, 2010 at 10:35 AM, Mitch Wheat <[email protected]> wrote: > Sorry, I meant order O(N) for the linear search. > > > > If you search degrades rapidly as the list increases, that doesn't sound > like O(N) performance, but more like O(N^2). > > > > Mitch > > > > *From:* [email protected] [mailto: > [email protected]] *On Behalf Of *Mitch Wheat > *Sent:* Monday, 17 May 2010 8:33 AM > *To:* 'ozDotNet' > *Subject:* RE: Filtering algorithm strategies to mimic intellisense > > > > Performing a linear search is O(N^2), so it will perform poorly as the list > grows, as you have observed. > > > > Either keep the list sorted and use binary search O(log N) or use some > other standard data structure such as a tree. > > > > Mitch > > > > *From:* [email protected] [mailto: > [email protected]] *On Behalf Of *Winston Pang > *Sent:* Monday, 17 May 2010 7:41 AM > *To:* ozDotNet > *Subject:* Filtering algorithm strategies to mimic intellisense > > > > Hey everyone, > > So I'm building a intellisense like autocomplete. I've stumbled on some > perf issues because its literally just iterating over the list and > re-applying a filter function on every item, based on every key stroke. The > perf degrades obviously as more times is in the list. > > I was wondering, does anyone have any strategies or past expeirence with > smarter ways to filter a list. Now this list is just a list of a custom > objects, with a particular display field that is a string. Filtering is > filtered based on a contains for each item. So it's essentially mimicing > VS2010's contains for intellisense. > > The VS2010 intellisense seems to be extremely speedy. > > Cheers, > > > Winston >
