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

首先,另一个数据点:模块中的Set数据结构Data.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

fillSet 1 Set.empty在GHCi中运行,包括一些额外的计算,以确保评估整个结果,运行时没有明显的延迟.所以,这似乎表明问题在于您的实施.

首先,我怀疑使用Data.Set.Set与实现之间的最大区别在于,如果我正确地读取您的代码,那么您实际上并不是在测试二叉树.您正在测试一个过于复杂的链表 - 即最大不平衡树 - 由于按递增顺序插入元素.Data.Set.Set使用平衡的二叉树,在这种情况下更好地处理病理输入.

我们还可以看看以下定义Set:

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

在没有详细说明的情况下,这说明了跟踪树的大小,并避免了一些不太有用的间接层,否则这些层将存在于数据类型中.

该Data.Set模块的完整资源可以在这里找到; 你可能会发现学习很有启发性.

还有一些观察,以展示不同运行方式之间的差异.我在您的代码中添加了以下内容:

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

main = print . sum . toList $ fillTree 1 EmptyTree

这将遍历树,对元素求和,并打印总数,这应该确保所有内容都是强制的.我的系统可能有点不寻常,所以你可能会自己尝试不同的结果,但相对差异应该足够准确.一些结果:

• 使用runhaskell,应该大致相当于在GHCi中运行它:

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

• 建筑用ghc --make -O0:

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

• 建筑用ghc --make -O2:

  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中评估表达式并使用秒表计时,这是测试代码性能的非常非常糟糕的方法.

Answer 2

我怀疑你在C中实现了相同的代码.你可能使用了非持久性树结构. 这意味着您将Haskell中的O(n ^ 2)算法与C中的O(n)算法进行比较 .Nevermind,您使用的具体情况是具有持久性结构的O(n ^ 2).持久性结构只有更多的分配,所以它不是一个基本的算法差异.

另外,看起来你从ghci运行它."我"在"ghci"中的意思是"翻译".是的,解释器可能比编译代码慢几十倍或几百倍.尝试使用优化进行编译并运行它. 我怀疑由于基本的算法差异,它仍然会慢,但它不会接近50秒.