Повышение производительности вставки карт F # - PullRequest
Новая
       77

Повышение производительности вставки карт F #

5 голосов
/ 08 мая 2020

Я сейчас делаю несколько тестов на картах F # и словарях C#. Я понимаю, что с точки зрения реализации они совершенно разные, но они одинаково используются для своих соответствующих языков.

Я разработал простой тест для проверки времени вставки из-за неизменности карты F #, поэтому она должна создавать совершенно новую карту для каждой вставки. Мне было интересно, насколько это удачно.

Тест выглядит следующим образом: 

 //F# 
 module Test = 
    let testMapInsert () = 
        let sw = Stopwatch()
        let rec fillMap endIdx curr map =
            if curr = endIdx then 
                map 
            else 
                fillMap endIdx (curr + 1) (map |> Map.add curr curr)
        sw.Start ()
        let q = fillMap 100000000 Map.empty
        sw.Stop ()
        printfn "%A" sw.ElapsedMilliseconds

 //C#
 class Program
    {
        static void Test(int x) {
            var d = new Dictionary<int,int>();
            for (int i = 0; i < x; i++) {
                d.Add(i,i);
            }
        }
        static void Main(string[] args) {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            Test(10000000);
            sw.Stop();
            System.Console.WriteLine(sw.ElapsedMilliseconds);
            //FSHARP.Test.testMapInsert(); f# function called in c#.

        }
    }

Выполнение 10 миллионов вставок элементов с этим дает следующее время, измеренное в мс: 

C#: 332

F#: 13605

Я подумал, что словарь C# будет немного быстрее, но это большая разница.

Есть ли способ ускорить словарь F # для такого рода сценариев использования? Или это просто так, и карта F # имеет компромисс с производительностью в этих ситуациях для обеспечения безопасности потоков?

1 Ответ

5 голосов
/ 09 мая 2020

Как упоминалось в комментариях, разница основана не на различии между C# и F #, а на различии между неизменяемой древовидной картой и изменяемым словарем на основе хеш-таблицы.

Использование #time, я получаю следующую производительность в F # interactive: 

#time 
// Immutable tree-based F# map (~14 sec)
let mutable map = Map.empty
for i in 0 .. 10000000 do
  map <- Map.add i i map

// Mutable hashtable-based .NET dictionary (~0.3 sec)
let dict = System.Collections.Generic.Dictionary<_, _>()
for i in 0 .. 10000000 do
  dict.Add(i, i)

Интересный вопрос - можно ли сделать неизменяемую карту F # быстрее? В принципе, вы можете построить карту быстрее, если знаете, что работаете с уже отсортированным массивом. Карта F # не имеет операции, которая позволила бы вам это сделать, но ее можно было бы добавить.

Когда я определяю свой собственный тип карты, который разделяет межсетевую структуру с картой F #: 

type MapTree<'Key, 'Value when 'Key : comparison > = 
  | MapEmpty 
  | MapOne of 'Key * 'Value
  | MapNode of 'Key * 'Value * MapTree<'Key, 'Value> *  MapTree<'Key, 'Value> * int

Затем я могу определить операцию ofSortedArray: 

let height = function
  | MapEmpty -> 0
  | MapOne _ -> 1
  | MapNode(_, _, _, _, h) -> h

let rec ofSortedArray (data:_[]) i j = 
  if i = j then MapOne(data.[i])
  elif i > j then MapEmpty 
  else 
    let m = i + (j - i) / 2
    let l, r = ofSortedArray data i (m - 1), ofSortedArray data (m + 1) j
    let k, v = data.[m]
    MapNode(k, v, l, r, 1 + (max (height l) (height r)))

Это все еще далеко не так эффективно, как изменяемая хеш-таблица, но я получаю следующее: 

// Immutable tree-based F# map, using sorted array 
let arr = [| for i in 0 .. 10000000 -> i, i |] // ~1 sec
let map = ofSortedArray arr 0 10000000         // ~3 sec

Если вы на самом деле хотел использовать это, вам понадобится ваша собственная версия карты F # - или вы могли бы отправить запрос на перенос в основные библиотеки F #, добавив поддержку чего-то вроде этого!

...