使用嵌套的Where子句（LINQ）优化数组迭代

Question

使用嵌套的Where子句（LINQ）优化数组迭代

3

我正在创建一个具有搜索功能的(C#)工具。这种搜索类似于“到任何地方”搜索（就像ReSharper或VS2013中一样）。

搜索上下文是一个包含所有项的字符串数组：

private string[] context; // contains thousands of elements

搜索是增量式的，每当用户提供新输入（字符）时就会进行。

我已经使用LINQ Where扩展方法实现了搜索：

// User searched for "c"
var input = "c";
var results = context.Where(s => s.Contains(input));

当用户搜索"ca"时，我尝试使用之前的结果作为搜索上下文，但这会导致（我认为？）嵌套的Where迭代，并且运行效果不佳。可以考虑类似以下代码的解决方案：

// Cache these results.
var results = var results = context.Where(s => s.Contains(input));

// Next search uses the previous search results
var newResults = results.Where(s => s.Contains(input));

有没有办法优化这种情况？

每次搜索时将IEnumerable转换为数组会导致高内存分配并且运行效率低下。

- lysergic-acid

你可以使用 ToList 来实现中间结果的实例化。但是，这样做真的比每次使用 context 更有效吗？ - Tim Schmelter

ToList 比 ToArray 更好吗？ - lysergic-acid

1

你没有使用 ToArray吗？如果列表很大，使用ToList可能更有效率，因为倍增算法只需要找到大于或等于项数的大小，而数组必须具有正确的大小。但那不是我的重点。 - Tim Schmelter

1

这似乎是使用Rx的完美案例，我在多个示例和教程中都看到了类似的情况，如果我找到了其中之一，我会贴出来或写一个答案。 - Dorus

考虑使用智能字符串搜索算法，随着输入字符串的增长和模式数量的增加，性能可能会显著下降。例如，Aho-Corasick或Rabin-Karp算法。 - Alexander

显示剩余2条评论

3个回答

1

我有几个有用的观点要补充，评论区不够用。

首先，我同意其他评论中提到的应该从 .take(100) 开始，以减少加载时间。更好的做法是逐个添加结果。

var results = context.Where(s => s.Contains(input));
var resultEnumerator = result.GetEnumerator()

循环遍历resultEnumerator以逐个显示结果，在屏幕满或启动新搜索时停止。

其次，限制输入速度。如果用户输入“Hello”，您不希望发起5次搜索，分别为“H”、“He”、“Hel”、“Hell”和“Hello”，而是只想搜索“Hello”。当用户稍后添加“world”时，将旧结果与“Hello world”添加到where子句可能是值得的。

results = results.Where(s => s.Contains(input));
resultEnumerator = result.GetEnumerator()

当用户添加新文本时，当然要取消当前正在进行的结果。

使用Rx，节流部分很容易，你会得到类似这样的东西：

var result = context.AsEnumerable();
var oldStr = "";
var resultEnumerator = result.GetEnumerator();
Observable.FromEventPattern(h => txt.TextChanged += h, h => txt.TextChanged -= h)
         .Select(s => txt.Text)
         .DistinctUntilChanged().Throttle(TimeSpan.FromMilliseconds(300))
         .Subscribe(s =>
         {
             if (s.Contains(oldStr))
                 result = result.Where(t => t.Contains(s));
             else
                 result = context.Where(t => t.Contains(s));
             resultEnumerator = result.GetEnumerator();
             oldStr = s;
             // and probably start iterating resultEnumerator again,
             // but perhaps not on this thread.
         });

- Dorus

0

如果你担心分配内存并且不想编写 trie 实现或使用第三方代码，那么你可以通过将上下文数组连续分区来将匹配的条目聚集在前面。虽然不是很 LINQ-ish，但速度快且没有内存成本。

这个分区扩展方法基于 C++ 的 std::partition。

/// <summary>
/// All elements for which predicate is true are moved to the front of the array.
/// </summary>
/// <param name="start">Index to start with</param>
/// <param name="end">Index to end with</param>
/// <param name="predicate"></param>
/// <returns>Index of the first element for which predicate returns false</returns>
static int Partition<T>(this T[] array, int start, int end, Predicate<T> predicate)
{
    while (start != end)
    {
        // move start to the first not-matching element
        while ( predicate(array[start]) )
        {
            if ( ++start == end )
            {
                return start;
            }
        }

        // move end to the last matching element
        do
        {
            if (--end == start)
            {
                return start;
            }
        }
        while (!predicate(array[end]));

        // swap the two
        var temp = array[start];
        array[start] = array[end];
        array[end] = temp;

        ++start;
    }
    return start;
}

现在你需要存储最后一个分区索引，它应该用context长度进行初始化：

private int resultsCount = context.Length;

然后，对于每个增量输入的更改，您可以运行：

resultsCount = context.Partition(0, resultsCount, s => s.Contains(input));

每次操作只会对之前未被筛选出的元素进行检查，这正是你想要的。

对于每个非增量更改，您需要将 resultsCount 重置为原始值。

您可以以方便、调试器友好和 LINQ 友好的方式公开结果：

public IEnumerable<string> Matches
{
    get { return context.Take(resultsCount); }
}

- gwiazdorrr

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Magnus · Accepted Answer

向用户呈现数千个搜索结果是相当无用的。在向用户呈现结果之前，您应该在查询中添加一个“top”（linq中的Take）语句。

var results = context.Where(s => s.Contains(input)).Take(100);

如果您想向用户呈现接下来的100个结果：

var results = context.Where(s => s.Contains(input)).Skip(100).Take(100);

同时，对于所有的搜索，只需使用原始数组，不要嵌套Where，因为除非您将查询实例化，否则没有任何好处。