1

I am making a module that will output a list of objects that are missing on a list. Currently the code I have takes too long for a list of about 300,000 objects.

public List<SimpleObject> GetNonExistentObjects()
{
     List<SimpleObject> source = GetNodes();//contains 300,000
     List<SimpleObject> target = GetNodes();//contains 300,005

     List<SimpleObject> nonExistentObjects = new List<SimpleObject>();

     foreach(Object obj in source)
     {
          bool existing = target.Any(x => x.Name == obj.Name && x.Label == obj.Label)
          if(!existing)
               nonExistentObjects.Add(obj);//Contains 5 objects
     }

     return nonExistentObjects;
}

I have to create a bunch of methods like this so I would like to ask how to optimize this particular method.

UPDATE: T is just a simple class that I have created that contains 2 properties. Just that

public class SimpleObject
{
     public string Name {get; set}
     public string Label {get; set;}
}
  • do you mean target.any? – Ewan Sep 15 '16 at 14:44
  • @Ewan edited the code, yes I mean target.Any – jmc Sep 15 '16 at 14:46
  • 3
    Something wrong with the existing Except method on IEnumerable<T>? – Oded Sep 15 '16 at 14:48
  • @Oded: using Except naively would just compare the equality of node references, I guess. – Doc Brown Sep 15 '16 at 14:49
  • @DocBrown added the edits – jmc Sep 15 '16 at 14:51
8

You need to override GetHashCode and Equals for your class SimpleObject (and implement them correctly). Then you can use the Except method of LINQ, like suggested by @Oded in a comment:

nonExistentObjects = source.Except(target).ToList();

Except uses a HashSet<T> internally, which makes it very fast.

Here is an example how to implement the two methods I mentioned above:

public class SimpleObject
{
     public string Name { get; set; }
     public string Label { get; set; }

     public override bool Equals(object obj)
     {
         if (obj is SimpleObject)
         {
              var so = (SimpleObject)obj;
              return so.Name == Name && so.Label == Label;
         }
         return false;
     }

     public override int GetHashCode()
     {
         return Name.GetHashCode() ^ Label.GetHashCode();
     }
}
| improve this answer | |
  • nice solution!! – Ewan Sep 15 '16 at 15:28
  • although shouldn't it be target.Except(source)? – Ewan Sep 15 '16 at 15:30
  • Don't forget to enclose GetHashCode code in an unchecked { } section, in order to suppress overflow-checking for integral-type exponentiation. It'll work fine, and it'll save you a lot of trouble debugging strange errors. Reference: msdn.microsoft.com/en-us/library/a569z7k8.aspx – Machado Sep 15 '16 at 17:55
  • @Machado: ^ is not exponentiation in C#, it is the XOR operation, so no overflow can occur here. But for other hashing function, you are right, see here. – Doc Brown Sep 15 '16 at 18:28
  • @Ewan: not the way the OP posted his question, his code puts elements from source into nonExistentObjects. – Doc Brown Sep 15 '16 at 18:31
3

This looks like a suboptimal use of collections to me. Can you use HashSet instead of List for target collection? Remember, in that case, you would have to redefine GetHashCode and Equals methods of classes that would be put in those collections.

| improve this answer | |
2

Put the searched values into a IDictionary

so something like :

indexedTarget = target.ToDictionary(i=> i.Name + "_separator_" + i.Label)

indexedTarget.ContainsKey(obj.Uid  + "_separator_" + obj.Label);

https://msdn.microsoft.com/en-us/library/bb549277(v=vs.110).aspx

as doc comments, string concatenation for the key isnt great. there must be a way to do the full test in one line of code without it.

indexedTarget = target.ToDictionary(i=> i.Name)

MyClass dupe;

if(IndexedTarget.TryGet(obj.Uid, out dupe) && dupe.Label != obj.Label) { nonExistentObjects.Add(dupe);}

edit : note on equality comparer solutions.

Personally I hate adding the extra GetHashCode and Equals Methods to poco classes. Its a good solution when you are always comparing things and there is a firm definition of what makes two of them equal. But it can get onerous when the definition is not as clear. ie this time you want to match the name AND label, but next time you just want to match the name

| improve this answer | |
  • 1
    I recommend removing your last comment. The dictionary is the way to go, it's O(N). Building the two sorted lists is O(N*log(N)) and will take more time to build as N increases. – dagnelies Sep 15 '16 at 14:55
  • you are right!! – Ewan Sep 15 '16 at 15:05
  • 2
    Maybe I am biased, but "magic separator" solutions for creating dictionary keys look always like an ugly hack to me. I have written such code in the past by myself, but today I typically avoid it. Those solutions are short, of course, but you have to be sure the separator is never part of the input data, and you need to make sure the magic string is the same whereever you create keys for the same dictionary. – Doc Brown Sep 15 '16 at 15:12
  • I agree, but I didn't want to complicate the example – Ewan Sep 15 '16 at 15:19
  • Dictionaries throw an exception if the key is not found, so your line var dupe = indexedTarget[obj.Uid] will not work as expected. Instead use indexedTarget.ContainsKey. – Erik Sep 15 '16 at 16:26
-1

I would use the Overide and Equal of Doc Brown +1

public IEnumerable<SimpleObject> GetNonExistentObjects()
{
     List<SimpleObject>    source = GetNodes(); //contains 300,000
     // List.Add is O(1)
     HashSet<SimpleObject> target = GetNodes(); //contains 300,005 

     foreach(SimpleObject s in source)
     {
          if(!target.Contains(s))   // O(1)  LINQ ANY is O(N)
               yield s; //Contains 5 objects
     }
}
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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