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
