Hiệu suất cà ri F #?

Question

Tôi có một chức năng trông như sau:

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

Chức năng này có thể được sử dụng để nhanh chóng kiểm tra xem một yếu tố là một phần ngữ nghĩa của một số bộ; ví dụ, để kiểm tra xem một đường dẫn tập tin thuộc về một tập tin html:

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

Tuy nhiên, khi tôi sử dụng một chức năng như, hiệu suất trên là nghèo từ đánh giá của cơ quan chức năng như được viết trong "isInSet" dường như bị trì hoãn cho đến khi tất cả các tham số được biết - đặc biệt, các bit bất biến như (Set.ofList setElems).Contains được đánh giá lại mỗi lần thực hiện isHtmlPath.

Làm cách nào tốt nhất tôi có thể duy trì sự kém phát triển của F #, bản chất có thể đọc được trong khi vẫn nhận được hành vi hiệu quả hơn trong đó việc xây dựng bộ được đánh giá trước.

Ở trên là chỉ là một ví dụ; Tôi đang tìm cách tiếp cận chung để tránh làm tôi thất vọng trong chi tiết triển khai - nếu có thể Tôi muốn tránh bị phân tâm bởi các chi tiết như lệnh thi hành vì điều đó thường không quan trọng đối với tôi và loại phá hoại điểm bán hàng của lập trình chức năng.

Answer 1

Câu trả lời từ Kha cho biết cách tối ưu hóa mã theo cách thủ công bằng cách sử dụng đóng trực tiếp. Nếu đây là mẫu thường xuyên mà bạn cần sử dụng thường xuyên, bạn cũng có thể xác định hàm bậc cao hơn để tạo mã hiệu quả từ hai hàm - số đầu tiên thực hiện trước khi xử lý của một số đối số và thực hiện việc xử lý thực tế thực tế sau khi nhận được các đối số còn lại.

Mã này sẽ trông như thế này:

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 

Đó là một câu hỏi liệu đây là tao nhã hơn mặc dù ...

khác (điên) ý kiến ​​cho rằng bạn có thể sử dụng biểu thức tính toán cho việc này. Định nghĩa của người xây dựng tính toán cho phép bạn làm điều này là rất phi tiêu chuẩn (nó không phải là thứ mà mọi người thường làm với họ và nó không liên quan đến monads hay bất kỳ lý thuyết nào khác). Tuy nhiên, chúng ta có thể viết này:

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

Trong curry tính toán, bạn có thể sử dụng let! để biểu thị mà bạn muốn để có những số tiếp theo của hàm (sau khi đánh giá các mã preceeding):

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 

Dưới đây là một số tài nguyên với nhiều thông tin về các biểu thức tính toán:

• cách thông thường của việc sử dụng tính toán nhanh ion được mô tả trong chương mẫu miễn phí của cuốn sách của tôi: Chapter 12: Sequence Expressions and Alternative Workflows (PDF)

• Ví dụ trên sử dụng một số chi tiết cụ thể của bản dịch mà là ở detailes đầy đủ mô tả trong the F# specification (PDF)

Answer 2

1. Cà ri không bị tổn thương. Currying đôi khi giới thiệu đóng cửa là tốt. Chúng thường hiệu quả. tham chiếu đến this question Tôi đã hỏi trước đây. Bạn có thể sử dụng nội dòng để tăng hiệu suất nếu cần.

2. Tuy nhiên, vấn đề hiệu suất của bạn trong ví dụ này chủ yếu là do mã của bạn:

   normalize p |> (Set.ofList setElems).Contains

đây bạn cần phải thực hiện Set.ofList setElems thậm chí bạn cà ri nó. Nó tốn thời gian O (n log n). Bạn cần thay đổi loại setElems thành F # Set, chứ không phải Danh sách bây giờ. Btw, cho tập hợp nhỏ, sử dụng danh sách nhanh hơn so với bộ ngay cả khi truy vấn.

Answer 3

Miễn là F # không phân biệt giữa mã thuần túy và không tinh khiết, tôi nghi ngờ chúng ta sẽ thấy tối ưu hóa loại đó. Bạn có thể, tuy nhiên, làm cho currying rõ ràng.

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

isHtmlSet bây giờ sẽ gọi isInSet chỉ một lần để có được việc đóng cửa, đồng thời thực hiện ofList.

Answer 4

@ Câu trả lời của Kha được phát hiện. F # không thể viết lại

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

vào

// 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 

trừ khi nó biết rằng g không có tác dụng, và trong .NET Framework ngày hôm nay, nó thường là không thể suy luận về những ảnh hưởng của 99% của tất cả các biểu thức. Điều này có nghĩa là lập trình viên vẫn chịu trách nhiệm về thứ tự đánh giá mã hóa rõ ràng như trên.