boostorg / boostorg/graph

astar_search does unnecessary initialization of vertices

オープン
#356 コメント 2 件 リアクション 1 件 担当者 0 名 GitHub で見る
performance
主要言語
C++
スター
392
フォーク
239
平均マージ
1日 11分
マージ済み PR(30日)
20

説明

From [Keith Bennet](https://github.com/boostorg/graph/wiki/Feedback-submissions-from-the-Boost-User-mailing-list#keith-bennett):
> astar_search() takes too much time to initialize all vertices (in a 2048x2048x40 matrix) even though we only need to initialize vertices when they are added to the open set. We ensure our data's initialization state is identical to a default-constructed object, then guarantee that the vertex initialization is done when the vertex is first added to the open set, and of course A* ensures that vertices aren't used until they're added to the open set (eg, when they're first discovered). To make resizing containers quicker, we ensure that our default-constructed objects are trivially-constructible so that resizing the underlying containers to match the matrix size does not require invoking expensive constructors which effectively reduces the initialization requirements to just resizing the containers correctly and setting the non-zero start-point state and end-point state.

コントリビューションガイド

コントリビューションガイドを開く

評価

この issue はまだ評価されていません。

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。