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

Question

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

List<int>

и

Dictionary<int, bool>

Со словарем я обнаружил немного лучшую производительность, хотя мне никогда не нужно логическое значение, помеченное каждой записью.Я ожидаю, что это происходит потому, что Список допускает индексированный доступ, а Словарь - нет.Что мне было интересно, так это, есть ли лучшее решение этой проблемы.Мне не нужно снова обращаться к записям, мне нужно только отследить, какие "первичные ключи" я видел, и убедиться, что я выполняю работу по добавлению только к записям, которые имеют новый первичный ключ.Я использую C # и .NET 2.0.И я не могу контролировать исправление входных данных, чтобы удалить дубликаты из источника (к сожалению!).Чтобы вы могли почувствовать масштабирование, в целом я проверяю приложение на наличие дубликатов около 1 000 000 раз, но в подмножествах не более 64 000, которые должны быть уникальными.

Answer 1

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

 // 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 с помощью перегрузки:Бинарный поиск (T item, IComparer< T > );