Как эффективно узнать, содержит ли последовательность хотя бы n элементов?

Question

Просто наивное использование Seq.length может быть недостаточно для взрыва бесконечных последовательностей.

Будет более интересно использовать что-то вроде ss |> Seq.truncate n |> Seq.length, но за кулисами может потребоваться двойной обход фрагмента последовательности аргументов в MoveNext().

IEnumerator.

Лучший подход, который мне удалось найти, это:

let hasAtLeast n (ss: seq<_>) =
    let mutable result = true
    use e = ss.GetEnumerator()
    for _ in 1 .. n do result <- e.MoveNext()
    result

Это включает в себя только один обход последовательности (точнее, выполнение e.MoveNext() n раз) и правильно обрабатывает граничные случаи пустых и бесконечных последовательностей. Кроме того, я могу добавить несколько небольших улучшений, таких как явная обработка конкретных случаев для списков, массивов и ICollection s, или некоторая обработка длины хода, но мне интересно, существует ли какой-либо более эффективный подход к проблеме, который я могу пропустить?

Спасибо за вашу помощь.

РЕДАКТИРОВАТЬ : Наличие под рукой 5 общих вариантов реализации функции hasAtLeast (2 моих собственных, 2 предложенных Daniel и один предложенный Ankur ) Я устроил марафон между ними. Результаты, которые связаны для всех реализаций, доказывают, что Guvante верен: простейшая комбинация существующих алгоритмов была бы лучшей, здесь нет никакого смысла в перепроектировании.

Далее, добавив коэффициент читабельности, я бы использовал либо мой собственный чистый F # на основе

let hasAtLeast n (ss: seq<_>) =
    Seq.length (Seq.truncate n ss) >= n

или предложенный Ankur полностью эквивалентный, основанный на Linq, который использует интеграцию .NET

let hasAtLeast n (ss: seq<_>) =
    ss.Take(n).Count() >= n

Answer 1

Вот краткое, функциональное решение:

let hasAtLeast n items = 
  items 
  |> Seq.mapi (fun i x -> (i + 1), x)
  |> Seq.exists (fun (i, _) -> i = n)

Пример:

let items = Seq.initInfinite id
items |> hasAtLeast 10000

А вот оптимальный вариант:

let hasAtLeast n (items:seq<_>) = 
  use e = items.GetEnumerator()
  let rec loop n =
    if n = 0 then true
    elif e.MoveNext() then loop (n - 1)
    else false
  loop n

Answer 2

Функциональное программирование разбивает рабочие нагрузки на небольшие куски, которые выполняют очень общие задачи и выполняют одну простую вещь. Определить, есть ли в последовательности хотя бы n элементов, не простая задача.

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

Однако мне интересно, не сработает ли ваше первое решение. MoveNext() вызывается только n раз в исходном методе наверняка, Current никогда не вызывается, и даже если MoveNext() вызывается для некоторого класса-оболочки, последствия для производительности, вероятно, крошечные, если n не огромен.

EDIT:

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

Я думаю, что необходимы пояснения, чтобы объяснить, что происходит в этих методах. Seq.truncate принимает последовательность и возвращает последовательность. Кроме сохранения значения n он ничего не делает до перечисления. Во время перечисления он считается и останавливается после значений n. Seq.length берет перечисление и считает, возвращая счет, когда он заканчивается. Таким образом, перечисление перечисляется только один раз, а количество накладных расходов составляет пару вызовов метода и два счетчика.

Answer 3

Используя Linq, это будет так просто:

let hasAtLeast n (ss: seq<_>) = 
   ss.Take(n).Count() >= n

Метод взятия Seq взрывается, если не хватает элементов.

Пример использования, чтобы показать, что он пересекает seq только один раз и донеобходимые элементы:

seq { for i = 0 to 5 do
        printfn "Generating %d" i
        yield i }
|> hasAtLeast 4 |> printfn "%A"