[C#] List<int> Sorteer aflopend

[Aloys]

Tja, mijn titel legt het hele probleem denk ik al uit . Ik wil dus een List sorteren, das allemaal geen probleem. Maar het probleem is dat het aflopend moet, omdat ik dus bepaalde items uit een lijst wil verwijderen.

Ff uitlegje: Wanneer ik een lijst met getallen heb van de indexen van items die verwijdert moeten worden, en je begint bij de laagste, zul je het probleem hebben dat alle items 1 plek doorschuiven. Dat probleem heb je geen last van wanneer je achteraan begint met verwijderen.

Ik heb al gezocht in de msdn van microsoft en op google, en ben er al wel achter dat ik iets met CompareTo met Sort moet doen. Maar hoe werkt dat ooit? . Iemand die me dat kan uitleggen?

[whoami]

Je kan een eigen Sorteer class maken, die IComparable implementeert. Je vergelijkt de x en de y, en het resultaat vermenigvuldig je met -1 en dat return je dan.

Maareh, als het enkel om het verwijderen gaat, dan kan je toch ook die lijst van achter naar voor doorlopen, en zo verwijderen ?

code:

for( int i = theList.Count - 1; i >= 0; i-- )
{
   if( .... )
       theList.RemoveAt (i);
}

[Feyd-Rautha]

ziehier: http://blogs.msdn.com/brada/archive/2004/04/15/114129.aspx

Die CompareTo wordt door het framework gebruikt om te bepalen dat element X kleiner is dan een ander element Y. Uw reverse sort, zal dus een CompareTo moeten implementeren die zegt dat element X groter is dan element Y.

[Aloys]

Ik had precies het zelfde stukje code als jouw, alleen zonder die >= (ik had >) Waarom moet ik weer moeilijk doen? Thnx Whoami

edit: Weet alweer waarom ik moeilijk deed: Had mijn code vervangen voor een foreach loopje. Dus als dat Comparable niet zo moeilijk is wil je het dan uitleggen?

[ Voor 37% gewijzigd door Aloys op 28-03-2007 16:13 ]

[whoami]

Of, je kan ook gebruik maken van de Comparision delegate in .NET 2.0:

code:

List<int> l = new List<int>();
l.Add (1);
l.Add (5);
l.Add (3);
l.Add (10);

l.Sort (new Comparision<int> (ReverseCompare));

..

private int ReverseCompare(int x, int y)
{
   return Comparer<int>.Default.Compare (x, y) * -1;
}

mooi he.

[Aloys]

ghgh

[whoami]

Maar je kan ook dit doen:

code:

public class ReverseIntegerSorter : IComparable<int>
{
    public int Compare(int x, int y)
    {
         return Comparer<int>.Default.Compare (x, y) * -1;
    }
}

En dan deze zo gebruiken:

code:

List<int> l = new List<int>();
l.Add (4);
l.Add (30);
l.Add (1);
l.Add (5);
l.Add (3);

l.Sort (new ReverseIntegerSorter());

[dotcode]

code:

list.Sort();
list.Reverse();

[Aloys]

nog meer gejank hier.... Dacht dat die Reverse niet bestond?? Was zeker zo bij ArrayList, want dat gebruikte ik eerst. Naja, gelukkig heb ik het nu werkend.

[EfBe]

Waarom gebruik je niet List<T>.RemoveAll(Predicate<U>) ? Dat kan dan in 1 regel, waarbij je een anonymous method gebruikt in een delegate die bv kijkt of de waarde in een lijstje staat van te verwijderen getallen. Dus iets als:

C#:

List<int> toRemove = new List<int>();
toRemove.Add(1);
toRemove.Add(2);

List<int> numbers = new List<int>();
for(int i = 0; i < 10; i++)
{
    numbers.Add(i);
}

numbers.RemoveAll(delegate(int toCheck) { return toRemove.Contains(toCheck);});

[.oisyn]

@whoami: Waarom eigenlijk een vermenigvuldiging met -1 en niet gewoon de - operator gebruiken?

[ Voor 8% gewijzigd door .oisyn op 28-03-2007 16:55 ]

[whoami]

Omdat ik dat duidelijker / leesbaarder vind dan

code:

-Comparer<int>.Default.Compare ( ... )

Maar die oplossing van EfBe is wel cool.

[ Voor 18% gewijzigd door whoami op 28-03-2007 17:27 ]

[farlane]

Waarom niet y.CompareTo( x ) ?

[Aloys]

EfBe schreef op woensdag 28 maart 2007 @ 16:54:
Waarom gebruik je niet List<T>.RemoveAll(Predicate<U>) ? Dat kan dan in 1 regel, waarbij je een anonymous method gebruikt in een delegate die bv kijkt of de waarde in een lijstje staat van te verwijderen getallen. Dus iets als:

C#:

List<int> toRemove = new List<int>();
toRemove.Add(1);
toRemove.Add(2);

List<int> numbers = new List<int>();
for(int i = 0; i < 10; i++)
{
    numbers.Add(i);
}

numbers.RemoveAll(delegate(int toCheck) { return toRemove.Contains(toCheck);});

Gaat op deze manier niet werken in mijn geval. Want ik moet een string uit een List verwijderen. En dat is de string met de index toRemove[huppeldepup].

[EfBe]

Dan moet je inderdaad de indices sorten en dan afsjouwen. Wat je ook kunt doen, en wellicht is dat efficienter, is een lijst aanmaken van de strings op de indices die je moet verwijderen en dan die RemoveAll gebruiken warbij toRemove de strings bevat die je wilt verwijderen. Scheelt een sort.

[Aloys]

EfBe schreef op donderdag 29 maart 2007 @ 19:06:
... Scheelt een sort.

Is een sort zo langzaam dan?... (Tis btw voor de contest... dus snelheid is interresant.)

[6K]

list.Sort(delegate(int i1, int i2) { return i1.CompareTo(i2); });

volgens mij werkt dit ook
(ik doe het in de contest zo met objecten ipv ints)

[.oisyn]

EfBe schreef op donderdag 29 maart 2007 @ 19:06:
Dan moet je inderdaad de indices sorten en dan afsjouwen. Wat je ook kunt doen, en wellicht is dat efficienter, is een lijst aanmaken van de strings op de indices die je moet verwijderen en dan die RemoveAll gebruiken warbij toRemove de strings bevat die je wilt verwijderen. Scheelt een sort.

Een sort van een paar ints ja, waarna je gewoon lineair over je lijst heen kan lopen en op de goede plek de elementen kunt verwijderen. Anders moet je n*k string compares doen. Dat laatste lijkt me toch een stuk duurder .

De allereerste oplossing van whoami lijkt me toch het handigst

[ Voor 5% gewijzigd door .oisyn op 30-03-2007 11:41 ]

[it0]

Aloys schreef op donderdag 29 maart 2007 @ 19:07:
[...]

Is een sort zo langzaam dan?... (Tis btw voor de contest... dus snelheid is interresant.)

Dat hangt van je algoritme en je lijst af. Hoe complexer het algoritme of hoe groter je lijst, hoe langer het duurt.

Daarom gebruikt men ook zo graag een hash of zo. Maar met computers van de huidige dag wordt dat dus een issue met zeer veel items.

[EfBe]

.oisyn schreef op vrijdag 30 maart 2007 @ 11:38:
[...]
Een sort van een paar ints ja, waarna je gewoon lineair over je lijst heen kan lopen en op de goede plek de elementen kunt verwijderen. Anders moet je n*k string compares doen. Dat laatste lijkt me toch een stuk duurder .
De allereerste oplossing van whoami lijkt me toch het handigst

Daar heb je ook weer gelijk in. Ikzelf gebruik zelden dit soort constructies vandaar dat ik dit finaal over het hoofd zag , zodra ik moet verwijderen uit een lijst gebruik ik een hashtable, indien mogelijk natuurlijk (een lijst met dupes kan niet) en dan heb je dit gezeik niet. Indexes in lijst 1 die verwijzen naar elementen in lijst 2 is overigens niet echt jofel, als je het kunt vermijden (dus als je geen 'view' bouwt op een lijst) dan zou ik dat zeker doen, dus ipv indices direct de references in de lijst gebruiken, eventueel keys gebruiken die je gebruikt als keys in een hashtable zodat je objects makkelijker opzoekt en ook weer verwijdert.