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

Они добавили класс HashSet в .NET 3.5. Но я думаю, он будет на уровне Словаря. Если у вас меньше 100 элементов, List, вероятно, будет работать лучше.

Я действительно не понимаю, о чем вы спрашиваете.

Во-первых, это прямо противоположно тому, что вы говорите. У словаря есть индексированный доступ (это хеш-таблица), а у de List - нет.

Если у вас уже есть данные в словаре, значит, все ключи уникальны, дубликатов быть не может.

Я полагаю, что у вас есть данные, хранящиеся в другом типе данных, и вы сохраняете их в словаре. В этом случае вставка данных будет работать с двумя словарями.

foreach (int key in keys)
{
  if (!MyDataDict.ContainsKey(key))
  {
    if (!MyDuplicatesDict.ContainsKey(key))
      MyDuplicatesDict.Add(key);
  }
  else
    MyDataDict.Add(key); 
}

Обновлено: не обращайте внимания на мой комментарий. Я думал, вы говорите о C++. Понятия не имею, актуален ли мой пост в мире C# ..

Хеш-таблица могла бы быть немного быстрее. Двоичные деревья (это то, что используется в словаре) имеют тенденцию быть относительно медленными из-за способа доступа к памяти. Это особенно актуально, если ваше дерево становится очень большим.

Однако, прежде чем изменять структуру данных, пробовали ли вы использовать специальный распределитель пула для своего словаря? Бьюсь об заклад, время тратится не на обход самого дерева, а на миллионы распределений и освобождений, которые словарь сделает за вас.

Вы можете увидеть увеличение скорости в 10 раз, просто подключив простой распределитель пула в шаблон словаря. Afaik boost имеет компонент, который можно использовать напрямую.

Другой вариант: если вы знаете, что существует только 64000 записей в ваших целых числах, вы можете записать их в файл и создать для него идеальную хеш-функцию. Таким образом, вы можете просто использовать хеш-функцию для сопоставления целых чисел в диапазоне от 0 до 64 000 и индексации битового массива.

Наверное, самый быстрый способ, но менее гибкий. Вы должны переделывать свою идеальную хеш-функцию (может выполняться автоматически) каждый раз, когда изменяется ваш набор целых чисел.

Если вы проверяете уникальность целых чисел, а диапазон целых чисел достаточно ограничен, вы можете просто использовать массив.

Для лучшей упаковки вы можете реализовать структуру данных растрового изображения (в основном массив, но каждый int в массиве представляет 32 int в ключевом пространстве, используя 1 бит на ключ). Таким образом, если ваше максимальное число составляет 1000000, вам понадобится всего ~ 30,5 КБ памяти для структуры данных.

Выполнение растрового изображения будет O (1) (за проверку), что трудно превзойти.

Некоторое время назад был вопрос по удаление дубликатов из массива. Для целей вопроса производительность не имела особого значения, но вы можете взглянуть на ответы, поскольку они могут дать вам некоторые идеи. Кроме того, я могу ошибаться здесь, но если вы пытаетесь удалить дубликаты из массива, тогда команда LINQ, такая как Перечислимый., может дать вам лучшую производительность, чем то, что вы пишете сами. Оказывается, есть способ получить LINQ работает на .NET 2.0, поэтому этот маршрут стоит изучить.

Если вы собираетесь использовать список, используйте BinarySearch:

 // initailize to a size if you know your set size
List<int> FoundKeys = new List<int>( 64000 );
Dictionary<int,int> FoundDuplicates = new Dictionary<int,int>();

foreach ( int Key in MyKeys )
{
   // this is an O(log N) operation
   int index = FoundKeys.BinarySearch( Key );
   if ( index < 0 ) 
   {
       // if the Key is not in our list, 
       // index is the two's compliment of the next value that is in the list
       // i.e. the position it should occupy, and we maintain sorted-ness!
       FoundKeys.Insert( ~index, Key );
   }
   else 
   {
       if ( DuplicateKeys.ContainsKey( Key ) )
       {
           DuplicateKeys[Key]++;
       }
       else
       {
           DuplicateKeys.Add( Key, 1 );
       }
   } 
} 

Вы также можете использовать это для любого типа, для которого вы можете определить IComparer с помощью перегрузки: BinarySearch (T item, IComparer <T>);