1

なぜこれをやろうとしているのかについていくつかの文脈を述べますが、最終的には文脈は無視することができます.なぜなら、それは主に古典的なコンピュータサイエンスとC ++の問題だからです.何も起きなかった…）

私は (大規模な) リアルタイム ストリーミング ポイント クラウドを扱っており、複数のセンサーから 2/3/4 ポイント クラウドを取得し、それらを結合して 1 つの大きなポイント クラウドを作成する必要がある場合があります。私は、実際には 1 つの構造ですべてのデータが必要な状況にいますが、通常、点群を視覚化するだけの場合は、ビューアーに個別にフィードすることで回避できます。

私は Point Cloud Library 1.6 を使用しています。よく調べてみると、そのPointCloud クラス(<pcl/point_cloud.h>興味がある場合は下) がすべてのデータ ポイントを STL ベクトルに格納しています。

今、バニラの CS ランドに戻ってきました...

PointCloud には、ある点群の内容を別の点群に追加するための += 演算子があります。ここまでは順調ですね。しかし、この方法はかなり非効率的です - 私が正しく理解していれば、1) ターゲット ベクトルのサイズを変更し、次に 2) 他のベクトルのすべてのポイントを実行し、それらをコピーします。

これは O(n) 時間の複雑さのケースのように見えます。通常はそれほど悪くないかもしれませんが、クラウドごとに少なくとも 300K ポイントをリアルタイムで処理する場合は悪いニュースです。

ベクトルをソートしたり分析したりする必要はなく、メモリ レベルで「くっつける」だけでよいため、プログラムは、最初のベクトルの最後に到達すると、最初のベクトルの開始位置にジャンプする必要があることを認識します。 2番目のもの。つまり、O(1) ベクトルのマージ方法を探しています。STLでこれを行う方法はありますか? それとも、std::list#splice のようなもののドメインですか?

注: このクラスは PCL のかなり基本的な部分であるため、「非侵襲的手術」が望ましいです。クラス自体に変更を加える必要がある場合 (ベクトルからリストへの変更、メモリの予約など)、PCL の残りの部分への影響を考慮する必要があり、広範囲に及ぶ可能性があります。

更新: PCL の GitHub リポジトリにイシューを提出し、以下の提案についてライブラリの作成者と議論するようにしました。どのアプローチを採用するかについて何らかの解決策が得られたら、関連する提案を回答として受け入れます。

4

7 に答える 7

8

ベクトルはリストではなく、シーケンスを表しますが、要素を連続したメモリに格納する必要があるという追加の要件があります。オブジェクトを移動せずに、2 つのベクトル (バッファーが連続しない) を 1 つのベクトルにまとめることはできません。

于 2013-07-25T16:08:21.247 に答える
6

この問題は、以前は String Rope クラスなどで何度も解決されてきました。

基本的なアプローチは、点群へのポインターを格納する新しいコンテナー タイプを作成することです。これは std::deque に似ていますが、可変サイズのチャンクが含まれる点が異なります。クラウドが標準サイズにチャンクしない限り?

この新しいコンテナを使用すると、イテレータは最初のチャンクで開始し、最後まで進んでから次のチャンクに移動します。このような可変サイズのチャンクを持つコンテナでランダム アクセスを行うには、バイナリ検索が必要です。実際、このようなデータ構造は、歪んだ形の B+ ツリーとして記述できます。

于 2013-07-25T16:08:05.297 に答える
3

いいえ、単純なリンクで 2 つのベクトルを連結することはできません。実際にそれらをコピーする必要があります。

でも！要素タイプに移動セマンティクスを実装すると、要素に含まれるものによっては、大幅な速度向上が得られる可能性があります。要素に重要な型が含まれていない場合、これは役に立ちません。さらに、必要なメモリを事前に確保しておくと、サイズ変更を必要としないため、スピードアップにも役立ちます (これにより、望ましくない巨大な新しい割り当てが発生し、そのメモリ サイズでデフラグが必要になる可能性があります。巨大な memcpy)。

それを除けば、リストの各「要素」が 10k 要素のベクトルである、リンクされたリストとベクトルの間のある種の混合を作成したいかもしれません。動的に成長しやすくなり、連結が簡単になります。

std::list<std::vector<element>> forIllustrationOnly; //Just roll your own custom type.

index = 52403;

listIndex = index % 1000
vectorIndex = index / 1000

forIllustrationOnly[listIndex][vectorIndex] = still fairly fast lookups
forIllustrationOnly[listIndex].push_back(vector-of-points) = much faster appending and removing of blocks of points.
于 2013-07-25T16:07:59.833 に答える
2

ベクトルでは、コピーを回避できないため、このスケーリング動作はベクトルでは得られません。また、一定時間内に任意の量のデータをコピーすることはできません。

PointCloud についてはわかりませんが、リンクされたリストなどの他のリスト タイプを使用できる場合、この動作は十分に可能です。ご想像のとおり、お使いの環境で機能し、2 番目のリストを最初のリストの最後に単純に貼り付けることができる連結リストの実装が見つかるかもしれません。

于 2013-07-25T16:07:52.363 に答える
1

http://www.boost.org/doc/libs/1_54_0/libs/range/doc/html/range/reference/utilities/join.htmlでブースト範囲ジョイントを見てください。

これは 2 つの範囲を取り、それらを結合します。vector1 と vector 2 があるとします。

あなたは書くことができるはずです

auto combined = join(vector1,vector2).

その後、必要に応じてアルゴリズムなどと組み合わせて使用​​できます。

于 2013-07-25T18:59:16.227 に答える
0

ベクトルの O(1) コピーはありませんが、確認する必要があります。

  • 要素の型は簡単にコピーできますか? (別名memcpy)
  • 私のvector実装はこの事実を利用していますか、それとも 300k 要素すべてを愚かにループして、要素ごとに簡単な割り当て (またはさらに悪いことに、copy-ctor-call) を実行していますか?

私が見たのは、memcpyループへの代入と同様に O(n) の複雑さがありますが、活用するソリューションmemcpyははるかに高速になる可能性があるということです。

したがって、問題は、ベクトルの実装が自明な型に対して最適ではない可能性があります。

于 2013-07-26T09:00:02.990 に答える