lustig genug, das ist wahrscheinlich ein Stack-Überlauf-Problem

Question

Die folgende Prozedur (Erklärung folgt) funktioniert gut für wirklich kleine Listen, aber wenn die Liste eine größere Anzahl von Elementen enthält (1/2 Millionen) die Anwendung gibt "nicht reagiert" Staat, und es dauert etwa 2,5 Minuten zu beenden (sehr schlechte Zeit). Ich könnte hinzufügen, die Anwendung benötigt, um Listen von 100 Millionen Artikel mindestens (schließlich) zu verarbeiten.

hier ist der Code für das problematische Verfahren:

public void removeItems(List<long> L, SortedList<long, List<long>> _subLists) 
    { 
     foreach (KeyValuePair<long, List<long>> kvp in _subLists) 
     { 
      foreach (long duplicate in kvp.Value) 
      { 
       int j = L.IndexOf(duplicate); 
       L.RemoveRange(j,(int)kvp.Key); 

      } 
     } 
    } 

L eine Liste von Long-Wert ist. _subLists ist eine sortierte Liste, wobei jeder Wert eine Liste von Werten von L ist, die eine arithmetische Progressionsreihe mit einer gewissen Differenz (nicht relevant) beginnt. Der diesem Wert zugeordnete Schlüssel ist die Länge der Reihe, die die Werte enthalten.

Beispiel:

L = {1,2,3,5,6,7,18,20,21} _subLists = {2, 20 <>} {3, < 1,5> }

Das Verfahren einfach entfernt die arithmetische Reihe Serie von L.

Answer 1

die Laufzeit dieses Verfahrens in O-Notation n^2, wäre das ziemlich langsam ist und Sie können eine langsame Laufzeit, wenn man erwarten, der Listen hat 100 Millionen Einträge. Es gibt hier kein Stack-Overflow-Problem, es ist einfach langsam, so viele Daten zu durchlaufen. Ich sehe hier wirklich keine Frage, willst du das schneller machen? Wenn ja, ist die verschachtelte For-Schleife definitiv das Problem.

Answer 2

Ihr Problem ist, dass Sie eine Menge von Artikeln aus L entfernen, was eine sehr kostspielige Operation ist. Jedes Mal, wenn ein Objekt entfernt wird, wird Speicher kopiert, um alle Objekte über den gelöschten Objekten zu verschieben. Je mehr Gegenstände entfernt werden und je mehr Gegenstände zu mischen sind, desto länger dauert es. Speicher ist ein Flaschenhals für die Leistung, RAM läuft langsamer als die CPU, und wenn Sie auf die Festplatte paging, ist es wirklich langsam.

Wie können Sie das verbessern?

Die einfachste Option ist die Verwendung eines Containers für L, der eine bessere Leistung beim Entfernen von Objekten bietet - beispielsweise eine LinkedList. LinkedLists müssen Elemente im Speicher nicht verschieben, wenn Elemente entfernt werden, aber sie benötigen mehr Speicher zum Speichern der Daten (zwei Zeiger pro Wert). Wenn dies zu viel Aufwand ist, dann vielleicht ein LinkedList <List <long>> statt wo jeder List <long> eine maximale Anzahl von Werten hält.

Alternativ können Sie den Löschalgorithmus ändern, sodass Sie über die Liste L iterieren und eine neue Liste erstellen, die die Werte enthält, die nicht in den _subLists gefunden werden. Sie können die Art ändern, in der _subLists Daten speichert, um das Auffinden von Elementen in Bereichen zu beschleunigen.

Answer 3

Wenn möglich:

A) Konvertieren Sie L in eine sortierte verkettete Liste. O: n * log (n)

B) Konvertieren Sie Unterlisten in sortierte Listenpaare, wobei das erste Element das # in der Sequenz in L ist (doppelt im gebuchten Code - Snippet) und das zweite Element die Länge des Sequenz. O: n * log (n)

C) Führen Sie einen einzelnen Durchlauf durch L mit Hilfe von Unterlisten durch, um zu bestimmen, wie viele Elemente an einer bestimmten Stelle in L entfernt werden sollen. Nutzen Sie die Tatsache, dass beide Listen so sortiert sind, dass sie nicht zurückverfolgt werden entweder Liste.O: n

Sollte in der Lage sein, O: n * log (n) Komplexität daraus zu erhalten, wenn es möglich ist zu verwenden. Natürlich bin ich nicht 100% sicher über alle Details des Problems. Zum Beispiel - kann L Duplikate haben? Wenn ja, ist die Reihenfolge der Unterlisten wichtig? Sie können gezwungen werden, einen solchen Algorithmus abhängig von den Antworten auf diese? S abzubrechen oder zu modifizieren. Außerdem wird dies offensichtlich mehr Speicher benötigen.