Effizientes Durchlaufen einer Liste, um ein Objekt mit der größten Zahl zu finden!

Question

Mit c# habe ich eine Liste, die Objekte haben alle eine Float-Masse, die randomisiert wird, wenn das Objekt erstellt wird.

Wie kann man am effizientesten eine Schleife durch die Liste ziehen und das Objekt mit der größten Masse finden?

Answer 1

Der effizienteste Weg, dies mit einer einfachen Liste zu tun, ist eine einfache Suche in linearer Zeit, wie in

SomeObject winner;
float maxMass = 0.0f; // Assuming all masses are at least zero!
foreach(SomeObject o in objects) {
    if(o.mass > maxMass) {
        maxMass = o.mass;
        winner = o;
    }
}

Wenn Sie vorhaben, dies regelmäßig zu tun, kann es von Vorteil sein, die Gegenstände nach ihrer Masse geordnet aufzubewahren und/oder einen geeigneteren Lagerbehälter zu verwenden.

Answer 2

Klingt wie ein perfekter Kandidat für die MaxBy/MinBy-Operatoren in morelinq . Sie können es wie folgt verwenden:

objects.MaxBy(obj=>obj.Mass)

Answer 3

Die Implementierung von IComparable würde die Dinge einfach und leicht zu pflegen machen. Ich habe ein Beispiel bereitgestellt. Ich hoffe, das hilft. Ich bin nicht sicher, ob dies effizienter ist als eine Schleife. Mir ist klar, dass die Verwendung von linq manchmal die Leistung beim ersten Aufruf etwas verschlechtert.

Aber sicherlich ist ein wartbarer Code oft wichtiger als ein geringer Leistungsgewinn. Kann jemand mehr Details zur Leistung der PARALLEL-Ausführung im Vergleich zur Schleifenbildung mit AsParallel() liefern?

class Program
{
    delegate int Del();
    static void Main(string[] args)
    {
        List<MyClass> connections = new List<MyClass>();
        connections.Add(new MyClass() { name = "a", mass = 5.001f });
        connections.Add(new MyClass() { name = "c", mass = 4.999f }); 
        connections.Add(new MyClass() { name = "b", mass = 4.2f });
        connections.Add(new MyClass() { name = "a", mass = 4.99f });

        MyClass maxConnection = connections.AsParallel().Max();
        Console.WriteLine("{0} {1} ", maxConnection.name, maxConnection.mass);
        Console.ReadLine();
    }

    class MyClass : IComparable
    {
        public string name { get; set; }
        public float mass { get; set; }

        public int CompareTo(object obj)
        {
            return (int)(mass - ((MyClass)obj).mass);
        }
    }
}

Answer 4

Wenn Sie bereit sind, ein wenig Platz gegen Zeit zu tauschen, können Sie in einem der Instanzkonstruktoren etwas wie das Folgende einfügen

public Foo(Foo min, Foo max)
{
   min = min ?? new Foo();  
   max = max ?? new Foo();

   if(max.mass < this.mass)
    max = this;

   if(min > this.mass)
    min = this;
}

Und bei der Objekterstellung muss die aufrufende Methode diese Parameter übergeben.

Foo min, max = null;

//Create a bunch of Foo objects

var Foos = from n in Enumerable.Range(0, 10000) select new Foo(min, max);

Answer 5

Die einfachste und effizienteste Lösung (unter der Annahme wiederholter Abfragen) ist die Sortierung der Liste nach Größe.

d.h.

private int SortByMass(ObjectWithMass left,ObjectWithMass right)
{
  return left.Mass.CompareTo(right.Mass);
}    
List<ObjectWithMass> myList = MyFunctionToPopulateTheList();
myList.sort(SortByMass);

Sobald die Liste sortiert ist, ist das erste Element das kleinste und das letzte das größte. Sie können verwenden myList.Reverse() wenn Sie es von der größten zur kleinsten Größe haben wollen.

Das Sortieren dauert o(nlog(n)), und das Finden des größten Objekts ist myList[myList.Count -1] . das ist o(1) für .net-Listen (sie sind eigentlich Arrays darunter)