C++ 및 하스켈에서 트리 탐색

Question

하스켈을 처음 사용했습니다. 내가 얼마나 잘 haskell 그들의 게으른 평가와 함께 재귀 함수 호출을 처리 할 수있는 감각을 얻으려고 노력하고 있어요. 내가 만든 실험은 단순히 C++과 Haskell 모두에서 이진 탐색 트리를 구축하고 각각 postorder에서 트래버스합니다. C++ 구현은 보조 스택이있는 표준 스택입니다. (일단 방문하면 요소를 출력합니다). 여기

내 하스켈 코드 :

module Main (main) where 

import System.Environment (getArgs) 
import System.IO 
import System.Exit 
import Control.Monad(when) 
import qualified Data.ByteString as S 

main = do 
    args <- getArgs 
    when (length args < 1) $ do 
      putStrLn "Missing input files" 
      exitFailure 

    content <- readFile (args !! 0) 
    --preorderV print $ buildTree content 
    mapM_ print $ traverse POST $ buildTree content 
    putStrLn "end" 


data BSTree a = EmptyTree | Node a (BSTree a) (BSTree a) deriving (Show) 
data Mode = IN | POST | PRE 

singleNode :: a -> BSTree a 
singleNode x = Node x EmptyTree EmptyTree 

bstInsert :: (Ord a) => a -> BSTree a -> BSTree a 
bstInsert x EmptyTree = singleNode x 
bstInsert x (Node a left right) 
      | x == a = Node a left right 
      | x < a = Node a (bstInsert x left) right 
      | x > a = Node a left (bstInsert x right) 

buildTree :: String -> BSTree String 
buildTree = foldr bstInsert EmptyTree . words 

preorder :: BSTree a -> [a] 
preorder EmptyTree = [] 
preorder (Node x left right) = [x] ++ preorder left ++ preorder right 

inorder :: BSTree a -> [a] 
inorder EmptyTree = [] 
inorder (Node x left right) = inorder left ++ [x] ++ inorder right 

postorder :: BSTree a -> [a] 
postorder EmptyTree = [] 
postorder (Node x left right) = postorder left ++ postorder right ++[x] 

traverse :: Mode -> BSTree a -> [a] 
traverse x tree = case x of IN -> inorder tree 
          POST -> postorder tree 
          PRE -> preorder tree 


preorderV :: (a->IO()) -> BSTree a -> IO() 
preorderV f EmptyTree = return() 
preorderV f (Node x left right) = do 
            f x 
            preorderV f left 
            preorderV f right 

내 테스트 결과 표시하는 C++ 크게 능가 하스켈 :

C++ 성능 :

(즉 first15000.txt이 first3000.txt의 약 5 배에 유의)

time ./speedTestTreeTraversal first3000.txt > /dev/null 

real 0m0.500s 
user 0m0.488s 
sys  0m0.008s 
time ./speedTestTreeTraversal first15000.txt > /dev/null 

real 0m3.511s 
user 0m3.436s 
sys  0m0.072s 

012,351,641 : 동일한 입력 파일과

time ./speedTestForTraversal first3000.txt > /dev/null 

real 0m0.158s 
user 0m0.156s 
sys  0m0.000s 
time ./speedTestForTraversal first15000.txt > /dev/null 

real 0m0.923s 
user 0m0.916s 
sys  0m0.004s 

하스켈

내가 기대하는 바는 haskell이 C++과 너무 멀리 떨어져 있지 않아야한다는 것이다. 내가 실수 한거야? 내 haskell 코드를 향상시킬 방법이 있습니까?

감사

편집 : 2014년 10월 18일

이 Serval의 경우를 테스트 한 후, 하스켈의 통과는 크게 여전히 C++ 구현보다 느립니다. 나는 그가 haskell 구현의 비효율을 지적하기 때문에 Cirdec의 대답에 완전한 신용을주고 싶다. 그러나, 내 원래의 질문은 C + +와 haskell 구현을 비교하는 것입니다. 그래서이 질문을 공개하고 더 많은 토론을 장려하기 위해 C++ 코드를 게시하고 싶습니다.

#include <iostream> 
#include <string> 
#include <boost/algorithm/string.hpp> 
#include <fstream> 
#include <stack> 
using namespace std; 
using boost::algorithm::trim; 
using boost::algorithm::split; 


template<typename T> 
class Node 
{ 
public: 
    Node(): val(0), l(NULL), r(NULL), p(NULL) {}; 
    Node(const T &v): val(v), l(NULL), r(NULL), p(NULL) {} 
    Node* getLeft() {return l;} 
    Node* getRight(){return r;} 
    Node* getParent() {return p;} 
    void setLeft(Node *n) {l = n;} 
    void setRight(Node *n) {r = n;} 
    void setParent(Node *n) {p = n;} 
    T &getVal() {return val;} 
    Node* getSucc() {return NULL;} 
    Node* getPred() {return NULL;} 
private: 
    T val; 
    Node *l; 
    Node *r; 
    Node *p; 
}; 

template<typename T> 
void destoryOne(Node<T>* n) 
{ 
    delete n; 
    n = NULL; 
} 

template<typename T> 
void printOne(Node<T>* n) 
{ 
    if (n!=NULL) 
    std::cout << n->getVal() << std::endl; 
} 




template<typename T> 
class BinarySearchTree 
{ 
public: 
    typedef void (*Visit)(Node<T> *); 

    BinarySearchTree(): root(NULL) {} 
    void delNode(const T &val){}; 
    void insertNode(const T &val){ 
    if (root==NULL) 
     root = new Node<T>(val); 
    else { 
     Node<T> *ptr = root; 
     Node<T> *ancester = NULL; 
     while(ptr && ptr->getVal()!=val) { 
     ancester = ptr; 
     ptr = (val < ptr->getVal()) ? ptr->getLeft() : ptr->getRight(); 
     } 
     if (ptr==NULL) { 
     Node<T> *n = new Node<T>(val); 
     if (val < ancester->getVal()) 
      ancester->setLeft(n); 
     else 
      ancester->setRight(n); 
     } // else the node exists already so ignore! 
    } 
    } 
    ~BinarySearchTree() { 
    destoryTree(root); 
    } 
    void destoryTree(Node<T>* rootN) { 
    iterativePostorder(&destoryOne); 
    } 

    void iterativePostorder(Visit fn) { 
    std::stack<Node<T>* > internalStack; 
    Node<T> *p = root; 
    Node<T> *q = root; 
    while(p) { 
     while (p->getLeft()) { 
     internalStack.push(p); 
     p = p->getLeft(); 
     } 
     while (p && (p->getRight()==NULL || p->getRight()==q)) { 
     fn(p); 
     q = p; 
     if (internalStack.empty()) 
      return; 
     else { 
      p = internalStack.top(); 
      internalStack.pop(); 
     } 
     } 
     internalStack.push(p); 
     p = p->getRight(); 
    } 
    } 


    Node<T> * getRoot(){ return root;} 
private: 
    Node<T> *root; 
}; 



int main(int argc, char *argv[]) 
{ 
    BinarySearchTree<string> bst; 
    if (argc<2) { 
    cout << "Missing input file" << endl; 
    return 0; 
    } 
    ifstream inputFile(argv[1]); 
    if (inputFile.fail()) { 
    cout << "Fail to open file " << argv[1] << endl; 
    return 0; 
    } 
    while (!inputFile.eof()) { 
    string word; 
    inputFile >> word; 
    trim(word); 
    if (!word.empty()) { 
     bst.insertNode(word); 
    } 
    } 

    bst.iterativePostorder(&printOne); 

    return 0; 
} 

편집 : 2014년 10월 20일 아래에서 크리스의 대답은 매우 철저 나는 결과를 반복 할 수 있습니다.

Answer 1

공백으로 구분 된 소문자 ASCII 알파벳 abcdefghijklmnopqrstuvwxyz에있는 모든 4 자 문자열을 포함하는 파일을 생성했습니다. 올바른 순서로 코드를 생성하여 코드가 생성하는 트리가 완벽하게 균형을 유지할 수 있다고 생각합니다.

3.5s Haskell처럼 컴퓨터에서 3.4 초가 걸리기 때문에이 길이를 선택했습니다. 나는 그것을 명백한 이유로 26_4.txt이라고 불렀다. 실제로 데이터 세트가 26 개의 단어에 가까워서 길이가 비슷합니다. (물론 /dev/null에 배관 표준 출력) 0.4s를 복용에 감소 내 데이터 세트에 대한

import System.IO 
main = do 
    mylist <- readFile "26_4.txt" 
    mapM_ putStrLn (words mylist) 

이 : 런타임에

하한 뭔가처럼 될 것입니다. 그래서 우리는 하스켈에서 이런 종류의 문제에 대해 10 배의 속도 향상을 기대할 수 없습니다. 그러나 그 요인은 문제의 영역 내에 있습니다. C++은이 초간단 프로그램보다 두 배 오래 걸립니다.

그러나 처리는 비현실적인 목표가 아닙니다.

import System.IO 
import qualified Data.Map.Strict as Map 

balancedTree = Map.fromList . map (\k -> (k,())) 

serializeTree = map fst . Map.toList 

main = do 
    mylist <- readFile "26_4.txt" 
    mapM_ putStrLn (serializeTree $ balancedTree $ words mylist) 

이 더 내 컴퓨터에 1.6s 같은 뭔가를 실행 : 우리는 우리가 이미 잘 하스켈을 이해하는 전문가들이 우리를 위해 최적화 된 데이터 구조를 사용하는 경우보다 현실적인 인 바운드를 얻을 수 있습니다. 당신의 C++만큼 빠르지는 않지만, C++은 제가 말할 수있는 한 나무의 균형을 맞추지 못합니다.

코드에 Cirdec의 수정을가 했으므로 코드를 3.1 초까지 줄 였으므로 코드 실행 시간이 파일의 약 10 % 만 줄어 들었습니다.

그러나 내 컴퓨터에서이 파일은 도 실행되지 않습니다. RTSopts로 더 많은 메모리를 제공하지 않는 한을 실행하십시오. 이는 중요한 최적화 인 꼬리 호출 최적화를 가리 킵니다.당신과 Cirdec 모두의 코드는 인 이 특별한 방법입니다. 꼬리 재귀 코드이 아니므로 GHC에서 루프로 바꿀 수 없습니다. 2.1s에 아래로 모든 방법을 가지고

postorder :: BSTree a -> [a] 
postorder t = go [] [t] 
    where go xs [] = xs 
      go xs (EmptyTree : ts) = go xs ts 
      go xs (Node x a b : ts) = go (x : xs) (b : a : ts) 

이 변경 같다 : 우리는 우리가에 내려하는 '수행 할 물건'의 명시 적 스택을 작성하여이 꼬리 재귀 할 수 있습니다.

시간이 낭비되는 C++과 Haskell의 또 다른 차이점은 Haskell 버전을 사용하면 검색 트리를 지연 생성 할 수 있지만 C++ 코드는이를 허용하지 않는다는 것입니다.

data BSTree a = EmptyTree 
      | Node !a !(BSTree a) !(BSTree a) deriving (Show) 

가 Cirdec의 결합이 변화는 우리가 당신의 C++ 코드에서와에 파있어 즉, 1.1 초에 우리를 제공합니다 : 우리는 같은 것을 제공이 다루는 엄격한 하스켈 코드를 만들 수 있습니다 적어도 내 컴퓨터에서. 이 문제가 컴퓨터의 주요 문제인지 테스트하기 위해 컴퓨터에서 테스트해야합니다. 추가 최적화 작업은 "안락 의자에서"수행 할 수 없으며 대신 적절한 프로파일 러를 사용해야합니다.

코드를 ghc -O2 기억하십시오. 그렇지 않으면 꼬리 - 호출 및 기타 최적화가 수행되지 않을 수 있습니다.

Answer 2

++과의 목록 연결이 느리고 매번 ++이 발생할 때마다 두 번째 인수를 추가 할 위치를 찾으려면 첫 번째 인수를 끝까지 지나야합니다. 당신은 첫 번째 인수는 standard prelude에서 ++의 정의에 [] 모든 방법을 횡단하는 방법을 볼 수 있습니다 ++ 재귀 적 사용이 통과가 비효율적이다 재귀의 각 수준에 대해 반복해야

(++) :: [a] -> [a] -> [a] 
[]  ++ ys = ys 
(x:xs) ++ ys = x : (xs ++ ys) 

.

목록을 작성하는 또 다른 방법이 있습니다. 목록을 작성하기 전에 목록의 끝에 오는 것이 무엇인지 알면 이미 끝까지 작성하십시오. 의 우리가 postorder left을 할 때, 우리는 이미 postorder right ++ [x] 것, 뒤에 올 것이다 알고, 그래서 나무의 왼쪽면에 대한 목록을 구축 나을 postorder

postorder :: BSTree a -> [a] 
postorder EmptyTree = [] 
postorder (Node x left right) = postorder left ++ postorder right ++ [x] 

의 정의를 살펴 보자 오른쪽에있는 값과 노드에 이미있는 값을 비교합니다. 마찬가지로 우리가 postorder right을 만들 때, 우리는 이미 그 뒤에 오는 것이 무엇인지, 즉 x을 알고 있습니다.우리는 입력으로 15,000 단어 사전과 함께 실행하면 내 컴퓨터에이 약 두 배 빠른 목록

postorder :: BSTree a -> [a] 
postorder tree = go tree [] 
    where 
     go EmptyTree rest = rest 
     go (Node x left right) rest = go left (go right (x:rest)) 

의 rest에 대한 누적 값을 전달하는 도우미 함수를 만들어 정확하게 할 수 있습니다. 우리가 더 깊은 이해를 얻을 수 있는지 좀 더 살펴 보도록하겠습니다. 우리는 함수의 합성 (.) 대신 중첩 된 괄호의 응용 프로그램 ($)를 사용하여 우리의 postorder 정의를 다시 작성하는 경우 우리는이 것

postorder :: BSTree a -> [a] 
postorder tree = go tree [] 
    where 
     go EmptyTree rest = rest 
     go (Node x left right) rest = go left . go right . (x:) $ rest 

우리는 심지어 rest 인수와 함수 응용 프로그램, $을 삭제하고이를 쓸 수 있습니다 약간 더 포인트가없는 스타일

postorder :: BSTree a -> [a] 
postorder tree = go tree [] 
    where 
     go EmptyTree = id 
     go (Node x left right) = go left . go right . (x:) 

이제 우리는 우리가 한 것을 볼 수 있습니다. 우리는 목록 [a]을 기존리스트에 추가하는 함수 [a] -> [a]으로 대체했습니다. 빈 목록은 ID 함수 인 id 인 목록 시작 부분에 아무 것도 추가하지 않는 함수로 바뀝니다. 싱글 톤 목록 [x]은 (x:)의 처음에 x을 추가하는 함수로 바뀝니다. 목록 연결 a ++ b은 기능 구성 f . g으로 바뀝니다. 먼저 g이 목록의 시작 부분에 추가 할 내용을 추가 한 다음 f이 해당 목록의 시작 부분에 추가 할 내용을 추가하십시오.