c++ - Multi-threading search of a large solution space

Question

I have to search a large solution space (enumerating all Latin Squares of a specific order) for valid solutions. I'm trying out multi-threading (boost::thread). I split up the solution space in subspaces and investigate a particular subspace within a single thread. This works well, since there are no dependencies between the threads.

But now I want to save all valid solutions in a list. Would it be best to use a single list (shared data) and surround it with a mutex or should I create lists (local data) per thread and join the lists after the threads have finished?

There might be millions of valid solutions for higher orders. So the process would either involve a lot of mutex locks/unlocks or it would involve a large memory footprint per thread.

Thanks, Daniel Dekkers

Answer 1

根据您的解释，您希望在算法结束时连接本地列表。如果每个线程都会找到许多解决方案，那么在互斥体中使用会大大减慢您的计算速度。根据我对您的上下文的了解，您现在应该认为内存非常便宜，但是如果不知道解决方案的大小，就很难确定。

还可以存在内存空间最小的列表合并算法（即通过一次复制少量数据），这可以解决内存占用量小的问题。

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