Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"deletable": true,
"editable": true
},
"source": [
"Use a hacked together benchmarking function using System.Diagnostics.Stopwatch to measure the speed of various algorithms to produce combinations of lists (from http://stackoverflow.com/questions/4528355/measure-time-of-execution-in-f) \n"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [],
"source": [
"let bench note f =\n",
" let sw = System.Diagnostics.Stopwatch.StartNew()\n",
" let res = f 2 [1..1000]\n",
" sw.Stop()\n",
" printfn \"%s: %f ms\" note sw.Elapsed.TotalMilliseconds\n",
" res"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"collapsed": true,
"deletable": true,
"editable": true
},
"outputs": [],
"source": [
"// by user \"kvb\"\n",
"let rec kvb_comb n l =\n",
" match (n,l) with\n",
" | (0,_) -> [[]]\n",
" | (_,[]) -> []\n",
" | (n,x::xs) ->\n",
" let useX = List.map (fun l -> x::l) (comb_kvb (n-1) xs)\n",
" let noX = kvb_comb n xs\n",
" useX @ noX\n",
"\n",
"// by user \"The_Ghost\"\n",
"let rec ghost_comb n l = \n",
" match n, l with\n",
" | 0, _ -> [[]]\n",
" | _, [] -> []\n",
" | k, (x::xs) -> List.map ((@) [x]) (ghost_comb (k-1) xs) @ ghost_comb k xs\n",
"\n",
"// by user \"Ray\" (first attempt)\n",
"let ray_1_comb _ lst =\n",
" let combHelper el lst =\n",
" lst |> List.map (fun lstEl -> el::[lstEl])\n",
" let filterOut el lst =\n",
" lst |> List.filter (fun lstEl -> lstEl <> el)\n",
" lst |> List.map (fun lstEl -> combHelper lstEl (filterOut lstEl lst)) |> List.concat\n",
"\n",
"// by user \"Ray\" (second attempt)\n",
"let rec ray_2_comb n lst =\n",
" let rec findChoices = function\n",
" | h::t -> (h,t) :: [ for (x,l) in findChoices t -> (x,l) ]\n",
" | [] -> []\n",
" [ if n=0 then yield [] else\n",
" for (e,r) in findChoices lst do\n",
" for o in ray_2_comb (n-1) r do yield e::o ]\n",
"\n",
"// by user \"Bill Johnson\"\n",
"let bill_comb size aList = \n",
" let rec pairHeadAndTail acc bList = \n",
" match bList with\n",
" | [] -> acc\n",
" | x::xs -> pairHeadAndTail (List.Cons ((x,xs),acc)) xs\n",
" let remainderAfter = aList |> pairHeadAndTail [] |> Map.ofList\n",
" let rec comboIter n acc = \n",
" match n with\n",
" | 0 -> acc\n",
" | _ -> \n",
" acc\n",
" |> List.fold (fun acc alreadyChosenElems ->\n",
" match alreadyChosenElems with\n",
" | [] -> aList //Nothing chosen yet, therefore everything remains.\n",
" | lastChoice::_ -> remainderAfter.[lastChoice]\n",
" |> List.fold (fun acc elem ->\n",
" List.Cons (List.Cons (elem,alreadyChosenElems),acc)\n",
" ) acc\n",
" ) []\n",
" |> comboIter (n-1)\n",
" comboIter size [[]]\n",
"\n",
"// by user \"mitzsh\"\n",
"let mitzsh_comb (k : int) (xs : 'a list) : ('a list) seq =\n",
" let rec loop (k : int) (xs : 'a list) : ('a list) seq = seq {\n",
" match xs with\n",
" | [] -> ()\n",
" | xs when k = 1 -> for x in xs do yield [x]\n",
" | x::xs ->\n",
" let k' = k - 1\n",
" for ys in loop k' xs do\n",
" yield x :: ys\n",
" yield! loop k xs }\n",
" loop k xs\n",
" |> Seq.filter (List.length >> (=)k)\n"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": false,
"deletable": true,
"editable": true
},
"outputs": [
{
"data": {
"text/plain": [
"kvb_comb: 715.447900 ms\n",
"ghost_comb: 803.832400 ms\n",
"ray_1_comb: 905.011200 ms\n",
"ray_2_comb: 61125.410800 ms\n",
"bill_comb: 304.491400 ms\n",
"mitzsh_comb: 0.656500 ms\n"
]
},
"metadata": {},
"output_type": "display_data"
},
{
"name": "stderr",
"output_type": "stream",
"text": []
}
],
"source": [
"// executing the test\n",
"let kvb_res = bench \"kvb_comb\" kvb_comb\n",
"let ghost = bench \"ghost_comb\" ghost_comb\n",
"let ray_1 = bench \"ray_1_comb\" ray_1_comb\n",
"let ray_2 = bench \"ray_2_comb\" ray_2_comb\n",
"let bill_res = bench \"bill_comb\" bill_comb\n",
"let mitzsh_res = bench \"mitzsh_comb\" mitzsh_comb"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "F#",
"language": "fsharp",
"name": "ifsharp"
},
"language": "fsharp",
"language_info": {
"codemirror_mode": "",
"file_extension": ".fs",
"mimetype": "text/x-fsharp",
"name": "fsharp",
"nbconvert_exporter": "",
"pygments_lexer": "",
"version": "4.3.1.0"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.