存储大量数值字段的最佳数据结构

Question

我正在处理一个类（Widget），该类具有大量真实世界的数字属性（例如高度、长度、重量、成本等）。有不同类型的小部件（sprockets、cogs等），但每个小部件都共享完全相同的属性（当然，各个小部件的值将不同，但它们都有重量、长度等）。我有数千个每种小部件（1,000个齿轮，1,000个链轮等）。

我需要对这些属性执行大量计算（例如计算1000个不同小部件的属性的加权平均值）。对于加权平均值，我针对每个小部件类型有不同的权重（即，我可能更关心齿轮的长度而不是链轮）。

现在，我正在每个小部件中存储所有属性，在其中使用Dictionary<string，double>。然后，我有一些计算器类，它们将每个属性的权重存储为Dictionary<WidgetType，Dictionary<string，double>>。要计算每个小部件的加权平均值，我只需迭代其属性字典键，如下所示：

double weightedAvg = 0.0;
foreach (string attibuteName in widget.Attributes.Keys)
{
    double attributeValue = widget.Attributes[attributeName];
    double attributeWeight = calculator.Weights[widget.Type][attributeName];
    weightedAvg += (attributeValue * attributeWeight);
}

所以这个方案运行良好，易于阅读和维护，但是当基于某些分析数据有1000多个小部件时速度非常慢。我的属性名称的宇宙在应用程序的使用期间已知且不会改变，因此我想知道有哪些更好的选择。我能想到的几种方式是：

1）将属性值和权重存储为double []数组。我认为这可能是最有效的选项，但是我需要确保这些数组始终按正确顺序存储在小部件和计算器之间。这也将数据从元数据中分离出来，因此我需要在某处存储一个数组（？），该数组将属性名称映射到属性值和权重的double []中的索引。

2）将属性值和权重存储为不可变的结构体。我喜欢这个选项，因为我不必担心排序问题，而且数据是“自文档”的。但是，在代码中循环遍历这些属性是否有简单的方法？我有近100个属性，因此我不想在代码中硬编码所有这些内容。我可以使用反射，但我担心这会导致更大的性能损失，因为我正在循环遍历如此多的小部件，并且必须对每一个进行反射。

是否有其他选择？

- S. Austin

---

当你说需要循环100个属性时，是指每个类都有100个属性吗？还是指您必须在单个属性（例如重量）上循环100个类的实例？我认为一个基类，每个更具体的类都会继承它，并且一个单独的方法来计算单个小部件会更合适。 - Chris Dunaway

你可以将所有内容存储在矩阵中（请参见 http://numerics.mathdotnet.com/ 获取一个免费的 NuGet 包，它非常出色），然后实现直接获取和设置值到矩阵的属性。这样你就可以获得访问的便利性，同时计算性能也会更好。 - Meirion Hughes

@ChrisDunaway，目前我只有一个Widget类，小部件的类型只是作为类的属性（枚举值）存储。我可以将小部件类型制作成不同的子类，但我认为这并不能解决我的问题。无论如何，回答你的问题，Widget类有100个属性。因此，要计算任何一个小部件的加权平均值，我需要执行100次乘法和加法。但我还要对1000多个不同的小部件实例执行这个加权平均值计算。 - S. Austin

它们是否都具有相同的属性列或不同的属性列？ - Meirion Hughes

嗯，你最好使用向量列表（双数组）...然后在列表上使用Parallel.For...这非常简单。我马上要吃晚饭了，如果没有其他人回答，我会发布一个答案。 - Meirion Hughes

Answer 1

有三种可能性立即浮现在脑海中。第一种，我认为你过于轻易地拒绝了，那就是在你的类中拥有单独的字段。也就是说，有命名为“height”、“length”、“weight”、“cost”等的单独的“double”值。你是对的，这样做需要更多的代码来进行计算，但你不需要字典查找的间接操作。

第二种是放弃字典而采用数组。因此，你只需要一个“double[]”，而不是一个“Dictionary”。同样，我认为你过于快速地拒绝了这个方法。你可以很容易地用枚举替换字符串字典键。所以你会有：

enum WidgetProperty
{
    First = 0,
    Height = 0,
    Length = 1,
    Weight = 2,
    Cost = 3,
    ...
    Last = 100
}

有了这个，加上一个 double 数组，你就可以很容易地遍历每个实例的所有值：

for (int i = (int)WidgetProperty.First; i < (int)WidgetProperty.Last; ++i)
{
    double attributeValue = widget.Attributes[i];
    double attributeWeight = calculator.Weights[widget.Type][i];
    weightedAvg += (attributeValue * attributeWeight);
}

直接访问数组比通过字符串访问字典要快得多。 最后，您可以稍微优化一下对字典的访问。不要在键上进行 foreach，然后进行字典查找，而应该在字典本身上进行 foreach：

foreach (KeyValuePair<string, double> kvp in widget.Attributes)
{
    double attributeValue = kvp.Value;
    double attributeWeight = calculator.Weights[widget.Type][kvp.Key];
    weightedAvg += (attributeValue * attributeWeight);
}

- Jim Mischel

---

谢谢Jim，这个答案很棒。我甚至没有考虑过可以以那种方式循环枚举。我曾考虑过用枚举代替字典中的字符串键，但使用枚举+数组似乎更好。 - S. Austin

Answer 2

为了计算加权平均数，而又不使用循环或反射，一个方法是计算每个属性的加权平均数，并将它们存储在某个地方。这应该在创建小部件实例时发生。以下是一段示例代码，需要根据您的需求进行修改。 此外，为了进一步处理小部件本身，您可以使用数据并行性。请参见我在此线程中的其他回复。

public enum WidgetType { }

public class Claculator { }

public class WeightStore
{
    static Dictionary<int, double> widgetWeightedAvg = new Dictionary<int, double>();
    public static void AttWeightedAvgAvailable(double attwightedAvg, int widgetid)
    {
        if (widgetWeightedAvg.Keys.Contains(widgetid))
            widgetWeightedAvg[widgetid] += attwightedAvg;
        else
            widgetWeightedAvg[widgetid] = attwightedAvg;
    }
}

public class WidgetAttribute
{
    public string Name { get; }
    public double Value { get; }
    public WidgetAttribute(string name, double value, WidgetType type, int widgetId)
    {
        Name = name;
        Value = value;
        double attWeight = Calculator.Weights[type][name];
        WeightStore.AttWeightedAvgAvailable(Value*attWeight, widgetId);
    }
}

public class CogWdiget
{
    public int Id { get; }
    public WidgetAttribute height { get; set; }
    public WidgetAttribute wight { get; set; }
}

public class Client
{
    public void BuildCogWidgets()
    {
        CogWdiget widget = new CogWdiget();
        widget.Id = 1;
        widget.height = new WidgetAttribute("height", 12.22, 1);
    }
}

- user1719287

---

所以您建议在对象创建时缓存加权值？谢谢，这是一个有用的想法，我没有考虑过。我不确定它是否适用于我的情况，因为有许多不同的计算器，大多数可能只针对小部件的子集进行调用（我事先不知道），因此我最终会缓存许多可能永远不会使用的数据。但我会考虑的。 - S. Austin

Answer 3

通常情况下，数据规范化的选择会决定性能的很大一部分。看起来你需要从当前模型转换到另一个模型或混合模型。

如果你不使用 C# 进行处理，而是使用数据库进行处理，那么你的场景就可以获得更好的性能。这样你就可以获得索引的好处，除了想要的结果之外，没有数据传输，还可以节省成千上万小时的性能优化时间。

- Norbert

---

楼主没有提到任何关于数据库的内容，这更像是一条评论而不是答案。 - Chris Dunaway

Answer 4

使用 .NET 4 及以上版本支持的数据并行性。

https://msdn.microsoft.com/en-us/library/dd537608(v=vs.110).aspx

以上链接的摘录：

并行循环运行时，TPL将数据源分区，以便循环可以同时操作多个部分。在幕后，任务计划程序根据系统资源和工作负载对任务进行分区。如果工作负载不平衡，调度程序会尽可能地重新分配工作到多个线程和处理器中。

- user1719287