Примеры последовательности и выполнения запросов - PullRequest
Новая
       44

Примеры последовательности и выполнения запросов

0 голосов
/ 11 марта 2011

Я хотел бы получить несколько указателей и / или пример кода о том, как использовать F # / функциональное программирование для поиска повторяющихся значений в списке.

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

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

TIA

Ответы [ 2 ]

1 голос
/ 11 марта 2011

Хотя мне нравится краткость кода Томаса, я не могу не думать, что более эффективная версия, на которую он намекал, действительно обязательна, особенно если реальная логика сравнения всегда дороже, чем простое интегральное сравнение. Я представляю следующую абстракцию: 

let findWindowBeginnings predicate minWindowSize data =
    if minWindowSize < 2 then
        invalidArg "minWindowSize" "minWindowSize must be greater than 1"

    ((None, []), data)
    ||> Seq.fold (fun (window, acc) x ->
        if predicate x then
            match window with
            | Some (start, size) -> let size' = size + 1
                                    let acc' = if size' = minWindowSize
                                               then start::acc
                                               else acc
                                    Some (start, size'), acc'
            | _                  -> Some (x, 1), acc
        else None, acc)
    |> snd
    |> List.rev

Ваш вариант использования последовательности кортежей дата + температура будет выглядеть так: 

let findHeatwaveBeginnings tempThreshold consecutiveDays data =
    (consecutiveDays, data)
    ||> findWindowBeginnings (snd >> (<) tempThreshold)
    // alternatively, if you're not a fan of point-free style code:
    //  findWindowBeginnings (fun (_, maxTemp) -> maxTemp > tempThreshold)
    |> List.map fst

Поскольку findWindowBeginnings управляется Seq.fold, он, естественно, будет работать естественным образом с массивами и списками. Кроме того, findWindowBeginnings абсолютно не зависит от исследуемого типа данных, поскольку передаваемый вами предикат выполняет экстраспекцию данных, и предикат, конечно, может работать с любым типом данных, который вам нравится (кортежи, записи, надлежащие классы / структуры и т. Д.). ). Единственное требование состоит в том, чтобы входные данные были логически отсортированы.

F # Ссылка на фрагмент: http://fssnip.net/3u

1 голос
/ 11 марта 2011

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

source
// Create groups of specified size
|> Seq.windowed requiredLength
// Add starting indices to the sequence
|> Seq.mapi (fun i v -> i, v)
// Find all groups that contain only numbers larger than treshold
|> Seq.filter (fun (i, v) -> v |> Seq.forall ((<) treshold))
// Get indices of such groups
|> Seq.map fst

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

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

...