4. 二分木
著者:梅谷 武
各言語において二分木の実装と性能比較を行なう。単純木と赤黒木の二種類の実装を共通インターフェースをもつモジュールとして用意し、メインプログラムから呼び出すようにしてモジュール化法を比較する。
作成:2024-04-11
更新:2024-10-25
更新:2024-10-25
C++20で新しいモジュール機構が導入されたが、現時点ではコンパイラ側の対応はまだ完全なものではない。そのため今回はC++20以前のモジュール化法を採用する。単純木と赤黒木はテンプレートクラスとして共通インターフェースを定義する仮想基底クラスを継承する形で実装される。赤黒木の実装にはstd::setを利用する。
モジュールについての概説はThe Racket Guide＞6 Modulesにある。赤黒木の実装はパッケージ:data-red-blackを用いる。これは次のようにインストールする。
raco pkg install data-red-black
入力ファイルを入力リスト:lstに読み込み、それから二分木:rootを生成し、走査しながら昇順整列し、出力リスト:lst2に書き込み、それを出力ファイルに書き出す。但し、二分木においてデータの重複は許さないものとする。
- 入力ファイルを読み込み、入力リスト:lstに格納
- lstの要素を空ノードに挿入し、二分木:rootを生成
- 二分木:rootをlstの全要素で探索
- 二分木を走査しながら昇順整列し、出力リスト:lst2に格納
- lst2を出力ファイルに書き出す
プログラムはこれらの処理に必要な機能を単純木と赤黒木を使った二種類の独立したモジュールとして用意し、それを同一インターフェースでメインプログラムから呼び出すように作る。メインプログラムはインターフェース仕様のみで作成され、モジュール内の実装詳細は隠蔽される。
単純木の実装ではnew/deleteによりメモリ領域の確保/解放を行なったが、これをスマートポインタにするとメモリ領域の確保/解放を明示的に記述する必要はなくなるがロスが大きい。赤黒木の実装はstd::setが赤黒木で実装されているのでそのまま使っている。
テンプレートクラスなので単一ヘッダーファイルにすべて収まる。
btree.h:
#include <deque>
#include <set>
#ifndef BTREE_H
#define BTREE_H
namespace ume {
template <typename T>
class BTree {
public:
virtual bool search(const T &value) const = 0;
virtual void insert(const T &value) = 0;
virtual int size() const = 0;
virtual std::deque<T> sort() const = 0;
virtual ~BTree() {}
};
template <typename T>
class SBTree : public BTree<T> {
private:
struct Node {
T data;
Node *left;
Node *right;
Node(const T &value) : data(value), left(nullptr), right(nullptr) {}
};
Node *root;
int numNodes;
bool search(Node *node, const T &value) const {
if (node == nullptr)
return false;
else if (value == node->data)
return true;
else if (value < node->data)
return search(node->left, value);
else
return search(node->right, value);
}
void insert(Node *&node, const T &value) {
if (node == nullptr) {
node = new Node(value);
numNodes++;
} else if (value < node->data)
insert(node->left, value);
else if (value > node->data)
insert(node->right, value);
else
;
}
void inorderTraversal(Node *node, std::deque<T> &result) const {
if (node == nullptr)
return;
inorderTraversal(node->left, result);
result.push_back(node->data);
inorderTraversal(node->right, result);
}
void destroyTree(Node *node) {
if (node == nullptr)
return;
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
public:
SBTree() : root(nullptr), numNodes(0) {}
bool search(const T &value) const override {
return search(root, value);
}
void insert(const T &value) override {
insert(root, value);
}
int size() const override {
return numNodes;
}
std::deque<T> sort() const override {
std::deque<T> result;
inorderTraversal(root, result);
return result;
}
~SBTree() {
destroyTree(root);
}
};
template <typename T>
class RBTree : public BTree<T> {
private:
std::set<T> rbTree;
public:
bool search(const T &value) const override {
return rbTree.find(value) != rbTree.end();
}
void insert(const T &value) override {
rbTree.insert(value);
}
int size() const override {
return rbTree.size();
}
std::deque<T> sort() const override {
std::deque<T> result;
for (const auto &value : rbTree)
result.push_back(value);
return result;
}
};
} // namespace ume
#endif // BTREE_H
Set.Makeファンクターを利用するために通常の「'a t」形式のpolymorphismを使うことができない。シグネチャはSet.Makeファンクターにより作られる型のシグネチャに合わせる形になる。赤黒木をスクラッチで書けば「'a t」形式を実現できるので興味ある方は挑戦してみていただきたい。
ソースファイル:btree.ml内に書かれたコードには自動的にモジュール名:Btreeが付与される。したがってSBTreeとRBTreeはBtree.SBTree, Btree.RBTreeという名前で参照される。
btree.ml:
module type BTree = sig
type elt
type t
val empty : t
val search : elt -> t -> bool
val insert : elt -> t -> t
val size : t -> int
val sort : t -> elt list
end
module SBTree : BTree with type elt = int = struct
type elt = int
type tree = Empty
| Node of elt * tree * tree
type t = tree
let empty = Empty
let rec search x = function
| Empty -> false
| Node (y, l, r) ->
if x < y then search x l
else if x > y then search x r
else true
let rec insert x = function
| Empty -> Node(x, Empty, Empty)
| Node(y, l, r) ->
if x < y then
Node(y, insert x l, r)
else if x > y then
Node(y, l, insert x r)
else
Node(y, l, r)
let rec size = function
| Empty -> 0
| Node(_, l, r) ->
1 + (size l) + (size r)
let sort tree =
let rec to_list lst = function
| Empty -> lst
| Node (v, l, r) ->
to_list (v :: to_list lst r) l in
to_list [] tree
end
module IntSet = Set.Make(Int)
module RBTree : BTree with type elt = int = struct
type elt = int
type t = IntSet.t
let empty = IntSet.empty
let search = IntSet.mem
let insert = IntSet.add
let size = IntSet.cardinal
let sort = IntSet.elements
end
Racketの場合、基本的にモジュール単位とコンパイル単位を一致させるという設計思想になっているのでそれに従って二つのファイルに分ける。
sbtree.rkt:
#lang racket
(provide empty-tree search insert size sort)
(struct node (value left right))
(define empty-tree empty)
(define (search x tree)
(cond
[(empty? tree) #f]
[(node? tree)
(let ([value (node-value tree)]
[left (node-left tree)]
[right (node-right tree)])
(cond
[(< x value) (search x left)]
[(> x value) (search x right)]
[else #t]))]
[else (error "Invalid tree.")]))
(define (insert x tree)
(cond
[(empty? tree) (node x empty empty)]
[(node? tree)
(let ([value (node-value tree)]
[left (node-left tree)]
[right (node-right tree)])
(cond
[(< x value) (node value (insert x left) right)]
[(> x value) (node value left (insert x right))]
[else tree]))]
[else (error "Invalid tree.")]))
(define (size tree)
(cond
[(empty? tree) 0]
[(node? tree)
(+ 1 (size (node-left tree)) (size (node-right tree)))]
[else (error "Invalid tree.")]))
(define (sort tree)
(define (to-list lst tree)
(cond
[(empty? tree) lst]
[(node? tree)
(to-list
(cons (node-value tree) (to-list lst (node-right tree)))
(node-left tree))]
[else (error "Invalid tree.")]))
(to-list '() tree))
rbtree.rkt:
#lang racket
(require data/red-black/ordered-set)
(provide empty-tree search insert size sort)
(define empty-tree (ordered-set))
(define (search x tree)
(ordered-set-member? tree x))
(define (insert x tree)
(ordered-set-add! tree x)
tree)
(define (size tree)
(ordered-set-count tree))
(define (sort tree)
(ordered-set->list tree))
単純木と赤黒木のメインプログラムを条件付きコンパイルを使って一つのソースにまとめている。
main.cpp:
#include "btree.h"
#include <chrono>
#include <deque>
#include <fstream>
#include <iostream>
#include <print>
#include <sstream>
#include <stdexcept>
bool test(const std::string &infile, const std::string &outfile) {
std::deque<long> lst;
// read file
auto start = std::chrono::high_resolution_clock::now();
std::ifstream fin(infile);
if (!fin) {
throw std::runtime_error("Could not open file for reading.");
return false;
}
int num;
while (fin >> num)
lst.push_back(num);
fin.close();
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration = end - start;
std::println("length = {}", lst.size());
std::println("read time: {:9.6f} [sec]", duration.count());
// make btree
start = std::chrono::high_resolution_clock::now();
#ifndef RBTREE
ume::SBTree<long> root;
#else
ume::RBTree<long> root;
#endif
for (long i : lst)
root.insert(i);
end = std::chrono::high_resolution_clock::now();
duration = end - start;
#ifndef RBTREE
std::println("simple btree nodes = {}", root.size());
#else
std::println("red-black btree nodes = {}", root.size());
#endif
std::println("make btree: {:9.6f} [sec]", duration.count());
// search
start = std::chrono::high_resolution_clock::now();
for (long i : lst)
if (root.search(i))
;
else
std::println("{} is not found.", i);
end = std::chrono::high_resolution_clock::now();
duration = end - start;
std::println("search time:{:9.6f} [sec]", duration.count());
// sort
start = std::chrono::high_resolution_clock::now();
std::deque<long> lst2 = root.sort();
end = std::chrono::high_resolution_clock::now();
duration = end - start;
std::println("sort time: {:9.6f} [sec]", duration.count());
// write file
start = std::chrono::high_resolution_clock::now();
std::ofstream fout(outfile);
if (!fout) {
throw std::runtime_error("Could not open file for writing.");
return false;
}
std::ostringstream buf;
for (long num : lst2)
buf << num << "\n";
fout << buf.str();
fout.close();
end = std::chrono::high_resolution_clock::now();
duration = end - start;
std::println("write time: {:9.6f} [sec]", duration.count());
return true;
}
int main(int argc, char *argv[]) {
try {
if (argc != 3) {
throw std::invalid_argument(
"Usage: main <infile> <outfile>");
}
std::string infile(argv[1]);
std::string outfile(argv[2]);
if (!test(infile, outfile))
std::println("An error has occurred.");
} catch (const std::logic_error &e) {
std::println(stderr, "Logic error: {}", e.what());
} catch (const std::runtime_error &e) {
std::println(stderr, "Runtime error: {}", e.what());
} catch (const std::exception &e) {
std::println(stderr, "Another std::exception: {}", e.what());
} catch (...) {
std::println(stderr, "Unknown exception.");
}
return 0;
}
上の一つのメインプログラムから単純木:smain_g, smain_l、赤黒木:rmain_g, rmain_lという四種類の実行ファイルを生成する。
makefile:
CPPG = g++
CPPL = clang++
CPPFLAGS = -std=c++23 -O2
HEADER = btree.h
SRC = main.cpp
EXES = smain_g smain_l rmain_g rmain_l
all: $(EXES)
smain_g: $(SRC) $(HEADER)
$(CPPG) $(CPPFLAGS) -o $@ $(SRC)
smain_l: $(SRC) $(HEADER)
$(CPPL) $(CPPFLAGS) -o $@ $(SRC)
rmain_g: $(SRC) $(HEADER)
$(CPPG) $(CPPFLAGS) -DRBTREE -o $@ $(SRC)
rmain_l: $(SRC) $(HEADER)
$(CPPL) $(CPPFLAGS) -DRBTREE -o $@ $(SRC)
clean:
rm -f $(EXES)
基準データ:uniform1m.txtで測定する。
$ measure ./smain_g uniform1m.txt sorted_sg.txt
length = 1000000
read time: 0.092537 [sec]
simple btree nodes = 995168
make btree: 0.900580 [sec]
search time: 0.683894 [sec]
sort time: 0.083510 [sec]
write time: 0.090753 [sec]
======================================
Process exited with status: 0
total time: 2.205251 [sec]
mem size: 68772 [KB]
code size: 140 [KB]
$ measure ./smain_l uniform1m.txt sorted_sl.txt
length = 1000000
read time: 0.095828 [sec]
simple btree nodes = 995168
make btree: 0.903665 [sec]
search time: 0.820304 [sec]
sort time: 0.081721 [sec]
write time: 0.088756 [sec]
======================================
Process exited with status: 0
total time: 2.330283 [sec]
mem size: 69624 [KB]
code size: 112 [KB]
$ measure ./rmain_g uniform1m.txt sorted_rg.txt
length = 1000000
read time: 0.096370 [sec]
red-black btree nodes = 995168
make btree: 0.902321 [sec]
search time: 0.903060 [sec]
sort time: 0.141716 [sec]
write time: 0.093211 [sec]
======================================
Process exited with status: 0
total time: 2.509102 [sec]
mem size: 84796 [KB]
code size: 143 [KB]
$ measure ./rmain_l uniform1m.txt sorted_rl.txt
length = 1000000
read time: 0.092469 [sec]
red-black btree nodes = 995168
make btree: 0.953849 [sec]
search time: 0.557808 [sec]
sort time: 0.142052 [sec]
write time: 0.091097 [sec]
======================================
Process exited with status: 0
total time: 2.213777 [sec]
mem size: 85988 [KB]
code size: 113 [KB]
基準データ:uniform1m.txtは一様分布なので単純木と赤黒木の差はでない。これを基準データ:normal1m.txtに変えると差がでるように思われたがあまり差がでなかったので今回の実験はuniform1m.txtのみとする。正規分布ではなくもっと偏った分布にすべきであった。
単純木と赤黒木のメインプログラムを条件付きコンパイルを使って一つのソースにまとめている。ソースにはプリプロセッサ:cppo用のプリプロセッサマクロが埋め込まれている。
main.ml:
open Printf
#ifndef RBTREE
module BT = Btree.SBTree
#else
module BT = Btree.RBTree
#endif
let read_data filename =
let ichan = open_in filename in
let rec read_lines acc =
match input_line ichan with
| line ->
let num = int_of_string line in
read_lines (num :: acc)
| exception End_of_file ->
close_in ichan;
List.rev acc in
read_lines []
let write_data filename lst =
let ochan = open_out filename in
List.iter (fun x -> fprintf ochan "%d\n" x) lst;
close_out ochan
let test infile outfile =
(* read file *)
let start = Unix.gettimeofday () in
let lst = read_data infile in
let end_ = Unix.gettimeofday () in
printf "length = %d\n" (List.length lst);
printf "read time: %9.6f [sec]\n" (end_ -. start);
(* make btree *)
let start = Unix.gettimeofday () in
let root = List.fold_left (fun acc x -> BT.insert x acc) BT.empty lst in
let end_ = Unix.gettimeofday () in
#ifndef RBTREE
printf "simple btree nodes = %d\n" (BT.size root);
#else
printf "red-black btree nodes = %d\n" (BT.size root);
#endif
printf "make btree: %9.6f [sec]\n" (end_ -. start);
(* search *)
let start = Unix.gettimeofday () in
List.iter
(fun v ->
if (BT.search v root) then ()
else printf "%d is not found.\n" v)
lst;
let end_ = Unix.gettimeofday () in
printf "search time:%9.6f [sec]\n" (end_ -. start);
(* sort *)
let start = Unix.gettimeofday () in
let lst2 = BT.sort root in
let end_ = Unix.gettimeofday () in
printf "sort time: %9.6f [sec]\n" (end_ -. start);
(* write file *)
let start = Unix.gettimeofday () in
write_data outfile lst2;
let end_ = Unix.gettimeofday () in
printf "write time: %9.6f [sec]\n" (end_ -. start)
let () =
try
if Array.length Sys.argv <> 3 then
raise (Invalid_argument
"Usage: main <infile> >outfile>")
else
let infile = Sys.argv.(1) in
let outfile = Sys.argv.(2) in
test infile outfile
with
| Invalid_argument msg ->
eprintf "Logic error: %s\n" msg
| Failure msg ->
eprintf "Runtime error: %s\n" msg
| exn ->
eprintf "Another exception: %s\n" (Printexc.to_string exn)
makefile:
OCAMLOPT = ocamlopt
OCAMLFLAGS = -O2
LIBPATH = -I +unix
LIBS = unix.cmxa
SRCS = btree.ml main.ml
PPS = -pp "cppo"
PPR = -pp "cppo -D RBTREE"
EXES = smain rmain
all: $(EXES)
smain: $(SRCS)
$(OCAMLOPT) $(OCAMLFLAGS) $(PPS) $(LIBPATH) -o $@ $(LIBS) $(SRCS)
rmain: $(SRCS)
$(OCAMLOPT) $(OCAMLFLAGS) $(PPR) $(LIBPATH) -o $@ $(LIBS) $(SRCS)
clean:
rm -f $(EXES) *.o *.cmx *.cmi
基準データ:uniform1m.txtで測定する。
$ measure ./smain uniform1m.txt sorted_s.txt
length = 1000000
read time: 0.278736 [sec]
simple btree nodes = 995168
make btree: 1.670094 [sec]
search time: 0.724873 [sec]
sort time: 0.113147 [sec]
write time: 0.251380 [sec]
======================================
Process exited with status: 0
total time: 3.091865 [sec]
mem size: 164096 [KB]
code size: 3357 [KB]
$ measure ./rmain uniform1m.txt sorted_r.txt
length = 1000000
read time: 0.272368 [sec]
red-black btree nodes = 995168
make btree: 1.949673 [sec]
search time: 0.858106 [sec]
sort time: 0.115870 [sec]
write time: 0.241498 [sec]
======================================
Process exited with status: 0
total time: 3.488585 [sec]
mem size: 176652 [KB]
code size: 3357 [KB]
メインプログラムの先頭で使用するモジュールを指定する。その際、モジュール間で名前が衝突しないようにprefix-inで名前空間を指定することができる。
smain.rkt:
#lang racket
(require iso-printf)
(require (prefix-in bt: "sbtree.rkt"))
(define (read-data filename)
(call-with-input-file filename
(lambda (port)
(let loop ([lst '()])
(let ([line (read-line port)])
(if (eof-object? line)
(reverse lst)
(loop (cons (string->number line) lst))))))))
(define (write-data filename lst)
(call-with-output-file filename #:exists 'replace
(lambda (port)
(for-each (lambda (num) (displayln num port))
lst))))
(define (test infile outfile)
; read file
(define start (current-inexact-milliseconds))
(define lst (read-data infile))
(define end (current-inexact-milliseconds))
(printf "length = %d\n" (length lst))
(printf "read time: %9.6f [sec]\n" (/ (- end start) 1000.0))
; make btree
(set! start (current-inexact-milliseconds))
(define root (foldl bt:insert bt:empty-tree lst))
(set! end (current-inexact-milliseconds))
(printf "simple btree nodes = %d\n" (bt:size root))
(printf "make btree: %9.6f [sec]\n" (/ (- end start) 1000.0))
; search
(set! start (current-inexact-milliseconds))
(for ([i lst])
(if (bt:search i root)
(void)
(printf "%d is not found.\n" i)))
(set! end (current-inexact-milliseconds))
(printf "search time:%9.6f [sec]\n" (/ (- end start) 1000.0))
; sort
(set! start (current-inexact-milliseconds))
(define lst2 (bt:sort root))
(set! end (current-inexact-milliseconds))
(printf "sort time: %9.6f [sec]\n" (/ (- end start) 1000.0))
; write file
(set! start (current-inexact-milliseconds))
(write-data outfile lst2)
(set! end (current-inexact-milliseconds))
(printf "write time: %9.6f [sec]\n" (/ (- end start) 1000.0)))
(define (main args)
(with-handlers
([exn:fail? (λ (e) (eprintf "%s\n" (exn-message e)))]
[exn? (λ (e) (eprintf "Unexpected: %s\n" (exn-message e)))])
(cond
[(not (= (vector-length args) 2))
(error "Usage: main <infile> <outfile>")]
[else
(let ([infile (vector-ref args 0)]
[outfile (vector-ref args 1)])
(test infile outfile))])))
(main (current-command-line-arguments))
基準データ:uniform1m.txtで測定する。
$ raco exe smain.rkt
$ measure ./smain uniform1m.txt sorted_s.txt
length = 1000000
read time: 0.774853 [sec]
simple btree nodes = 995168
make btree: 2.366238 [sec]
search time: 1.077546 [sec]
sort time: 0.082800 [sec]
write time: 0.885487 [sec]
======================================
Process exited with status: 0
total time: 5.713926 [sec]
mem size: 210428 [KB]
code size: 12463 [KB]
rmain.rkt(smain.rktで二行変更):
(require (prefix-in bt: "rbtree.rkt"))
(printf "red-black btree nodes = %d\n" (bt:size root))
基準データ:uniform1m.txtで測定する。
$ raco exe rmain.rkt
$ measure ./rmain uniform1m.txt sorted_r.txt
length = 1000000
read time: 0.778972 [sec]
red-black btree nodes = 995168
make btree: 3.642388 [sec]
search time: 2.010633 [sec]
sort time: 0.050583 [sec]
write time: 0.936998 [sec]
======================================
Process exited with status: 0
total time: 7.910118 [sec]
mem size: 264992 [KB]
code size: 12729 [KB]
測定結果を表にまとめる。単位は秒[sec]。
| 測定項目 | GCC | Clang | OCaml | Racket | |
|---|---|---|---|---|---|
| 単純木 | read file | 0.093 | 0.096 | 0.279 | 0.775 |
| make btree | 0.901 | 0.904 | 1.670 | 2.366 | |
| search | 0.684 | 0.820 | 0.725 | 1.078 | |
| sort | 0.084 | 0.082 | 0.113 | 0.083 | |
| write file | 0.091 | 0.089 | 0.251 | 0.885 | |
| 赤黒木 | read file | 0.096 | 0.092 | 0.272 | 0.779 |
| make btree | 0.902 | 0.954 | 1.950 | 3.642 | |
| search | 0.903 | 0.558 | 0.858 | 2.011 | |
| sort | 0.142 | 0.142 | 0.116 | 0.051 | |
| write file | 0.093 | 0.091 | 0.241 | 0.937 | |
RacketのsortはC++並みあるいはそれ以上速い。
This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani