2

C++ シミュレーション フレームワークの API をプログラミングしています。そして、この API をたとえば C# で使用したいと考えています。しかし、シミュレーションですべてのキャラクターの位置を取得する際にパフォーマンスの問題が発生しています。このフレームワークがどのように機能するかを詳しく説明します。

シミュレータークラスがあります：

class Simulator
{
  /// A list of the characters that are currently in the simulation.
  std::vector<Character> characters;
  /// A list of the path planning results for the characters currently in the simulation.
  std::vector<PathPlanningResult*> pathPlanningResults;
  /// A mapping from character IDs (which can be set externally) to their positions in the 'characters' and 'PathPlanningResults' lists (which always number from 0).
  std::map<int, int> characterVectorPositions;

  /** Finds and returns a pointer to the character with the specified ID.
  * @param id       The ID of the character to find.
  * @return A pointer to the Character object that matches the given ID, or NULL if no such character exists.
  */
  inline Character* getCharacter(int id)
  { 
    std::map<int,int>::iterator findIt = characterVectorPositions.find(id);
    if(findIt == characterVectorPositions.end()) return NULL;
      return &characters[findIt->second];
    }

  /// Adds a character to the simulation, with the specified settings.
  bool Simulator::addCharacter(const Point& pos, short layer, const CharacterSettings& settings, int id)
  {
    Character newCharacter(id, pos, layer, settings);

    // add the character
    characters.push_back(newCharacter);
    // add an empty result
    pathPlanningResults.push_back(NULL);
    // add the ID mapping
    characterVectorPositions.insert(std::pair<int,int>(id, characters.size()-1));
  }
}

このクラスは、シミュレーション内のすべての文字オブジェクトを保持しています。

位置を取得するメソッドを持つ文字クラスがあります。

class Character
{
  /** Returns the current 2D position of the character on its current layer.
  * @return The current position of the character.
  */
  inline const Point& getPosition() const { return pos; }
}

Point オブジェクトには、X 座標と Y 座標が含まれています

そして、キャラクターの位置を取得するための 2 つのメソッドを持つ API クラス API_simulator があります。

class API_simulator 
{
  extern "C" EXPORT_API double GetCharacterX(int charid) {
    return simulator->getCharacter(charid)->getPosition().x;
  }

  extern "C" EXPORT_API double GetCharacterY(int charid) {
    return simulator->getCharacter(charid)->getPosition().y;
  }
}

この API を C# で使用すると、すべて正常に動作します。シミュレーターに多くのキャラクターを追加し、すべてのキャラクターの位置を取得する必要がある場合を除きます。各文字のすべての X 座標と Y 座標をツリー構造で見つける必要があるため、これには時間がかかります。一度にすべてのキャラクターの位置を取得するより高速な方法はありますか? 共有メモリは解決策ですか?

4

3 に答える 3

2

マップがボトルネックではないと思います。十分にスケーラブルである必要があるため、マップを介して文字ごとの情報を検索すると、数千文字の場合でも十分に高速である必要があります (10 から 15 の検索になります)。
ただし、すべての文字の座標が必要な場合は、各文字の ID でオフセットを調べるのではなく、正しいベクトルをすぐに反復する方がよいでしょう。

于 2013-05-22T12:57:59.703 に答える
0

入力のサイズと比較して、データベースのサイズに実際に依存します。

入力内のすべての文字 (入力の場合は N) を調べて、データベース マップ (データベースの場合は D) で毎回検索しようとすると、O(NlogD) の操作が必要になります。

データベース内のすべての文字が必要であると判断し、charactersベクトルをループするとO(D)になります。

入力がはるかに大きい場合は、マップまたはベクトルで入力を並べ替えてから、データベースをループして、それを入力と比較できます。これは、ソートの O(NlogN ) +データベースのトラバースのO(DlogN)です。

于 2013-05-22T13:02:37.683 に答える
0

  1. API メソッドを公開します。これには、 (x,y)位置を取得するために、同じルックアップを 2 回行う代わりにGetCharacterXY、1 回の対数時間ルックアップが必要になります。

    • これはまだ としてスケーリングされO(n log n)ますが、より高速になるはずです

  2. std::unordered_mapの代わりに使用してみてstd::mapください。ID でソートされた文字が必要な場合を除きます。これにより、対数時間ルックアップの代わりに定数時間が得られる

    • これはですが、 n 個のアイテムO(n)のそれぞれに対してハッシュ ルックアップを行っています。

  3. Yochai が提案するように、複数のルックアップの代わりに線形スキャンを使用してすべての(id,x,y)タプルを返すメソッドを公開しますcharacters

    • これがO(n)最速である可能性が高いです（各アイテムに対して余分な作業を最小限に抑えるため）
于 2013-05-22T13:08:39.800 に答える