SortList<ulong,ulong> Exception on .Min().key; ! why?

M

mario semo

Hello,

why does the following simple collection code throws an exception on Min()
when there are more than 1 element in the Collection?


static void SLTest()
{
SortedList<ulong, ulong> lList = new SortedList<ulong, ulong>();
lList.Add(1, 0);
lList.Add(2, 0);
ulong l = lList.Min().Key;
Console.WriteLine(l);

/* (at least one element must implement IComparable ...)
Unbehandelte Ausnahme: System.ArgumentException: Mindestens ein Objekt muss
IComparable implementieren.
bei System.Collections.Comparer.Compare(Object a, Object b)
bei System.Collections.Generic.ObjectComparer`1.Compare(T x, T y)
bei System.Linq.Enumerable.Min[TSource](IEnumerable`1 source)
bei EulerDotNetProblems.EulerDotNetProblems.SLTest() in
S:\VS\Test\MS\ConsoleApplication4\ConsoleApplication4\Program
..cs:Zeile 3891.
bei EulerDotNetProblems.EulerDotNetProblems.Main(String[] args) in
S:\VS\Test\MS\ConsoleApplication4\ConsoleApplicati
on4\Program.cs:Zeile 124.
Drücken Sie eine beliebige Taste . . .
*/

}
 
P

Pavel Minaev

Hello,

why does the following simple collection code throws an exception on Min()
when there are more than 1 element in the Collection?

    static void SLTest()
    {
      SortedList<ulong, ulong> lList = new SortedList<ulong, ulong>();
      lList.Add(1, 0);
      lList.Add(2, 0);
      ulong l = lList.Min().Key;
      Console.WriteLine(l);

/*  (at least one element must implement IComparable ...)
Click to expand...

The reason why you can use Max() here is that SortedList<TKey, TValue>
is enumerable; it may not be so obvious that it's actually
IEnumerable<KeyValuePair<TKey, TValue>>. So when you use Min(), it's
trying to compare the KeyValuePair objects in the list; and they are
not comparable (they don't implement IComparable, as the error message
tells you).

This makes sense, anyway - what behavior do you expect from a
comparison of two tuples of two ints? There's no reasonable default
ordering here. What were you actually trying to do? Get the element
with the smallest key?
 
M

mario semo

Pavel Minaev said:
On Jan 21, 3:13 pm, "mario semo" <[email protected]> wrote:
Click to expand...
The reason why you can use Max() here is that SortedList<TKey, TValue>
is enumerable; it may not be so obvious that it's actually
IEnumerable<KeyValuePair<TKey, TValue>>. So when you use Min(), it's
trying to compare the KeyValuePair objects in the list; and they are
not comparable (they don't implement IComparable, as the error message
tells you).

This makes sense, anyway - what behavior do you expect from a
comparison of two tuples of two ints? There's no reasonable default
ordering here. What were you actually trying to do? Get the element
with the smallest key?
Click to expand...

Pavel,

thanks for your explanation.

yes. i thought the collection is sorted by key and i want to get the element
with the smallest key. (i am just interested in the smallest key).

mario.
 
S

Stefan L

Hi Mario,

as the collection is sorted (SortedList), iList[0].Key should already do
the trick.

HTH,
Stefan
 
M

mario semo

Stefan L said:
Hi Mario,

as the collection is sorted (SortedList), iList[0].Key should already do
the trick.
Click to expand...

Stefan,

This was my first try, but this is even not compileable (and i didnt mention
it in my first)

static void SLTest()
{
SortedList<ulong, ulong> lList = new SortedList<ulong, ulong>();
lList.Add(1, 456);
lList.Add(2, 789);
ulong l = lList[0].Key;

Error 1 'ulong' does not contain a definition for 'Key' and no extension
method 'Key' accepting a first argument of type 'ulong' could be found (are
you missing a using directive or an assembly reference?)S:\VS\Test\MS\ConsoleApplication4\ConsoleApplication4\Program.cs 3891 26 EulerDotNetApp Console.WriteLine(l);
}

ok, so i tried

Console.WriteLine(lList[0].ToString());

with the runtime error:


Unbehandelte Ausnahme: System.Collections.Generic.KeyNotFoundException: Der
angegebene Schlüssel war
angegeben.
bei System.ThrowHelper.ThrowKeyNotFoundException()
bei System.Collections.Generic.SortedList`2.get_Item(TKey key)
bei EulerDotNetProblems.EulerDotNetProblems.SLTest() in
S:\VS\Test\MS\ConsoleApplication4\Console

(ok, that was to be expected : operator [] tries to access the collection
via key, and returns the corresponding value)
list[x] == list.findValueWithKey(x). // pseudo code

so : after list.Add(2,789) we get : list[2] == 789
 
J

Jeff Johnson

as the collection is sorted (SortedList), iList[0].Key should already do
the trick.
Click to expand...

Stefan,

This was my first try, but this is even not compileable (and i didnt
mention it in my first)
Click to expand...

I believe a foreach loop will return the items in sorted order, so you can
do this:

ulong minKey;

foreach(KeyValuePair<ulong, ulong> kvp in IList)
{
minKey = kvp.Key;
break;
}
 
C

Chris Dunaway

Stefan L said:
Hi Mario,
Click to expand...
as the collection is sorted (SortedList), iList[0].Key should already do
the trick.
Click to expand...

Stefan,

This was my first try, but this is even not compileable (and i didnt mention
it in my first)

static void SLTest()
{
SortedList<ulong, ulong> lList = new SortedList<ulong, ulong>();
lList.Add(1, 456);
lList.Add(2, 789);
ulong l = lList[0].Key;

Error 1 'ulong' does not contain a definition for 'Key' and no extension
method 'Key' accepting a first argument of type 'ulong' could be found (are
you missing a using directive or an assembly reference?)S:\VS\Test\MS\ConsoleApplication4\ConsoleApplication4\Program.cs 3891 26 EulerDotNetApp Console.WriteLine(l);
}

ok, so i tried

Console.WriteLine(lList[0].ToString());

with the runtime error:

Unbehandelte Ausnahme: System.Collections.Generic.KeyNotFoundException: Der
angegebene Schlüssel war
angegeben.
bei System.ThrowHelper.ThrowKeyNotFoundException()
bei System.Collections.Generic.SortedList`2.get_Item(TKey key)
bei EulerDotNetProblems.EulerDotNetProblems.SLTest() in
S:\VS\Test\MS\ConsoleApplication4\Console

(ok, that was to be expected : operator [] tries to access the collection
via key, and returns the corresponding value)
list[x] == list.findValueWithKey(x). // pseudo code

so : after list.Add(2,789) we get : list[2] == 789
Click to expand...

Try this:

static void Main(string[] args) {

SortedList<ulong, ulong> lList = new SortedList<ulong,
ulong>();
lList.Add(2, 123);
lList.Add(6, 456);
lList.Add(1, 789);

ulong smallestKey = lList.Keys[0];
ulong valueOfSmallestKey = lList[lList.Keys[0]];

Console.WriteLine("Smallest Key: {0}, Value: {1}",
smallestKey, valueOfSmallestKey);
Console.ReadLine();
}

Chris
 
S

Stefan L

Ahhhh, yes, right. These are the moments where one starts thinking about
why calling something *List what's a Dictionary in the end..
Funny, I think I actually really got caught in this trap, too, when I
was using the SortedList once.
BTW: Does someone know the exact difference to a SortedDictionary? Help
says something from a slightly differing internal implementation, but I
can't figure it out...



Chris said:
Stefan L said:
Hi Mario,
as the collection is sorted (SortedList), iList[0].Key should already do
the trick.
Click to expand...
Stefan,

This was my first try, but this is even not compileable (and i didnt mention
it in my first)

static void SLTest()
{
SortedList<ulong, ulong> lList = new SortedList<ulong, ulong>();
lList.Add(1, 456);
lList.Add(2, 789);
ulong l = lList[0].Key;

Error 1 'ulong' does not contain a definition for 'Key' and no extension
method 'Key' accepting a first argument of type 'ulong' could be found (are
you missing a using directive or an assembly reference?)S:\VS\Test\MS\ConsoleApplication4\ConsoleApplication4\Program.cs 3891 26 EulerDotNetApp Console.WriteLine(l);
}

ok, so i tried

Console.WriteLine(lList[0].ToString());

with the runtime error:

Unbehandelte Ausnahme: System.Collections.Generic.KeyNotFoundException: Der
angegebene Schlüssel war
angegeben.
bei System.ThrowHelper.ThrowKeyNotFoundException()
bei System.Collections.Generic.SortedList`2.get_Item(TKey key)
bei EulerDotNetProblems.EulerDotNetProblems.SLTest() in
S:\VS\Test\MS\ConsoleApplication4\Console

(ok, that was to be expected : operator [] tries to access the collection
via key, and returns the corresponding value)
list[x] == list.findValueWithKey(x). // pseudo code

so : after list.Add(2,789) we get : list[2] == 789
Click to expand...

Try this:

static void Main(string[] args) {

SortedList<ulong, ulong> lList = new SortedList<ulong,
ulong>();
lList.Add(2, 123);
lList.Add(6, 456);
lList.Add(1, 789);

ulong smallestKey = lList.Keys[0];
ulong valueOfSmallestKey = lList[lList.Keys[0]];

Console.WriteLine("Smallest Key: {0}, Value: {1}",
smallestKey, valueOfSmallestKey);
Console.ReadLine();
}

Chris
Click to expand...
 
J

Jeff Johnson

BTW: Does someone know the exact difference to a SortedDictionary? Help
says something from a slightly differing internal implementation, but I
can't figure it out...
Click to expand...

I believe the help says that the list is better for fewer entries, whereas
the dictionary is better for many entries. That's from memory, though....
 
P

Pavel Minaev

Ahhhh, yes, right. These are the moments where one starts thinking about
why calling something *List what's a Dictionary in the end..
Funny, I think I actually really got caught in this trap, too, when I
was using the SortedList once.
BTW: Does someone know the exact difference to a SortedDictionary? Help
says something from a slightly differing internal implementation, but I
can't figure it out...
Click to expand...

Yes, it's an implementation difference. SortedList is essentially just
a an auto-sorted array; SortedDictionary is your typical binary tree
similar to std::map in C++ and TreeMap in Java. So SortedList
insertions are O(n), while SortedDictionary are O(log n); but
SortedList is more memory efficient, and has faster lookups and
indexing.
 
M

mario semo

Pavel Minaev said:
On Jan 22, 8:59 am, Stefan L <[email protected]>

Yes, it's an implementation difference. SortedList is essentially just
a an auto-sorted array; SortedDictionary is your typical binary tree
similar to std::map in C++ and TreeMap in Java. So SortedList
insertions are O(n), while SortedDictionary are O(log n); but
SortedList is more memory efficient, and has faster lookups and
indexing.
Click to expand...

Pavel,

ahhh, thats explains why my implementation (about 1000000000 (10**10)
insertions, searches and removes of elements) takes in C# about 4000sec
(while in C++ it requires just 0.6sec)

So i changed
SortedList<ulong, ulong> lHammingList = new SortedList<ulong,
ulong>();
to
SortedDictionary<ulong, ulong> lHammingList = new
SortedDictionary<ulong, ulong>();

and from:
ulong l = lHammingList.Keys[0]; // does not compile with
SortedDirectory
to
ulong l = lHammingList.Keys.First();

and now the code performs much better! (and yield the same result)

duration: 7171,875 milliseconds.
instead of 4440000 ms.

Question: Are the type of data structures behind these C# Lists and
Directories etc some documented (not : what is an AVL* Tree, just
SortedDirectory is a binary tree or AVL or ...???) ?

thanks a lot.
 
P

Pavel Minaev

Question: Are the type of data structures behind these C# Lists and
Directories etc some documented (not : what is an AVL* Tree, just
SortedDirectory is a binary tree or AVL or ...???) ?
Click to expand...

The data structures are not documented, but algorithmic compexity is,
if you look at the corresponding MSDN articles for those collection
classes.
 
Top