2

我正在为 C++ 模拟框架编写 API。我想在 C# 中使用这个 API。但是我在获取模拟中所有角色的位置时遇到了性能问题。我试图给你一个广泛的解释这个框架是如何工作的。

有一个模拟器类：

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 坐标

还有一个 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;
  }
}

当我在 C# 中使用这个 API 时，一切正常。除非我在模拟器中添加了很多角色并且我需要获取所有角色的位置。这需要很长时间，因为每个字符的每个 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. 公开一个GetCharacterXYAPI 方法：这将需要一次对数时间查找来获取(x,y)位置，而不是进行两次相同的查找

    • 这仍然按比例缩放O(n log n)，但应该更快

  2. 尝试使用std::unordered_map而不是std::map，除非您在某个地方需要按 id 排序的字符，因为这提供了恒定时间而不是对数时间查找

    • 这是O(n)，但您仍在为n项中的每一项进行哈希查找

  3. 正如 Yochai 所建议的，公开一个使用线性扫描而不是多次查找返回所有(id,x,y)元组的方法characters

    • 这是O(n)并且可能是最快的（因为您为每个项目做的多余工作最少）
于 2013-05-22T13:08:39.800 回答