Re: Compare methods

[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<stringlist1, List<stringlist2)
{
if (list1.Count != list2.Count)
return false;
return (list1.Except(list2).Count() == 0 && list2.Except(list1).Count()
== 0);
}

static bool SortCompare(List<stringlist1, List<stringlist2)
{
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<stringlist1, List<stringlist2)
{
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;
}
}
}

[Stefan Nobis]

"Peter Morris" <mr*********@SPAMgmail.comwrites:

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.