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

Question

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

List<int>

и

Dictionary<int, bool>

С помощью словаря я нашел немного лучшую производительность, хотя мне никогда не нужно, чтобы логическое значение было помечено каждой записью. Я ожидаю, что это потому, что List позволяет индексированный доступ, а Dictionary нет. Мне было интересно, есть ли лучшее решение этой проблемы. Мне не нужно снова получать доступ к записям, мне нужно только отслеживать, какие «первичные ключи» я видел, и убедиться, что я выполняю только дополнительную работу с записями, которые имеют новый первичный ключ. Я использую 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

Если вы собираетесь использовать Список, используйте 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 );

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

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

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

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