2016-04-05 24 views
0

Ich habe ein Problem, wie man ein Dikton in .NET 2.0 richtig sortieren. Dieses bisschen Code ist irgendwie alt (2002 oder so) und es funktioniert, aber nicht so, wie ich es möchte. Da das AvailableFlights Wörterbuch sehr groß sein kann, kann diese Sortierfunktion viel Zeit in Anspruch nehmen, die Kunden nicht sooo haben.Wörterbuch Sortieren .NET 2.0

jemand eine Idee, wie dies zu tun, ist der einzige Weg, ich weiß, ist ein orderby oder etwas hinzufügen, da ich im Garten spielte, als es war 2002.

Hinweis: dies Code eine laufende Website, das Problem ist, mein Chef will das schneller, aber ich kann keine großen Änderungen an dem Projekt vornehmen.

Die Sortierfunktion selbst funktioniert wie folgt: Es gibt ein Wörterbuch AvailableFlight die Flugobjekte enthält (mit dem Totalprice). Dies kommt von einer externen Quelle, daher ist eine Vorfilterung keine Option. Das Ziel zu erreichen ist, die Flüge mit dem niedrigsten Gesamtpreis auf zu haben.

FÜR DIE LEUTE, die keine Ahnung haben, was ich frage, es in meinem Projekt ist ein Wörterbuch, der als Objekt mit entsprechenden Integer-Schlüssel gespeichert Flugobjekte enthält. Ein Flugobjekt hat eine Eigenschaft Gesamtpreis, die sortiert werden müssen ASC. Dies geschieht mit dem von mir bereitgestellten Code, nur dass die Verarbeitung dieses Codeabschnitts etwa 30 Sekunden oder länger dauert, was nicht akzeptabel ist. Die Frage ist also, wie kann ich dies verbessern, so dass die Zeit Verarbeitung reduziert wird.

public void SortFlightResult() 
    { 
     //bool to check sorting is done or not 
     bool blSort = true; 
     //bool to stay in while or not 
     bool blWhileSort = true; 
     while (blWhileSort) 
     { 
      //check the availableFlights 
      foreach (int i in AvailableFlights.Keys) 
      { 
       foreach (int j in AvailableFlights.Keys) 
       { 
        //if id j is greater then id i and price is less then j must be in place of i 
        if ((AvailableFlights[j].TotalPrice < AvailableFlights[i].TotalPrice) && (j > i)) 
        { 
         //set temperary AvailableFlight object 
         AvailableFlight avTemp = new AvailableFlight(); 
         avTemp = AvailableFlights[i]; 
         AvailableFlights[i] = AvailableFlights[j]; 
         //keep id of the i (if j.id = 3 and i.id = 2) replace i with j but let id = 2 
         AvailableFlights[i].ID = i; 
         AvailableFlights[j] = avTemp; 
         AvailableFlights[j].ID = j; 
         //set bool fase so we know sort is not done 
         blSort = false; 
         //end both foreach loop so we can start over from the top of availableFlights 
         goto endLoop; 
        } 
       } 
      } 
     endLoop: 
      //if true --> availableFlights is sorted set bool while false to quit the function 
      if (blSort) 
      { 
       blWhileSort = false; 
      } 
      else 
      {//set bool sort back to true 
       blSort = true; 
      } 
     } 
    } 

die bullsh * Alle beiseite t, dank @D Stanley für seine nützlichen Kommentar. I Changed auf einen Heap-Algorithmus sortiert und die Zeit, die Schnitte Art der Verarbeitung nach unten von etwa 30 Sekunden bis 400 miliseconds, wirklich froh, mit dem!

Für die Menschen, die in dem Stapelsortier-Code Interesse:

Heapsort

public void HeapSort() 
    { 
     Stopwatch watch = System.Diagnostics.Stopwatch.StartNew(); 

     //Build Max-Heap 
     Dictionary<int, AvailableFlight> input = AvailableFlights; 
     int heapSize = input.Keys.Count; 

     for (int p = (heapSize -1) /2; p >= 0; p--) 
     { 
      MaxHeapify(AvailableFlights, heapSize, p); 
     } 
     for (int i = AvailableFlights.Count - 1; i > 0; i--) 
     { 
      //Swap 
      AvailableFlight temp = input[i]; 
      input[i] = input[0]; 
      input[0] = temp; 

      heapSize--; 
      MaxHeapify(AvailableFlights, heapSize, 0); 
     } 

     watch.Stop(); 
     Debug.WriteLine("SortFlightResult 2: " + watch.ElapsedMilliseconds); 
    } 

MaxHeapify

private static void MaxHeapify(Dictionary<int, AvailableFlight> input, int heapSize, int index) 
    { 
     int left = (index + 1) * 2 - 1; 
     int right = (index + 1) * 2; 
     int largest = 0; 

     if (left < heapSize && input[left].TotalPrice > input[index].TotalPrice) 
     { 
      largest = left; 
     } 
     else 
     { 
      largest = index; 
     } 

     if (right < heapSize && input[right].TotalPrice > input[largest].TotalPrice) 
     { 
      largest = right; 
     } 
     if (largest != index) 
     { 
      AvailableFlight temp = input[index]; 
      input[index] = input[largest]; 
      input[largest] = temp; 

      MaxHeapify(input, heapSize, largest); 
     } 
    } 
+4

Wörterbücher sind nicht sortiert - wenn Sie eine Liste der Elemente haben wollen und in der Lage, die Elemente verwenden eine 'list' neu zu ordnen anstelle eines 'Dictionary' –

+2

[' SortedDictionary'] (https://msdn.microsoft.com/en-us/library/f7fta44c (v = vs.110) .aspx). – Sinatr

+0

Ja. SortedDictionary. – TomTom

Antwort

3

Sie Angenommen, haben so etwas wie diese AvailableFlight Klasse:

public class AvailableFlight 
{ 
    public decimal TotalPrice { get; set; } 
    // ... more properties 
} 

Sie können eine Klasse erstellen IComparer<AvailableFlight> wie diese Umsetzung:

public class FlightByPriceComparer : IComparer<AvailableFlight> 
{ 
    public int Compare(AvailableFlight x, AvailableFlight y) 
    { 
     if (ReferenceEquals(x, null)) 
      return ReferenceEquals(y, null) ? 0 : -1; 
     if (ReferenceEquals(y, null)) return 1; 
     return x.TotalPrice.CompareTo(y.TotalPrice); 
    } 
} 

Und diese verwenden, um ein List<AvailableFlight> Ihres Wörterbuch der Werte zu sortieren:

Dictionary<int, AvailableFlight> AvailableFlights = ... // whereever you got them from 
List<AvailableFlight> sortedFlights = new List<AvailableFlight>(AvailableFlights.Values); 
sortedFlights.Sort(new FlightByPriceComparer()); 

Dies sollte Ihre Blase Art schneller als , nach MSDN verwendet es diese Sortieralgorithmen:

Diese Methode verwendet System.Array.Sort, das den QuickSort-Algorithmus verwendet. Diese Implementierung führt eine instabile Sortierung durch; Das heißt, wenn zwei Elemente gleich sind, wird ihre Reihenfolge möglicherweise nicht beibehalten. Im Gegensatz dazu behält eine stabile Sortierung die Reihenfolge der Elemente bei, die gleich sind.

Im Durchschnitt ist diese Methode eine O (n log n) -Operation, wobei n Count ist; im schlimmsten Fall ist es eine O (n^2) -Operation.


Beachten Sie, dass es sich um ein Wörterbuch zu sortieren nach seinen Werten nicht möglich ist, gibt es eine SortedDictionary aber das nur durch seine Keys sortiert ist.

+0

Wenn es aus einem normalen Wörterbuch kommt, ist es wahrscheinlich sowieso unsortiert. QuickSort ist so ziemlich das schnellste, das Sie erhalten werden, ohne alles parallelisieren zu müssen (was wahrscheinlich als große Veränderung gilt) - also denke ich, dass dies die beste Antwort auf das Problem ist. –

-2

Verwenden System.Linq es einfach und klar für das Lesen zu machen:

AvailableFlights = AvailableFlights.OrderBy(x => x.Value.TotalPrice).ToDictionary(x => x.Key, x=>x.Value); 
+0

LINQ ist in .NET2.0 nicht verfügbar, daher wird dies nicht einmal in OPs Code kompiliert. –

+0

Uuups, sah nicht auf die Voraussetzungen, sorry. Daher ist die Sortierung nach List oder Array die einzige Wahl! –