6

特定のクエリ ポイントに最も近いポイントのリストを作成する K 最近傍クエリ メソッドをいくつか作成しました。隣接要素のリストを維持するためにstd::priority_queue、最上位の要素がクエリ ポイントから最も遠い隣接要素になるように を使用します。このようにして、現在調査中の新しい要素をプッシュする必要があるかどうか (現在の最も遠い隣接要素よりも距離が短い場合) を認識し、優先度キューに K 個を超える要素がある場合に最も遠い要素を pop() できます。

これまでのところ、すべて順調です。ただし、要素を出力するときは、最も近いものから最も遠いものへと並べたいと思います。現在、単純にプライオリティ キューからすべての要素をポップし、(反復子を介して) 出力コンテナーに配置します。これにより、最も遠いものから最も近いものへと順序付けられたポイントのシーケンスが生成されます。次に、std::reverse出力反復子の範囲を呼び出します。 .

簡単な例として、プライオリティ キューを使用する線形検索を次に示します (明らかに、私が使用する実際の最近傍クエリ方法ははるかに複雑です)。

  template <typename DistanceValue,
            typename ForwardIterator,
            typename OutputIterator,
            typename GetDistanceFunction,
            typename CompareFunction>
  inline 
  OutputIterator min_dist_linear_search(ForwardIterator first,
                                        ForwardIterator last,
                                        OutputIterator output_first,
                                        GetDistanceFunction distance,
                                        CompareFunction compare,
                                        std::size_t max_neighbors = 1,
                                        DistanceValue radius = std::numeric_limits<DistanceValue>::infinity()) {
    if(first == last) 
      return output_first;

    typedef std::priority_queue< std::pair<DistanceValue, ForwardIterator>, 
                                 std::vector< std::pair<DistanceValue, ForwardIterator> >,
                                 detail::compare_pair_first<DistanceValue, ForwardIterator, CompareFunction> > PriorityQueue; 

    PriorityQueue output_queue = PriorityQueue(detail::compare_pair_first<DistanceValue, ForwardIterator, CompareFunction>(compare));

    for(; first != last; ++first) {
      DistanceValue d = distance(*first);
      if(!compare(d, radius)) 
        continue;

      output_queue.push(std::pair<DistanceValue, ForwardIterator>(d, first));

      while(output_queue.size() > max_neighbors)
        output_queue.pop();

      if(output_queue.size() == max_neighbors)
        radius = output_queue.top().first;
    };

    OutputIterator it = output_first;
    while( !output_queue.empty() ) {
      *it = *(output_queue.top().second);
      output_queue.pop(); ++it;
    };
    std::reverse(output_first, it);
    return it;
  };

上記は、1 つのことを除いてすべてダンディです。出力イテレータの型が双方向であり、本質的に事前に割り当てられたコンテナーを指している必要があります。さて、出力イテレータによって規定された範囲内に出力を格納するというこのプラクティスは、優れており、かなり標準的でもあります (たとえばstd::copy、他の STL アルゴリズムはその良い例です)。ただし、この場合、STL コンテナーおよび iostream に提供されているような back-inserter イテレーターを使用できるようにするために、フォワード出力イテレーター・タイプのみを要求できるようにしたいと考えています。

したがって、これは要約すると、出力イテレータにコンテンツをダンプする前に、プライオリティ キューを逆にすることになります。したがって、これらは私が思いついたより良いオプションです。

  • を作成しstd::vector、その中の優先度キューの内容をダンプし、ベクトルの逆反復子を使用して要素を出力反復子にダンプします。

  • std::priority_queueをソートされたコンテナー (例: ) に置き換えてからstd::multimap、適切なトラバーサル順序を使用してコンテンツを output-iterator にダンプします。

他に合理的な選択肢はありますか？

std::multimap上記の2番目のオプションのように、このアルゴリズムや他のアルゴリズムの以前の実装で aを使用していました。しかし、 に切り替えるとstd::priority_queue、パフォーマンスが大幅に向上しました。したがって、隣人のリストを維持するために優先度キューを使用する方が、並べ替えられた配列に依存するよりもはるかに優れているように思われるため、2 番目のオプションは使用したくありません。std::vectorところで、私は で並べ替えを維持しているも試しましたstd::inplace_merge。これはマルチマップよりも優れていましたが、優先キューとは一致しませんでした。

この時点での私の最良のオプションである最初のオプションについては、このデータの二重転送 (キュー -> ベクトル -> 出力) を行う必要があるのは無駄に思えます。これを行うにはもっと簡単な方法が必要だと思う傾向があります...私が見逃しているもの..

最初のオプションは、このアプリケーションではそれほど悪くはありませんが (それに先行するアルゴリズムの複雑さを考慮すると)、この二重のメモリ転送を回避するトリックがあれば、それについて知りたいです。

4

3 に答える 3

5

問題が解決しました！

私はとてもばかです...明らかに何かが欠けていることを知っていました。この場合、std::sort_heap()関数。リファレンス ページには、まさに私が必要とすることを実行する例もあります (そしてstd::priority_queue、ランダム アクセス コンテナーとヒープ関数 (pop_heap、push_heap、make_heap) に関して実装されているだけなので、これらの関数を直接使用しても実際の違いはありません)。クラスの代わりにstd::priority_queue）。どうやってそれを逃したのかわかりません。

とにかく、これが同じ問題を抱えている人の助けになることを願っています。

于 2012-02-25T02:38:29.190 に答える
3

宣言で反対の比較関数を指定してみませんか。

#include <iostream>
#include <queue>
#include <vector>
#include <functional>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int> > pq;
    pq.push(1);
    pq.push(10);
    pq.push(15);
    std::cout << pq.top() << std::endl;
}
于 2012-09-25T13:48:20.970 に答える
3

それにもかかわらず、動作することが保証されている1つの汚いアイデアは、次のとおりです。

std::priority_queue<int, std::vector<int>, std::less<int> > queue;
queue.push(3);
queue.push(5);
queue.push(9);
queue.push(2);

// Prints in reverse order.
int* front = const_cast<int*>(&queue.top());
int* back = const_cast<int*>(front + queue.size());
std::sort(front, back);
while (front < back) {
    printf("%i ", *front);
    ++front;
}

その場での並べ替えは、キューを壊す可能性が高いことに注意してください。

于 2012-02-24T22:44:45.647 に答える