Compare methods

  • Thread starter Thread starter csharpula csharp
  • Start date Start date
C

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!
 
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;
}
 
csharpula said:
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!
Click to expand...

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;
}
 
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#?
Click to expand...

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
 
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?
 
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;
}
}
}
 
Peter Morris said:
I wasn't expecting this...
Click to expand...

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 :-)
Click to expand...

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. :)
 
Back
Top