速度（成对的矢量）vs（成对的矢量）C++

-3

背景：我已经完成了作为一项家庭作业的写作游戏。我们必须做一个十六进制游戏。我决定使用2d节点向量来实现该板，并使用2个向量来跟踪节点邻居的x和y坐标。我用来确定获胜者的路径寻找算法与Dijkstra的相似。速度（成对的矢量）vs（成对的矢量）C++

我意识到使用2个向量的缺点是它们必须始终保持同步，但我在问速度。我也意识到，实现该板的更快方法可能是使用1d矢量（我在完成该程序时意识到了这一点）。

问题：就原始速度而言，如果使用双向量向量来实现，路径搜索算法会以2个向量运行得更快以跟踪（x，y）还是算法运行得更快？

来源

2014-02-18 paeynivek

当提供一个小型的自包含代码示例时，可以最好地回答这类问题，当你完成这些时，你有90％的方法可以构建自己的基准测试。 – DavidO

我在过去做过这样的事情，而不是担心'（x，y）'中的对，我只是将这些对转换为整数（（* x Number_Of_rows + y）），这就是我用来存储每个对在板上的个人位置。邻居以类似的方式存储，其中每个节点将存储邻居的“std :: list ” – smac89

也许你想阅读http://stackoverflow.com/questions/7274268/which-is-faster-vector-of - 结构或向量编号尽管它是一个繁重的阅读，但它们的实现的增强文档可以对Djikstra具体有更多的了解：http://www.boost.org/doc/libs/1_55_0/libs /graph/doc/dijkstra_shortest_paths.html –

选择其中更适合您需要的产品。在软件设计的这个阶段，你不应该关心性能。更重要的是选择最适合的数据结构。

在这样做时，性能优势可能已经在您身边。

来源

2014-02-18 17:01:59 poitroae

他说他已经完成了它，并且在一个项目完成之后，功能似乎成为了获得一些性能优势的最佳时机。此外，告诉他们他们不需要回答他们的问题并不是一个答案。 – Luke

分析是优化，猜测或人们称之为微优化的最佳方式。 – poitroae

@ user2581799：从这个*答案*中可能不明显的是用户是否实际想到了设计。从这个问题来看，他似乎甚至没有考虑在项目的晚些时候才开始配对的可能性。现在，aoeu建议重新考虑设计：*您最适合使用哪种数据结构？*应该是否定的。 1的设计驱动力（我想可能会有更好的配对向量）。你甚至可以说，对于这种特殊情况，你甚至不应该考虑性能（直到测量） –

我的直觉告诉我，对的向量会更快，但您可能需要测试它。创建一个测试程序，将数百万个点插入到格式和时间更快的地方。然后，时间格式更快以提取存储的数据。

来源

2014-02-18 17:06:47 Luke

aoeu有权利：首先担心好的代表性。第二，如果你担心游戏速度缓慢，配置文件。发现问题领域并担心这些问题。

这就是说，一些关于速度：

内存访问是最快的，当它是连续的。跳来跳去是不好的。一个接一个地访问值是很好的。

对（更一般地说，结构向量，VoS）或一对向量（向量结构，SoV）的向量是否更快的问题完全取决于您的访问模式。你是否一起访问坐标对，或者你是先处理所有的x，然后处理所有的y值？答案很可能会显示更快的数据布局。

这就是说，“最可能”是指下蹲。简介，简介，简介。

来源

2014-02-18 17:07:18

首先，aoeu是关键。

其次，对于一般的优化：

优化的第一步就是测量，否则你不会有一个基准来比较的改善。

下一步是使用某种类型的分析器来查看代码花费周期/内存/其他的位置，它可能不是您的想法。

当你完成了这两项工作之后，你就可以开始以正确的方式优化代码的正确部分了。

来源

2014-02-18 17:09:20 dutt

除了我的评论。如果你的实现在游戏进行时运行得更慢（我猜测它的AI部分），那么可能是因为你在每次移动后都在运行Dijkstra。随着游戏规模越来越大，AI的性能越来越差。

建议使用disjoint-set方法而不是Dijkstra来确定获胜者。与Dijkstra相比，disjoint-set的优势在于它不仅使用更少的内存，而且随着游戏进行速度不会变慢，所以您可以在每个玩家移动后运行它。 Disjoint-set - Wikipedia，Union-find - princeton

我认识到，改变项目的重要组成部分之一的实施是一项艰巨的任务，因为它要求几乎不必DO IT ALL OVER AGAIN，但是这仅仅是一个建议，如果你是担心AI的速度，那么这绝对值得研究。还有其他的方法可以实现AI，例如minMAX tree,Alphabeta pruning（这是对minmax树的改进）

G1。

来源

2014-02-18 17:26:43 smac89

速度（成对的矢量）vs（成对的矢量）C++

回答

相关问题