5

I have a list of objects that I wish to reduce to only the ones that have properties contained within a separate list.

List1 is a list of simple strings.

List2 is a list of objects containing two string-properties; A and B.

All items where A and B are not present in List1, should be removed.

This process is very time-dependent and needs to be as quick as possible. Currently I have the following implementation;

var List1 = new List<String>() {"Around", "9000", "strings"}; //List of about 9000 strings
var List2 = databaseList.ToList(); //Around 2.5 million objects

var reducedList = new HashSet<Object>();            
foreach (var item in List2)
{
    if(List1.Contains(item.A) && List1.Contains(item.B))
    {
        reducedList.Add(item);
    }
}

This process takes around 7 seconds to complete, which for my current requirements is too slow.

I have tried running this using LINQ, but gives the same result, around 7 seconds.

var reducedList = List2.Where(r => List1.Contains(r.A)).Where(r => List1.Contains(r.B)).ToList();

Any suggestions to what I can do to improve this?

EDIT: I am unable to do this on the SQL side of things, since the 9000 strings that I need to compare against cannot be "translated" into and SQL-query, but will go above the allowed 2100 input parameters which are allowed in our SQL Server setup.

5
  • 8
    HashSet.
    – Wai Ha Lee
    Commented Dec 3, 2015 at 9:48
  • How long does just doing a foreach over all the items in the database take? Are you timing the foreach loop, or the two initialisation statements also?
    – Wai Ha Lee
    Commented Dec 3, 2015 at 9:49
  • 3
    The foreach over databaseList that contains over 2.5 million objects is what bothers me; also given the name (databaseList) are you sure you can't do a query at db level ? Commented Dec 3, 2015 at 9:55
  • What's the size of List1, is it really "around 9000 strings " ? And does it come from db too ? Commented Dec 3, 2015 at 10:03
  • I think it is the second line (executing the db-query and loading all objects from db) which uses up all the time. Do you need the full object/row there? If not, use projection to load only the required columns and thus speedup the query.
    – ChriPf
    Commented Dec 3, 2015 at 10:20

6 Answers 6

3

I have not tried it but probably it would increase the performance.

var List1 = new List<String>() {"Around", "9000", "strings"};
var List2 = databaseList.ToList(); //Around 2.5 million objects

var reducedList = List2.RemoveAll(i => !List1.Contains(i.A) && !List1.Contains(i.B)).ToList();
1
  • List<T>.RemoveAll(Predicate<T>) returns an int, not a list, so this doesn't compile. Also, the .Contains(...) are still executed, so why would this be any better?
    – Maarten
    Commented Dec 3, 2015 at 10:48
2

First, Let's make the first list quicker to lookup on:

var sought = new HashSet<String>() {"Around", "9000", "strings"};

Also why bother pulling creating a list in memory if you're just going to iterate through it. Unless you are going to want to use List2 for some other purpose, it's not doing anything.

foreach (var item in databaseList)
{
  if(sought.Contains(item.A) && sought.Contains(item.B))
  {
    reducedList.Add(item);
  }
}

Also type your reducedList hashlist appropriately as new HashList<TheActualTypeOfTheItemsHere>.

If that type doesn't implement IEquatable<T> then add that implementation. If that's impossible then create an appropriate IEqualityComparer<T> that and use that in reducedList's constructor.

3
  • The list with 9000 strings would be translated to 9000 parameters, and the SQL something like WHERE item.A = value1 OR item.A = value2 OR .... Also SQL Server doesn't support that many parameters.
    – Maarten
    Commented Dec 3, 2015 at 10:50
  • @Maarten heh. I didn't even look at the actual strings and thought to myself "well, if there are only going to be a few strings in the first list…"!
    – Jon Hanna
    Commented Dec 3, 2015 at 10:59
  • @Maarten a bit saner now for that use.
    – Jon Hanna
    Commented Dec 3, 2015 at 11:08
0

As pointed by @Ondrej Svejdar, if databaseList comes from EntityFramework, you then you shouldn't call ToList(), as it makes a db query, which return 2.5 million records

var reducedList = databaseList
                 .Where(r => List1.Contains(r.A) && List1.Contains(r.B))
                 .ToList();

Also if List1 comes from database (I hope as 9000 is a big number to build manually), then consider using join operator.

1
  • 1
    If List1 is an in-memory list, then the 9000 items would be translated to SQL parameters, which probably wouldn't compile (not in SQL Server anyway).
    – Maarten
    Commented Dec 3, 2015 at 10:51
0

The version of your database could be an issue: Reference: Slower sqlite Since i don't know what king of DB you are using, this might be "useless". But look if your DB has the latest version and also look how fast it can be. Test your program on another pc/browser/phone and see if you get same results.

Now you should find WHAT exactly is taking a long time. Try removing your if-statement and see if speed improves. If it doesn't improve it is querying speed that is an issue. If it does, try query your DB in a way you don't need to use that if.

0

You could try implementing IEquatable on your object, as it is the method that Contains will call to see if the object is in the list

See this post for more info.

0

How big is List1 typically? If it's a small list as in your sample, then staying with a list would be fine. If that's not the case, you may get better results with a HashSet instead.

The real game changer, I believe, is avoid loading the List2 with the 2.5 million objects, just to filter them later. If databaseList is some kind of IEnumerable to a DbSet, you may get better results with something like:

var List1 = new List<String>() {"Around", "9000", "strings"};
var reducedList = (from item in databaseList
                   where List1.Contains(item.A) && List1.Contains(item.B)
                   select item).ToList();

Using a HashSet for your reduced list will only slow down insertions. If you are using it to avoid duplicates, or to speed up lookup afterwards, then you should keep it. Otherwise a List will be better.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.