Швидкі способи уникнути дублікатів у списку <> в C #

Моя програма C# генерує випадкові рядки з заданого шаблону. Ці рядки зберігаються у списку. Оскільки дублікати не допускаються, я роблю це так:

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

Як ви можете собі уявити, це добре працює для декількох сотень записів. Але я стикаюсь з ситуацією, щоб створити кілька мільйонів рядків. І при кожному доданому рядку перевірка дублікатів стає повільніше і повільніше.

Чи існують більш швидкі способи уникнути дублікатів?

21
@ Джонезі: це звучить як щось варто перевірити для певного набору даних. Якщо це виявиться швидшим, тоді можна було б зважити, що оптимізація продуктивності по відношенню до заплутаності, яку він додає до коду (що в даному випадку мало).
додано Автор David, джерело
Чи буде це швидше занадто додати їх усіх, а потім використовувати Distinct (), щоб перевірити наявність дублікатів, а потім додати назад номер, який був видалений?
додано Автор Jonesopolis, джерело
Просто поза інтересом, що саме ви використовуєте для цього?
додано Автор musefan, джерело
@Серві: достатньо справедливо, ви, напевно, правильні, вочевидь це звучить логічно
додано Автор musefan, джерело
@Servі: залежить, наскільки імовірним є конфлікт. Якщо програмі потрібно перш за все завантажити Список з БД, це може бути прийнятним компромісом.
додано Автор musefan, джерело
Якщо ви зберігаєте свій список у базі даних, ви також можете спробувати зробити поле унікальним, а потім, якщо INSERT не вдасться, ви можете спробувати інший - просто щось інше, щоб розглянути
додано Автор musefan, джерело
@ Сервіс, на жаль, немає. Шаблон начебто спеціальний, тому GUID не допоможе.
додано Автор Robert Strauch, джерело
@musefan Мені потрібні ті, хто створює серійні номери для документів.
додано Автор Robert Strauch, джерело
@musefan Робіть всю подорож з БД просто, щоб дізнатись, що рядок вже існує, це ... проблема.
додано Автор Servy, джерело
@musefan Задавання навіть одного запиту DB, щоб визначити, чи елемент вже існує в БД, займе більше сотень тисяч, якщо не мільйони перевірок, щоб побачити наявність об'єкта в масиві в пам'яті. Використання БД для вирішення цієї конкретної проблеми може бути легко уповільненням у декілька тисяч разів.
додано Автор Servy, джерело
@ Роберт Ви можете використовувати GUID для кожного документа?
додано Автор Servy, джерело
використовувати набір для уникнення дублікатів
додано Автор Jayram Singh, джерело
@David Я, швидше за все, зробив теоретичний аргумент, що HashSet буде швидшим через менший вплив пам'яті спочатку, і після цього не потрібно повністю повторити його. Вартість перевірки кожного елемента все ще існує, але структура даних оптимізована для цього.
додано Автор Adam Houldsworth, джерело

7 Відповіді

Використовуйте структуру даних, яка може набагато ефективніше визначати, чи є елемент, а саме HashSet . Він може визначити, чи є товар в наборі в постійному часі, незалежно від кількості елементів у наборі.

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

35
додано
Гаразд, тому я використав HashSet , і збільшення швидкості величезне. Однак у мене є нова проблема. Мені потрібна певна кількість записів у наборі хеш-пам'яті. Якщо я використовую for-for-loop, як у моєму питанні, то він зупиняється після 2 000 000 циклів. Дублікати не існують в хеш-наборі, але якщо дублікат натиснуто, набір хешу не містить 2 000 000 записів. Як я можу уникнути цього? if (myList.Count <2000000) myList.Add (random_string); перешкоджає цьому, але знову ж таки, повільно.
додано Автор Robert Strauch, джерело
@Robert Замість для (int i = 0; i просто використовуйте для (int i = 0; set.Count . Або, якщо вам взагалі не потрібно i , то просто while (set.Count .
додано Автор Servy, джерело
схоже, що пошук елемента для HasSet - це O (1), так що якщо ви знайшли цей елемент = додати його до списку подвійних списків.
додано Автор user2545071, джерело

Don't use List<>. Use Dictionary<> or HashSet<> instead!

9
додано
Використовуючи HashSet, ви не можете отримати доступ до об'єкта та змінювати його, як це можна зробити в списку.
додано Автор ppumkin, джерело

Найпростіший спосіб це використовувати:

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

Хоча це вимагатиме створення списку один раз, а потім створення нового списку. Кращий спосіб - зробити ваш генератор заздалегідь:

public IEnumerable 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
додано
Використання .Distinct для видалення декількох мільйонів рядків у списку не здається ефективним IMO.
додано Автор Darren Davies, джерело
Крім того, якщо в результаті виникає певна кількість рядків, то для створення GetRandomStrings має сенс створити нескінченно довгу послідовність, а потім використати Take , щоб обмежити її бажаний розмір Потім ви можете помістити Take до або після Distinct , залежно від того, чи хочете ви вказати кількість створених рядків або кількість унікальних Створені рядки.
додано Автор Servy, джерело
@ p.s.w.g Я вважаю, що ваш метод GetRandomStrings призначений для yield рядка, а не просто встановити його на локальний, а потім викинути його.
додано Автор Servy, джерело
@ DarrenDavies Внутрішньо, Distinct використовує HashSet , як і інші запропонували. Єдиною неефективною частиною є спочатку генерація списку, а потім використання окремої, яку я звернув у другій частині моєї відповіді.
додано Автор p.s.w.g, джерело
@ Сервіс Так, дякую
додано Автор p.s.w.g, джерело
@Servy я спочатку реалізував це так, але нескінченні генератори можуть бути небезпечними, і їх потрібно обробляти з певною обережністю.
додано Автор p.s.w.g, джерело

You could use a HashSet if order is not important:

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

Клас HashSet забезпечує високопродуктивні задані операції. Набір - це колекція, яка не містить дублікатів елементів та елементи яких не мають жодного порядку.

MSDN

Або якщо значення є , я рекомендую використовувати SortedSet (лише .net 4,5)

5
додано
Як отримати хеш-об'єкт? HashSet НЕ GET, і це не дуже ефективно для реалізації вашої самостійності.
додано Автор ppumkin, джерело
Зауважте, що SortedSet сортує елементи. Якщо замовлений набір потрібний (тобто замовлення елемента підтримується), OrderedDictionary буде кращим вибором. Недоліком є ​​те, що він не є загальним.
додано Автор Olivier Jacot-Descombes, джерело

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

    }
1
додано

Hashtable буде швидшим способом перевірити наявність елемента, ніж список.

0
додано
У нього немає ключових/ціннісних відносин, просто купу струн, тому йому потрібен набір, а не карта. Крім того, HashTable не є загальним; замість цього вам слід скористатися загальним Dictionary , якщо вам дійсно потрібна структура карти. Ви ніколи не повинні використовувати HashTable у нестабільному коді.
додано Автор Servy, джерело

Ти намагався:

myList = myList.Distinct()
0
додано
var chat = new Chat();
var chat = new Chat();
642 учасників

Обсуждение вопросов по C# / .NET / .NET Core / .NET Standard / Azure Сообщества-организаторы: — @itkpi — @dncuug