c++ - 最佳排序 C++ 容器

Question

关闭。这个问题需要更多focused .它目前不接受答案。












想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post .

7年前关闭。




Improve this question




我正在用 C++ 编写一个国际象棋引擎，并试图编写尽可能干净和正确的代码，因为这是一个学习练习。
目前，我有一个移动类，它定义了一个可能的移动。然后人工智能对每一个可能的 Action 进行评分。在数据结构中将移动的分数与移动本身配对的最佳方法是什么？

每个分数必须能够有多个移动(两个移动的分数都可以为 735)。我认为这排除了 std::map?

它也应该可以快速排序，所以我可以向前看并递归地执行此操作以获得最佳移动。

任何帮助将不胜感激，包括链接。谢谢!

Answer 1

你的问题不是很清楚。一方面，你说你想要一个排序的容器，但另一方面，你谈论事物的方式是你要生成 Action ，将它们放入一个容器中，然后根据你的 AI 定义的标准对它们进行排序。

让我们分别考虑一下。首先，我们假设您想使用分数作为键，并查找与特定分数相匹配的 Action 。在这种情况下，您将生成一个移动，AI 将对该移动进行评分，然后您将存储该移动，并将其分数作为关键。由于您可以有多个具有相同分数的移动(即等效键)，因此您需要用于这种情况的数据结构是 std::multimap .

另一种可能性是您生成所有 Action ，将它们全部放入一个数据结构中，对它们进行评分，然后按评分对它们进行排序。对于这种情况，您可能希望使用 std::vector<std::pair<score_type, move>> .在这种情况下，当您生成每个移动时，您可能会为其分配一个类似 0 的分数。然后您将遍历 vector 并让 AI 为每个移动生成一个分数。然后，您可以使用仅考虑分数的比较函数对它们进行排序。

这两个都可以。哪个更可取取决于具体情况。使用 vector 可能会最小化开销——也就是说，它将使用最少的内存和最少的 CPU 时间从原始移动到所有移动按排序顺序存储的 vector 。

强度std::multiset是它一直保持排序。例如，如果您想在达到某个时间限制之前生成移动，它会让您非常干净地完成该操作——生成移动，对其进行评分，然后将其插入到多重集合中。无论您何时停止，到那时为止您生成的所有走法都已排序，因此(例如)如果与您的程序对战的人可以迫使 AI 立即走棋，则 AI 始终会记录最好的走法移动它找到了，所以它可以立即做出它“认为”最好的移动。

另一种可能性是使用优先队列。在国际象棋的典型案例中，您要做的一件事是生成(例如)几十个或可能的下一步 Action 。然后您将选择其中最好的，并为这些可能的反 Action 得分。然后，您将选择其中最好的并计算这些移动的计数器，依此类推，直到您得分(例如)4 或 5 个完整的移动深度。

为此，您并不真正关心将所有移动按顺序排列——您只想快速检索 N 个最佳移动。在这种情况下，优先队列工作得很好。您可以检索 N 个最佳 Action ，然后忽略其余 Action 。这意味着您只对 N 个最佳移动(您关心的移动)进行完全排序，并最大限度地减少其余移动的开销，但仅做足以验证它们的分数较低的 Action 。

我还应该提到，如果这是您真正想要的，您可以在数组情况下完成相同的操作。您可以使用 nth_element 仅查找 N 个最佳分数，而不是使用 sort 按分数对所有 Action 进行排序。 nth_element将数组/vector 分为两组:那些将在某个选定元素之前排序的那些，然后是选定元素，然后是在该选定元素之后排序的那些。例如，给定 100 次移动，您希望保留前 5 次移动，您可以使用 nth_element将它们排列成 95 个较小的 Action ，第 95 个元素，然后是其他 4 个元素。虽然没有尝试对每个组中的项目进行排序。

这样做的好处是它可以在 O(N) 时间内完成，而不是完成排序所需的 O(N log N)。

在这两种可能性( priority_queue 与 nth_element )之间，我们得到了与 set::multiset 之间的权衡大致相同的权衡。和 std::vector与 std::sort : priority_queue时刻保持秩序。即使您或多或少任意地混合插入和删除，它仍然非常有效。带 std::vector和 std::nth_element ，您通常要插入所有元素，然后调用 nth_element ，然后考虑最重要的项目。如果您要混合两者(插入一些元素，然后删除一些最好的元素，再插入一些元素，再删除一些元素，等等)，您必须调用 nth_element。每次从插入过渡到删除时，这可能会很快降低效率。