4

我正在尝试学习 LINQ，似乎应该可以找到一系列与谓词匹配的“n”元素，但我似乎无法弄清楚如何解决这个问题。

我的解决方案实际上需要第二个不同的谓词来测试序列的“结束”，但是在至少 5 个通过测试的元素的序列之后找到第一个没有通过测试的元素也会很有趣。

这是我天真的非 LINQ 方法....

 int numPassed = 0;
 for (int i = 0; i < array.Count - 1; i++ )
 {
     if (FirstTest(array[i]))
     {
        numPassed++;
     }
     else
     {
        numPassed = 0;
     }

     if ((numPassed > 5) && SecondTest(array[i + 1]))
     {
          foundindex = i;
          break;
     }
  }
4

6 回答 6

3

一个高性能的 LINQ 解决方案是可能的，但坦率地说相当难看。这个想法是隔离与描述匹配的子序列（一系列 N 项与谓词匹配，当找到与第二个谓词匹配的项时结束），然后选择其中具有最小长度的第一个。

假设参数是：

var data = new[] { 0, 1, 1, 1, 0, 0, 2, 2, 2, 2, 2 };

Func<int, bool> acceptPredicate = i => i != 0;

// The reverse of acceptPredicate, but could be otherwise
Func<int, bool> rejectPredicate = i => i == 0;

GroupBy使用一堆丑陋的有状态代码可以隔离子序列（这是固有的尴尬——你必须保持非平凡的状态）。这个想法是通过一个人为的和任意的“组号”进行分组，每当我们从一个可能可以接受的子序列移动到一个绝对不可接受的子序列时选择一个不同的数字，并且当相反的情况发生时：

var acceptMode = false;
var groupCount = 0;
var groups = data.GroupBy(i => {
    if (acceptMode && rejectPredicate(i)) {
        acceptMode = false;
        ++groupCount;
    }
    else if (!acceptMode && acceptPredicate(i)) {
        acceptMode = true;
        ++groupCount;
    }
    return groupCount;
});

最后一步（找到可接受长度的第一组）很容易，但还有最后一个陷阱：确保您不选择不满足规定条件的组：

var result = groups.Where(g => !rejectPredicate(g.First()))
                   .FirstOrDefault(g => g.Count() >= 5);

以上所有这些都是通过源序列上的单次传递来实现的。

请注意，此代码将接受也结束源序列的项目序列（即它不会终止，因为我们找到了一个满足的项目，rejectPredicate而是因为我们用完了数据）。如果您不希望这样做，则需要稍作修改。

看到它在行动。

于 2012-08-03T08:31:58.723 回答
1

不优雅，但这会起作用：

var indexList = array
                 .Select((x, i) => new 
                     { Item = x, Index = i })
                 .Where(item => 
                     item.Index + 5 < array.Length && 
                     FirstTest(array[item.Index]) && 
                     FirstTest(array[item.Index+1]) && 
                     FirstTest(array[item.Index+2]) && 
                     FirstTest(array[item.Index+3]) && 
                     FirstTest(array[item.Index+4]) && 
                     SecondTest(array[item.Index+5]))
                 .Select(item => item.Index);
于 2012-08-03T08:15:46.623 回答
1

与其尝试组合现有的扩展方法，不如使用Enumerator.

例子：

IEnumerable<T> MatchThis<T>(IEnumerable<T> source, 
                            Func<T, bool> first_predicate,
                            Int32 times_match,
                            Func<T, bool> second_predicate)
{
    var found = new List<T>();
    using (var en = source.GetEnumerator())
    {
        while(en.MoveNext() && found.Count < times_match)
            if (first_predicate((T)en.Current))
                found.Add((T)en.Current);
            else
                found.Clear();

        if (found.Count < times_match && !en.MoveNext() || !second_predicate((T)en.Current))
            return Enumerable.Empty<T>();

        found.Add((T)en.Current);
        return found;
    }
}

用法：

var valid_seq = new Int32[] {800, 3423, 423423, 1, 2, 3, 4, 5, 200, 433, 32};
var result = MatchThis(valid_seq, e => e<100, 5, e => e>100);

结果：

在此处输入图像描述

于 2012-08-03T08:43:14.853 回答
0

看起来你想要连续的 6 个元素，其中前 5 个匹配 predicate1，最后一个（第 6 个）匹配 predicate2。您的非 linq 版本工作正常，在这种情况下使用 linq 有点不情愿。并且试图在一个 linq 查询中解决问题会使问题变得更加困难，这是一个（也许）更干净的 linq 解决方案：

int continuous = 5;
var temp = array.Select(n => FirstTest(n) ? 1 : 0);
var result = array.Where((n, index) => 
               index >= continuous 
               && SecondTest(n) 
               && temp.Skip(index - continuous).Take(continuous).Sum() == continuous)
    .FirstOrDefault();

如果你有方法，事情会更容易。Morelinq.Batch

于 2012-08-03T08:46:29.770 回答
0 
var result = array.GetSixth(FirstTest).FirstOrDefault(SecondTest);

internal static class MyExtensions
{
      internal static IEnumerable<T> GetSixth<T>(this IEnumerable<T> source, Func<T, bool> predicate)
       {
            var counter=0;
            foreach (var item in source)
            {
                if (counter==5) yield return item;
                counter = predicate(item) ? counter + 1 : 0;
            }
        }
}
于 2012-08-03T08:53:20.800 回答
-1

就像其他人提到的那样，LINQ 并不是这种模式匹配需求的理想解决方案。但是，它仍然是可能的，而且它不一定是丑陋的：

Func<int, bool> isBody = n => n == 8;
Func<int, bool> isEnd = n => n == 2;
var requiredBodyLength = 5;

//    Index:       0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
int[] sequence = { 6, 8, 8, 9, 2, 1, 8, 8, 8, 8, 8, 8, 8, 2, 5 };
//                                         ^-----------^  ^
//                                             Body      End

// First we stick an index on each element, since that's the desired output.
var indexedSequence = sequence.Select((n, i) => new { Index = i, Number = n }).ToArray();

// Scroll to the right to see comments
var patternMatchIndexes = indexedSequence
    .Select(x => indexedSequence.Skip(x.Index).TakeWhile(x2 => isBody(x2.Number)))             // Skip all the elements we already processed and try to match the body
    .Where(body => body.Count() == requiredBodyLength)                                         // Filter out any body sequences of incorrect length
    .Select(body => new { BodyIndex = body.First().Index, EndIndex = body.Last().Index + 1 })  // Prepare the index of the first body element and the index of the end element
    .Where(x => x.EndIndex < sequence.Length && isEnd(sequence[x.EndIndex]))                   // Make sure there is at least one element after the body and that it's an end element
    .Select(x => x.BodyIndex)                                                                  // There may be more than one matching pattern, get all their indices
    .ToArray();

//patternMatchIndexes.Dump();   // Uncomment in LINQPad to see results

请注意，此实现根本不是高性能的，它只是作为一种教学辅助工具来展示如何在 LINQ 中完成某些事情，尽管以这种方式解决它并不合适。

于 2012-08-03T08:53:12.467 回答