Searching a sequence for a pattern

Question

I have written the following tiny extension method to help me when I'm working with sequences in which I have to find a pattern.

public static IEnumerable<T[]> SearchPattern<T>(this IEnumerable<T> seq, params Func<T[], T, bool>[] matches)
{
      Contract.Requires(seq != null);
      Contract.Requires(matches != null);
      Contract.Requires(matches.Length > 0);

      var matchedItems = new List<T>(matches.Length);
      int itemIndex = 0;

      foreach (T item in seq)
      {
          if (matches[matchedItems.Count](matchedItems.ToArray(), item))
          {
              matchedItems.Add(item);

              if (matchedItems.Count == matches.Length)
              {
                  yield return matchedItems.ToArray();

                  matchedItems.Clear();
              }
          }
          else
          {
              if (matchedItems.Any())
              {
                  foreach (T[] results in seq.Skip(itemIndex - matchedItems.Count + 1).SearchPattern(matches)) // is this a tail call? can it be optimized?
                  {
                      yield return results;
                  }
                  break;
              }
          }
          itemIndex++;
      }
}

It appears to be working fine, but I'm wondering if there's a better way to do it. Primarily I'm concerned with the recursive call (at the nested foreach), which makes the method very inefficient, not to mention potential stack-overflows when working with very large collections.

I know about tail-calls, and that they can be optimized into a loop (like in F#). I also recall having seen something about tail-calls on an IL level. What confuses me is that I'm already using the iterator pattern (yield return) - so is it a tail call at all? If it is, is it one I can eliminate?

Any input would be much appreciated!

Edit: usage sample:

var results = (new int[] { 0, 1, 2, 3, 3, 4, 4, 5, 7, 9 }).SearchPattern(
    (prevs, curr) => true,
    (prevs, curr) => prevs[0] == curr,
    (prevs, curr) => curr % 2 != 0
); // => { [ 4, 4, 5 ] }

Answer 1

Personally, here is how I would do it. I think this is pretty straight-forward. I think it is also no less efficient than the other (longer, more complex) answer. The method Subarray is something I wrote before, I didn’t write it just for this.

/// <summary>Similar to <see cref="string.Substring(int,int)"/>, only for arrays. Returns a new
/// array containing <paramref name="length"/> items from the specified
/// <paramref name="startIndex"/> onwards.</summary>
public static T[] Subarray<T>(this T[] array, int startIndex, int length)
{
    if (array == null)
        throw new ArgumentNullException("array");
    if (startIndex < 0)
        throw new ArgumentOutOfRangeException("startIndex", "startIndex cannot be negative.");
    if (length < 0 || startIndex + length > array.Length)
        throw new ArgumentOutOfRangeException("length", "length cannot be negative or extend beyond the end of the array.");
    T[] result = new T[length];
    Array.Copy(array, startIndex, result, 0, length);
    return result;
}

public static IEnumerable<T[]> SearchPattern<T>(this IEnumerable<T> seq, params Func<T[], T, bool>[] matches)
{
    Contract.Requires(seq != null);
    Contract.Requires(matches != null);
    Contract.Requires(matches.Length > 0);

    // No need to create a new array if seq is already one
    var seqArray = seq as T[] ?? seq.ToArray();

    // Check every applicable position for the matching pattern
    for (int j = 0; j <= seqArray.Length - matches.Length; j++)
    {
        // If this position matches...
        if (Enumerable.Range(0, matches.Length).All(i =>
            matches[i](seqArray.Subarray(j, i), seqArray[i + j])))
        {
            // ... yield it
            yield return seqArray.Subarray(j, matches.Length);

            // and jump to the item after the match so we don’t get overlapping matches
            j += matches.Length - 1;
        }
    }
}

Answer 2

The way a tail call works at the IL level, is that the current stack frame is discarded before calling the method*. So whatever the called method returns is effectively by the calling method. I read somewhere that Microsoft's x64 JIT will optimise this into a loop while their x86 JIT will leave it as a standard function call.

In your particular instance, the tail call cannot be used since the calling method uses the result of the inner call to generate its own result rater than simply returning it.

You can drop the recursion by copying the enumerable into a list and indexing into it. You will need to iterate over all the elements anyway, and by doing it this way you do not need to restart the enumeration every time you recurse.

public static IEnumerable<T[]> SearchPattern<T>(this IEnumerable<T> seq, params Func<T[], T, bool>[] matches)
{
    Contract.Requires(seq != null);
    Contract.Requires(matches != null);
    Contract.Requires(matches.Length > 0);

    var matchedItems = new List<T>(matches.Length);
    var seqList = new List<T>(seq);
    int start = 0;

    while (start + matches.Length < seqList.Count)
    {
        bool fail = false;

        for (int i = 0; i < matches.Length; i++)
        {
            T[] itemsArray = matchedItems.ToArray();

            if (!matches[i](itemsArray, seqList[i + start]))
            {
                fail = true;
                break;
            }

            matchedItems.Add(seqList[i + start]);
        }

        if (!fail)
        {
            yield return matchedItems.ToArray();
            start = start + matches.Length;
        }
        else
        {
            start++;
        }

        matchedItems.Clear()
    }
}

---

[*] The stack will not always be discarded, particularly if it's required for security checks (see OpCodes.TailCall).

Answer 3

You might consider the Knuth-Morris-Pratt algorithm. It was designed for finding a sequence of characters within a string but might be adapted to your needs.

The main thing is in KMP you build a table of offsets of duplicated starting sequences for the pattern you want to find. This lets you efficiently fall back to an earlier position in the pattern and continue your comparisons against the main sequence - no recursion needed.

Edit:

KMP requires the specific pattern in order to build its fall back table. Your sample usage implies a pattern that is more like characteristics (e.g. any number of repeated items that are not odd) which would require customization of the KMP algorithm to work with characteristics, probably by way of a Func as you are doing now.