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.Collecti ons.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplicat ion14
{
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().ToSt ring();
int listToAddTo = rnd.Next(2) + 1;
if ((listToAddTo & 1) != 0)
list1.Add(value ToAdd);
if ((listToAddTo & 2) != 0)
list2.Add(value ToAdd);
}

//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(lis t1, list2);
var linqTimeTaken = DateTime.Now - startTime;

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

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

Console.WriteLi ne("Linq " + linqTimeTaken.T otalMillisecond s.ToString());
Console.WriteLi ne("Sort " + sortTimeTaken.T otalMillisecond s.ToString());
Console.WriteLi ne("Dict " + dictTimeTaken.T otalMillisecond s.ToString());
Console.WriteLi ne("Linq - Sort = " + (linqTimeTaken -
sortTimeTaken). TotalMillisecon ds.ToString());
Console.WriteLi ne("Linq - Dict = " + (linqTimeTaken -
dictTimeTaken). TotalMillisecon ds.ToString());
Console.ReadLin e();
}

static bool LinqCompare(Lis t<stringlist1, List<stringlist 2)
{
if (list1.Count != list2.Count)
return false;
return (list1.Except(l ist2).Count() == 0 && list2.Except(li st1).Count()
== 0);
}

static bool SortCompare(Lis t<stringlist1, List<stringlist 2)
{
if (list1.Count != list2.Count)
return false;

var compareList1 = new List<string>(li st1);
compareList1.So rt();

var compareList2 = new List<string>(li st2);
compareList2.So rt();

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

return true;
}

static bool DictCompare(Lis t<stringlist1, List<stringlist 2)
{
if (list1.Count != list2.Count)
return false;
var dict = new Dictionary<stri ng, int>(list1.Coun t);
foreach (string s in list1)
{
if (dict.ContainsK ey(s))
{
dict[s]++;
}
else
{
dict.Add(s, 1);
}
}

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

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

return true;
}
}
}

[Stefan Nobis]

Re: Compare methods

"Peter Morris" <mrpmorrisNO@SP AMgmail.comwrit es:

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.