Der schnellste Weg, um eine Liste von eindeutigen Zeichenfolgen innerhalb einer Schleife zu erstellen?

Question

Ich habe eine Reihe von Zeichenfolgen (~80 000), auf die ich nur sequentiell über die Methode hits.Doc(int).Get("fieldName") zugreifen kann.

List<string> idStrings = new List<string>();
int count = hits.Length();
for (int i = 0; i < count; i++)
{
    string idString = hits.Doc(i).Get("id");
    if (!idStrings.Contains(idString))
        idStrings.Add(idString);
}

Die Zeichenketten müssen später mit int.TryParse() analysiert werden. Ich denke, es sollte einen schnelleren Weg geben, dies zu tun. Irgendwelche Vorschläge?

Answer 1

Verwenden Sie zunächst eine Hashset<string> anstelle einer Liste, geht die Contains-Methode schneller:

int count = hits.Length();
Hashset<string> idStrings = new Hashset<string>();

EDIT: Sie müssen "Contains" nicht aufrufen, wenn Sie ein Hashset verwenden, da es keine doppelten Elemente enthalten kann. Verwenden Sie einfach "Hinzufügen", es werden automatisch doppelte Werte entfernt.

Answer 2

Verwenden Sie eine Dictionary anstelle einer List . Die Dictionary.ContainsKey Methode ist viel schneller als die List.Contains Methode.

Dictionary<string, int> idStrings = new Dictionary<string, int>();
int count = hits.Length();
for (int i = 0; i < count; i++) {
   string idString = hits.Doc(i).Get("id");
   if (!idStrings.ContainsKey(idString)) {
      idStrings.Add(idString, 1);
   }
}

Wenn Sie Framework 3.5 verwenden, können Sie eine HashSet anstelle einer Dictionary :

HashSet<string> idStrings = new HashSet<string>();
int count = hits.Length();
for (int i = 0; i < count; i++) {
   string idString = hits.Doc(i).Get("id");
   idStrings.Add(idString);
}

Answer 3

Die Anweisung, die Ihren Code verlangsamt, lautet idStrings.Contains(idString) .

Sie können versuchen, eine schnellere Datenstruktur zu verwenden als List (vielleicht ein Baum oder eine Hashtabelle?).

Konkret benötigen Sie eine Datenstruktur mit sublinearer Suchzeit. Hashtabellen haben eine konstante Suchzeit, während Bäume normalerweise eine logarithmische Suchzeit haben.