создание списка путей в f # - PullRequest
Новая
       31

создание списка путей в f #

0 голосов
/ 21 марта 2012

(Это, вероятно, классика, но мне интересно, как это лучше выразить)

Я начинаю слева, в какой-то момент.Для некоторых активов я могу вычислить доходность от начальной даты до некоторой будущей даты.С этой будущей даты я могу рекурсивно двигаться дальше во времени.

Я хотел бы сгенерировать все пути, которые идут как можно дальше вправо, но это останавливается до некоторой целевой даты.

Вот мой код'a является активом, и (DateTime * DateTime) 2 раза, для которых у меня есть котировка для указанного базового актива.

  member this.getPaths dtstart dtend : Set<('a*(DateTime*DateTime)) list>=
     let rec getPaths dtstart dtend (pastpath:List<'a*(DateTime*DateTime)>) : seq<('a*(DateTime*DateTime)) list>=
        let udls = this.getUnderlyingsQuotingAt dtstart
        let onestep = seq { for udl in udls do
                                let qt = this.QuoteNextAfterSrict udl dtstart 
                                if qt.IsNone || (qt.Value |> fst > dtend) then
                                   yield pastpath |> List.rev  
                                else
                                   let nextdate = qt.Value |> fst 
                                   yield! (getPaths nextdate dtend  ((udl, (dtstart, nextdate))::pastpath) )  } 
        onestep
     getPaths dtstart dtend  List.empty |> Set.ofSeq

Поскольку я использую yield !, я буду собирать новый путь для каждой ошибки в конце.Итак, в конце я должен дублировать свою последовательность.Мой вопрос: есть ли лучший способ найти полный путь без дедупликации?

Я мог бы сделать второй проход или добавить аргумент List, но есть ли какой-то «чистый» способ сделать это в одномидти?

обновление

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

update 2

Первое переписывание - это следующее, которое перемещает выход |> List.rev на один уровень выше, позволяя резатьненужное исследование. 

  member this.getPaths dtstart dtend : Set<('a*(DateTime*DateTime)) list>=
     let count = ref  0

     printfn "computing path from %A to %A " dtstart dtend
     let rec getPaths dtstart dtend (pastpath:List<'a*(DateTime*DateTime)>)  : seq<('a*(DateTime*DateTime)) list>=
        let udls      = this.getUnderlyingsQuotingAt dtstart
        let udlquotes = udls |> Seq.map   (fun udl -> (udl , this.QuoteNextAfterSrict udl dtstart))
                                              |> Seq.filter (fun   (_, q) -> q.IsSome)
                                              |> Seq.map    (fun   (udl, q) -> (udl, q.Value))
                                              |> Seq.filter (fun   (_, q) -> fst q <= dtend  )

        let onestep = seq { if udlquotes.IsEmpty then
                                yield pastpath  |> List.rev  
                            else
                                for (udl, q) in udlquotes  do
                                      let nextdate =  (fst q)
                                      count := !count + 1
                                      if !count%1000 = 0 then printfn "!count  %A , path : %A " !count pastpath
                                      yield! (getPaths nextdate dtend  ((udl, (dtstart,  nextdate))::pastpath)   )
                       }
        onestep
     getPaths dtstart dtend  List.empty |> Set.ofSeq

1 Ответ

1 голос
/ 21 марта 2012

Я не совсем понимаю ваш алгоритм, но я думаю, что общая структура выглядит хорошо. Что вы подразумеваете под "дедупликация"? Если вы имеете в виду вызов List.rev, который используется в конце рекурсивной обработки, то это довольно распространенный шаблон (и я не думаю, что есть лучший способ сделать это).

Что касается стиля кодирования F #, то немного разочаровывает, что вы не можете легко использовать сопоставление с образцом при анализе значения qt (поскольку условие не может быть закодировано с использованием встроенного шаблона). Однако вы можете определить параметризованный активный шаблон помощника, который соответствует, когда входное значение больше, чем параметр: 

let inline (|MoreThan|_|) limit input = 
  if input > limit then Some input else None

Используя шаблон, вы можете сделать тело вашего seq более читабельным: 

let rec getPaths dtstart dtend pastpath = seq {
  let udls = this.getUnderlyingsQuotingAt dtstart 
  for udl in udls do 
    match this.QuoteNextAfterSrict udl dtstart with
    | None 
    | Some (MoreThan dtend _, _) ->
        yield pastpath |> List.rev   
    | Some (nextdate, _) ->
        let newpath = (udl, (dtstart, nextdate))::pastpath
        yield! getPaths nextdate dtend newpath }
...