Быстрая реализация двоичного дерева Haskell - PullRequest
Новая
       9

Быстрая реализация двоичного дерева Haskell

5 голосов
/ 22 июля 2011

Я реализовал структуру данных двоичного дерева в 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, может быть, я смогу сделать реализацию бинарного дерева более эффективной?

Спасибо.

Ответы [ 2 ]

14 голосов
/ 22 июля 2011

Во-первых, еще одна точка данных: структура данных 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 и синхронизация их с помощью секундомера - очень и очень плохой способ проверить производительность вашего кода.

6 голосов
/ 22 июля 2011

Я сомневаюсь, что вы реализовали тот же код на C. Вы, вероятно, вместо этого использовали непостоянную древовидную структуру. Это означает, что вы сравниваете алгоритм O (n ^ 2) в Haskell с алгоритмом O (n) в C. Не имеет значения, конкретный случай, который вы используете, будет O (n ^ 2) с постоянная структура или нет. С постоянной структурой намного больше распределения, так что это не принципиальное алгоритмическое различие.

Кроме того, похоже, что вы запустили это из ghci. Что «я» в «ghci» означает «переводчик». И да, интерпретатор может быть в десятки или сотни раз медленнее, чем скомпилированный код. Попробуйте скомпилировать его с оптимизацией и запустить. Я подозреваю, что это все еще будет медленнее из-за фундаментальных алгоритмических различий, но это не будет около 50 секунд.

...