- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我找到了一篇文章:
Solving the 0-1 knapsack problem using continuation-passing style with memoization in F#
关于在F#中实现的背包问题。当我学习这种语言时,我发现这真的很有趣,并尝试对其进行一些研究。这是我编写的代码:
open System
open System.IO
open System.Collections.Generic
let parseToTuple (line : string) =
let parsedLine = line.Split(' ') |> Array.filter(not << String.IsNullOrWhiteSpace) |> Array.map Int32.Parse
(parsedLine.[0], parsedLine.[1])
let memoize f =
let cache = Dictionary<_, _>()
fun x ->
if cache.ContainsKey(x)
then cache.[x]
else
let res = f x
cache.[x] <- res
res
type Item =
{
Value : int
Size : int
}
type ContinuationBuilder() =
member b.Bind(x, f) = fun k -> x (fun x -> f x k)
member b.Return x = fun k -> k x
member b.ReturnFrom x = x
let cont = ContinuationBuilder()
let set1 =
[
(4, 11)
(8, 4)
(10, 5)
(15, 8)
(4, 3)
]
let set2 =
[
(50, 341045); (1906, 4912); (41516, 99732); (23527, 56554); (559, 1818); (45136, 108372); (2625, 6750); (492, 1484)
(1086, 3072); (5516, 13532); (4875, 12050); (7570, 18440); (4436, 10972); (620, 1940); (50897, 122094); (2129, 5558)
(4265, 10630); (706, 2112); (2721, 6942); (16494, 39888); (29688, 71276); (3383, 8466); (2181, 5662); (96601, 231302)
(1795, 4690); (7512, 18324); (1242, 3384); (2889, 7278); (2133, 5566); (103, 706); (4446, 10992); (11326, 27552)
(3024, 7548); (217, 934); (13269, 32038); (281, 1062); (77174, 184848); (952, 2604); (15572, 37644); (566, 1832)
(4103, 10306); (313, 1126); (14393, 34886); (1313, 3526); (348, 1196); (419, 1338); (246, 992); (445, 1390)
(23552, 56804); (23552, 56804); (67, 634)
]
[<EntryPoint>]
let main args =
// prepare list of items from a file args.[0]
let header, items = set1
|> function
| h::t -> h, t
| _ -> raise (Exception("Wrong data format"))
let N, K = header
printfn "N = %d, K = %d" N K
let items = List.map (fun x -> {Value = fst x ; Size = snd x}) items |> Array.ofList
let rec combinations =
let innerSolver key =
cont
{
match key with
| (i, k) when i = 0 || k = 0 -> return 0
| (i, k) when items.[i-1].Size > k -> return! combinations (i-1, k)
| (i, k) -> let item = items.[i-1]
let! v1 = combinations (i-1, k)
let! beforeItem = combinations (i-1, k-item.Size)
let v2 = beforeItem + item.Value
return max v1 v2
}
memoize innerSolver
let res = combinations (N, K) id
printfn "%d" res
0
最佳答案
通过在FSI中运行此代码:
open System
open System.Diagnostics
open System.Collections.Generic
let time f =
System.GC.Collect()
let sw = Stopwatch.StartNew()
let r = f()
sw.Stop()
printfn "Took: %f" sw.Elapsed.TotalMilliseconds
r
let mutable cacheHits = 0
let mutable cacheMisses = 0
let memoize f =
let cache = Dictionary<_, _>()
fun x ->
match cache.TryGetValue(x) with
| (true, v) ->
cacheHits <- cacheHits + 1
//printfn "Hit for %A - Result is %A" x v
v
| _ ->
cacheMisses <- cacheMisses + 1
//printfn "Miss for %A" x
let res = f x
cache.[x] <- res
res
type Item = { Value : int; Size : int }
type ContinuationBuilder() =
member b.Bind(x, f) = fun k -> x (fun x -> f x k)
member b.Return x = fun k -> k x
member b.ReturnFrom x = x
let cont = ContinuationBuilder()
let genItems n =
[| for i = 1 to n do
let size = i % 5
let value = (size * i)
yield { Value = value; Size = size }
|]
let N, K = (80, 400)
printfn "N = %d, K = %d" N K
let items = genItems N
//let rec combinations_cont =
// memoize (
// fun key ->
// cont {
// match key with
// | (0, _) | (_, 0) -> return 0
// | (i, k) when items.[i-1].Size > k -> return! combinations_cont (i - 1, k)
// | (i, k) -> let item = items.[i-1]
// let! v1 = combinations_cont (i-1, k)
// let! beforeItem = combinations_cont (i-1, k - item.Size)
// let v2 = beforeItem + item.Value
// return max v1 v2
// }
// )
//
//
//cacheHits <- 0
//cacheMisses <- 0
//let res = time(fun () -> combinations_cont (N, K) id)
//printfn "Answer: %d" res
//printfn "Memo hits: %d" cacheHits
//printfn "Memo misses: %d" cacheMisses
//printfn ""
let rec combinations_plain =
memoize (
fun key ->
match key with
| (i, k) when i = 0 || k = 0 -> 0
| (i, k) when items.[i-1].Size > k -> combinations_plain (i-1, k)
| (i, k) -> let item = items.[i-1]
let v1 = combinations_plain (i-1, k)
let beforeItem = combinations_plain (i-1, k-item.Size)
let v2 = beforeItem + item.Value
max v1 v2
)
cacheHits <- 0
cacheMisses <- 0
printfn "combinations_plain"
let res2 = time (fun () -> combinations_plain (N, K))
printfn "Answer: %d" res2
printfn "Memo hits: %d" cacheHits
printfn "Memo misses: %d" cacheMisses
printfn ""
let recursivelyMemoize f =
let cache = Dictionary<_, _>()
let rec memoizeAux x =
match cache.TryGetValue(x) with
| (true, v) ->
cacheHits <- cacheHits + 1
//printfn "Hit for %A - Result is %A" x v
v
| _ ->
cacheMisses <- cacheMisses + 1
//printfn "Miss for %A" x
let res = f memoizeAux x
cache.[x] <- res
res
memoizeAux
let combinations_plain2 =
let combinations_plain2Aux combinations_plain2Aux key =
match key with
| (i, k) when i = 0 || k = 0 -> 0
| (i, k) when items.[i-1].Size > k -> combinations_plain2Aux (i-1, k)
| (i, k) -> let item = items.[i-1]
let v1 = combinations_plain2Aux (i-1, k)
let beforeItem = combinations_plain2Aux (i-1, k-item.Size)
let v2 = beforeItem + item.Value
max v1 v2
let memoized = recursivelyMemoize combinations_plain2Aux
fun x -> memoized x
cacheHits <- 0
cacheMisses <- 0
printfn "combinations_plain2"
let res3 = time (fun () -> combinations_plain2 (N, K))
printfn "Answer: %d" res3
printfn "Memo hits: %d" cacheHits
printfn "Memo misses: %d" cacheMisses
printfn ""
let recursivelyMemoizeCont f =
let cache = Dictionary HashIdentity.Structural
let rec memoizeAux x k =
match cache.TryGetValue(x) with
| (true, v) ->
cacheHits <- cacheHits + 1
//printfn "Hit for %A - Result is %A" x v
k v
| _ ->
cacheMisses <- cacheMisses + 1
//printfn "Miss for %A" x
f memoizeAux x (fun y ->
cache.[x] <- y
k y)
memoizeAux
let combinations_cont2 =
let combinations_cont2Aux combinations_cont2Aux key =
cont {
match key with
| (0, _) | (_, 0) -> return 0
| (i, k) when items.[i-1].Size > k -> return! combinations_cont2Aux (i - 1, k)
| (i, k) -> let item = items.[i-1]
let! v1 = combinations_cont2Aux (i-1, k)
let! beforeItem = combinations_cont2Aux (i-1, k - item.Size)
let v2 = beforeItem + item.Value
return max v1 v2
}
let memoized = recursivelyMemoizeCont combinations_cont2Aux
fun x -> memoized x id
cacheHits <- 0
cacheMisses <- 0
printfn "combinations_cont2"
let res4 = time (fun () -> combinations_cont2 (N, K))
printfn "Answer: %d" res4
printfn "Memo hits: %d" cacheHits
printfn "Memo misses: %d" cacheMisses
printfn ""
N = 80, K = 400
combinations_plain
Took: 7.191000
Answer: 6480
Memo hits: 6231
Memo misses: 6552
combinations_plain2
Took: 6.310800
Answer: 6480
Memo hits: 6231
Memo misses: 6552
combinations_cont2
Took: 17.021200
Answer: 6480
Memo hits: 6231
Memo misses: 6552
combinations_plain
来自latkin的答案。 combinations_plain2
显式公开递归备注步骤。 combinations_cont2
将递归内存功能改编为内存连续结果的功能。 combinations_cont2
的工作原理是在将延续结果传递给实际延续之前将其截获。随后在同一键上的调用提供了一个延续,并且这个延续被提供给我们最初截获的答案。 关于performance - 在F#: performance中解决背包问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17445855/
我有以下代码: interface F { (): string; a(): number; } function f() { return '3'; } f['a'] = f
比如我有一个 vector vector > v={{true,1},{true,2},{false,3},{false,4},{false,5},{true,6},{false,7},{true,8
我需要编写一个要在 GHCi 上运行的模块,并将函数组合为相同的函数。这个(经典的fog(x) = f(g(x)))运行: (.) f g = (\x -> f (g x)). 当我尝试这样写时出现问
动态规划这里有一个问题 大写字母AZ对应于整数[-13,12],因此一个字符串对应于一整列。我们将对应的整列的总和称为字符串的特征值。例如:字符串ACM对应的总体列为{-13,-11,-1},则ACM
我想知道为什么 F-Sharp 不支持无穷大。 这适用于 Ruby(但不适用于 f#): let numbers n = [1 .. 1/0] |> Seq.take(n) -> System.Div
如何从已编译的 F# 程序中的字符串执行 F# 代码? 最佳答案 这是一个小脚本,它使用 FSharp CodeDom 将字符串编译为程序集,并将其动态加载到脚本 session 中。 它使用类型扩展
有什么方法可以在 F# List 和 F# Tuple 之间转换? 例如: [1;2;3] -> (1,2,3) (1,2,3,4) -> [1;2;3;4] 我需要两个函数来做到这一点: le
我想将一个或多个 .fsx 文件加载到 F# 交互中,并将 .fsx 文件中定义的所有函数都包含在作用域中,以便我可以直接使用控制台中的功能。 #load 指令执行指定的 .fsx 文件,但随后我无法
我正在尝试像 this page 中那样编写 F 代数.不同之处在于,不是用元组组合,而是像这样: type FAlgebra[F[_], A] = F[A] => A def algebraZip[
给定一个 F# 记录: type R = { X : string ; Y : string } 和两个对象: let a = { X = null ; Y = "##" } let b = {
所以我们有一组文件名\url,如file、folder/file、folder/file2、folder/file3、folder/folder2/fileN等。我们得到一个字符串,如文件夹/。我们想
假设我有一个字符串“COLIN”。 这个字符串的数值是: 3 + 15 + 12 + 9 + 14 = 53. 所以 A = 1, B = 2, C = 3, and so on. 为此,我什至不知道
在 C# 中,我有以下代码来创建一个对象实例。 var myObject = new MyClass("paramvalue") { Property1 = "value1" Proper
即,标准库中有这样的函数吗? let ret x _ = x 为了保持代码可读性,我想尽量减少自制基本构建功能构建块的数量,并使用现有的东西。 最佳答案 不。你可能想看看 FSharpX。 关于f#
目前,我有一个函数可以将列表中每个列表的第一个元素( float )返回到单独的列表。 let firstElements list = match list with | head:
我刚刚解决了problem23在 Project Euler 中,我需要一个 set 来存储所有丰富的数字。 F# 有一个不可变集合,我可以使用 Set.empty.Add(i) 创建一个包含数字 i
F#语言具有计算自然对数的函数log和计算以10为底的对数的log10。 在F#中以2为底的对数的最佳计算方法是什么? 最佳答案 您可以简单地使用以下事实:“ b的a对数” = ln(b)/ ln(a
动机 我有一个长时间运行的 bool 函数,它应该在数组中执行,如果数组中的元素满足条件,我想立即返回。我想并行搜索并在第一个完整线程返回正确答案时终止其他线程。 问题 在 F# 中实现并行存在函数的
我最近完成了一个生成字符串列表的项目,我想知道执行此操作的最佳方法。 字符串生成是上下文敏感的,以确定它是否可以接受(这是游戏中的一系列游戏,所以你必须知道最后一次游戏是什么) 我这样做的方法是使用一
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the he
我是一名优秀的程序员,十分优秀!