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

My C# программа генерирует случайные строки из заданного шаблона. Эти строки хранятся в списке. Поскольку никаких дубликатов не допускается Я делаю это так:Быстрые способы избежать дубликатов в списке <> в C#

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); 
}

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

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

источник

2013-06-24 Robert Strauch

использовать набор для избежания дубликатов –

было бы быстрее, тоже добавить их все, а затем использовать Distinct(), чтобы проверить наличие дубликатов, а затем добавить обратно число, которые были удалены? – Jonesopolis

@ Jonesy: Это похоже на то, что нужно проверить для определенного набора данных. Если это будет быстрее, тогда можно было бы взвесить эту оптимизацию производительности против обфускации, которую она добавляет к коду (что в этом случае не так уж и много). – David

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

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

источник

2013-06-24 14:59:10 Servy

Итак, я использовал «HashSet», и увеличение скорости огромно. Однако у меня есть новая проблема. Мне нужно определенное количество записей в хэш-наборе. Если я использую for-loop, как в моем вопросе, то он останавливается после 2 000 000 циклов. Дубликаты не существуют в хэш-наборе, но если дубликат попал, хэш-набор не имеет 2 000 000 записей. Как я мог избежать этого? 'if (myList.Count <2000000) myList.Add (random_string);' предотвращает это, но опять-таки медленно. –

@Robert Вместо 'for (int i = 0; i Servy

кажется, что поиск объекта для HasSet равен O (1), поэтому, если вы найдете этот элемент = добавьте его в дублирующий список. – user2545071

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

источник

2013-06-24 14:58:49

У него нет отношения ключ/значение, просто куча строк, поэтому ему нужен набор, а не карта. Кроме того, HashTable не является общим; вы должны использовать общий «Словарь», если вам действительно нужна структура карты. Вы никогда не должны использовать HashTable в не устаревшем коде. – Servy

Самый простой способ заключается в использовании этого:

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.

источник

2013-06-24 14:59:10

Использование '.Distinct' для удаления нескольких миллионов строк в списке не означает, что эффективная IMO. –

@ DarrenDavies Внутренне, 'Distinct' использует' HashSet', как и другие. Единственная неэффективная часть - сначала генерирует список, а затем использует различные, которые я рассмотрел во второй части моего ответа. –

@ p.s.w.g Я предполагаю, что ваш метод GetRandomStrings' предназначен для 'yield' строки, а не только для локализации, а затем выбросить ее. – Servy

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

источник

2013-06-24 14:59:30 catfood

С помощью HashSet вы НЕ МОЖЕТЕ получить доступ и изменить объект, как вы можете, со списком. – ppumkin

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

myList = myList.Distinct()

источник

2013-06-24 15:00:59 jdehlin

Вы можете использовать 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)

источник

2013-06-24 15:01:16 DGibbs

Обратите внимание, что 'SortedSet ' сортирует элементы. Если требуется упорядоченный набор (т. Е. Порядок элементов поддерживается), 'OrderedDictionary' будет лучшим выбором. Недостатком является то, что он не является общим. –

Как мне получить хешированный объект? У HashSet нет GET, и это не очень эффективно для реализации вашего. – ppumkin

не хороший способ, но вид быстро исправить, взять 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; 
    } 

    }

источник

2017-11-26 12:10:36

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

ответ

Смежные вопросы