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

Question

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

List<int> 

и

Dictionary<int, bool> 

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

Answer 1

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

Answer 2

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

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

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

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

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

Answer 3

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

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

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

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

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

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

Answer 4

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

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

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

Answer 5

Был ли еще вопрос на removing duplicates from an array. Для цели выполнения вопроса было не очень важно, но вы можете взглянуть на ответы, поскольку они могут дать вам некоторые идеи. Кроме того, я могу быть вне базы здесь, но если вы пытаетесь удалить дубликаты из массива, то команда LINQ, такая как Enumerable.Distinct, может дать вам лучшую производительность, чем то, что вы пишете сами. Как оказалось, есть способ получить LINQ working on .NET 2.0, так что это может быть маршрут, который стоит исследовать.

Answer 6

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