Mercurial > hg > Papers > 2017 > tatsuki-master
comparison indexupdate.tex @ 13:7acd7d5afeb6
commit
| author | tatsuki |
|---|---|
| date | Tue, 07 Feb 2017 18:50:35 +0900 |
| parents | 498b8f4175f9 |
| children | 33d8077a5d45 |
comparison
equal
deleted
inserted
replaced
| 12:04aa9dcd29c9 | 13:7acd7d5afeb6 |
|---|---|
| 3 そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。 | 3 そのため、Commitを行うたび、O(n)のIndexのUpdateが入り、木の編集時大きなネックとなっていた。 |
| 4 なので、高速にIndexの更新を行う差分アップデートを実装した。 | 4 なので、高速にIndexの更新を行う差分アップデートを実装した。 |
| 5 | 5 |
| 6 \section{差分 Updateの実装} | 6 \section{差分 Updateの実装} |
| 7 Indexの差分 Updateを行うためには、編集を行ったノードを覚えておく必要がある。 | 7 Indexの差分 Updateを行うためには、編集を行ったノードを覚えておく必要がある。 |
| 8 なので、Jungleの木に編集を行ったノードをリストに格納する。 | 8 Jungleの木に編集を行ったノードをリストに格納する。 |
| 9 そして、Commit時にリストにあるノードと、そのノードまでの経路にあるノードに対して、IndexをのUpdateを行う。 | 9 そして、Commit時にリストにあるノードと、そのノードまでの経路にあるノードに対して、IndexをのUpdateを行う。 |
| 10 | 10 |
| 11 Indexの Update は、ノードの削除とノードの挿入の２つのプロセスで行われる。 | 11 Indexの Update は、ノードの削除とノードの挿入の２つのプロセスで行われる。 |
| 12 | 12 |
| 13 \section{Indexの中身の削除} | 13 \section{Indexの中身の削除} |
| 39 \end{enumerate} | 39 \end{enumerate} |
| 40 | 40 |
| 41 | 41 |
| 42 \section{Full Update との使い分け} | 42 \section{Full Update との使い分け} |
| 43 Indexの差分Updateは、不要なノードの削除と新しく木に追加されたノードの挿入を行っているため、1ノードに対する処理は Full Updateより大きい。 | 43 Indexの差分Updateは、不要なノードの削除と新しく木に追加されたノードの挿入を行っているため、1ノードに対する処理は Full Updateより大きい。 |
| 44 そのため、少ない編集後の Commit は、差分Updateの方が高速に行えるが、多くの編集を行った後の Commitだと、Full Updateの方が高速に動作する。 | 44 少ない回数編集を行った後の Commit は、差分Updateの方が高速に行えるが、多くの編集を行った後の Commitだと、Full Updateの方が高速に動作する可能性がある。 |
| 45 なので、木の編集回数によって、Indexの更新方法を変更する必要がある。 | 45 そのため、Commit 前の、木の編集回数によって、Indexの更新方法を変更したほうが高速に Update を行える可能性がある。 |
| 46 | 46 これに関しての検証は、性能測定の章に記述する。 |
| 47 | 47 |
| 48 \newpage | 48 \newpage |