11
\$\begingroup\$

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 ] }
\$\endgroup\$
2
  • \$\begingroup\$ I haven't looked at the details of your code, but just keep in mind that LINQ itself -- as well as the yield statements -- are very inefficient. \$\endgroup\$
    – user541686
    Apr 9 '11 at 22:47
  • \$\begingroup\$ @Mehrdad: I understand that, and a certain level of inefficiency is an acceptable trade for ease-of-use. What I'm trying to determine is whether it's possible to optimize the above recursive code, mainly by eliminating the recursive call. \$\endgroup\$
    – ShdNx
    Apr 9 '11 at 22:51
4
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ A most elegant solution, thank you very much! I'm going to wait a few more hours to see if anybody can offer an even better answer (which I doubt), but so far I like your solution the most. \$\endgroup\$
    – ShdNx
    Apr 10 '11 at 16:20
3
\$\begingroup\$

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).

\$\endgroup\$
4
  • \$\begingroup\$ I suspect that instead of start = start + matches.Length; you actually want start++; as otherwise you will be skipping items that could potentially match. As far as I can tell the original implementation in the question does look at all sequences starting at every item. \$\endgroup\$
    – Timwi
    Apr 10 '11 at 0:50
  • 1
    \$\begingroup\$ Furthermore, I believe you will need to move the matchedItems.Clear(); and the start++; to after the if. You want to clear it and move to the next item whether the match failed or not; otherwise the next iteration will have junk in it. \$\endgroup\$
    – Timwi
    Apr 10 '11 at 0:52
  • \$\begingroup\$ @Timwi: On your first point, I thought about that, but the original increments by matches.Length upon recursing without continuing upon return. So I figured the OP did not want overlapping matches. Good point on the second one though, I'll fix. \$\endgroup\$ Apr 10 '11 at 1:17
  • \$\begingroup\$ Very nice answer, thank you! I have not tried your implementation yet, but I understand what you're doing - and that's the real point. To be entirely honest, I haven't given overlapping matches a thought, but this is something easy to change, and e.g. bind to a bool allowOverlapping parameter. \$\endgroup\$
    – ShdNx
    Apr 10 '11 at 16:11
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ That looks fairly interesting, although I believe what the others have suggested are better in my case. Thanks anyway, +1. \$\endgroup\$
    – ShdNx
    Apr 11 '11 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.