Efficent filtering on property in large data set

Question

I have an in memory list with a lot of objects (let's say 150000). Each object has a string property that I want to search/filter on, something like this:

var searchTerm = "something";
var result = listOfObjects.Where(o => o.Prop.Contains(searchTerm)).ToList();

This is obviusly very slow. Is there any way to speed it up? I've tried processing in parallel without any benefits. Is there any way to involve hashsets? Or perhaps sort it and do a binary search?

Answer 1

Here is what I tried, granted my data is a bit different since I just generated random strings to test filtering on. But here is my example code.

class Program
{
    static void Main(string[] args)
    {
        Start:

        List<Test> TestList = new List<Test>();
        int ObjectsToCreate = 1000000;
        Console.WriteLine($"Creating {ObjectsToCreate} Objects!");
        for (int x = 1; x <= ObjectsToCreate; x++)
        {
            TestList.Add(new Test() { Name = RandomString(100) });
        }
        Console.WriteLine($"Created {TestList.Count} objects.");
        string StringToSearchFor = "A";
        Console.WriteLine($"Benchmarking Now");
        System.Diagnostics.Stopwatch Watch = System.Diagnostics.Stopwatch.StartNew();

        var TestCollection = TestList.Where(Item => Item.Name.Contains(StringToSearchFor));
        Watch.Stop();
        Console.WriteLine($"Elapsed Time With Where Into VAR: {Watch.ElapsedMilliseconds}ms");
        Console.WriteLine($"Elapsed Time With Where Into VAR: {Watch.ElapsedTicks} ticks");

        Watch = System.Diagnostics.Stopwatch.StartNew();
        IEnumerable<Test> TestCollection_ = TestList.Where(Item => Item.Name.Contains(StringToSearchFor));
        Watch.Stop();
        Console.WriteLine($"Elapsed Time With Where Into IEnumerable<Test>: {Watch.ElapsedMilliseconds}ms");
        Console.WriteLine($"Elapsed Time With Where Into IEnumerable<Test>: {Watch.ElapsedTicks} ticks");

        Watch = System.Diagnostics.Stopwatch.StartNew();
        List<Test> TestCollection2 = TestList.Where(Item => Item.Name.Contains(StringToSearchFor)).ToList();
        Watch.Stop();
        Console.WriteLine($"Elapsed Time With Where Into List<Test>: {Watch.ElapsedMilliseconds}ms");
        Console.WriteLine($"Elapsed Time With Where Into List<Test>: {Watch.ElapsedTicks} ticks");

        Watch = System.Diagnostics.Stopwatch.StartNew();
        List<Test> TestCollection3 = TestList.AsParallel().Where(Item => Item.Name.Contains(StringToSearchFor)).ToList();
        Watch.Stop();
        Console.WriteLine($"Elapsed Time With AsParallel First Where Into List<Test>: {Watch.ElapsedMilliseconds}ms");
        Console.WriteLine($"Elapsed Time With AsParallel First Where Into List<Test>: {Watch.ElapsedTicks} ticks");

        Watch = System.Diagnostics.Stopwatch.StartNew();
        List<Test> TestCollection4 = TestList.Where(Item => Item.Name.Contains(StringToSearchFor)).AsParallel().ToList();
        Watch.Stop();
        Console.WriteLine($"Elapsed Time With AsParallel Last Where Into List<Test>: {Watch.ElapsedMilliseconds}ms");
        Console.WriteLine($"Elapsed Time With AsParallel Last Where Into List<Test>: {Watch.ElapsedTicks} ticks");

        Console.ReadLine();
        goto Start;
    }

    public class Test
    {
        public string Name { get; set; }
    }

    private static Random random = new Random();
    public static string RandomString(int length)
    {
        const string chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        return new string(Enumerable.Repeat(chars, length)
          .Select(s => s[random.Next(s.Length)]).ToArray());
    }
}

And here is the output I get from running it.

Creating 1000000 Objects!
Created 1000000 objects.
Benchmarking Now
Elapsed Time With Where Into VAR: 0ms
Elapsed Time With Where Into VAR: 192 ticks
Elapsed Time With Where Into IEnumerable<Test>: 0ms
Elapsed Time With Where Into IEnumerable<Test>: 4 ticks
Elapsed Time With Where Into List<Test>: 273ms
Elapsed Time With Where Into List<Test>: 934287 ticks
Elapsed Time With AsParallel First Where Into List<Test>: 164ms
Elapsed Time With AsParallel First Where Into List<Test>: 564069 ticks
Elapsed Time With AsParallel Last Where Into List<Test>: 192ms
Elapsed Time With AsParallel Last Where Into List<Test>: 658852 ticks

If I run this same test several times the results of putting that data into VAR goes down to about 7-8 ticks on my machine but exporting to IEnumerable goes down to about 2-3. And this is with 1 million objects. So I'm a bit confused as to what you would define as "very slow". Unless I'm completely misunderstanding something.

Edit: My example with VAR and IEnumerable are not as valid as I originally thought, see the comments on my answer below.

Answer 2

There are some things I can think about.

• At first start with the prediacte you want to test on. Contains is pretty expensive, compared to StartsWith and EndsWith. Therefore, use a performance optimal predicate.
• Parallelize the filter process. Hint Parallel Namespace
• Apply a function (hash) to all objects and insert them into a Dictionary. (To enable O(1) access time) Add some other properties (salt) to the hash if the "key" does occur more than once.
• Consider using a database

Furthermore, it strongly depends on your object structure. Does the object provide any additional information we could use for the comparison? If yes:

• Chunk the data set into groups (depending on property values) and start searching (parallel) in the group with the highest probability. (Heuristic function)
• Use more "complex" structures, like trees, to minimize the data amount

Depending on your program's behaviour, avoid loading all data sets. Load (based on a heuristic value) only a specific amount of data sets (lets say 10.000) and use a displacement strategy if the value isn't preset, to fetch new data.