Вопросы Теги

Эффективность приправляющего карри F#?

У меня есть функция, которая смотрит следующим образом:

let isInSet setElems normalize p = 
        normalize p |> (Set.ofList setElems).Contains

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

let getLowerExtension p = (Path.GetExtension p).ToLowerInvariant()
let isHtmlPath = isInSet [".htm"; ".html"; ".xhtml"] getLowerExtension

Однако, когда я использую функцию, такую как вышеупомянутое, производительность плоха, так как оценка тела функции, как записано в "isInSet", кажется, задержана, пока все параметры не известны - в частности, инвариантные биты такой как (Set.ofList setElems).Contains переоценены каждое выполнение isHtmlPath.

Как может лучше всего я поддерживать succint F#, читаемая природа, все еще получая более эффективное поведение, в котором предварительно оценена конструкция набора.

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

9
задан Eamon Nerbonne 24 April 2010 в 10:27
поделиться

4 ответа

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

Код выглядел бы так: 

let preProcess finit frun preInput =  
  let preRes = finit preInput
  fun input -> frun preRes input

let f : string list -> ((string -> string) * string) -> bool =
  preProcess 
    Set.ofList                           // Pre-processing of the first argument
    (fun elemsSet (normalize, p) ->      // Implements the actual work to be 
      normalize p |> elemsSet.Contains) // .. done once we get the last argument

Вопрос, является ли это более элегантным, хотя...

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

type CurryBuilder() = 
  member x.Bind((), f:'a -> 'b) = f
  member x.Return(a) = a
let curry = new CurryBuilder()

В вычислении curry вы можете использовать let! , чтобы обозначить, что вы хотите взять следующий аргумент функции (после оценки предыдущего кода):

let f : string list -> (string -> string) -> string -> bool = curry {
  let! elems = ()
  let elemsSet = Set.ofList elems
  printf "elements converted"
  let! normalize = ()
  let! p = ()
  printf "calling"
  return normalize p |> elemsSet.Contains }

let ff = f [ "a"; "b"; "c" ] (fun s -> s.ToLower()) 
// Prints 'elements converted' here
ff "C"
ff "D"
// Prints 'calling' two times

Вот некоторые ресурсы с дополнительной информацией о вычислительных выражениях:

5
ответ дан 4 December 2019 в 10:03
поделиться

@ Kha ответ точно на высоте. F # не может переписать 

// effects of g only after both x and y are passed
let f x y =
    let xStuff = g x
    h xStuff y

в 

// effects of g once after x passed, returning new closure waiting on y
let f x =
    let xStuff = g x
    fun y -> h xStuff y

, если он не знает, что g не имеет никакого эффекта, а в .NET Framework сегодня обычно невозможно рассуждать о эффектах 99% всех выражений. Это означает, что программист по-прежнему несет ответственность за явный порядок оценки кода, как указано выше.

5
ответ дан 4 December 2019 в 10:03
поделиться

  1. Каррирование не повредит. Каррирование также иногда приводит к закрытию. Обычно они тоже эффективны. обратитесь к этот вопрос , который я задавал ранее. При необходимости вы можете использовать встроенный для повышения производительности.

  2. Однако ваша проблема с производительностью в этом примере в основном связана с вашим кодом:

    normalize p |> (Set.ofList setElems). Содержит

, здесь вам нужно выполнить Set.ofList setElems даже карри. Это стоит O (n log n) времени. Вам необходимо изменить тип setElems на F # Set, а не List now. Кстати, для небольшого набора использование списков быстрее, чем наборов, даже для запросов.

2
ответ дан 4 December 2019 в 10:03
поделиться

Пока F # не делает различий между чистым и нечистым кодом, я сомневаюсь, что мы увидим оптимизацию такого рода . Однако вы можете сделать каррирование явным. 

let isInSet setElems =
    let set = Set.ofList setElems
    fun normalize p -> normalize p |> set.Contains

isHtmlSet теперь будет вызывать isInSet только один раз, чтобы получить закрытие, одновременно выполняя ofList .

9
ответ дан 4 December 2019 в 10:03
поделиться
Другие вопросы по тегам:

Похожие вопросы: