大型解决方案空间的多线程搜索

Question

我必须搜索一个大的解决方案空间(枚举所有特定顺序的拉丁方)来寻找有效的解决方案。我正在尝试多线程(boost::thread)。我将解决方案空间划分为子空间，并在单个线程中研究特定的子空间。这很好用，因为线程之间没有依赖关系。

但现在我想将所有有效的解决方案保存在一个列表中。最好是使用单个列表(共享数据)并用互斥锁包围它，还是应该为每个线程创建列表(本地数据)，并在线程完成后连接这些列表？

对于更高的订单，可能有数百万种有效的解决方案。因此，这个过程要么涉及到大量的互斥锁/解锁，要么涉及到每个线程占用大量内存。

谢谢，丹尼尔·德克斯

Answer 1

根据您的解释，您需要在算法结束时连接本地列表。如果每个线程都要找到许多解决方案，那么在互斥锁中使用会大大降低你的计算速度。根据我对你的理解，你现在应该认为内存相当便宜，但如果不知道解决方案的大小，就很难确定。

也可以有在存储空间中最小的列表合并算法(即，通过一次复制少量数据)，这可以解决小存储器占用问题。

话虽如此，对于您的问题也有混合解决方案。例如，您可以创建一个共享容器并对其进行分区，以便将分区分配给每个线程，可以是交错的，也可以是块的。这将允许您删除每次访问的互斥锁，但将需要容器增长的复杂机制(因为似乎不可能预先知道您将有多少解决方案)。