F#合并排序 - 试图实现与结构
我归并排序总码匹配时IndexOutOfRangeException,看起来是这样的:F#合并排序 - 试图实现与结构
let remove array =
Array.sub array 1 (array.Length - 1)
let rec merge (chunkA : int[]) (chunkB : int[]) =
if chunkA.Length = 0 && chunkB.Length = 0 then [||]
else if chunkA.Length = 0 || chunkB.[0] < chunkA.[0] then Array.append [| chunkB.[0] |] (merge chunkA (remove chunkB))
else Array.append [| chunkA.[0] |] (merge (remove chunkA) chunkB)
let rec mergesort (array : int[]) =
let middle = array.Length/2
let chunkA = match middle with
| 1 -> [| array.[0] |]
| _ -> mergesort [| for i in 0 .. middle - 1 -> array.[i]|]
let chunkB = match array.Length - middle with
| 1 -> [| array.[array.Length - 1] |]
| _ -> mergesort [| for i in middle .. array.Length - 1 -> array.[i]|]
merge chunkA chunkB
此代码工作得很好,但我想改变系列if语句中的merge
函数为match with
语句。
然后,我尝试执行以下代码:
let rec merge (chunkA : int[]) (chunkB : int[]) =
match chunkA.Length with
| 0 when chunkA.Length = chunkB.Length -> [||]
| 0 | _ when chunkB.[0] < chunkA.[0] -> Array.append [| chunkB.[0] |] (merge chunkA (remove chunkB))
| _ -> Array.append [| chunkA.[0] |] (merge (remove chunkA) chunkB)
当我跑我的代码,Visual Studio将引发一个 “IndexOutOfRangeException” 我,特别是在这里:
| 0 when chunkA.Length = chunkB.Length -> [||]
在这种情况下,chunkA
是空的,但chunkB
有一个单一的数字。因此,我不完全确定为什么F#甚至试图返回这种情况,因为块A和B的长度不一样,但我也很困惑,为什么这会抛出索引错误,特别是在空数组上。
另外,我对F#和函数式编程一般都比较陌生。如果我的代码中的结构或方法不符合标准,那么请随时对此进行评论。
另外,如果我很厚,请随时告诉我。
非常感谢, 卢克
正如陀Soikin指出的那样,你的异常的来源是这一行:
| 0 | _ when chunkB.[0] < chunkA.[0] -> Array.append [| chunkB.[0] |] (merge chunkA (remove chunkB))
但为什么多数民众赞成抛出一个异常,它可能不是很明显你。 As I learned last week to my surprise,when
子句中的匹配表达式适用于全部以前的案例->
。换句话说,当你写上面的线,F#理解你的意思,你要应用到要么的0
情况或的_
情况when
条款。 (当然这是多余的)。
这就是你例外的原因:F#看到0
的情况,但仍然适用when chunkB.[0] < chunkA.[0]
测试 - 因为chunkA
是空的,那总是会抛出一个异常。为了解决这个问题,你必须对这两种情况分开,使when
仅适用于你的意思是它适用于情况:
| 0 -> Array.append [| chunkB.[0] |] (merge chunkA (remove chunkB))
| _ when chunkB.[0] < chunkA.[0] -> Array.append [| chunkB.[0] |] (merge chunkA (remove chunkB))
不幸的是,这是否意味着一些代码重复。在这种情况下,这不是什么大问题,因为重复的代码是单行代码的,但是如果您有大量的代码会因为必须拆分两个这样的案例而重复出现(两个案例不应共享一个when
条件),那么你可以把这个重复的块变成一个函数,以便它不再被复制。
编辑:我刚刚注意到一段代码可能更简单。您的原始代码包括:
let chunkA = match middle with
| 1 -> [| array.[0] |]
| _ -> mergesort [| for i in 0 .. middle - 1 -> array.[i]|]
let chunkB = match array.Length - middle with
| 1 -> [| array.[array.Length - 1] |]
| _ -> mergesort [| for i in middle .. array.Length - 1 -> array.[i]|]
你在做什么在这里走的是阵列中分得一杯羹,但F#有数组切片一个非常方便的语法:array.[start..end]
其中start
和end
是切片的包容性指数你想。因此,表达式[| for i in 0 .. middle - 1 -> array.[i]|]
可以简化为array.[0 .. middle - 1]
,并且表达式[| for i in middle .. array.Length - 1 -> array.[i]|]
可以简化为array.[middle .. array.Length - 1]
。让我们来替换那些表情在你的代码,看看我们得到:现在
let chunkA = match middle with
| 1 -> [| array.[0] |]
| _ -> mergesort array.[0 .. middle - 1]
let chunkB = match array.Length - middle with
| 1 -> [| array.[array.Length - 1] |]
| _ -> mergesort array.[middle .. array.Length - 1]
,看着这个,我注意到1
条件在这两种情况下,实际处理完全相同的阵列片作为_
条件;唯一的区别是,如果中间值为1,则不会调用mergesort
。我怎么知道它是完全相同的数组切片?那么,如果middle
为1,那么array.[0 .. middle-1]
表达式将变为array.[0..0]
,这是从索引0开始的数组中长度为1的片段,与[| array.[0] |]
完全相同。如果array.Length
恰好比middle
多1,那么array.[middle .. array.Length - 1]
表达式将是array.[middle .. middle]
,这完全等于[| array.[middle] |]
。
因此,如果不是拨打mergesort
,我们可以合并这两个表达式。事实上,有一个非常简单的方法可以做到这一点。只需将长度检查移动到mergesort
顶部,就像这样:
let rec mergesort (array : int[]) =
if array.Length < 2 then
array // Arrays of length 0 or 1 are already sorted
else
// rest of mergesort function goes here
现在你可以放心地巩固您match
的两种情况,知道你不会打一个无限递归循环:
let middle = array.Length/2
let chunkA = mergesort array.[0 .. middle - 1]
let chunkB = mergesort array.[middle .. array.Length - 1]
merge chunkA chunkB
把这个都在一起,我原来的mergesort
功能的建议的版本是这样的:
let rec mergesort (array : int[]) =
if array.Length < 2 then
array // Arrays of length 0 or 1 are already sorted
else
let middle = array.Length/2
let chunkA = mergesort array.[0 .. middle - 1]
let chunkB = mergesort array.[middle .. array.Length - 1]
merge chunkA chunkB
作为奖励,这款v mergesort
的版本没有您原始版本的微妙错误:您忘记考虑空数组的情况。在空数组上调用原始mergesort
会产生无限循环。你可能会从中得到更多的好处,而不是从我这里解释如何,所以我只想提到在F#for i in 0 .. -1
不是错误,而是会通过for
循环零次(即for
循环的主体将会不被执行)。同样,array.[0..-1]
不是错误,但会产生一个空数组。掌握了这些细节的知识后,您应该能够完成原始mergesort
函数的代码,并且如果您传递了空字符串,它将无限循环。 (虽然你的mergesort
这个无限循环中的调用不是尾部调用,但它不会是尾部调用,所以栈最终会溢出,从而避免出现“真正的”无限循环)。
由于某种原因,调试器显示不正确的行。错误的真正来源是'chunkB。[0]
另外,'| 0 | _当chunkB。[0]'行将'when'条件应用于**两种情况。 “when”的工作方式通常会引起新的F#程序员的惊讶(甚至令我惊讶)(http://*.com/questions/43455264/incomplete-pattern-match-when-two-patterns-share-a -when-clause)上周,而且我一直在使用F#)。所以这里的'0'情况下仍然会测试'when chunkB。[0]
rmunn