Sorted List by value

[Guest]

Hello,

I´ve a problem with my Key-Value SortedList.

Is there a way to sort a list (or any other data structure) by value?

I have a list with 1000 key-value pairs and want to get
the pairs with the 20st highest values.


Regards,
Martin

 

[Marc Gravell]

SortedList is always sorted by value - however, you could perhaps
create a List<T> from the .Values, and .Sort() that, using either a
cobbled comparer / delegate, else just reverse after the default sort:
// dummy data
SortedList<int, int> sl = new SortedList<int, int>();
sl.Add(1, 6);
sl.Add(2, 1);
sl.Add(3, 3);
sl.Add(100, 2);
sl.Add(4, 17);
// sort values descending
List<int> l = new List<int>(sl.Values);
l.Sort();
l.Reverse();
// output the highest 3
for (int i = 0; i < 3; i++)
{
Console.WriteLine(l);
}

Marc

 

[Ignacio Machin \( .NET/ C# MVP \)]

Hi,

| Hello,
|
| I´ve a problem with my Key-Value SortedList.
|
| Is there a way to sort a list (or any other data structure) by value?

As you probably found out it's ordered only by Key , not by value.
That said I do not see a clean or clever solution for this. You could always
create a new instance with inverted mapping ( original keys are values).

 

[Guest]

SortedList is always sorted by value - however, you could perhaps
create a List<T> from the .Values, and .Sort() that, using either a
cobbled comparer / delegate, else just reverse after the default sort:
// dummy data
SortedList<int, int> sl = new SortedList<int, int>();
sl.Add(1, 6);
sl.Add(2, 1);
sl.Add(3, 3);
sl.Add(100, 2);
sl.Add(4, 17);
// sort values descending
List<int> l = new List<int>(sl.Values);
l.Sort();
l.Reverse();
// output the highest 3
for (int i = 0; i < 3; i++)
{
Console.WriteLine(l);
}

Thanks a lot!
But this won´t help.

Because I need the 3 keys of the 3-highest values

With your solution I only get the 3-highest values without keys.


It seems to me that there is no real solution,
except swapping keys- and values.


Regards,
Martin

 

[Marc Gravell]

OK, I missed the key bit... the following works... just about... I
wouldn't go near a SortedList<> for the inversion, as you can't
(without additional knowledge) guarantee that the current values are
unique:

SortedList<int, int> sl = new SortedList<int, int>();
sl.Add(1, 6);
sl.Add(2, 1);
sl.Add(3, 3);
sl.Add(100, 2);
sl.Add(4, 17);

List<KeyValuePair<int, int>> l = new
List<KeyValuePair<int,int>>(sl);
l.Sort(delegate(KeyValuePair<int, int> lhs,
KeyValuePair<int,int> rhs) {
return rhs.Value.CompareTo(lhs.Value); // note inversion
});

for (int i = 0; i < 3; i++) {
Console.WriteLine(l.Key + ": " + l.Value);
}

 

[Marc Gravell]

SortedList is always sorted by value
(d'oh, I clearly meant key, even if my fingers typed value... no,
really!)

Marc

 

[Bobbo]

Is there a way to sort a list (or any other data structure) by value?

An excellent suggestion I've seen from Jon Skeet somewhere (I forget
where sorry Jon!) is to maintain a parallel, reversed list where the
key and value pairings become reversed.

You could even take this a step further and implement a class
inheriting from SortedList (more thoroughly than my illustrative one
here) and maintain it automatically. The new class should just then
drop into wherever you're using SortedList.

class KeySortedList : SortedList
{
public SortedList ReversedList = new SortedList();

public new void Add(object key, object value)
{
ReversedList.Add(value, key);
base.Add(key, value);
}
}


If you're able to make the step to .net 2 then do so, as you can use
generics.

class KeySortedList<K, V> : SortedList<K, V>
{
public SortedList<V, K> ReversedList = new SortedList<V, K>();

public new void Add(K key, V value)
{
ReversedList.Add(value, key);
base.Add(key, value);
}
}

 

[Christof Nordiek]

SortedList is always sorted by value - however, you could perhaps create
a List<T> from the .Values, and .Sort() that, using either a cobbled
comparer / delegate, else just reverse after the default sort:
// dummy data
SortedList<int, int> sl = new SortedList<int, int>();
sl.Add(1, 6);
sl.Add(2, 1);
sl.Add(3, 3);
sl.Add(100, 2);
sl.Add(4, 17);
// sort values descending
List<int> l = new List<int>(sl.Values);
l.Sort();
l.Reverse();
// output the highest 3
for (int i = 0; i < 3; i++)
{
Console.WriteLine(l);
}

Thanks a lot!
But this won´t help.

Because I need the 3 keys of the 3-highest values

With your solution I only get the 3-highest values without keys.


It seems to me that there is no real solution,
except swapping keys- and values.

You could fill a (unsorted) List with the key-value-pairs and then sort this
by value. You'll have to use an IComparer or an Compare delegate wich
compares the values.
Or you use a sorted List with KeyValuePair where the value is where the
value is the key and the key is the value
But this wouldn't work, if the values aren't unique.
But you could try to built a datacontainer wich contains aswell the key as
also the value and wich can compare itself by value + key.

HTH
Christof

 

[Bobbo]

I wouldn't go near a SortedList<> for the inversion, as you can't
(without additional knowledge) guarantee that the current values are
unique:

Ah yes I forgot that little clanger, my turn to hold my hands up! As
I say I can't remember where I saw Jon's original post, but I dare say
it didn't contain such glaring omissions. Martin, ignore pretty much
everything I've said...

 

[not_a_commie]

So what I've done in the past with this is store the same object for
both the key and the value. The object has a IComparable that compares
the member of my object that I care about sorting. You can avoid
having to reverse the list by making larger numbers return -1, etc. In
the case that my IComparable determines two values are equal, I return
the comparison of the hashcodes instead, which should never return
equal.

 

[Marc Gravell]

determines two values are equal, I return the comparison of the hashcodes
instead, which should never return equal.

I must admit that I didn't really follow this (my bad: I'm being slow
this evening); however, it is perfectly expected for two different
values to return the same hashcode. In fact, if the IComparable says
equal, it would be curious for the hashcode to be different. Further,
for IEqualityComparer<T> (which is admitedly a bit different to
IComparable) the hashcode provision is lifted to the comparer to help
enable this (expected) behavior.

Marc

 

[not_a_commie]

I must admit that I didn't really follow this (my bad: I'm being slow
this evening); however, it is perfectly expected for two different
values to return the same hashcode. In fact, if the IComparable says
equal, it would be curious for the hashcode to be different. Further,
for IEqualityComparer<T> (which is admitedly a bit different to
IComparable) the hashcode provision is lifted to the comparer to help
enable this (expected) behavior.

A class is worth a thousand words. I wasn't sure if comparing
hashcodes was the right thing to do. I should probably just change a
cmp == 0 to cmp = 1, but I didn't know if that would cause some
infinite loop on the sort algorithm. Consider the following class used
for both key and value in a sorted list (as part of an A* search
algorithm):

private class NodeScore : IComparable<NodeScore>
{
public NodeScore ParentNodeScore;
public Edge InputEdge;
public Node CurrentNode;
public double ScoreToEnd;
public double ScoreFromStart;
public double G
{
get { return ScoreFromStart; }
}
public double H
{
get { return ScoreToEnd; }
}
public NodeScore() { }
public NodeScore(NodeScore parent, Node Node, Edge inputEdge,
double scoreToEnd, double scoreFromStart)
{
ParentNodeScore = parent;
CurrentNode = Node;
InputEdge = inputEdge;
ScoreToEnd = scoreToEnd;
ScoreFromStart = scoreFromStart;
}
public double Score
{
get { return ScoreFromStart + ScoreToEnd; }
}
public double F
{
get { return Score; }
}

#region IComparable<NodeScore> Members

public int CompareTo(NodeScore other)
{
int cmp = Score.CompareTo(other.Score);
if (cmp == 0) // we don't allow an equal: we'll compare hashcodes
if necessary
return GetHashCode().CompareTo(other.GetHashCode());
return cmp;
}

#endregion
}

 

[Marc Gravell]

Personally I wouldn't worry at all about returning 0 from CompareTo();
this just means that they aer (in sorting terms) comparable, and the
Sort() algorithms expect this. For *eqaulity* tests the Equals test
(ideally doubled via IEquatable) is preferable, as here Equals means
Equals... not just comparable.

However, the test you use
(GetHashCode().CompareTo(other.GetHashCode()) should be perfectly well
defined, so shouldn't be a problem; in a single pass of a Sort() the
hashcodes shouldn't themselves change (if ever), so comparing them
will be fine.

(for reference only)
The best way to truly screw a Sort() / SortedList (IComparable/
IComparer) is to make the CompareTo() non-transitive. Transitive (in
this context) means that if A < B, and B < C, then you can assume A <
C. Interesting fact: string.CompareTo() is demonstrably non-
transitive! This has been logged as a bug, which was acknowledged with
"will not fix". And they weren't even that "far out" strings! (http://
connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?
FeedbackID=236900)

The best way to truly screw a Dictionary (IEquatable/
IEqualityComparer) is to base GetHashCode() on non-immutable fields -
i.e. you change your Customer.Name and all of a sudden you get a
different hashcode and you can't find your entries in the dictionary.

Marc