Forum guidelines
  • Home
  • »
  • C# Language
  • »
  • Excluding value on one list from other list-Taking too long
AuthorQuestion
Excluding value on one list from other list-Taking too long
Posted on: 02 Dec 2012
So, I have two list of int array. 
Say result1 and result2. I am using the code as follow which will exclude all the items that are in result2 from result1. 
But it's talking too much time, since I have thousands of item on both list of int array. Is there any other approach with which I can achieve same efficiently? Appreciated!!



List<int[]> result1 = new List<int[]> { new int[] { 1, 2, 3 }, new int[] { 4, 5, 6 } };
List<int[]> result2 = new List<int[]> { new int[] { 1, 2, 3 }, new int[] { 7, 8, 9 } };

result2.ForEach(t => result1.RemoveAll(z => z.OrderBy(k=>k).SequenceEqual(t.OrderBy(k=>k))));



AuthorReply
Re: Excluding value on one list from other list-Taking too long
Posted on: 02 Dec 2012  
Is the approach I suggested in one of your previous threads any faster?

http://www.c-sharpcorner.com/Forums/Thread/193268/how-to-exclude-two-ilistint.aspx

or are you wanting two integers arrays to be regarded as equal if they contain the same elements, regardless of how they're ordered?

So {1, 2, 3} would be regarded as equal to {1, 3, 2}.

Re: Excluding value on one list from other list-Taking too long
Posted on: 02 Dec 2012  
Thanks Vulpes for the response. Sorry I had missed somehow to reply to your earlier thread. 

Yes, the order of the integer array is not relevant in my case. So like you said 
{1, 2, 3} would be regarded as equal to {1, 3, 2}. 
Any Suggestions or tips?

Re: Excluding value on one list from other list-Taking too long
Posted on: 02 Dec 2012  
Can the integer arrays contain duplicate elements?

If they can't, then using HashSets may be quicker.

Re: Excluding value on one list from other list-Taking too long
Posted on: 02 Dec 2012  
I am not 100% sure on that, but I guess the integer arrays can contain duplicate elements.

At this point I am not sure what other options I have.


Vulpes
  • 1
  • 0
accepted
Re: Excluding value on one list from other list-Taking too long
Posted on: 02 Dec 2012   Accepted Answer
OK, well you could try my previous approach which I've adjusted so that the order of elements in the arrays is no longer important. The changes are highlighted:

using System;
using System.Collections.Generic;
using System.Linq;

class Int32ArrayEqualityComparer : IEqualityComparer<int[]>
{
    public bool Equals(int[] ia1, int[] ia2)
    {
        if (ia1 == null || ia2 == null) return false;
        if (ia1.Length != ia2.Length) return false;
        
        Array.Sort(ia1);
        Array.Sort(ia2);

        for(int i = 0; i < ia1.Length; i++)
        {
           if (ia1[i] != ia2[i]) return false;
        }
        return true;
    }

    public int GetHashCode(int[] ia)
    {
        if (ia == null || ia.Length == 0) return 0;
        int combined = ia[0]; 
        for(int i = 1; i < ia.Length; i++) combined ^= ia[i];  
        return combined.GetHashCode();
    }
}

class Test
{
   static void Main()
   {
      List<int[]> result  = new List<int[]> {new int[]{1,2,3}, new int[]{4,5,6} };
      List<int[]> result1 = new List<int[]> {new int[]{3,2,1}, new int[]{7,8,9} };
      List<int[]> result2 = result.Except(result1, new Int32ArrayEqualityComparer()).ToList();

      // check it worked
      foreach(int[] ia in result2)
      {
         foreach(int i in ia) Console.Write("{0} ", i);
         Console.WriteLine();
      }

      Console.ReadKey();
   }
}



Re: Excluding value on one list from other list-Taking too long
Posted on: 02 Dec 2012  
Thanks Vulpes! I did tried your new modified code, but still it's taking long time to process. I had to stop the program as it was talking more than 30 mins. May be I will need to rethink on reducing the size of the array before trying to exclude it. 


Re: Excluding value on one list from other list-Taking too long
Posted on: 02 Dec 2012  
One thing you could try is to sort all the arrays in each list before you attempt any comparisons.

You can then use the version of the code which doesn't sort the arrays in the Equals method.

My suspicion is that both the LINQ code and my version are sorting each array multiple times which will clearly slow things down. So just sorting the arrays the one time might help here.

Re: Excluding value on one list from other list-Taking too long
Posted on: 02 Dec 2012  
Thanks Vulpes! I just tried sorting the Array before running the comparison logic, but it still takes time at the when it reaches - 
 List<int[]> result2 = result.Except(result1, new Int32ArrayEqualityComparer()).ToList();

I guess it's just because the size of the list is too large. 

SPONSORED BY

Custom Software Development
MCN is your source for developing solutions involving websites, mobile apps, cloud-computing, databases, BI, back-end services and processes and client-server applications.