Skip to content

Instantly share code, notes, and snippets.

@fjod
Last active May 28, 2021 05:26
Show Gist options
  • Save fjod/abd3a94d06b078e101dfd818c5baace2 to your computer and use it in GitHub Desktop.
Save fjod/abd3a94d06b078e101dfd818c5baace2 to your computer and use it in GitHub Desktop.
F# reverse tree using tail-call recursion (code can be shortened)
open BenchmarkDotNet.Attributes
open BenchmarkDotNet.Running
type Tree<'a when 'a : comparison> =
| Node of 'a * Tree<'a> * Tree<'a>
| Empty
let rec insert newValue (tree : Tree<'a>) =
match tree with
| Empty -> Node (newValue, Empty, Empty)
| Node (value, left, right) when newValue < value ->
let left' = insert newValue left
Node (value, left', right)
| Node (value, left, right) when newValue > value ->
let right' = insert newValue right
Node (value, left, right')
| _ -> tree
let fillTree (t:Tree< 'a >) (collection: 'a seq) =
let mutable temp = t
let adder (ve:'a) =
temp <- insert ve temp
()
Seq.iter adder collection
temp
let swapTail (t:Tree<'a>) : Tree<'a> =
let rec inner (t:Tree<'a>) (f : Tree<'a> -> Tree<'a>) : Tree<'a> =
match t with
| Node (v,Empty, right) -> f (Node (v, right, Empty))
| Node (v, left, Empty) -> f(Node (v, Empty, left))
| Empty -> f Empty
| Node (v,left,right) -> inner left (function v2 -> inner right (function v3 -> f(Node(v,v3,v2))))
inner t (function v -> v)
let rec swap = function
| Empty -> Empty
| Node (value, left, right) ->
Node(value, swap right, swap left)
[<MemoryDiagnoser>]
//[<SimpleJob(1, 3, 3)>]
type Benchmarks () =
let mutable tree = Node(1,Empty,Empty)
[<Params(1000,10000)>]
member val public amount = 0 with get, set
[<IterationSetup>]
member self.IterationSetup() =
tree <- Node(1,Empty,Empty)
let nodeStart = Node(0,Empty,Empty)
let range = seq {1..self.amount}
tree <- fillTree nodeStart range
[<Benchmark>]
member this.tailCall () =
swapTail tree |> ignore
[<Benchmark>]
member this.swap () =
swap tree |> ignore
[<EntryPoint>]
let main argv =
BenchmarkRunner.Run<Benchmarks>() |> printf "%A"
0
@fjod
Copy link
Author

fjod commented May 26, 2021

Ayrat Hudaygulov, [25.05.21 16:18]
постигание этого фокуса откроет чакры и третий глаз.

@fjod
Copy link
Author

fjod commented May 28, 2021

Method amount Mean Error StdDev Median Gen 0 Gen 1 Gen 2 Allocated
tailCall 1000 2.697 us 0.6335 us 1.808 us 1.850 us - - - 40 B
swap 1000 24.345 us 2.5913 us 7.393 us 21.900 us - - - 40040 B
tailCall 10000 4.069 us 0.4503 us 1.186 us 3.950 us - - - 40 B
swap 10000 470.323 us 41.1906 us 121.451 us 475.250 us - - - 400040 B

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment