私は 10 エントリの固定長テーブルを管理しています。各項目は 4 つのフィールドのような構造です。数値位置で指定された挿入、更新、削除操作があります。この情報テーブルを管理するために使用する最適なデータ構造はどれかと思っています。
配列 - 挿入/削除はシフトのため線形時間がかかります。更新には一定時間がかかります。ポインターにはスペースは使用されません。[] を使用して項目にアクセスすると高速になります。
stl ベクター - 挿入/削除はシフトのため線形時間がかかります。更新には定数時間がかかります。ポインターにはスペースは使用されません。項目へのアクセスは、operator[] とリンク リストの呼び出しであるため、配列よりも遅くなります。
stl リスト - 挿入と削除には、挿入/削除を適用する前に特定の位置まで反復処理する必要があるため線形時間がかかります。ポインター用に追加のスペースが必要です。リンク リストの線形トラバーサルであるため、項目へのアクセスは配列よりも遅くなります。
現時点では、配列を使用するという選択をしています。これは正当なのでしょうか? それとも、何か見落としているのでしょうか?
リストを走査してからノードを挿入するのと、配列内の項目をシフトして空の位置を生成してからその位置に項目を挿入するのとでは、どちらが速いでしょうか?
このパフォーマンスを測定する最適な方法は何ですか? 操作の前後のタイムスタンプを表示するだけでよいですか?
ベストアンサー1
STLを使用するvectorと同様に豊富なインターフェースを提供しlist、配列に必要なメモリを管理する手間を省きます。
パフォーマンス コストを明らかにするには非常に努力する必要があります。operator[]通常はインライン化されます。
具体的な数字はわかりませんが、挿入や削除でも (もちろん、一定のサイズ以下) がvector<int>よりも高速であるというパフォーマンス分析を読んだことを覚えていますlist<int>。実際のところ、私たちが使用しているプロセッサは非常に高速で、ベクトルが L2 キャッシュに収まる場合は、非常に高速になります。一方、リストはヒープ オブジェクトを管理する必要があり、これが L2 を殺します。