Быстрые способы избежать дубликатов в списке <> в С#

Моя программа С# генерирует случайные строки из заданного шаблона. Эти строки хранятся в списке. Поскольку дубликатов не разрешено, я делаю это так:

List<string> myList = new List<string>();
for (int i = 0; i < total; i++) {
  string random_string = GetRandomString(pattern);
  if (!myList.Contains(random_string)) myList.Add(random_string);
}

Как вы можете себе представить, это работает отлично для нескольких сотен записей. Но я столкнулся с ситуацией, чтобы создать несколько миллионов строк. И с каждой добавленной строкой проверка дубликатов становится медленнее и медленнее.

Есть ли более быстрые способы избежать дубликатов?

Ответы

Ответ 1

Используйте структуру данных, которая может намного более эффективно определять, существует ли элемент, а именно HashSet. Он может определить, находится ли элемент в наборе в постоянное время, независимо от количества элементов в наборе.

Если вам действительно нужны элементы в List, или вам нужно, чтобы элементы в результирующем списке находились в том порядке, в котором они были сгенерированы, вы можете хранить данные как в списке, так и в хешсе; добавив элемент в обе коллекции, если он не существует в HashSet.

Ответ 2

Не используйте List<>. Вместо этого используйте Dictionary<> или HashSet<>!

Ответ 3

Вы можете использовать HashSet<string>, если порядок не важен:

HashSet<string> myHashSet = new HashSet<string>();
for (int i = 0; i < total; i++) 
{
   string random_string = GetRandomString(pattern);
   myHashSet.Add(random_string);
}

Класс HashSet обеспечивает высокопроизводительные операции набора. Набор представляет собой набор, который не содержит повторяющихся элементов и элементы которого не имеют особого порядка.

MSDN

Или, если порядок важен, я бы рекомендовал использовать SortedSet (только .net 4.5)

Ответ 4

Самый простой способ - это:

myList = myList.Distinct().ToList();

Хотя для этого потребуется создать список один раз, а затем создать новый список. Лучше всего сделать ваш генератор раньше времени:

public IEnumerable<string> GetRandomStrings(int total, string pattern)
{
    for (int i = 0; i < total; i++) 
    {
        yield return GetRandomString(pattern);
    }
}

...

myList = GetRandomStrings(total, pattern).Distinct().ToList();

Конечно, если вам не нужно обращаться к элементам по индексу, вы, вероятно, могли бы повысить эффективность еще больше, сбросив ToList и просто используя IEnumerable.

Ответ 5

не лучший способ, но скорее быстрое исправление, возьмите bool, чтобы проверить, есть ли в целом списке какая-либо повторяющаяся запись.

bool containsKey;
string newKey;

    public void addKey(string newKey){

         foreach(string key in MyKeys){
           if(key == newKey){
             containsKey = true;
          }
         }

      if(!containsKey){
       MyKeys.add(newKey);
     }else{
       containsKey = false;
     }

    }

Ответ 6

Hashtable будет более быстрым способом проверить, существует ли элемент, чем список.

Ответ 7

Вы пробовали:

myList = myList.Distinct()