c# - 如何在数据表中查找匹配的记录

Question

我有一个包含两列的数据表:一个数字和一个日期，例如:

125 | 2013/10/20
100 | 2013/10/21
150 | 2013/10/24
225 | 2013/10/24
250 | 2013/10/28
310 | 2013/10/30

现在，我想搜索所有按日期排序且总和等于 500 的记录。我可以很容易地看到第一、第三和第四条记录 (125 + 150 + 225 = 500) 提供了一个匹配，但要编写这样的程序，我只能想到遍历数据表无数次，直到找到正确的匹配。

有人有更好的主意吗？

Answer 1

在最坏的情况下，您必须遍历所有 2^n你的数据集的子集，但如果你的所有项目都是非负的，你可以开始过滤 item.Number <= 500 .

这是一个可能的 Subsets方法(实际上是对 How to get all subsets of an array? 的回答，但不要告诉他们):

public static IEnumerable<IEnumerable<T>> Subsets(this IEnumerable<T> source)
{
    var first = source.FirstOrDefault();
    if (first == null) return new[] { Enumerable.Empty<T>() };

    var others = source.Skip(1).Subsets();
    return others.Concat(others.Select(s => s.Concat(new { first })));
}

一旦你有了你的 Subsets方法，那么你可以按如下方式过滤结果，尽管性能仍然是一个巨大的数量级(或者 2^n 如果你想挑剔的话)。

var sets = items.Where(i => i.Number <= 500)
    .Subsets().Where(s => s.Sum(i => i.Number) == 500);

但是，如果您对 Number 有约束, 它是非负的，你可以结合 Subsets搜索目标总和的操作。那意味着你会定义

public static IEnumerable<IEnumerable<T>> SubsetsAddingUpTo(this IEnumerable<T> source, int target)
{
    // This stopping condition ensures that you will not have to walk the rest of the tree when you have already hit or exceeded your target.
    // It assumes that the Number values are all non-negative.
    if (target < 0) return Enumerable.Empty<IEnumerable<T>>();

    var first = source.FirstOrDefault();
    if (first == null) return Enumerable.Empty<IEnumerable<T>>();

    var tail = source.Skip(1).Where(i => i.Number <= target).ToList();

    var othersIncludingFirst = tail.SubsetsAddingUpTo(target - first.Number);
    var othersExcludingFirst = tail.SubsetsAddingUpTo(target);

    return othersExcludingFirst.Concat(othersIncludingFirst.Select(s => s.Concat(new { first })));
}

因为检查 <= target发生在方法内部，您不必进行任何预过滤。但是，您可以在进行搜索之前执行排序，以便以分层日期顺序为您提供集合。电话将是

var sets = items.OrderByDescending(i => i.Date).SubsetsAddingUpTo(500);

这实际上应该会给您带来不错的性能。最坏的情况(每个项目的数字为 0 或 1)不会很好(顺序 2^n )，但如果 Number 的大部分值与您的目标总和具有相似的数量级，就像您的示例中的情况一样，那么停止条件将助您一臂之力，并为您节省大量不必要的操作。