F#我应该如何考虑在序列中划分项目？

Question

F#我应该如何考虑在序列中划分项目？

为新秀问题道歉.我试图将我的心理范式从程序性转变为功能性.

例如,假设我有一个我要打印的名称列表,如"John,Paul,George和Ringo".但是这段代码不满足:

let names = [ "John"; "Paul"; "George"; "Ringo" ]
names |> Seq.iter (fun s -> printf "%s, " s)

Run Code Online (Sandbox Code Playgroud)

我的程序本能是寻找一种方法来将谓词暗示为lambda,以便它可以在","或","和"."之间分支,这取决于我们在迭代序列的位置.我认为这是错的,但我感觉周围的事情是正确的.

将序列分成几部分会更好吗？

在这种情况下,似乎我们希望将序列拆分成对应于不同定界符行为的部分.我们想在最后拆分它,所以我们不能使用Seq.但我们可以使用List.splitAt.

let start, ending = List.splitAt (names.Length - 1) names
let penultimate, last = List.splitAt 1 ending
start |> Seq.iter (fun s -> printf "%s, " s)
penultimate |> Seq.iter (fun s -> printf "%s, and " s)
last |> Seq.iter (fun s -> printf "%s. " s)

Run Code Online (Sandbox Code Playgroud)

这是一种正义的做法吗？有没有一个我忽略的更好的解决方案？我在思考正确的方向吗？

Answer 1

Car*_*Dev 8

我采取的解决这类问题的一般方法是将它们分成更小的部分并单独解决:

一个空列表[]导致""
一个元素["a"]导致"a."
两个元素[ "a"; "b" ]导致"a and b."
a :: rest导致更多元素(即)"a, " + takeCareOf rest,takeCareOf遵循上述规则.请注意,我们不需要知道完整列表的长度.

上面的配方直接转换为F#(和一般的函数式语言):

let rec commaAndDot' = function
| [] -> ()
| [ a ] -> printfn "%s." a
| a :: [ b ] -> printfn "%s and %s." a b
| a :: rest -> printf "%s, " a; commaAndDot' rest

Run Code Online (Sandbox Code Playgroud)

我们完成了吗？不,commaAndDot'违反了单一责任原则,因为该功能实现了我们的"业务逻辑" 并打印到控制台.我们来解决这个问题:

let rec commaAndDot'' = function
| [] -> ""
| [ a ] -> sprintf "%s." a
| a :: [ b ] -> sprintf "%s and %s." a b
| a :: rest -> sprintf "%s, " a + commaAndDot'' rest

Run Code Online (Sandbox Code Playgroud)

作为额外的好处,我们现在可以并行调用函数,输出不会再混淆了.

我们完成了吗？不,上面的函数不是尾递归的(我们需要commaAndDot'' rest在将它连接到当前结果之前进行计算)并且会为大型列表打击堆栈.解决此问题的标准方法是引入累加器acc:

let  commaAndDot''' words =
    let rec helper acc = function
    | [] -> acc
    | [ a ] -> sprintf "%s%s." acc a
    | a :: [ b ] -> sprintf "%s%s and %s." acc a b
    | a :: rest ->  helper (acc + sprintf "%s, " a) rest
    helper "" words

Run Code Online (Sandbox Code Playgroud)

我们完成了吗？不,commaAndDot'''为中间结果创建了很多字符串.由于F#不是纯语言,我们可以利用本地(私有,不可观察)突变来优化内存和速度:

let  commaAndDot words =
    let sb = System.Text.StringBuilder()
    let rec helper = function
    | [] -> sb
    | [ a ] -> sprintf "%s." a |> sb.Append
    | a :: [ b ] -> sprintf "%s and %s." a b |> sb.Append
    | a :: rest ->
        sprintf "%s, " a |> sb.Append |> ignore
        helper rest
    helper words |> string

Run Code Online (Sandbox Code Playgroud)

我们完成了吗？可能......至少这是我认为惯用F#并愉快地提交的东西.为了进一步优化(例如分别Append用逗号和点或改变模式的顺序),我首先在牺牲可读性之前编写微基准.

所有版本都生成相同的输出:

commaAndDot []                          // ""
commaAndDot [ "foo" ]                   // "foo."
commaAndDot [ "foo"; "bar" ]            // "foo and bar."
commaAndDot [ "Hello"; "World"; "F#" ]  // "Hello, World and F#."

Run Code Online (Sandbox Code Playgroud)

更新:SCNR,创建了一个基准测试...结果在下面作为HTML片段(对于漂亮的表格数据).

BuilderOpt是StringBuilder版本,[]案例移到底部,BuilderChained带有链接的Append调用,例如sb.Append(a).Append(" and ").Append(b),BuilderFormat就是例如sb.AppendFormat("{0} and {1}", a, b).完整源代码可用.

正如预期的那样,'更简单'的版本对小列表表现更好,列表越大,BuilderChained越好.Concat的性能比我预期的要好,但没有产生正确的输出(缺少".",缺少一个案例).收益率变得相当缓慢......

<!DOCTYPE html>
<html lang='en'>
<head>
<meta charset='utf-8' />
<title>Benchmark.CommaAndDot</title>

<style type="text/css">
	table { border-collapse: collapse; display: block; width: 100%; overflow: auto; }
	td, th { padding: 6px 13px; border: 1px solid #ddd; }
	tr { background-color: #fff; border-top: 1px solid #ccc; }
	tr:nth-child(even) { background: #f8f8f8; }
</style>
</head>
<body>
<pre><code>
BenchmarkDotNet=v0.11.1, OS=Windows 10.0.16299.726 (1709/FallCreatorsUpdate/Redstone3)
Intel Core i7 CPU 950 3.07GHz (Nehalem), 1 CPU, 8 logical and 4 physical cores
Frequency=2998521 Hz, Resolution=333.4977 ns, Timer=TSC
  [Host]     : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 64bit LegacyJIT-v4.7.3190.0 DEBUG
  DefaultJob : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.3190.0
</code></pre>
<pre><code></code></pre>

<table>
<thead><tr><th>  Method</th><th>Verbosity</th><th>    Mean</th><th>Error</th><th>StdDev</th><th>  Median</th><th>Scaled</th><th>ScaledSD</th>
</tr>
</thead><tbody><tr><td>Concat</td><td>0</td><td>39.905 ns</td><td>0.0592 ns</td><td>0.0494 ns</td><td>39.906 ns</td><td>1.02</td><td>0.11</td>
</tr><tr><td>Yield</td><td>0</td><td>27.235 ns</td><td>0.0772 ns</td><td>0.0603 ns</td><td>27.227 ns</td><td>0.69</td><td>0.07</td>
</tr><tr><td>Accumulator</td><td>0</td><td>1.956 ns</td><td>0.0109 ns</td><td>0.0096 ns</td><td>1.954 ns</td><td>0.05</td><td>0.01</td>
</tr><tr><td>Builder</td><td>0</td><td>32.384 ns</td><td>0.2986 ns</td><td>0.2331 ns</td><td>32.317 ns</td><td>0.82</td><td>0.09</td>
</tr><tr><td>BuilderOpt</td><td>0</td><td>33.664 ns</td><td>1.0371 ns</td><td>0.9194 ns</td><td>33.402 ns</td><td>0.86</td><td>0.09</td>
</tr><tr><td>BuilderChained</td><td>0</td><td>39.671 ns</td><td>1.2097 ns</td><td>3.5669 ns</td><td>41.339 ns</td><td>1.00</td><td>0.00</td>
</tr><tr><td>BuilderFormat</td><td>0</td><td>40.276 ns</td><td>0.8909 ns</td><td>1.8792 ns</td><td>39.494 ns</td><td>1.02</td><td>0.12</td>
</tr><tr><td>Concat</td><td>1</td><td>153.116 ns</td><td>1.1592 ns</td><td>0.9050 ns</td><td>152.706 ns</td><td>0.87</td><td>0.01</td>
</tr><tr><td>Yield</td><td>1</td><td>154.522 ns</td><td>0.2890 ns</td><td>0.2256 ns</td><td>154.479 ns</td><td>0.88</td><td>0.00</td>
</tr><tr><td>Accumulator</td><td>1</td><td>223.342 ns</td><td>0.3678 ns</td><td>0.2872 ns</td><td>223.412 ns</td><td>1.27</td><td>0.00</td>
</tr><tr><td>Builder</td><td>1</td><td>232.194 ns</td><td>0.2951 ns</td><td>0.2465 ns</td><td>232.265 ns</td><td>1.32</td><td>0.00</td>
</tr><tr><td>BuilderOpt</td><td>1</td><td>232.016 ns</td><td>0.5654 ns</td><td>0.4722 ns</td><td>232.170 ns</td><td>1.31</td><td>0.00</td>
</tr><tr><td>BuilderChained</td><td>1</td><td>176.473 ns</td><td>0.3918 ns</td><td>0.3272 ns</td><td>176.341 ns</td><td>1.00</td><td>0.00</td>
</tr><tr><td>BuilderFormat</td><td>1</td><td>219.262 ns</td><td>6.7995 ns</td><td>6.3603 ns</td><td>217.003 ns</td><td>1.24</td><td>0.03</td>
</tr><tr><td>Concat</td><td>10</td><td>1,284.042 ns</td><td>1.7035 ns</td><td>1.4225 ns</td><td>1,283.443 ns</td><td>1.68</td><td>0.05</td>
</tr><tr><td>Yield</td><td>10</td><td>6,532.667 ns</td><td>12.6169 ns</td><td>10.5357 ns</td><td>6,533.504 ns</td><td>8.55</td><td>0.24</td>
</tr><tr><td>Accumulator</td><td>10</td><td>2,701.483 ns</td><td>4.8509 ns</td><td>4.5376 ns</td><td>2,700.208 ns</td><td>3.54</td><td>0.10</td>
</tr><tr><td>Builder</td><td>10</td><td>1,865.668 ns</td><td>5.0275 ns</td><td>3.9252 ns</td><td>1,866.920 ns</td><td>2.44</td><td>0.07</td>
</tr><tr><td>BuilderOpt</td><td>10</td><td>1,820.402 ns</td><td>2.7853 ns</td><td>2.3258 ns</td><td>1,820.464 ns</td><td>2.38</td><td>0.07</td>
</tr><tr><td>BuilderChained</td><td>10</td><td>764.334 ns</td><td>19.8528 ns</td><td>23.6334 ns</td><td>756.988 ns</td><td>1.00</td><td>0.00</td>
</tr><tr><td>BuilderFormat</td><td>10</td><td>1,177.186 ns</td><td>1.9584 ns</td><td>1.6354 ns</td><td>1,177.897 ns</td><td>1.54</td><td>0.04</td>
</tr><tr><td>Concat</td><td>100</td><td>25,579.773 ns</td><td>824.1504 ns</td><td>688.2028 ns</td><td>25,288.873 ns</td><td>5.33</td><td>0.14</td>
</tr><tr><td>Yield</td><td>100</td><td>421,872.560 ns</td><td>902.5023 ns</td><td>753.6302 ns</td><td>421,782.071 ns</td><td>87.87</td><td>0.23</td>
</tr><tr><td>Accumulator</td><td>100</td><td>80,579.168 ns</td><td>227.7392 ns</td><td>177.8038 ns</td><td>80,547.868 ns</td><td>16.78</td><td>0.05</td>
</tr><tr><td>Builder</td><td>100</td><td>15,047.790 ns</td><td>26.2248 ns</td><td>21.8989 ns</td><td>15,048.903 ns</td><td>3.13</td><td>0.01</td>
</tr><tr><td>BuilderOpt</td><td>100</td><td>15,287.117 ns</td><td>39.8679 ns</td><td>31.1262 ns</td><td>15,293.739 ns</td><td>3.18</td><td>0.01</td>
</tr><tr><td>BuilderChained</td><td>100</td><td>4,800.966 ns</td><td>11.3614 ns</td><td>10.0716 ns</td><td>4,801.450 ns</td><td>1.00</td><td>0.00</td>
</tr><tr><td>BuilderFormat</td><td>100</td><td>8,382.896 ns</td><td>87.8963 ns</td><td>68.6236 ns</td><td>8,368.400 ns</td><td>1.75</td><td>0.01</td>
</tr></tbody></table>
</body>
</html>

Run Code Online (Sandbox Code Playgroud)

这个问题不是我特别感兴趣的问题,但无论如何心不在焉地阅读它,我觉得我偶然发现了一个非常棒的演讲!谢谢. (2认同)

归档时间：	7 年前
查看次数：	141 次
最近记录：	7 年前