-1

2 つのベクトルがvector<DataPoint> dataあり、vector<string> labelswhereDataPointは単なる float のベクトルです: typedef vector<float> DataPoint。各データポイントdata[i]には、関連付けられたラベルがありlabels[i]ます。

特定のデータポイントのラベルxをすばやく取得する方法はありますか? string getLabel(DataPoint x){..}どちらが速いかのようなもの。

4

3 に答える 3

2

ベクトルがソートされている場合、DataPointのインデックスを見つけることが期待できる最善の方法dataはO(log(n))、(二分探索を使用して) 複雑さです。それ以外の場合は、線形検索です。dataO(n)

問題の核心は、関連するデータを含む 2 つのベクトルがあることです。これは常に管理が面倒です (そして、悪い設計の強いヒントです)。両方のベクトルを a (aと avector<LabeledDataPoints>の 2 つのメンバーを持つ構造体) に置き換えるのが最適です。DataPointstring

于 2013-10-28T11:43:41.367 に答える
0

いくつかの注意: でベクトルを並べ替えstd::sort()、事前に並べ替えられたベクトルを で検索std::binary_search()できます。std::unordered_mapは C++11 ハッシュ テーブルstd::mapです。挿入と消去。ドキュメントについては、それらのいずれかをGoogleで検索してください。

既存のデータ構造では、dataPoint が事前に並べ替えられている場合、N が dataPoint.size() である O(log2N) があり、平均的に等しくない dataPoints 比較で最初の float または two を比較するだけでよいと仮定します。ソートされていない、O(N) です。

data明らかに、パフォーマンスの問題は、共通のインデックスが判明した後にラベルを調べる必要がないことです。ベクトルの外側にある dataPoint オブジェクトが与えられた場合に、そのインデックスが何であるかを調べるだけです。

並べ替えが望ましくない場合、または O(log2N) がまだ遅すぎる場合は、dataPoints をラベル付きのハッシュ テーブルに入れることを検討できます。

まれに、パフォーマンスの問題が dataPoints が定期的に同じフロートの先頭シーケンスで始まることが原因であるというまれなケースでは、(ベクトルの後ろから前に向かって比較するような簡単な解決策がないと仮定して) 何らかの種類のハッシュまたは最初に比較する要素の合計。既に等しいことがわかっている場合にのみ、float ごとの比較を行います。

于 2013-10-28T11:54:31.293 に答える