Mercurial > hg > Papers > 2017 > tatsuki-master

comparison benchMark.tex @ 18:d5306971efbf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
eng abst
author tatsuki
date Fri, 10 Feb 2017 10:24:52 +0900
parents 4d66607c369c
children 4365c210d1cb
comparison
equal deleted inserted replaced
17:4d66607c369c 18:d5306971efbf
26 26
27 \newpage 27 \newpage
28 28
29 \section{TreeMapの測定} 29 \section{TreeMapの測定}
30 5章で実装した TreeMap の性能測定を行う。 30 5章で実装した TreeMap の性能測定を行う。
31 比較対象には、 TreeMap 実装前に Jungle 使用していた Functional Java の TreeMap を使用する。 31 比較対象には、 TreeMap 実装前に Jungle で使用していた Functional Java の TreeMap を使用する。
32 32
33 図\ref{find}は、 TreeMap に対する値の Get のベンチマークである。 33 図\ref{find}は、 TreeMap に1000回の Get を行った際のベンチマークである。
34 TreeMap に対して1000回行う際の時間を測定した。
35 X 軸は Get を行う TreeMap のノード数。 34 X 軸は Get を行う TreeMap のノード数。
36 Y 軸は かかった時間を表す 35 Y 軸は Get にかかった時間を表す
37 36
38 \begin{figure}[htpb] 37 \begin{figure}[htpb]
39 \begin{center} 38 \begin{center}
40 \includegraphics[scale=0.6,angle=-90]{result/treemap/find.pdf} 39 \includegraphics[scale=0.6,angle=-90]{result/treemap/find.pdf}
41 \caption{TreeMap への Get} 40 \caption{TreeMap への Get}
43 \label{find} 42 \label{find}
44 \end{figure} 43 \end{figure}
45 44
46 \ref{find}より、Functional Java の TreeMap と比較して、 Jungle の TreeMap の方が非常に高速に動いている。 45 \ref{find}より、Functional Java の TreeMap と比較して、 Jungle の TreeMap の方が非常に高速に動いている。
47 理由として、Jungle の TreeMap は、検索対象の値を持つノードを、二分探索木の探索アルゴリズムに則り探索するのに対し、 46 理由として、Jungle の TreeMap は、検索対象の値を持つノードを、二分探索木の探索アルゴリズムに則り探索するのに対し、
48 Functional Java の TreeMap は、検索対象のノードがルートに来る木を構築し、ルートを返す。といったアルゴリズムを採用していため、 47 Functional Java の TreeMap は、検索対象のノードがルートになる木を構築し、ルートを返す。といったアルゴリズムを採用していため、
49 探索アルゴリズムの差が図\ref{find}の結果に出た。 48 探索アルゴリズムの差が図\ref{find}の結果に出た。
50 その他の処理についても、Jungleの TreeMap の方が高速に動作していた。 49 その他の処理についても、Jungleの TreeMap の方が高速に動作していた。
51 50
52 \newpage 51 \newpage
53 \section{Index の差分 Update の測定} 52 \section{Index の差分 Update の測定}
68 図\ref{index}より、Index の Full Update は、グラフがO(n\verb|^|2)なのに対し、 差分 Update は、O(n)で行えている。 67 図\ref{index}より、Index の Full Update は、グラフがO(n\verb|^|2)なのに対し、 差分 Update は、O(n)で行えている。
69 68
70 しかし、Jungleでは木に変更を加える際、毎回 Commit を行うわけでなく、 基本的に複数回変更を行った後、一気にCommit を行う。 69 しかし、Jungleでは木に変更を加える際、毎回 Commit を行うわけでなく、 基本的に複数回変更を行った後、一気にCommit を行う。
71 差分 Update は、変更を加えたノードを記憶し、 Commit 時に Index の更新を行う。 70 差分 Update は、変更を加えたノードを記憶し、 Commit 時に Index の更新を行う。
72 一方、Full Update では、 Commit を行うまでに木に加えた変更の数に関係なく、新しい Index を構築する。 71 一方、Full Update では、 Commit を行うまでに木に加えた変更の数に関係なく、新しい Index を構築する。
73 よって、 Commit を行うまでに行う木の編集回数が増えた場合、 Index の Full Update と 差分 Update では、Full Update の方が、Index の Update にかかる時間の短縮率が大きい。 72 よって、 Commit を行うまでに行う木の編集回数が増えた場合、 Index の Full Update と 差分 Update では、差分 Update の方が、Index に対して多くの変更を行うことになる。
74 そのため、Commit を行うまでの 木に対する変更回数によっては、 Full Update の方が高速に Index の構築を行える可能性がある。 73 そのため、Commit を行うまでの 木に対する変更回数によっては、 Full Update の方が高速に Index の構築を行える可能性がある。
75 74
76 そこで、図\ref{index2}に、Commit を行うまでに行った木の編集回数と、 Index の Update 速度の測定結果を記述する。 75 そこで、図\ref{index2}に、Commit を行うまでに行った木の編集回数と、 Index の Update 速度の測定結果を記述する。
77 X軸は、1回の Commit を行うまでに木に行った変更のセット回数。 76 X軸は、1回の Commit を行うまでに木に行った変更のセット回数。
78 Y軸は、Commit にかかった時間を表す。 77 Y軸は、Commit にかかった時間を表す。
87 86
88 図\ref{index2} より、Commit の前に行った木の編集回数に関係なく、基本的に Index の更新は差分 Update の方が早いことがわかった。 87 図\ref{index2} より、Commit の前に行った木の編集回数に関係なく、基本的に Index の更新は差分 Update の方が早いことがわかった。
89 88
90 89
91 \newpage 90 \newpage
92 \section{正順線形木の構築時間の測定} 91 \section{正順の線形木の構築時間の測定}
93 7章で実装した、 Differential Jungle Tree の性能測定を行う。 92 7章で実装した、 Differential Jungle Tree の性能測定を行う。
94 比較対象は、Default Jungle Tree を用いる。 93 比較対象は、Default Jungle Tree を用いる。
95 図\ref{dfTree}は、正順の木を構築するまでにかかった時間のベンチマークである。 94 図\ref{dfTree}は、正順の木を構築するまでにかかった時間のベンチマークである。
96 X 軸は、構築した木のノード数。 95 X 軸は、構築した木のノード数。
97 Y 軸は、構築にかかった時間を表す。 96 Y 軸は、構築にかかった時間を表す。
98 また、木を構築する正確な時間を測定するため、Index は作っていない。 97 また、木のみを構築する時間を測定するため、Index は作っていない。
99 98
100 \begin{figure}[htpb] 99 \begin{figure}[htpb]
101 \begin{center} 100 \begin{center}
102 \includegraphics[scale=0.6]{result/createListTree.pdf} 101 \includegraphics[scale=0.6]{result/createListTree.pdf}
103 \caption{Differential Tree と Default Jungle Tree} 102 \caption{Differential Tree と Default Jungle Tree}
104 \label{dfTree} 103 \label{dfTree}
105 \end{center} 104 \end{center}
106 \end{figure} 105 \end{figure}
107 106
108 図\ref{dfTree}より、Default Jungle Tree より、Differential Jungle Tree の方が高速に木の構築している。 107 図\ref{dfTree}より、Default Jungle Tree より、Differential Jungle Tree の方が高速に木の構築している。
109 これは、Default Jungle Tree が、木を構築する際に複製を行うのに対し、Differential Jungle Tree は破壊的に木を構築しているからである。 108 これは、Default Jungle Tree が、木を構築する際に複製を行うのに対し、Differential Jungle Tree は複製を行っていないからである。
109 期待通りの結果が出たといえる。
110
110 111
111 \section{Red Black Jungle Tree の測定} 112 \section{Red Black Jungle Tree の測定}
112 8章で実装した、Red Black Jungle Tree の性能測定を行う。 113 8章で実装した、Red Black Jungle Tree の性能測定を行う。
113 比較対象は、Default Jungle Tree を用いる。 114 比較対象は、Default Jungle Tree を用いる。
114 図\ref{redblack}は、正順の木を構築するまでにかかった時間のベンチマークである。 115 図\ref{redblack}は、正順の木を構築するまでにかかった時間のベンチマークである。