Hoàn thành, thực hiện mô-đun NumericLiteral đầy đủ, hiệu quả

Question

Xây dựng trên một cuộc thảo luận trong this question, bất kỳ ai có thể cung cấp mã hoặc liên kết đến mã, hiển thị việc triển khai hoàn chỉnh mô-đun NumericLiteralX (chẳng hạn như this one)? Tôi đặc biệt quan tâm đến việc triển khai hiệu quả FromInt32/64 cho mô-đun NumericLiteralX tạo điều kiện thuận lợi cho các hoạt động số chung. Dưới đây là triển khai có lẽ không hiệu quả được lấy từ câu hỏi được đề cập ở trên:

module NumericLiteralG = 
    let inline FromZero() = LanguagePrimitives.GenericZero 
    let inline FromOne() = LanguagePrimitives.GenericOne 
    let inline FromInt32 (n:int) = 
     let one : ^a = FromOne() 
     let zero : ^a = FromZero() 
     let n_incr = if n > 0 then 1 else -1 
     let g_incr = if n > 0 then one else (zero - one) 
     let rec loop i g = 
      if i = n then g 
      else loop (i + n_incr) (g + g_incr) 
     loop 0 zero 

Làm cách nào để cải thiện và hoàn thành?

Answer 1

Tôi sẽ chỉ địa chỉ FromInt32. Trong một thế giới lý tưởng, chúng ta có thể định nghĩa nó đơn giản như

let inline FromInt32 i = 
    ((^t or int) : (static member op_Explicit : int -> ^t) i) 

mà sẽ sử dụng hạn chế tĩnh để đảm bảo rằng chúng ta có thể nội tuyến một chuyển đổi rõ ràng từ int. Thật không may, có hai vấn đề với điều này. Đầu tiên là cú pháp không hợp lệ - bạn không thể có một loại cụ thể (như int) trong phần "tĩnh-typars" của một ràng buộc thành viên. Chúng tôi có thể giải quyết vấn đề này bằng cách xác định chức năng trợ giúp

let inline cvt i = ((^t or ^u) : (static member op_Explicit : ^u -> ^t) i) 
let inline FromInt32 (i:int) = cvt i 

Vì cả hai chức năng này được gạch chân, điều này không kém hiệu quả so với lần thử đầu tiên, nó chỉ là từ ngữ.

Đây là nơi chúng tôi chạy vào vấn đề thứ hai: điều này sẽ làm việc cho các định nghĩa op_Explicit thực (hoặc op_Implicit, được xử lý đặc biệt bởi trình biên dịch sao cho nó được gộp bởi op_Explicit). Vì vậy, (10G : bigint) sẽ được inline như thể bạn đã viết System.Numerics.BigInt.op_Implicit 10, hiệu quả như chúng tôi có thể hy vọng. Tuy nhiên, F # cũng mô phỏng op_Explicit cho nhiều loại nguyên thủy (ví dụ như cho các chuyển đổi từ int để float, byte, vv), và kể từ khi định nghĩa của FromInt32 dựa vào sự tồn tại của các thành viên đó sẽ thất bại trong thời gian chạy (có nghĩa là, (10G : float) và thậm chí (10G : int) sẽ biên dịch nhưng sẽ ném một ngoại lệ khi được thực hiện). Lý tưởng nhất là một phiên bản tương lai của F # có thể cho phép điều này hoạt động như hiện tại, nhưng tính đến thời điểm F # 2.0, chúng ta sẽ cần phải giải quyết vấn đề này. Sẽ rất tuyệt nếu chúng ta có thể sử dụng cách tiếp cận tương tự như cách thư viện lõi F # xử lý loại vấn đề này, điều này sẽ yêu cầu vỏ bọc đặc biệt tất cả các toán tử ngụ ý nhưng sẽ dẫn đến mọi thứ được hiệu quả hoàn hảo:

let inline FromInt32 (i : int) : ^t = 
    cvt i 
    when ^t : int = int i 
    when ^t : float = float i 
    when ^t : byte = byte i 
    ... 

Tuy nhiên, trình biên dịch F # từ chối điều này với thông báo "Static optimization conditionals are only for use within the F# library" (và biên dịch với cờ --compiling-fslib bí mật chỉ làm mọi thứ tồi tệ hơn :)).

Thay vào đó, chúng ta cần phải sử dụng thêm một vài lớp khác nhau để đạt được điều gì đó tương tự khi chạy. Đầu tiên, chúng ta sẽ tạo một ánh xạ thời gian chạy của các loại chức năng chuyển đổi bằng cách sử dụng một thành viên tĩnh của một kiểu generic:

type IntConverterDynamicImplTable<'t>() = 
    static let result : int -> 't = 
    let ty = typeof< 't> //' 
    if ty.Equals(typeof<sbyte>)  then sbyte  |> box |> unbox 
    elif ty.Equals(typeof<int16>)  then int16  |> box |> unbox 
    elif ty.Equals(typeof<int32>)  then int  |> box |> unbox 
    elif ty.Equals(typeof<int64>)  then int64  |> box |> unbox 
    elif ty.Equals(typeof<nativeint>) then nativeint |> box |> unbox 
    elif ty.Equals(typeof<byte>)  then byte  |> box |> unbox 
    elif ty.Equals(typeof<uint16>)  then uint16  |> box |> unbox 
    elif ty.Equals(typeof<char>)  then char  |> box |> unbox 
    elif ty.Equals(typeof<uint32>)  then uint32  |> box |> unbox 
    elif ty.Equals(typeof<uint64>)  then uint64  |> box |> unbox 
    elif ty.Equals(typeof<unativeint>) then unativeint |> box |> unbox 
    elif ty.Equals(typeof<decimal>) then decimal |> box |> unbox 
    elif ty.Equals(typeof<float>)  then float  |> box |> unbox 
    elif ty.Equals(typeof<float32>) then float32 |> box |> unbox 
    else 
     let m = 
     try ty.GetMethod("op_Implicit", [| typeof<int> |]) 
     with _ -> ty.GetMethod("op_Explicit", [| typeof<int> |]) 
     let del = 
     System.Delegate.CreateDelegate(typeof<System.Func<int,'t>>, m) 
     :?> System.Func<int,'t> 
     del.Invoke |> box |> unbox 
    static member Result = result 

này tương tự như những gì chúng tôi đang cố gắng để đạt được với các điều kiện tối ưu hóa tĩnh trong nỗ lực trước , nhưng nó được hoãn lại cho thời gian chạy thay vì mọi thứ được đánh giá tại thời gian biên dịch.Bây giờ chúng ta chỉ cần xác định một vài giá trị sử dụng loại này:

let inline constrain< ^t, ^u when (^t or ^u) : (static member op_Explicit : ^t -> ^u)>() =() 
let inline FromInt32 i : ^t = 
    constrain<int, ^t>() 
    IntConverterDynamicImplTable.Result i 

Ở đây, constrain hàm được chỉ được sử dụng để đảm bảo rằng FromInt32 chỉ có thể được áp dụng cho các loại, nơi có một chuyển đổi rõ ràng từ int (hoặc một mô phỏng bởi trình biên dịch). Cuộc gọi thực tế tới constrain() trong phạm vi FromInt32 sẽ được tối ưu hóa trong khi biên dịch.

Với phương pháp này, (10G : bigint) sẽ được biên soạn một cái gì đó giống như IntConverterDynamicImplTable<bigint>.Result 10, và IntConverterDynamicTable<bigint>.Result sẽ có giá trị tương đương với (System.Func<int,bigint>(bigint.op_Implicit)).Invoke (nhưng lưu trữ, do đó các đại biểu chỉ được tạo ra một lần). Tương tự, (10G : int64) sẽ biên dịch thành IntConverterDynamicImplTable<int64>.Result 10 và IntConverterDynamicTable<int64>.Result sẽ có giá trị tương đương với hàm chuyển đổi (int64 : int -> int64), vì vậy có tổng chi phí của một số cuộc gọi phương thức nhưng hiệu suất tổng thể phải rất tốt.

EDIT

Tuy nhiên, nếu bạn chỉ tìm kiếm cái gì hiệu quả hơn so với một hiện thực ngây thơ của FromInt32 và FromInt64 dành thời gian O (n), đây là một phiên bản mà vẫn còn tương đối đơn giản và chỉ mất O (nhật ký n) thời gian:

module SymmetricOps = 
    let inline (~-) (x:'a) : 'a = -x 
    let inline (+) (x:'a) (y:'a) : 'a = x + y 
    let inline (-) (x:'a) (y:'a) : 'a = x - y 
    let inline (*) (x:'a) (y:'a) : 'a = x * y 
    let inline (/) (x:'a) (y:'a) : 'a = x/y 
    let inline (%) (x:'a) (y:'a) : 'a = x % y 

module NumericLiteralG = 
    open SymmetricOps 
    let inline FromOne() = LanguagePrimitives.GenericOne 
    let inline FromZero() = LanguagePrimitives.GenericZero 
    let rec compute zero one two (/) (%) Two (+) (-) (*) pow2 rest n = 
    if n = zero then rest 
    else 
     let rest' = 
     let nmod2 = n % two 
     if nmod2 = zero then rest 
     elif nmod2 = one then rest + pow2 
     else rest - pow2 
     compute zero one two (/) (%) Two (+) (-) (*) (Two * pow2) rest' (n/two) 
    let inline FromInt32 i = compute 0 1 2 (/) (%) (FromOne() + FromOne()) (+) (-) (*) (FromOne()) (FromZero()) i 
    let inline FromInt64 i = compute 0L 1L 2L (/) (%) (FromOne() + FromOne()) (+) (-) (*) (FromOne()) (FromZero()) i