Optimizing List<string> performance

Question

I have a List<string> being stored in my cache with about 600K members. I want this to act as the backend for an Ajax autocomplete box. It's accessible through my model:

public static List<string> GetProducts()
{            
    var cached = HttpContext.Current.Cache["MyApp-Products"];
    if (cached == null)
    {
        UpdateCache();
        return GetProducts();
    }
    return ((List<string>)cached);
}

My ajax call uses this method to get it's data:

[HttpPost]
public JsonResult ProductSearch(string term)
{
    return Json(MyModel.GetProducts()
        .Where(s => s.ToUpper().StartsWith(term.ToUpper()))
        .OrderBy(s => s)
        .Take(5)
        .ToList<string>()
    );
}

The problem is, this Ajax call to ProductSearch() is waiting 2.09 seconds for a response. I'm doing the same with other objects in my model that have smaller list sizes and they respond in 35-125ms (which is acceptable).

So, I believe my performance issue is somewhere in accessing the list. Is there a faster way to access this list besides the Linq code that I'm using, or just a better way to use Linq?

Answer 1

Marc has the best answer but a trivial step in the right direciton would be to drop all the expensive ToUpper calls. Just replace .Where(s => s.ToUpper().StartsWith(term.ToUpper())) with .Where(s => s.StartsWith(term, StringComparison.InvariantCultureIgnoreCase)

Answer 2

A starts-with should be easy enough to store in a pre-sorted list, ideally using a case-insensitive sort comparer rather than applying conversions each sort. Then: use binary search to find the first match, and keep moving forwards until it no longer matches. Should be pretty efficient.

If this needs to be edited in a shared multi-threaded context, be sure to use appropriate synchronization - presumably readers will be more common than writers, so a ReaderWriterLockSlim may be the best option.

Answer 3

I see that you order the list just to take 5 items. .OrderBy(s => s).Take(5). This is an O(n*log(n)) operation. Instead you can find the top most N items in an O(n) time. Here is an extension method TakeOrdered ( http://pastebin.com/NHDdrbYV ) I wrote some time ago just for this purpose .

 return Json(MyModel.GetProducts()
    .Where(s => s.ToUpper().StartsWith(term.ToUpper()))
    .TakeOrdered(5,s=>s)
    .ToList<string>()
);

you can compare the performance results with a function like below

void PerformanceTest()
{
    Stopwatch sw = new Stopwatch();

    int N = 1000000;
    int M = 10;

    //JIT - Warm up
    var seq1 = RandomSequence().Take(10).OrderBy(x => x).Take(M).ToArray();
    var seq2 = RandomSequence().Take(10).TakeOrdered(M).ToArray();

    
    sw.Start();
    seq1 = RandomSequence().Take(N).OrderBy(x => x).Take(M).ToArray();
    long t1 = sw.ElapsedMilliseconds;

    sw.Restart();
    seq2 = RandomSequence().Take(N).TakeOrdered(M).ToArray();
    long t2 = sw.ElapsedMilliseconds;

    for (int i = 0; i < seq1.Length; i++) Debug.Assert(seq1[i] == seq2[i]);

    Console.WriteLine(t1 + " " + t2);
}

public IEnumerable<int> RandomSequence()
{
    Random rnd = new Random(0);
    while (true)
        yield return rnd.Next();
}

 N   |.OrderBy.Take     .TakeOrdered (in ms.)
-----+---------------------------
100K | 65               23
600K | 578              131
1M   | 1110             224
10M  | 16540            2243

And since It doesn't require all items to be kept in memory(for sorting), it consumes much less RAM

PS: TakeOrdered utilizes PriorityQueue of Lucene.Net internally http://lucene.apache.org/core/old_versioned_docs/versions/3_0_2/api/all/org/apache/lucene/util/PriorityQueue.html

Here is more explanation: How can I use Lucene's PriorityQueue when I don't know the max size at create time?

---

@mast, Updated after 10 years; a generation may have missed my point :). I still believe that minor improvements as in accepted answer doesn't solve the real problem

Suppose op wants to find the top 1 item in the list. Would you sort it first? No. A simple pass over the array to find the max/min would be enough.

For 2?

No. You would extend your code to compare the temp max/min with the current values...

So If we continue with that approach, instead of sorting the whole array (in memory), storing top N items in a sorted smaller array would be more feasable.

A poor performance test code for TakeTopN

void TestTopN()
{
    Random rnd = new Random();
    var array = Enumerable.Range(0, 1000 * 1000).Select(_ => rnd.Next()).ToArray();
    for (int j = 0; j < 10; j++)
    {

        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < 10; i++)
        {
            var top = array.OrderBy(x => x).Take(5).ToArray();
        }
        var t1 = sw.ElapsedMilliseconds;

        sw.Restart();
        for (int i = 0; i < 10; i++)
        {
            var top = array.TakeTopN(5, x => x).ToArray();
        }
        var t2 = sw.ElapsedMilliseconds;
        Console.WriteLine(t1 + " " + t2);

    }
}

results on my machine

2512 108
2454 108
2390 105
2393 106
2433 107
2476 107
2373 107
2261 104
2202 102
2188 106

And the Oscar goes to .....

//similar to Lucene's PriorityQueue
using System;
using System.Collections.Generic;
using System.Linq;

namespace WindowsFormsApp1 //YOUR PROJECT'S NAMESPACE
{
    public static class LinqExtensions
    {
        public static IEnumerable<T> TakeTopN<T, TKey>(this IEnumerable<T> list, int n, Func<T, TKey> keySelector, bool ascending = true) where TKey : IComparable<TKey>
        {
            IComparer<TKey> comparer = Comparer<TKey>.Default;
            if (ascending == false) comparer = new ReverseComparer<TKey>(comparer);

            List<T> values = new List<T>(n + 1);
            List<TKey> keys = new List<TKey>(n + 1);

            TKey max = keySelector(list.First());

            foreach (var item in list)
            {
                var key = keySelector(item);

                if (keys.Count < n)
                {
                    int index = FindIndex<TKey>(keys, key, comparer);
                    keys.Insert(index, key);
                    values.Insert(index, item);
                    max = keySelector(values[values.Count - 1]);
                    continue;
                }

                if (comparer.Compare(key, max) < 0)
                {
                    int index = FindIndex<TKey>(keys, key, comparer);
                    keys.Insert(index, key);
                    values.Insert(index, item);
                    if (keys.Count > n)
                    {
                        keys.RemoveAt(n);
                        values.RemoveAt(n);
                    }
                    max = keySelector(values[values.Count - 1]);
                }
            }

            return values;
        }

        //Needed for stable sort...
        private static int FindIndex<TKey>(List<TKey> keys, TKey key, IComparer<TKey> comparer) where TKey : IComparable<TKey>
        {
            int index = keys.BinarySearch(key, comparer);
            if (index < 0) index = ~index;
            while (index < keys.Count && comparer.Compare(keys[index], key) == 0) index++;
            return index;
        }

        class ReverseComparer<T> : IComparer<T>
        {
            IComparer<T> _Comparer;

            public ReverseComparer(IComparer<T> comparer)
            {
                _Comparer = comparer;
            }

            public int Compare(T x, T y)
            {
                return _Comparer.Compare(y, x);
            }
        }
    }
}

Answer 4

You should put your strings in a database.

CREATE TABLE MyStrings
(
  UpperCaseVersion varchar(8000)
  StringValue varchar(8000)
  PRIMARY KEY(UpperCaseVersion, StringValue)
)

Now it's threadsafe and quickly searchable (via the ordering from the primary key).

This solution will easily scale to 100 Million strings.

Answer 5

You can get rid of the OrderBy statement and just make sure that you're filling the cache with an already sorted list - this will not save a lot of time, but should give some improvement.

Answer 6

You're asking the wrong question. You should be asking how to return the results quickly, not how to do it quickly with a particular data structure (a List).

There has been a lot of work done on exactly this sort of problem. I don't know a lot about this, but most likely some sort of tree structure will be much faster. Off the top of my head, I would look into a trie structure, which is a particular type of tree. (Yeah, the spelling is confusing.)

But I'm certainly no expert on this, and there might well be better options. You may want to post this question on a board with a more algorithmic focus.

Answer 7

If you're doing a StartsWith, perhaps you could break the list down into sub-lists, which obviously would take time, but it wouldn't be time that a human would wait on, since it could be done in the background. Then you could have a list for each letter of the alphabet (or break it down more for common letters and group a few common ones together, whatever works to break it down most evenly).

It wouldn't be 'elegant' to have a bunch of switch statements for each starting letter, but you could easily trim the list length from 600k to sort through to 60k or less, which would drastically reduce the time required to return results.

Alternatively, another option would be to change your datatype entirely. You could pre-sort your 600k list into Dictionary<string, List<string>> with the key being a string of the "StartsWith" you want to match. Then modify your code to simply pull the list stored as the value in the dictionary that matches your StartsWith. So, if you pre-sort to 2 letters, such as aa, ab, ac, ad, etc etc, once you match that, you get can then sort through a drastically smaller list. You could even pre-sort to 3 letters, such as aaa, aab, aac, and so on, which should result in needing to parse through a list of probably under 1000 elements for the longest list in the dictionary, with many being significantly smaller than 1000.

Using a 3-letter key would result in a dictionary with around 17k keys, which should yield acceptable performance. Accessing the dictionary value should be well under 1ms, then sorting through a list with under 1000 elements should be under 10ms, which should result in your function returning a value in more like 20ms rather than 2 seconds. The downside would be needing to break apart your 600k element list into 17,576 smaller sorted lists, then storing each of those in a dictionary with the appropriate "StartsWith" key. This, however, should only take a few seconds and can be done at initialization (and new entries for your list, which I assume isn't static, can be added to the dictionary rather than the jumbo-list, resulting in only needing to sort the list once, ever).

The best bet would be a database, but since that's not an option for you, the second-best thing would be simply reducing the length of your list from 600k down to something much much smaller.