Haskell二叉树快速实现

Question

我在Haskell中实现了二叉树数据结构。

我的代码：

module Data.BTree where 

data Tree a = EmptyTree 
       | Node a (Tree a) (Tree a) 
       deriving (Eq, Ord, Read, Show) 

emptyTree :: a -> Tree a 
emptyTree a = Node a EmptyTree EmptyTree 

treeInsert :: (Ord a) => a -> Tree a -> Tree a 
treeInsert x EmptyTree = emptyTree x 
treeInsert x (Node a left right) 
     | x == a = (Node x left right) 
     | x < a = (Node a (treeInsert x left) right) 
     | x > a = (Node a left (treeInsert x right)) 


fillTree :: Int -> Tree Int -> Tree Int 
fillTree 10000 tree = tree 
fillTree x tree = let a = treeInsert x tree 
        in fillTree (x + 1) a 

此代码非常缓慢。我运行：

fillTree 1 EmptyTree 

我得到：50.24秒

我试图实现在C语言的代码，我的这个测试结果：0m0.438s

为什么这么大的差别？ Haskell代码依赖如此之慢，或者我在haskell中的二叉树不好？我想问问haskell guru，也许我可以让我的二叉树实现更有效？

谢谢。

Answer 1

我怀疑你在C中实现了相同的代码。你可能使用了非持久化树结构。 这意味着你在Haskell为O（n^2）算法比较的O在C. 没关系（n）的算法，您使用将与一个持久性结构为O（n^2）的特定情况下或不。这个持久化结构的分配更多，所以它不是一个基本的算法差异。

此外，它看起来像你从ghci跑这个。 “我”在“ghci”中表示“解释者”。是的，解释器可能比编译代码慢数十倍或数百倍。尝试通过优化编译并运行它。 由于基本的算法差异，我怀疑它仍然会变慢，但它不会接近50秒。

Answer 2

首先，另一个数据点：在Data.Set模块中的Set数据结构碰巧是一个二叉树。我翻译好fillTree功能，使用它，而不是：

import qualified Data.Set as Set 
import Data.Set (Set) 

fillSet :: Int -> Set Int -> Set Int 
fillSet 10000 set = set 
fillSet x set = let a = Set.insert x set 
       in fillSet (x + 1) a 

在GHCI运行fillSet 1 Set.empty，包括一些额外的计算，以确保整个结果进行评估，运行速度没有明显的延迟。所以，这似乎表明问题在于你的实现。

首先，我怀疑使用Data.Set.Set对你实施的是，如果我正确地读你的代码，你不实际测试的二进制树之间的最大区别。您正在测试一个过于复杂的链表 - 也就是最大程度地不平衡的树 - 因为按递增顺序插入元素。 Data.Set.Set使用平衡的二叉树，在这种情况下更好地处理病理输入。

我们也可以看看Set定义：

data Set a = Tip 
      | Bin {-# UNPACK #-} !Size a !(Set a) !(Set a) 

没有进入太多细节，这是什么说的是，跟踪树的大小，并避免一些不那么有用层否则会存在于数据类型中的间接性。

Data.Set所述模块的完整源可以发现here;你可能会发现它对学习有启发。

---

一些更多的观察，以演示运行它的不同方式之间的差异。添加以下到您的代码：

toList EmptyTree = [] 
toList (Node x l r) = toList l ++ [x] ++ toList r 

main = print . sum . toList $ fillTree 1 EmptyTree 

这遍历树，总结的要素，并打印总量，应确保一切都被迫。我的系统可能有点不寻常，所以你可能会得到相当不同的结果，但相对差异应该足够准确。一些结果：

• 使用runhaskell，这应该是大致相当于GHCI运行它：用ghc --make -O0

  real 1m36.055s 
  user 0m0.093s 
  sys  0m0.062s 
  

• 大厦：与ghc --make -O2

  real 0m3.904s 
  user 0m0.030s 
  sys  0m0.031s 
  

• 大厦：

  real 0m1.765s 
  user 0m0.015s 
  sys  0m0.030s 
  

使用基于我的等价功能上，而不是Data.Set：

• 使用runhaskell：

  real 0m0.521s 
  user 0m0.031s 
  sys  0m0.015s 
  

• 使用ghc --make -O2：

  real 0m0.183s 
  user 0m0.015s 
  sys  0m0.031s 
  

今天的故事的道德是：在GHCi中评估表达式并使用秒表对它们进行计时是测试代码性能的一种非常非常糟糕的方式。