Огромный набор данных в памяти. Нужен быстрый поиск по целочисленному идентификатору

Question

У меня есть огромный набор в памяти (например, ~ 100K записей) простых объектов CLR определенного типа.Этот тип имеет публичное свойство int Id {get;задавать;}.Какова лучшая структура .NET для хранения этого огромного набора данных, чтобы обеспечить быстрый доступ к любому элементу по его идентификатору?Более конкретно, предполагается, что этот набор данных будет использоваться внутри цикла для поиска элемента по Id, поэтому поиск следует выполнять как можно быстрее.Поиск может выглядеть следующим образом:

// Find by id
var entity = entities.First(e => e.Id == id)

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

Спасибо

Результаты тестирования : К вашему сведению: словарь не просто быстрый, он просто несопоставим.Мой небольшой тест показал увеличение производительности примерно с 3000+ мс (вызов First () в IEnumerable) до 0 ([index] в словаре)!

Answer 1

Я бы пошел с Dictionary<TKey, TValue>:

var index = new System.Collections.Generic.Dictionary<int, T>();

, где T - это тип объектов, к которым вы хотите получить доступ.

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

• Чтобы добавить запись, выполните index.Add(entity.Id, entity);

• Чтобы проверить, есть ли элемент в коллекции, index.ContainsKey(id).

• Для полученияпредмет по ID, index[id].

Answer 2

Обычно поиск в памяти лучше всего выполнять с помощью словаря:

System.Collections.Generic.Dictionary

Опционально, когда ваш набор данных больше не помещается в памяти, можно использовать btree .

на основе диска.

Answer 3

Dictionary<TKey, TValue>, где TKey равно int и TValue равно YourEntity.

Пример

var dictionary = new Dictionary<TKey, TValue>();
dictionary.Add(obj1.Id, obj1); 
// continue 

Или, если у вас есть коллекция объектов, вы можете создать словарь с помощью запроса

var dictionary = list.ToDictionary(obj => obj.Id, obj => obj);

Примечание: значения ключей должны быть уникальными.Если у вас есть неуникальная коллекция, сначала отфильтруйте дубликаты (возможно, вызвав Distinct() перед созданием словаря. В качестве альтернативы, если вы циклически перебираете коллекцию для создания словаря вручную, проверьте метод ContainsKey перед попыткой Add операция.

Answer 4

На основании предоставленной информации HashTable, вероятно, будет самым быстрым. Класс Dictionary предоставит вам лучший компромисс между простотой использования и производительностью. Если вам действительно нужна максимальная производительность, я бы попробовал все следующие классы. В зависимости от использования памяти, скорости вставки, скорости поиска все они работают по-разному:

• ListDictionary
• HashTable
• словарь
• SortedDictionary
• ConcurrentDictionary

в дополнение к производительности вас может беспокоить многопоточный доступ. Эти две коллекции обеспечивают безопасность нити:

• HashTable (многократное чтение, разрешено писать только одному потоку)
• ConcurrentDictionary

Answer 5

Это зависит от ваших данных. Если существует ограничение на количество имеющихся у вас объектов и не слишком много пропущенных объектов (то есть вы не можете иметь больше, чем X объектов, и у вас обычно есть близко к X объектам), тогда обычный массив будет самым быстрым.

T[] itemList = new T[MAX_ITEMS];

Однако, если ни одно из этих двух условий не выполняется, возможно, лучшим вариантом будет IDictionary.

Dictionary<int, T> itemList = new Dictionary<int, T>();