Самый быстрый способ объединения списков, имеющих общее поле?

Я изучаю F #, и я делаю и сравниваю сравнение (ala www.bestbetting.com) с теорией pu на практике. Пока у меня есть следующие структуры данных:

type price = {    Bookie : string;    Odds : float32;    }

type selection = {
    Prices : list<price>;
    Name : string;
    }

type event = {    Name : string;    Hour : DateTime;    Sport : string;    Selections : list<selection>;    }

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

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

Я хотел бы знать, будет ли более быстрый способ сделать это, поскольку производительность будет важна. Я уже видел это Объединять несколько списков данных вместе по общему идентификатору в F #... И хотя это было полезно, я прошу наилучшего решения с высокой эффективностью. Возможно, используя любую другую структуру, которая не является списком или другим способом их слияния... так что любой совет будет очень благодарен.

Спасибо!

Ответы

Ответ 1

Как упоминал Даниил в комментарии, ключевым вопросом является то, насколько лучше сравнивать производительность с решением на основе стандартной функции Seq.groupBy? Если у вас много данных для обработки, то для этой цели может быть проще использовать некоторую базу данных.

Если вам нужно что-то в 1,7 раза быстрее (или, возможно, больше, в зависимости от количества ядер:-)), вы можете попробовать заменить Seq.groupBy на параллельную версию на основе Parallel LINQ, которая доступна в F # PowerPack. Используя PSeq.groupBy (и другие функции PSeq), вы можете написать примерно следующее:

#r "FSharp.PowerPack.Parallel.Seq.dll"
open Microsoft.FSharp.Collections

// Takes a collection of events and merges prices of events with the same name/hour
let mergeEvents (events:seq<event>) = 
  events 
  |> PSeq.groupBy (fun evt -> evt.Name, evt.Hour)
  |> PSeq.map (fun ((name, hour), events) ->
      // Merge prices of all events in the group with the same Selections.Name
      let selections = 
        events 
        |> PSeq.collect (fun evt -> evt.Selections)
        |> PSeq.groupBy (fun sel -> sel.Name)
        |> PSeq.map (fun (name, sels) ->
            { Name = name
              Prices = sels |> Seq.collect (fun s -> s.Prices) |> List.ofSeq } )
        |> PSeq.toList
      // Build new Event as the result - since we're grouping just using 
      // name & hour, I'm using the first available 'Sport' value 
      // (which may not make sense)
      { Name = name
        Hour = hour
        Sport = (Seq.head events).Sport
        Selections = selections })   
  |> PSeq.toList

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

Ответ 2

Я не тестировал его, но думаю, что это сработает.

let events = List.init 10 (fun _ -> Unchecked.defaultof<event>) //TODO: initialize to something meaningful

for ((name, hour), evts) in (events |> Seq.groupBy (fun e -> e.Name, e.Hour)) do
  printfn "Name: %s, Hour: %A" name hour
  let prices = 
    seq {
      for e in evts do
        for s in e.Selections do
          for p in s.Prices do
            yield s.Name, p 
    }
    |> Seq.groupBy fst

  for (selectionName, p) in prices do
    printfn "  Selection Name: %s" selectionName
    for (_, price) in p do
      printfn "    %A" price