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

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

нуждающегося клиент с определенным именем? 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?

источник

2010-03-18 Juliet

База данных ... Zing! –

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

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

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

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

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

источник

2010-03-18 21:32:06

Проблема с несколькими словарями заключается в том, что они не поддерживают составные поисковые запросы: age Dictionary > возвращает диапазон клиентов для определенного возраста в постоянное время, но что делать, если я также хочу искать по имени? Я вернусь к линейному поиску. – Juliet

Если вы объедините результаты (через ANDing/ORing), я думаю, вы будете лучше, чем линейные. – micahtan

@Juliet: Вы вернулись к линейному поиску, но в очень ограниченном пространстве. Каждый дополнительный поиск ограничивается только действительными элементами из первого, поэтому пространство поиска намного меньше. Второй поиск - O (n), но N становится очень маленьким. При этом другой вариант по-прежнему использует встроенную базу данных, которая обеспечивает быстрый запрос с произвольными критериями ... –

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

источник

2010-03-18 21:42:27 Vlad

Для начала это не очень общее решение. У нас есть такие типы поиска не только для клиентов, и было бы немного безумным создать 1000 слов из словарей для 100-х типов коллекций, которые мы регулярно ищем. Во-вторых, несколько словарей не поддерживают поиск на составных ключах в разумные сроки, например, я не могу искать людей с заданным именем И возраст без линейного поиска через один из моих словарей. – Juliet

-1

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

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

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

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

источник

2012-09-11 17:03:12 RS999

Что это касается структуры данных? –

Не структура, но если он пытается запросить эти массивы и не хочет вращать свои колеса, пытаясь найти идеальный дизайн, просто делайте LINQ против своих массивов и называйте это днем. – RS999

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

ответ

Смежные вопросы