包含多个索引的列表

Question

给定一个通用List我需要某种索引(在数据库意义上),这将允许我快速检索.这个索引的键不是唯一的,所以我不能使用字典.这就是我的想法:给定一个类Foo {P1,P2,P3}可能有这样的数据

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

我需要快速访问P1为"bbb"(第3,第4和第5)的所有记录或P2为111(第1和第3)的所有记录.我可以使用排序列表,但如果我需要多种排序/索引方法,我最终会得到重复列表.

.NET框架中是否有内置的东西,或者可能是OS库,它会做这样的事情？谢谢.

PS我提到"排序列表"的想法是排序列表将更快地返回/找到项目.我不需要列表必须排序; 我只是在寻找快速检索/发现.

Answer 1

永远不要忘记这个原则:做到正确,说清楚,简洁,快速.以该顺序.所以,首先编写天真的实现代码:

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<T> : ICollection<T>允许你索引各种属性的东西并不会太难.

这是一个天真的实现,可以帮助您入门:

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);
}

但是请注意,除非天真的实现还不够快,否则你不这样做的原因是因为你刚刚添加到系统中的额外复杂性.您刚刚添加了新代码来维护,需要测试新代码,如果现实数据速度不快或者不是应用程序的瓶颈,则可能无法获得任何代码.

Answer 2

(编辑精心制作基于收集的策略)

.NET中没有内部结构可供查找使用各种索引.这是两个好的策略:

选项1:LINQ,灵活性和简单性
为了简化和许多其他集成选项,创建一个List(或其他实现IEnumerable的)自定义类型,并使用LINQ进行按需查找.请注意,如果方便,您可以使用匿名类型.您还可以将数据保存在XML结构中,并且仍然可以完成所有这些操作.您可能能够获取数据,执行查找以及在少量明确代码中操作结果.在.Net 4.0中,您可以使用并行 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类.创建您的列表.然后,对于要为其编制索引的每个字段,请创建一个Lookup对象.它们无法构造,但是从您的IEnumerable集合派生:
  Lookup<string, foo> LookupP1 = (Lookup<string, foo>) fooList.ToLookup(f => f.P1, f => p)
  请参阅链接以获取检索项目的语法.基本上,LookupP1包含P1的每个唯一值的IGrouping对象,键入该P1值.您遍历该对象以获取匹配的项目.Lookup对象的一个​​关键属性是它们是不可变的; 因此,每次从fooList中添加/减去时,都必须重做所有Lookup对象.但是如果你很少改变你的fooList,这就是你要走的路.
• Dictionary<T, List<foo>>为每个需要按索引搜索的字段创建一个,其中T是该值的类型.因此,对于您的示例,我们将创建:
  var FoosByP1 = new Dictionary<String,List<foo>>
var FoosByP2 = new Dictionary<Int32,List<foo>>等等.
  然后添加到FoosByP1,键入每个唯一的P1值,List包含P1具有该值的所有foo项.(例如,由"aaa"键入,包含P1为"aaa"的所有foo对象的List.)对每个Foo字段重复.根据您的数据,FoosByP1You将包含3个List对象,分别包含2,3和1个foo项.使用此方案,您可以非常快速地检索.(字典基本上是一个哈希表).
  主要问题是您的数据会在每个词典中重复出现,这可能是也可能不是问题.如果Foo有20个字段并且你有很多foo项,你可以通过一个带有数字键的中心字典和所有你的foo项来节省内存,而单个索引字典则是Dictionary<T, List<Int32>>,其中整数将是Foo的索引中央词典中的项目.这样可以节省内存并且仍然非常快.
  无论你是否有中心词典,建立你的Dictonaries都需要一些cpu周期,但是一旦你拥有它们,你将会处于良好的状态.并使用Linq来构建你的词典!

Answer 3

我从来没有真正有机会使用它，但你可以尝试i4o。它应该为内存中对象提供索引以供 Linq 使用。您可以使用属性或作为构造索引器的一部分指定类的索引，然后创建 IndexableCollection。

此时，您只需使用 Linq 查询集合，索引就会在幕后工作以优化数据的访问模式。