Хорошая структура данных для эффективной вставки / запроса произвольных свойств

Question

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

• Нужен клиент с конкретным именем? customer.Find(x => x.Name == name)
• Нужен клиент с определенным уникальным идентификатором? customer.Find(x => x.Id == id)
• Нужен клиент определенного типа и возраста? customer.Find(x => x is PreferredCustomer && x.Age >= age)
• Нужен клиент определенного имени и возраста? customer.Find(x => x.Name == name && x.Age == age)

Почти во всех случаях критерии поиска четко определены. Например, мы ищем клиентов только по одному или нескольким свойствам Id, Type, Name или Age. Мы редко ищем что-либо еще.

Является ли хорошая структура данных для поддержки произвольных запросов этих типов с поиском лучше, чем O (n)? Какие-нибудь готовые реализации для .NET?

Answer 1

Для в памяти, у вас есть несколько вариантов.

Большинство опций будет O (n). При этом поиск в словаре может приближаться к O (1).

Один из вариантов - хранить своих клиентов в нескольких словарях, каждый из которых имеет ключи, заданные для имени, идентификатора и возраста. Если вы используете одни и те же ссылки на объекты в словарях, вы можете выполнить любой отдельный поиск O (1) без огромных затрат.

Конечно, это становится менее практичным по мере увеличения количества критериев, но с 3 это не так уж и плохо.

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

Answer 2

Я предполагаю, что все массивы имеют IEnumerable?

Как насчет использования LINQ для объектов?

http://www.beansoftware.com/ASP.NET-Tutorials/Linq-Objects-Collections-Arrays.aspx

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

Answer 3

Почему вы не можете поместить свои данные в несколько словарей? Один словарь сопоставляет имя с данными, другой - возраст и т. Д.