Поиск последовательности по шаблону


Я написал следующий крошечные метод расширения, чтобы помочь мне, когда я работаю с последовательности, в которой я должен найти закономерность.

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++;
      }
}

Это, кажется, работает нормально, но я интересно, если есть лучший способ сделать это. В первую очередь я беспокоюсь о рекурсивного вызова (на вложенные циклы foreach), что делает метод очень неэффективен, не говоря уже о потенциальных стека переполнение при работе с очень большими коллекциями.

Я знаю про хвост-звонки, и что они могут быть оптимизированы в петлю (как в F#). Я также помню, что видел что-то про хвост-звонки на уровне Ил. Что меня смущает это то, что я уже через итератор шаблон (возврата) - так это хвост называть вообще? Если это так, это я могу устранить?

Любой вклад будет высоко ценится!

Редактировать: пример использования:

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 ] }


6377
11
задан 9 апреля 2011 в 10:04 Источник Поделиться
Комментарии
3 ответа

Лично, вот как я бы это сделал. Я думаю, что это довольно прямо вперед. Я думаю, что это тоже не менее эффективны, чем другие (более сложные) ответа. Метод подмассив - это то, что я писал раньше, я это писала не только для этого.

/// <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;
}
}
}

4
ответ дан 10 апреля 2011 в 01:04 Источник Поделиться

Путь хвостовой вызов, работает на уровне Ил, заключается в том, что текущий кадр стека удаляется перед вызовом метода*. Так что вызываемый метод возвращает фактически вызывающий метод. Я где-то читал, что Майкрософт х64 JIT-компилятор будет оптимизировать это в цикле, пока их архитектурой x86 JIT-компилятором будет оставить его как стандартный вызов функции.

В вашем конкретном случае, хвост вызов не может быть использован после вызова метода использует результат внутреннего вызова, чтобы генерировать собственный тарификатор результат, чем просто вернуть его.

Вы можете оставить рекурсию, копируя перечисляемую в список и индексации в него. В любом случае потребуется перебрать все элементы, и делая это таким образом, вам не нужно перезагружать перечисление каждый раз, когда вы повторить.

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()
}
}


[*] Стек не всегда будет отбросить, особенно если это требуется для проверки безопасности (см. опкодов.TailCall).

3
ответ дан 10 апреля 2011 в 12:04 Источник Поделиться

Вы могли бы рассмотреть Кнута-Морриса-Пратта алгоритм. Он был предназначен для поиска последовательности символов в строке, но может быть адаптирован к вашим потребностям.

Главное в КМП можно построить таблицу смещений дублируются начиная последовательностей шаблон, который вы хотите найти. Это позволяет эффективно вернуться к более ранней позиции в шаблон и продолжить сравнения с главной последовательности - не рекурсия нужна.

Редактировать:

КМП требует определенной схеме для того, чтобы построить его упасть обратно стол. Ваш пример подразумевает использование шаблона, который больше похож характеристик (например, количество повторных элементов, не странно), что потребует настройки алгоритма КМП для работы с характеристиками, возможно с помощью функции, как вы делаете сейчас.

2
ответ дан 10 апреля 2011 в 04:04 Источник Поделиться