Хорошая структура данных для эффективного вставляет/запрашивает на произвольных свойствах
Я работаю над проектом, где Массивы являются структурой данных по умолчанию для всего, и каждый запрос является линейным поиском в форме:
- Нужен клиент с конкретным именем?
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, Типа, Имени или Возраста. Мы редко ищем чем-либо еще.
Хорошая структура данных состоит в том, чтобы поддерживать произвольные запросы этих типов с поиском лучше, чем O (n)? Какие-либо out-of-the-box реализации для.NET?
2 ответа
Для памяти у вас есть несколько вариантов.
Большинство вариантов будут O (n). При этом поиск по словарю может приближаться к O (1).
Один из вариантов - хранить ваших клиентов в нескольких словарях, каждый с ключом, установленным на имя, идентификатор и возраст. Если вы используете одни и те же ссылки на объекты в словарях, вы можете выполнить любой одиночный поиск O (1) без огромных накладных расходов.
Конечно, это становится менее практичным по мере увеличения количества критериев, но с 3 это не так уж и плохо.
Если вам нужна большая гибкость, то база данных - подходящий вариант. Многие базы данных имеют возможность работать как база данных полностью в памяти, включая SQLite, что позволяет выполнять произвольные запросы со скоростью намного лучше, чем O (n).
Почему вы не можете поместить данные в несколько словарей? Один словарь сопоставляет имя с данными, другой - возраст и т. д.