Реализация быстрого CustomEquality и CustomComparison для различаемых типов объединения

Question

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

Обратите внимание на следующий фрагмент кода:

[<CustomEquality; CustomComparison>]
type Coord = 
| Spot of AssetKey
| Vol of AssetKey * DateTime option 
| Rate of Currency                                   
.....

    member this.sortKey = 
        match this with
        | Spot(key)                               -> (0 , key.toString)
        | Vol(key)                                -> (1 , key.toString)
        | Vol(key, Some(t))                       -> (2 , key.toString + t.ToShortString())
        | Rate(cur)                               -> (3 , cur.toString)
        ......

    interface IComparable with 
        member this.CompareTo(obj) = 
            match obj with 
            | :? Coord as other -> compare this.sortKey other.sortKey
            | _ -> invalidArg "obj" "not a Coord type"

    override this.Equals(obj) = 
            match obj with 
            | :? Coord as other -> this.sortKey = other.sortKey
            | _ -> false

    override this.GetHashCode() = this.sortKey.GetHashCode()

Мне нужно установить определенный порядок сортировки.Например, Spot

AssetKey - снова очень похожий тип различаемого объединения:

[<StructuralEqualityAttribute; StructuralComparisonAttribute>]
type AssetKey =
| Equity of string
| EquityIndex of string
.....

Так что все это работает хорошо, но медленно.Насколько я понимаю, если вызывается функция sortKey, весь ключ создается снова, в частности, функции toString вызываются снова.

Одним очевидным улучшением было бы добавление слоя кэширования, которыйскорее взлом, чем решение.

Дальнейшая оптимизация будет заключаться в использовании хеш-ключа в строках.Но здесь я снова должен добавить кеширование, потому что мне нужно кешировать ключ хеша, и я не хочу пересчитывать его заново.

Оптимизация производительности была бы проще, если бы я использовал структуру или класс, но тогда я потерял бы гибкость сопоставления с образцом, как, например,

match c with 
| Coord.Vol(ak, _) when ak = assetKey -> true
| _ -> false

Каким был бы альтернативный подход, которыйхорошо работает?В некоторые из моих временных интервалов 30% и более от общей производительности теряется в функции sortKey.

Спасибо за любые предложения и улучшения.

Answer 1

Простая оптимизация
Одна из основных оптимизаций, которую вы могли бы легко сделать, - это избегать вызова toString, когда вы можете принять решение, основываясь только на типе Coord. Вместо построения sortKey вы можете написать:

// Separate functions that return tag and key, so that we don't
// have to call 'toString' if we can decide based just on the Tag
member this.Tag = 
    match this with 
    | Spot _ -> 0 | Vol(_, None) -> 1 
    | Vol _ -> 2 | Rate _ -> 3
member this.Key = 
    match this with 
    | Spot(key) | Vol(key, None) -> key.toString | Rate cur -> cur.toString
    | Vol(key, Some t) -> key.toString + t.ToShortString())  

interface IComparable with  
    member this.CompareTo(obj) =  
        match obj with  
        | :? Coord as other -> 
            let c = compare this.Tag other.Tag
            // Try comparing based on the tag first - if the tags 
            // are the same, then get Key and compare based on the key
            if c <> 0 then c else compare this.Key other.Key
        | _ -> invalidArg "obj" "not a Coord type" 

Если вы хотите кэшировать результат toString, вам нужно будет использовать некоторую структуру, которая позволяет хранить локальные поля. Я бы, вероятно, использовал тип объекта (представленный в виде класса или простой структуры).

Упаковка типа
В этом случае вы все равно можете получить хорошее сопоставление с шаблоном, используя активные шаблоны, но это требует определения активного шаблона для каждого класса (что, вероятно, не так уж и плохо). Вот пример:

// This type will not be used directly - it is an internal implementation
// hidden from the users that will be accessed using active patterns
[<RequiresQualifiedAccess>]
type AssetKeyInternal =       
  | Equity of string       
  | EquityIndex of string  
  override x.ToString() = ...

// Public type with active patterns for pattern matching
type AssetKey(key:AssteKeyInternal) = 
  let str = lazy key.ToString() // Lazily cached string
  member x.Key = str.Value      // Evaluated when accessed for the first time

  member x.Value = key // Returns the internal representation

// Define active patterns working over AssetKey type
let (|Equity|EquityIndex|) (k:AssetKey) =
  match k.Value with
  | AssetKeyInternal.Equity(e) -> Equity(e)
  | AssetKeyInternal.EquityIndex(e) -> EquityIndex(e)

Учитывая значение типа AssetKey, теперь вы можете написать k.Key, чтобы получить кэшированное строковое представление, и вы можете сопоставить шаблон с ним, используя активные шаблоны:

match k with 
| Equity k -> ...
| EquityIndex i -> ...

Answer 2

Вы можете подумать о том, чтобы сделать что-то вроде

type CoordRepr =
| Spot of AssetKey 
| Vol of AssetKey * DateTime option  
| Rate of Currency              

let sortKey = function
| Spot(key) -> 1,key.ToString()
| Vol(key,None) -> 2,key.ToString()
| Vol(key,Some(v)) -> 2,key.ToString() + v.ToShortDateString()
| Rate(key) -> 3,key.ToString()

type Coord(repr) =
    let sortKey = sortKey repr
    member __.Repr = repr
    member __.SortKey = sortKey
    override __.Equals(that) =
        match that with
        | :? Coord as c -> sortKey = c.SortKey
        | _ -> false
    override __.GetHashCode() = sortKey.GetHashCode()
    interface System.IComparable with
        member __.CompareTo(that) =
            match that with
            | :? Coord as c -> compare sortKey c.SortKey
            | _ -> failwith "invalidArg"

let Spot k = Coord(Spot k)
let Vol(k,v) = Coord(Vol(k,v))
let Rate(k) = Coord(Rate(k))

let (|Spot|Vol|Rate|) (c:Coord) =
    match c.Repr with
    | Spot k -> Spot k
    | Vol(k,v) -> Vol(k,v)
    | Rate k -> Rate k

и затем использовать файл подписи, чтобы скрыть конструктор CoordRepr, Coord, sortKey и т. Д.