Список с несколькими индексами

(Редактировано для разработки стратегии, основанной на коллекции)

В .NET нет внутренней структуры для поиска с использованием различных индексов. Вот две хорошие стратегии:

Вариант 1: LINQ, для гибкости и простоты
. Для простоты и множества других интегрированных опций создайте список (или что-то еще, реализующее IEnumerable) пользовательских типов и используйте LINQ для выполнения поиска по требованию. Обратите внимание, что вы можете использовать анонимные типы, если это удобно для вас. Вы также можете иметь свои данные в XML-структуре и при этом делать все это. Скорее всего, вы сможете получить свои данные, выполнить поиск и манипулировать результатами в небольшом объеме чистого кода. В .Net 4.0 вы можете использовать parallel Ling (PLINQ), чтобы этот процесс без труда использовал преимущества многоядерной обработки.

List<foo> bigFooList = new List<foo>  
{  
     new Foo {"aaa", 111, "yes"},  
     new Foo {"aaa", 112, "no"},  
     new Foo {"bbb", 111, "no"},  
     new Foo {"bbb", 220, "yes"},  
     new Foo {"bbb", 220, "no"},  
     new Foo {"ccc", 300, "yes"}  
};    
var smallFooList = From f In bigFooList Where f.P2 = 220 Select f; 

Вариант 2: Многочисленные коллекции , для индексированной поисковой мощности.
Если вы делаете много просмотров на большом наборе и вам нужна мощность, вы можете использовать несколько коллекций для достижения более быстрого просмотра. Самое сложное - это ваше требование, чтобы значения индекса можно было дублировать. Вот несколько стратегий:

• Проверьте класс поиска . Создайте свой список. Затем для каждого поля, для которого Вы хотите индексированный поиск, создайте объект Lookup. Они не могут быть созданы, но являются производными от вашей коллекции IEnumerable:
  Lookup LookupP1 = (Lookup) fooList.ToLookup(f => f.P1, f => p)
  Смотрите ссылку на синтаксис для получения ваших элементов. В основном LookupP1 содержит IGrouping объекты для каждого уникального значения P1, привязанного к этому значению P1. Вы выполняете итерацию через этот объект, чтобы получить соответствующие объекты. Ключевым атрибутом Lookup объектов является то, что они являются неизменяемыми; поэтому каждый раз, когда вы добавляете/вычитаете из своего списка, вы должны будете переделать все ваши Lookup объекты. Но если вы редко меняете свой список, то так будет лучше.
• Создайте Словарь> для каждого поля, по которому вам нужно будет искать по индексу, где T - тип этого значения. Для вашего примера мы создадим:
  var FoosByP1 = новый словарь>
var FoosByP2 = новый словарь> и др.
  Затем добавьте в FoosByP1, квитируемый на каждом уникальном значении P1, список, содержащий все элементы ФУ, где P1 имеет это значение. (например, "aaa", Список, содержащий все объекты ФО, для которых P1 имеет значение "aaa"). Повторите для каждого поля Foo. Основываясь на своих данных, FoosByP1You будет содержать 3 объекта Списка, содержащих 2, 3 и 1 объект Foo соответственно. С помощью этой схемы вы сможете очень быстро получить данные. (Словарь - это в основном хэш-таблица).
  Главная загвоздка заключается в том, что ваши данные будут дублироваться в каждом из этих словарей, что может быть проблемой, а может и не быть. Если Foo имеет поля 20 и у вас много элементов Foo, вы можете сохранить память, имея центральный словарь с числовым ключом и все элементы Foo, а отдельные индексированные словари будут Dictionary>, где целое число будет индексом элемента Foo в вашем центральном словаре. Это позволит сэкономить память и при этом будет достаточно быстрым.
  Независимо от того, есть ли у вас центральный словарь или нет, создание ваших Диктонов займет несколько циклов на процессоре, но как только вы их получите, вы будете в отличной форме. И используйте Linq для создания своих словарей!

Одним из путей будет использование встроенной реляционной базы данных a la SQLite (здесь есть привязка ADO.NET: http://sqlite.phxsoftware.com/)

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

Вы можете посмотреть что-то вроде lucene.net , библиотека индексации и поиска. Я не знаю, может ли это быть более сложным решением, чем вы искали, но это определенно удовлетворит ваши потребности в производительности.

Я знаю, что вы сказали, что не можете использовать словарь, но сработает ли следующее?

Для вашего примера набора данных:

{ "aaa", 111, "yes" }
{ "aaa", 112, "no"  }
{ "bbb", 111, "no"  }
{ "bbb", 220, "yes" }
{ "bbb", 220, "no"  }
{ "ccc", 300, "yes" }

Вы можете использовать следующее:

var p1Lookup = new Dictionary<string,int []>();
p1Lookup.Add( "aaa", new int [] {0, 1} );
p1Lookup.Add( "bbb", new int [] {2, 3, 4} );
p1Lookup.Add( "ccc", new int [] {5} );

var p2Lookup = new Dictionary<int,int []>();
p1Lookup.Add( 111, new int [] {0, 2} );
p1Lookup.Add( 112, new int [] {1} );
p1Lookup.Add( 220, new int [] {3, 4} );
p1Lookup.Add( 300, new int [] {5} );

var p3Lookup = new Dictionary<int,int []>();
p1Lookup.Add( "yes", new int [] {0, 3, 5} );
p1Lookup.Add(  "no", new int [] {1, 2, 4} );

В зависимости от использования, вы можете построить поисковые словари всего один раз

Почему бы не использовать хеш-метал для хранения различных экземпляров объекта FOO (который будет уникальным), а затем используйте запрос LINQ для получения тех, которые соответствуют данным критериям?

что-то Как:

var hash = new HashSet<Foo>
{
new Foo { P1 = "aaa", P2 = 111, P3 = "yes"},
new Foo { P1 = "aaa", P2 = 112, P3 = "no"},
new Foo { P1 = "bbb", P2 = 111, P3 = "no"},
new Foo { P1 = "bbb", P2 = 220, P3 = "yes"},
new Foo { P1 = "bbb", P2 = 220, P3 = "no"},
new Foo { P1 = "ccc", P2 = 300, P3 = "yes"},
};

var results = from match in hash
where match.P1 == "aaa"
select match;

Никогда не забывайте этот принцип: сделайте его правильным, сделайте его понятно, сделайте его лаконичкой, сделайте его быстро. В этой последовательности. Итак, первый код до наивной реализации:

static IEnumerable<T> GetByIndex<T>(
    List<T> list,
    Func<T, TIndex> func,
    TIndex key
) {
    return list.Where(x => func(x) == key);
}

Использование:

List<Test> tests = new List<Test>() {
            new Test { Name = "aaa", Value = 111, Valid = Valid.Yes },
            new Test { Name = "aaa", Value = 111, Valid = Valid.Yes },
            new Test { Name = "bbb", Value = 112, Valid = Valid.No },
            new Test { Name = "bbb", Value = 111, Valid = Valid.No },
            new Test { Name = "bbb", Value = 220, Valid = Valid.No },
            new Test { Name = "ccc", Value = 220, Valid = Valid.Yes }
};
IEnumerable<Test> lookup = GetByIndex(tests, x => x.Name, "bbb");

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

Итак, насколько быстро делает его быстро, вы должны сначала измерить:

1. установить разумный критерий производительности.
2. Установите тест-кровать реальных данных.
3. Профиль простой подход к промежуточному слову реальных данных. Следует отметить, что профилирование включает в себя вывод, является ли эта функция узкого места в вашем приложении.

Тогда, если и только если это недостаточно быстро для вас, если вы пытаетесь оптимизировать. Было бы не слишком сложно реализовать indexedList : iconceplection , который позволил бы вам индексировать различные свойства.

Вот наивная реализация, которая может начать:

class IndexedList<T> : IEnumerable<T> {
    List<T> _list;
    Dictionary<string, Dictionary<object, List<T>>> _dictionary;
    Dictionary<string, Func<T, object>> _propertyDictionary;

    public IndexedList(IEnumerable<string> propertyNames) : this(propertyNames, new List<T>()) { }

    public IndexedList(IEnumerable<string> propertyNames, IEnumerable<T> source) {
        _list = new List<T>();
        _dictionary = new Dictionary<string, Dictionary<object, List<T>>>();
        _propertyDictionary = BuildPropertyDictionary(propertyNames);
        foreach (var item in source) {
            Add(item);
        }
    }

    static Dictionary<string, Func<T, object>> BuildPropertyDictionary(IEnumerable<string> keys) {
        var propertyDictionary = new Dictionary<string,Func<T,object>>();
        foreach (string key in keys) {
            ParameterExpression parameter = Expression.Parameter(typeof(T), "parameter");
            Expression property = Expression.Property(parameter, key);
            Expression converted = Expression.Convert(property, typeof(object));
            Func<T, object> func = Expression.Lambda<Func<T, object>>(converted, parameter).Compile();
            propertyDictionary.Add(key, func);
        }
        return propertyDictionary;
    }

    public void Add(T item) {
        _list.Add(item);
        foreach (var kvp in _propertyDictionary) {
            object key = kvp.Value(item);
            Dictionary<object, List<T>> propertyIndex;
            if (!_dictionary.TryGetValue(kvp.Key, out propertyIndex)) {
                propertyIndex = new Dictionary<object, List<T>>();
                _dictionary.Add(kvp.Key, propertyIndex);
            }
            List<T> list;
            if (!propertyIndex.TryGetValue(key, out list)) {
                list = new List<T>();
                propertyIndex.Add(key, list);
            }
            propertyIndex[key].Add(item);
        }
    }

    public IEnumerable<T> GetByIndex<TIndex>(string propertyName, TIndex index) {
        return _dictionary[propertyName][index];
    }

    public IEnumerator<T> GetEnumerator() {
        return _list.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }
}

Использование:

List<Test> tests = new List<Test>() {
            new Test { Name = "aaa", Value = 111, Valid = Valid.Yes },
            new Test { Name = "aaa", Value = 111, Valid = Valid.Yes },
            new Test { Name = "bbb", Value = 112, Valid = Valid.No },
            new Test { Name = "bbb", Value = 111, Valid = Valid.No },
            new Test { Name = "bbb", Value = 220, Valid = Valid.No },
            new Test { Name = "ccc", Value = 220, Valid = Valid.Yes }
};
// build an IndexedList<Text> indexed by Name and Value
IndexedList<Test> indexed = new IndexedList<Test>(new List<string>() { "Name", "Value" }, tests);
// lookup where Name == "bbb"
foreach (var result in indexed.GetByIndex("Name", "bbb")) {
    Console.WriteLine(result.Value);
}

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