Compare methods

[csharpula csharp]

Hello,

I would like to compare two list<string> in such way:

for example:

ListA = {aa,bb,cc}

ListB = {bb,aa,cc}

both of them are equal because the consist same elements (no matter in
which order).

What is the best way to do it in c#?

Thanks!

 

[Peter Morris]

I would do something like this

public static bool AreSame(List<string> list1, List<string> list2)
{
if (list1.Count != list2.Count)
return false;

var compareList1 = new List<string>(list1);
compareList1.Sort();

var compareList2 = new List<string>(list2);
compareList2.Sort();

for (int index = 0; index < compareList1.Count; index ++)
if (compareList1[index] != compareList2[index])
return false;

return true;
}

 

[Göran Andersson]

Hello,

I would like to compare two list<string> in such way:

for example:

ListA = {aa,bb,cc}

ListB = {bb,aa,cc}

both of them are equal because the consist same elements (no matter in
which order).

What is the best way to do it in c#?

Thanks!

I think that the most efficient way is to add the items from one list to
a dictionary, and loop through the other list to check that all the
items are in the dictionary.

public bool Compare(List<string> ListA, List<string> ListB) {
if (ListA.Count != ListB.Count) return false;
Dictionary<string, int> dict = new Dictionary<string, int>(ListA.Count);
foreach (string s in ListA) {
dict.Add(s, 1);
}
foreach (string s in ListB) {
if (!dict.ContainsKey(s)) {
return false;
}
}
return true;
}

If there can be duplicates in the strings, you would count the
occurances in one list, then subtract the number of occurances in the
other list, and check that all counters are zero.

public bool Compare(List<string> ListA, List<string> ListB) {
if (ListA.Count != ListB.Count) return false;
Dictionary<string, int> dict = new Dictionary<string, int>(ListA.Count);
foreach (string s in ListA) {
if (dict.ContainsKey(s) {
dict++;
} else {
dict.Add(s, 1);
}
}
foreach (string s in ListB) {
if (!dict.ContainsKey(s)) {
return false;
}
dict--;
}
foreach (int v in dict.Values) {
if (v != 0) {
return false;
}
}
return true;
}

 

[Jon Skeet [C# MVP]]

I would like to compare two list<string> in such way:

for example:

ListA = {aa,bb,cc}

ListB = {bb,aa,cc}

both of them are equal because the consist same elements (no matter in
which order).

What is the best way to do it in c#?

Assuming .NET 3.5 (and thus LINQ to Objects):

if (ListA.Except(ListB).Count() == 0 &&
ListB.Except(ListA).Count() == 0)

....

There are other solutions using the LINQ set operations too...

Jon

 

[Peter Morris]

if (ListA.Except(ListB).Count() == 0 &&
ListB.Except(ListA).Count() == 0)
<<

I suspected there would be a LINQ way to do it

However, for a large list I wonder how efficient it is compared to my
approach of sorting both lists?

 

[Peter Morris]

I will try it

 

[Peter Morris]

I wasn't expecting this...

(Time in MS)
Linq 858
Sort 9721
Dict 316
Linq - Sort = -8863
Linq - Dict = 542

I was originally writing something like the dictionary one but then I
thought "There must be a LINQ way that is more simple than this!" I didn't
know what it was so I thought "Sorting should be simple + quick" and went
for that instead.

This makes me wonder

01: How does LINQ implement it?
02: Why does sorting add so much overhead? I thought sort algorithms were
really quick, obviously not as fast as I first thought

What an interesting exercise



--
Pete
====
http://mrpmorris.blogspot.com
http://www.capableobjects.com



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

namespace ConsoleApplication14
{
class Program
{
static void Main(string[] args)
{
var list1 = new List<string>();
var list2 = new List<string>();

//Make up lots of random numbers
Random rnd = new Random();
for (int i = 0; i < 2 * 1000 * 1000; i++)
{
string valueToAdd = rnd.Next().ToString();
int listToAddTo = rnd.Next(2) + 1;
if ((listToAddTo & 1) != 0)
list1.Add(valueToAdd);
if ((listToAddTo & 2) != 0)
list2.Add(valueToAdd);
}

//Ensure the lists are the same length
while (list1.Count < list2.Count)
list1.Add("1");
while (list2.Count < list1.Count)
list2.Add("2");

var startTime = DateTime.Now;
bool linqResult = LinqCompare(list1, list2);
var linqTimeTaken = DateTime.Now - startTime;

startTime = DateTime.Now;
bool sortResult = SortCompare(list1, list2);
var sortTimeTaken = DateTime.Now - startTime;

startTime = DateTime.Now;
bool dictResult = DictCompare(list1, list2);
var dictTimeTaken = DateTime.Now - startTime;

Console.WriteLine("Linq " + linqTimeTaken.TotalMilliseconds.ToString());
Console.WriteLine("Sort " + sortTimeTaken.TotalMilliseconds.ToString());
Console.WriteLine("Dict " + dictTimeTaken.TotalMilliseconds.ToString());
Console.WriteLine("Linq - Sort = " + (linqTimeTaken -
sortTimeTaken).TotalMilliseconds.ToString());
Console.WriteLine("Linq - Dict = " + (linqTimeTaken -
dictTimeTaken).TotalMilliseconds.ToString());
Console.ReadLine();
}

static bool LinqCompare(List<string> list1, List<string> list2)
{
if (list1.Count != list2.Count)
return false;
return (list1.Except(list2).Count() == 0 && list2.Except(list1).Count()
== 0);
}

static bool SortCompare(List<string> list1, List<string> list2)
{
if (list1.Count != list2.Count)
return false;

var compareList1 = new List<string>(list1);
compareList1.Sort();

var compareList2 = new List<string>(list2);
compareList2.Sort();

for (int index = 0; index < compareList1.Count; index++)
if (compareList1[index] != compareList2[index])
return false;

return true;
}

static bool DictCompare(List<string> list1, List<string> list2)
{
if (list1.Count != list2.Count)
return false;
var dict = new Dictionary<string, int>(list1.Count);
foreach (string s in list1)
{
if (dict.ContainsKey(s))
{
dict++;
}
else
{
dict.Add(s, 1);
}
}

foreach (string s in list2)
{
if (!dict.ContainsKey(s))
return false;
dict--;
}

foreach (int v in dict.Values)
if (v != 0)
return false;

return true;
}
}
}

 

[Stefan Nobis]

I wasn't expecting this...

But why didn't you expect this?

02: Why does sorting add so much overhead? I thought sort
algorithms were really quick, obviously not as fast as I first
thought

Basic knowledge on algorithms and complexity:

- Sorting is (best average cases): O(n * log(n))
- Set difference (A without B): O(n)
- Hashtable lookup: O(1)

The drawback of the generic Dictionary is memory consumption and bad
worst cases performance (for both, open and closed hashmaps, IIRC in
..Net only open hashmaps are available).

So the really good solution is: If you need a collection with set
semantics, write your own collection class that implements these
semantics.