-4

I have two lists, A and B. I want to check A with B and make sure that A contains only the elements that B contains. Example: In A={1, 2, 3, 4}, B ={3, 4, 5, 6}. At the end, I want A to be {3, 4, 5, 6}. Conditions: I don't want to replace A completely with B and I don't want to change B.

public void setA(List B)
{
   foreach(x in B)
   {
      if(!A.Contains(x))
           A.Add(x)
   }
   foreach(x in A)
   {
      if(!B.Contains(x))
          A.Delete(x)
   }
}

Is there any better way to do this? (May be in a single for loop or even better)

Alexander Paes
  • 101
  • 4
  • 13
  • 1
    I'm confused. Are you checking for equality or are you copying an array? – Andrew Li Aug 29 '16 at 20:50
  • This is likely O(n2) because `Contains` would have an O(n) complexity. Can definitely be done better by using hashing. – Some Guy Aug 29 '16 at 20:50
  • And replacing A completely with B is exactly what your algorithm does, in a convoluted manner though. – Some Guy Aug 29 '16 at 20:51
  • I agree with @SomeGuy here - it *is* O(n^2). Also, you can't modify a list in a foreach loop so this won't run. – EJoshuaS - Stand with Ukraine Aug 29 '16 at 21:15
  • It's not clear to me exactly how you want this to behave. Can you clarify? As pointed out, this *will* replace A with B, and in the example you give A ends up being exactly equal to B. How do you want this to differ from simply making A a copy of B? – EJoshuaS - Stand with Ukraine Aug 29 '16 at 21:22
  • Consider elements as files that have to been fetched from server(expensive call) and copying whole list is also very expensive. I would like to copy files that are missing in A and delete files deprecated in A. Let me know if you need more explanation. My ultimate goal is to do this in a smart way in less than O(n^2) may be in linear time(if possible). – Alexander Paes Aug 29 '16 at 22:13
  • @SomeGuy It is not equivalent if the goal is to also detect differences and perform some operation at each add and delete. Also there may be duplicates. – stark Aug 30 '16 at 11:35

1 Answers1

0

Try the following:

var listATest = new List<int>() { 1, 2, 3, 4, 34, 3, 2 };
var listBTest = new List<int>() { 3, 4, 5, 6 };

// Make sure listATest is no longer than listBTest first
while (listATest.Count > listBTest.Count)
{
    // Remove from end; as I understand it, remove from beginning is O(n)
    // and remove from end is O(1) in Microsoft's implementation
    // See http://stackoverflow.com/questions/1433307/speed-of-c-sharp-lists
    listATest.RemoveAt(listATest.Count - 1);
}

for (int i = 0; i < listBTest.Count; i++)
{
    // Handle the case where the listATest is shorter than listBTest
    if (i >= listATest.Count)
        listATest.Add(listBTest[i]);

    // Make sure that the items are different before doing the copy
    else if (listATest[i] != listBTest[i])
        listATest[i] = listBTest[i];
}
EJoshuaS - Stand with Ukraine
  • 11,977
  • 56
  • 49
  • 78
  • consider the elements to be files that need to be checked for sure. But I want to make that with only one comparison, I should be able to add and delete. And you cannot copy all the files each time because disk writes takes long time. The above solution is not optimal to my case. Thank you for the help. Please let me know if you can think of an alternative. – Alexander Paes Aug 31 '16 at 14:40
  • @MouryaKoluguri Like I said in the comments in the original answer, change "else listATest[i] = listBTest[i];" to "else if (listATest[i] = listBTest[i])...[do copy]" - that way you only do the copy if the files are different. I edited to put that in the answer to make it easier to follow. – EJoshuaS - Stand with Ukraine Aug 31 '16 at 14:56