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!

*** Sent via Developersdex http://www.developersdex.com ***

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;
}



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

csharpula csharp wrote:
> 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[s]++;
} else {
dict.Add(s, 1);
}
}
foreach (string s in ListB) {
if (!dict.ContainsKey(s)) {
return false;
}
dict[s]--;
}
foreach (int v in dict.Values) {
if (v != 0) {
return false;
}
}
return true;
}


--
Göran Andersson
_____
http://www.guffa.com

On Oct 23, 10:42*am, csharpula csharp <csharp...@yahoo.com> wrote:
> 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

>>
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?



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

I will try it :-)

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[s]++;
}
else
{
dict.Add(s, 1);
}
}

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

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

return true;
}
}
}

"Peter Morris" <(E-Mail Removed)> writes:

> 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.

--
Stefan.