2

バイナリ データの多数の連続したフレームで構成されるビデオ ファイルがあります。各フレームには一意のタイムスタンプもあります (これはファイル内の連続番号ではなく、記録時にカメラによって提供される値です)。一方、そのフレームの連番に基づいてそのフレームを取得する API 関数があります。物事をもう少し複雑にするために、タイムスタンプが提供され、そのフレームのバイナリデータを取得する必要があるプレーヤーがいます。

ここでもう 1 つ悲しいことがあります。タイムスタンプは連続していません。それらは連続することができますが、保証されていません。したがって、一連のタイムスタンプは、54567、54568、...、65535、65536、... または
54567、54568、 ...、65535、0、1、... のいずれかになります。

したがって、次のようになります。

Frame 0
timestamp 54567
binary data
........
Frame 1
timestamp 54569
binary data
........
Frame 2
timestamp 54579
binary data
.
.
.
Frame n
timestamp m
binary data

0 <= n <= 65536 (MAX_UNSIGNED_SHORT)
0 <= m <= MAX_UNSIGNED_INT

クリップ プレーヤー API は、タイムスタンプによってバイナリ フレームを取得できる必要があります。ただし、内部的には、フレームの連番だけでフレームを取得できます。したがって、timestamp を求められた場合は、timestampを持つフレームを見つけるために、フレームmを反復処理する必要があります。nm

最適化するために、インデックス ファイルを作成することにしました。これにより、タイムスタンプとフレームの連続番号が一致します。そして、ここに私の質問があります：

現在、私のインデックス ファイルは2*sizeof(unsigned int)、タイムスタンプとフレームの連続番号を含む size のバイナリ ペアで構成されています。Player は後で、そのファイルから , を使用して作成しstl mapます。key==timestampvalue==frame sequential number

より効率的に行う方法はありますか？インデックス ファイルを何らかのデータ構造のダンプとして作成し、後でクリップを開くときにクリップ プレーヤーによってメモリにロードできるようにする必要があります。これにより、フレームへの O(1) アクセスが可能になります。他の提案はありますか？

更新:

名前と要件を更新しました (タイムスタンプは必ずしも連続しているわけではなく、フレーム番号は MAX_UNSIGNED_SHORT 値で制限されています)。また、すでに時間を割いて回答してくれたすべての人に感謝したいと思います。補間検索は興味深いアイデアですが、自分で試したことはありません。O(1)問題は、実行中と実行中のデルタになると思いO(log log N)ます。

4

3 に答える 3

1

次の前提を立てることができるように思われます: a) ビデオ ファイル自体は、作成後に変更されない b) プレーヤーは連続したフレームを検索する場合がある、つまり、通常の再生を行っている場合 c) プレーヤーがランダムなフレームを見つけたい、つまり FF、REW を実行している、またはチャプターごとにスキップしている場合

これを考えると、フレーム ID とフレーム インデックスを関連付ける HashMap を実行しないのはなぜでしょうか? 一度それを作成すると、プレーヤーはそれを読み取ることができ、要求されたフレームの簡単で時間制限のあるルックアップを行うことができます。

于 2013-03-07T16:08:55.430 に答える
0

ここで行うべき一連のトレードオフがあります。

インデックス ファイルは、既にデータ構造のダンプである配列です。フレームを頻繁に挿入または削除する予定がなく、この配列をソートされた順序に保つ場合は、配列に対して ( を使用して) 二分探索を行うのは簡単std::binary_searchです。挿入と削除は O(N) かかりますが、検索は O(log N) です。配列がメモリ内で占有するスペースが少なくなり、インデックス ファイルからの読み取りと書き込みが高速になります。

フレームの挿入と削除を頻繁に行っている場合は、std::map構造に変換するとパフォーマンスが向上します。フレームの数が多い場合、またはフレームと共にさらに多くのメタデータを保存したい場合は、B ツリー構造を調べるか、 SqliteやBerkeleyDBなどの組み込みデータベースを使用することをお勧めします。これらはどちらも B ツリー インデックスを実装しており、十分にテストされたコードです。

于 2013-03-07T16:03:05.767 に答える
0

インデックスがフレーム番号を表す配列にフレーム データを格納するだけです。次に、カメラ インデックスからフレーム番号へのハッシュ マップを作成します。現在のアプローチよりもメモリをほとんど使用せずに、O(1) のフレーム番号またはカメラ インデックスに属するフレームを取得できます。

または、(カメラ インデックス、データ) ペアを格納するフレーム番号でインデックス付けされた配列を維持し、カメラ インデックスでアクセスする必要がある場合に O(log n) 二分探索を実行することもできます。これは、カメラのインデックスがソートされているという事実を利用しています。

C++ の標準ライブラリでstd::unordered_mapは、ツリーベースstd::map(O(log n) を使用) lookup) は、おそらくこの目的には十分です。

二分探索の実装は として入手できますstd::binary_search。

于 2013-03-07T16:28:46.037 に答える