Was ist falsch in Bezug auf die Leistung mit diesem Code? List.Contains, zufällige Verwendung, Threading?

Question

Ich habe eine lokale Klasse mit einer Methode zum Erstellen einer Liste von Zeichenfolgen und ich finde, dass, wenn ich diese Methode (in einer for-Schleife von 1000 Mal) oft nicht die Menge, die ich anfordern, zurückgibt.

Ich habe eine globale Variable:

string[] cachedKeys 

Parameter an die Methode übergeben:

int requestedNumberToGet 

Das Verfahren ähnlich wie diese aussieht:

List<string> keysToReturn = new List<string>(); 
int numberPossibleToGet = (cachedKeys.Length <= requestedNumberToGet) ? 
cachedKeys.Length : requestedNumberToGet; 
Random rand = new Random(); 

DateTime breakoutTime = DateTime.Now.AddMilliseconds(5); 

//Do we have enough to fill the request within the time? otherwise give 
//however many we currently have 
while (DateTime.Now < breakoutTime 
    && keysToReturn.Count < numberPossibleToGet 
    && cachedKeys.Length >= numberPossibleToGet) 
{ 
    string randomKey = cachedKeys[rand.Next(0, cachedKeys.Length)]; 
    if (!keysToReturn.Contains(randomKey)) 
     keysToReturn.Add(randomKey); 
} 

if (keysToReturn.Count != numberPossibleToGet) 
    Debugger.Break(); 

Ich habe etwa 40 Saiten in CachedKeys, deren Länge 15 Zeichen nicht überschreitet.

Ich bin kein Experte mit Threading, so dass ich diese Methode buchstäblich 1000 Mal in einer Schleife aufrufen und konsequent dort debuggen.

Die Maschine, auf der diese läuft, ist ein ziemlich bulliger Desktop, also würde ich erwarten, dass die Breakout-Zeit realistisch ist, tatsächlich bricht sie zufällig an irgendeinem Punkt der Schleife (ich habe 20s, 100s, 200s, 300s gesehen) .

Hat jemand irgendwelche Ideen, wo ich damit falsch liege?

Edit: Begrenzt auf .NET 2.0

Edit: Der Zweck des Ausbruchs ist so, dass, wenn das Verfahren zu lange dauert auszuführen, der Client (mehrere Web-Server die Daten für XML-Feeds verwenden) muss nicht warten, während die anderen Projektabhängigkeiten initialisiert werden, sie erhalten nur 0 Ergebnisse.

Edit: Ich dachte, die Wertentwicklung aufweisen würde Statistik

Original-

• ',0042477465711424217323710136' - 10
• '0,0479597267250446634977350473' - 100
• ',4721072091564710039963179678' - 1000

Skeet

• '0,0007076318358897569383818334' - 10
• ',007256508857969378789762386' - 100
• ',0749829936486341141122684587' - 1000

Freddy Rios

• '0,0003765841748043396576939248' - 10
• ',0046003053460705201359390649' - 100
• ‚0.0417058592642360970458535931' - 1000

Answer 1

Das Hauptproblem ist die Verwendung von Wiederholungsversuchen in einem zufälligen Szenario, um sicherzustellen, dass Sie eindeutige Werte erhalten. Dies gerät schnell außer Kontrolle, insbesondere wenn die Anzahl der angeforderten Elemente der Anzahl der zu erreichenden Elemente nahe kommt. Wenn Sie also die Anzahl der Schlüssel erhöhen, wird das Problem seltener auftreten, aber das kann vermieden werden.

Bei der folgenden Methode wird eine Liste der verbleibenden Schlüssel gespeichert.

List<string> GetSomeKeys(string[] cachedKeys, int requestedNumberToGet) 
{ 
    int numberPossibleToGet = Math.Min(cachedKeys.Length, requestedNumberToGet); 
    List<string> keysRemaining = new List<string>(cachedKeys); 
    List<string> keysToReturn = new List<string>(numberPossibleToGet); 
    Random rand = new Random(); 
    for (int i = 0; i < numberPossibleToGet; i++) 
    { 
     int randomIndex = rand.Next(keysRemaining.Count); 
     keysToReturn.Add(keysRemaining[randomIndex]); 
     keysRemaining.RemoveAt(randomIndex); 
    } 
    return keysToReturn; 
} 

Der Timeout wurde auf Version notwendig, da Sie möglicherweise ein neuer Versuch gestartet könnte einen Wert für eine lange Zeit zu erhalten. Insbesondere, wenn Sie die gesamte Liste abrufen wollten, würden Sie fast sicher einen Fehler mit der Version erhalten, die auf Wiederholungen angewiesen ist.

Update: Die oben führt besser als diese Variationen:

List<string> GetSomeKeysSwapping(string[] cachedKeys, int requestedNumberToGet) 
{ 
    int numberPossibleToGet = Math.Min(cachedKeys.Length, requestedNumberToGet); 
    List<string> keys = new List<string>(cachedKeys); 
    List<string> keysToReturn = new List<string>(numberPossibleToGet); 
    Random rand = new Random(); 
    for (int i = 0; i < numberPossibleToGet; i++) 
    { 
     int index = rand.Next(numberPossibleToGet - i) + i; 
     keysToReturn.Add(keys[index]); 
     keys[index] = keys[i]; 
    } 
    return keysToReturn; 
} 
List<string> GetSomeKeysEnumerable(string[] cachedKeys, int requestedNumberToGet) 
{ 
    Random rand = new Random(); 
    return TakeRandom(cachedKeys, requestedNumberToGet, rand).ToList(); 
} 

Einige Zahlen mit 10.000 Iterationen:

Function Name Elapsed Inclusive Time Number of Calls 
GetSomeKeys    6,190.66  10,000 
GetSomeKeysEnumerable  15,617.04  10,000 
GetSomeKeysSwapping  8,293.64  10,000 

Answer 2

Das Problem möglicherweise hier sein könnte:

if (!keysToReturn.Contains(randomKey)) 
    keysToReturn.Add(randomKey); 

Dies wird über die Liste Iterieren benötigen, um zu bestimmen, ob der Schlüssel in der Rückgabeliste ist. Allerdings sollten Sie versuchen, dies mit einem Tool zu tun. Außerdem ist 5ms ziemlich schnell bei 0,005 Sekunden, vielleicht möchten Sie das erhöhen.

Answer 3

Warum nicht einfach eine Kopie der Liste - O (n) - mische es, auch O (n) - und dann die Anzahl der Schlüssel zurückzugeben, die angefordert wurden. In der Tat muss der Shuffle nur O (nRequested) sein. Halten Sie ein zufälliges Mitglied des ungemischten Bit der Liste mit dem Beginn des ungemischten Bit Swapping, erweitern Sie dann die neu gemischt Bit 1 (nur ein fiktiven Zähler).

EDIT: Hier ist ein Code, der die Ergebnisse als IEnumerable<T> ergibt. Beachten Sie, dass eine verzögerte Ausführung verwendet wird. Wenn Sie also die übergebene Quelle ändern, bevor Sie die Ergebnisse zum ersten Mal durchlaufen, werden diese Änderungen angezeigt. Nachdem das erste Ergebnis abgerufen wurde, wurden die Elemente zwischengespeichert.

static IEnumerable<T> TakeRandom<T>(IEnumerable<T> source, 
            int sizeRequired, 
            Random rng) 
{ 
    List<T> list = new List<T>(source); 

    sizeRequired = Math.Min(sizeRequired, list.Count); 

    for (int i=0; i < sizeRequired; i++) 
    { 
     int index = rng.Next(list.Count-i);    
     T selected = list[i + index]; 
     list[i + index] = list[i]; 
     list[i] = selected; 
     yield return selected; 
    } 
} 

Die Idee ist, an jedem Punkt, dass Sie nach n Elemente geholt haben, die ersten n Elemente der Liste werden die Elemente sein - so stellen wir sicher, dass wir wählen nicht diejenigen wieder. Wenn Sie dann ein zufälliges Element aus dem "Rest" auswählen, tauschen Sie es gegen die richtige Position aus und geben Sie es ab.

Hoffe, das hilft. Wenn Sie C# 3 verwenden, sollten Sie dies zu einer Erweiterungsmethode machen, indem Sie "this" vor den ersten Parameter stellen.

Answer 4

Ein paar Gedanken.

Zuerst Ihre keysToReturn Liste wird möglicherweise durch die Schleife zu jeder Zeit hinzugefügt werden, nicht wahr? Sie erstellen eine leere Liste und fügen dann jeden neuen Schlüssel zur Liste hinzu. Da die Liste nicht vordefiniert war, wird jede Addition zu einer O (n) -Operation (see MSDN documentation). Um das Problem zu beheben, versuchen Sie, die Liste so vorzuspannen.

int numberPossibleToGet = (cachedKeys.Length <= requestedNumberToGet) ? cachedKeys.Length : requestedNumberToGet; 
List<string> keysToReturn = new List<string>(numberPossibleToGet); 

Zweitens ist Ihre Breakout-Zeit unrealistisch (ok, ok, unmöglich) unter Windows. Alle Informationen, die ich jemals über Windows-Timing gelesen habe, legen nahe, dass das Beste, auf das man hoffen kann, eine Auflösung von 10 Millisekunden ist, aber in der Praxis sind es eher 15-18 Millisekunden. Versuchen Sie diesen Code:

for (int iv = 0; iv < 10000; iv++) { 
    Console.WriteLine(DateTime.Now.Millisecond.ToString()); 
} 

Was Sie in der Ausgabe sehen werden, sind diskrete Sprünge. Hier ist eine Beispielausgabe, die ich gerade auf meinem Rechner ausgeführt habe.

13 
... 
13 
28 
... 
28 
44 
... 
44 
59 
... 
59 
75 
... 

Millisekundenwert springt 13-28 bis 44-59 bis 75, die in der für meine Maschine DateTime.Now Funktion etwa ein 15-16 Millisekunden-Auflösung ist. Dieses Verhalten stimmt mit dem überein, was Sie beim Aufruf von c funtime ftime() sehen würden. Mit anderen Worten, es ist eine systemische Eigenschaft des Windows-Timing-Mechanismus. Der Punkt ist, Sie sollten sich nicht auf eine konsistente 5-Millisekunden-Breakout-Zeit verlassen, weil Sie es nicht bekommen werden.

Drittens bin Recht gehe ich davon aus, dass der Ausbruch Zeit ein Blockieren der Hauptthread verhindern ist? Wenn dies der Fall ist, ist es ziemlich einfach, Ihre Funktion in einem ThreadPool-Thread zu veröffentlichen und sie unabhängig von der Dauer des Vorgangs vollständig ausführen zu lassen. Ihr Haupt-Thread kann dann mit den Daten arbeiten.

Answer 5

Verwenden HashSet stattdessen HashSet ist viel schneller für die Suche als List

HashSet<string> keysToReturn = new HashSet<string>(); 
int numberPossibleToGet = (cachedKeys.Length <= requestedNumberToGet) ? cachedKeys.Length : requestedNumberToGet; 
Random rand = new Random(); 

DateTime breakoutTime = DateTime.Now.AddMilliseconds(5); 
int length = cachedKeys.Length; 

while (DateTime.Now < breakoutTime && keysToReturn.Count < numberPossibleToGet) { 
    int i = rand.Next(0, length); 
    while (!keysToReturn.Add(cachedKeys[i])) { 
     i++; 
     if (i == length) 
      i = 0; 
    } 
} 

Answer 6

Betrachten Stopwatch statt DateTime.Now verwenden. Es kann einfach die Ungenauigkeit von DateTime.Now sein, wenn Sie über Millisekunden sprechen.