对于多个属性(键)和作为值的列表，最合适的数据类型是什么?

本文关键字：列表 是什么 数据类型 属性 于多个 | 更新日期: 2023-09-27 18:06:51

我需要一个有点"复杂"的数据类型来存储我的数据:

  • 3属性:角度，宽度，高度
  • 一个有多达4000个项目的大列表，我想将其分类到组，其值高于/低于/等于这3个属性中的每一个。
  • 我需要一个数据类型来存储这三个属性的每个组合，一个适合这三个类别的项目的(子)列表。
  • Edit:还有一种特殊情况，即属性高度可以具有所有值(例如100- 200,200 - 300,300 -400;
  • 这个数据类型应该非常快 &当指定三个属性的值时，支持获取项目(子)列表的可能性。

我想象如下:

dataType[angle][width][height] --> returns a list with items exactly fitting to these three categories

它类似于键-值对，但有三个键，值是(子)列表。

我现在不确定c# (WindowsPhone)中实现的最佳(和最高性能)数据类型是什么:-我可以很容易地做到这一点与ObservableCollection和Linq-Queries。但这将是缓慢的，也许是过度的-我认为内部数据库也可能是多余的，特别是我认为WindowsPhone上的数据库有点慢…-还有什么我错过了(字典，哈希等)?

任何建议都非常感谢!(我希望我能把我的问题描述得通俗易懂…)

对于多个属性(键)和作为值的列表，最合适的数据类型是什么?

我们可以创建一个类来保存您拥有的三个数据块，只要我们给出该类型可感知的Equals和GetHashCode实现，我们就可以将其用作Dictionary中的键，这是一个基于散列的结构，查找速度非常快。

public class Foo : IEquatable<Foo> //TODO give better name
{
    public double Angle { get; set; }
    public double Width { get; set; }
    public double Height { get; set; }
    public override bool Equals(object obj)
    {
        return Equals(obj as Foo);
    }
    public bool Equals(Foo other)
    {
        if (other == null)
            return false;
        return Angle == other.Angle &&
            Width == other.Width &&
            Height == other.Height;
    }
    public override int GetHashCode()
    {
        return new { Angle, Width, Height }.GetHashCode();
    }
}

(您也可以修改此类型使其不可变，只需从构造函数设置属性)

使用这个我们可以创建一个Dictionary<Foo, List<Whatever>>和查找一个集合…无论如何，给定一个对象指定这三个值。

现在，这只适用于寻找所有给定值都完全相等的值。基于散列的结构本身并不能在给定范围内找到所有可能的值。为了做到这一点，我们需要将所有数据存储在一个有序的数据结构中，找到范围开始上方的第一个项，然后继续抓取连续的项，直到该项通过范围的末尾。

要做到这一点，我们将从BinarySearch方法开始，该方法可以找到等于给定项的项的索引，或者第二大项的索引:

public static int BinarySearch<T>(
    this  IList<T> collection, T item, IComparer<T> comparer = null)
{
    comparer = comparer ?? Comparer<T>.Default;
    int startIndex = 0;
    int endIndex = collection.Count;
    while (startIndex <= endIndex)
    {
        int testIndex = startIndex + ((endIndex - startIndex) / 2);
        if (testIndex == collection.Count)
            return testIndex;
        int comparision = comparer.Compare(collection[testIndex], item);
        if (comparision > 0)
        {
            endIndex = testIndex - 1;
        }
        else if (comparision == 0)
        {
            return testIndex;
        }
        else
        {
            startIndex = testIndex + 1;
        }
    }
    return startIndex;
}

从这里，我们可以编写一个方法来获取一个排序列表中给定范围内的所有项:

public static IEnumerable<T> GetWithinRange<T>
    (this IList<T> collection, T start, T end,
    IComparer<T> comparer = null)
{
    comparer = comparer ?? Comparer<T>.Default;
    int index = collection.BinarySearch(start, comparer);
    while (index < collection.Count &&
        comparer.Compare(collection[index], end) <= 0)
    {
        yield return collection[index];
        index++;
    }
}

现在是一个实际的数据结构。因为您说您只需要按范围比较三个参数中的一个，所以其他两个可以利用基于散列的数据结构:

public class Vector : IEquatable<Vector> //TODO consider renaming
{
    public double Angle { get; set; }
    public double Width { get; set; }
    public override bool Equals(object obj)
    {
        return Equals(obj as Vector);
    }
    public bool Equals(Vector other)
    {
        if (other == null)
            return false;
        return Angle == other.Angle &&
            Width == other.Width;
    }
    public override int GetHashCode()
    {
        return new { Angle, Width }.GetHashCode();
    }
}
使用

，我们现在可以写:

Dictionary<Vector, SortedList<double, List<Something>>>

然而，试图直接处理这个问题，并且根据需要不断创建中间结构，将是困难的，所以我们最好创建一个自定义的数据结构来抽象它:

public class FooDataStructure //TODO rename
{
    private Dictionary<Vector, SortedList<double, List<Something>>> dictionary
        = new Dictionary<Vector, SortedList<double, List<Something>>>();
    public void Add(Foo foo, Something something)
    {
        var vector = new Vector { Angle = foo.Angle, Width = foo.Width };
        SortedList<double, List<Something>> list;
        if (!dictionary.TryGetValue(vector, out list))
        {
            list = new SortedList<double, List<Something>>();
            dictionary.Add(vector, list);
        }
        List<Something> somethings;
        if (!list.TryGetValue(foo.Height, out somethings))
        {
            somethings = new List<Something>();
            list.Add(foo.Height, somethings);
        }
        somethings.Add(something);
    }
    public IEnumerable<Something> Find(
        double angle, double width, double minHeight, double maxHeight)
    {
        var vector = new Vector { Angle = angle, Width = width };
        SortedList<double, List<Something>> list;
        if (!dictionary.TryGetValue(vector, out list))
        {
            return Enumerable.Empty<Something>();
        }
        return list.Keys.GetWithinRange(minHeight, maxHeight)
            .SelectMany(key => list[key]);
    }
}

这当然不是完整的。它没有Remove方法，它没有Find方法，不需要高度范围，或者任何其他可能需要查找的操作，但是在这个前提下，您应该能够对大多数方法进行建模。

您可以尝试在列表中使用Tuple

http://msdn.microsoft.com/en-us/library/system.tuple.aspx

相关文章：