0 
item_list = [("a", 10, 20), ("b", 25, 40), ("c", 40, 100), ("d", 45, 90),
             ("e", 35, 65), ("f", 50, 110)] #weight/value
results = [("", 0, 0)]  #an empty string and a 2-tupel to compare with the new
                        #values

class Rucksack(object):
    def __init__(self, B):
        self.B = B   #B=maximum weight
        self.pack(item_list, 0, ("", 0, 0))

    def pack(self, items, n, current):  
        n += 1   #n is incremented, to stop the recursion, if all
        if n >= len(items) - 1:
            if current[2] > results[0][2]:
                #substitutes the result, if current is bigger and starts no
                #new recursion
                results[0] = current
        else:
            for i in items:
                if current[1] + i[1] <= self.B and i[0] not in current[0]:
                    #first condition: current + the new value is not bigger
                    #than B; 2nd condition: the new value is not the same as
                    #current
                    i = (current[0] + " " + i[0], current[1] + i[1],
                         current[2] + i[2])
                    self.pack(items, n, i)
                else:
                    #substitutes the result, if current is bigger and starts no
                    #new recursion
                    if current[2] > results[0][2]:
                        results[0] = current

背包1 = 背包(100)

这是背包问题的一个小算法。我必须以某种方式并行化代码，但到目前为止我还没有得到线程模块。我认为唯一可以使用并行化的地方是 for 循环，对吧？所以，我尝试了这个：

def run(self, items, i, n, current):
    global num_threads, thread_started
    lock.acquire()
    num_threads += 1
    thread_started = True
    lock.release()
    if current[1] + i[1] <= self.B and i[0] not in current[0]:
        i = (current[0] + " " + i[0], current[1] + i[1], current[2] + i[2])
        self.pack(items, n, i)
    else:
        if current[2] > results[0][2]:
            results[0] = current
    lock.acquire()
    num_threads -= 1
    lock.release()

但结果很奇怪。什么都没有发生，如果我让键盘中断，结果是正确的，但这绝对不是实现的意义。你能告诉我第二个代码有什么问题，或者我还能在哪里正确使用 perallelisation。谢谢。

4

1 回答 1

1

首先，由于您的代码受 CPU 限制，由于GIL的原因，您从使用线程进行并行处理中获得的好处很少，正如 bereal 解释的那样。幸运的是，线程和进程之间只有一些区别——基本上，所有共享数据都必须显式传递或共享（有关详细信息，请参阅进程之间的共享状态）。

其次，如果您想对代码进行数据并行化，您必须锁定对可变共享对象的所有访问权限。乍一看，虽然items看起来current是不可变的，但该results对象是一个共享的全局对象，您可以在任何地方进行修改。如果您可以更改代码以返回链上的值，那是理想的。如果没有，如果您可以累积一堆单独的返回值并在处理完成后将它们合并，那通常也很好。如果两者都不可行，您将需要results用锁保护所有访问权限。有关详细信息，请参阅进程之间的同步。

最后，您询问将并行性放在哪里。关键是要找到独立任务之间的正确分界线。

理想情况下，您希望找到大量可以排队的中型作业，并且只有一个进程池，每个进程都可以处理下一个。快速浏览一下，执行此操作的明显位置要么是在对 的递归调用处self.pack，要么是在循环的每次迭代处for i in items:。如果它们实际上是独立的，只需使用concurrent.futures，如ProcessPollExecutor示例中所示。（如果您使用的是 Python 3.1 或更早版本，则需要该futures模块，因为它没有内置在 stdlib 中。）

如果没有简单的方法来做到这一点，通常至少可以创建少量（N 或 2N，如果你有 N 个内核）大小大致相等的长时间运行的作业，并为每个作业分配自己的multiprocessing.Process. 例如：

n = 8
procs = [Process(target=rucksack.pack, args=(items[i//n:(i+1)//n],)) for i in range(n)]

最后一点：如果您完成了您的代码，并且看起来您已经摆脱了隐式共享全局变量，那么您实际上所做的是编写的代码通常但并非总是在某些平台上有效，而在其他平台上则永远不会。请参阅文档的Windows部分multiprocessing以了解应避免什么，如果可能，请定期在 Windows 上进行测试，因为它是限制性最强的平台。

你还问了第二个问题：

你能告诉我第二个代码有什么问题吗？

尚不完全清楚您在这里尝试做什么，但有一些明显的问题（除了上面提到的问题）。

  • 您不会在向我们展示的代码中的任何地方创建线程。仅在名称中创建带有“线程”的变量并不能提供并行性。添加锁也不行——如果你没有任何线程，锁所能做的就是无缘无故地减慢你的速度。
  • 根据您的描述，听起来您正在尝试使用该thread模块，而不是threading. 文档的最顶部thread告诉您不要使用它并改用它是有原因的threading。
  • 您有一个锁来保护您的线程数（根本不需要），但没有锁来保护您的results. 在大多数情况下，在 Python 中你会侥幸逃脱（因为上面提到的相同 GIL 问题——你的线程基本上不会同时运行，因此它们不会有竞争），但这仍然是一个非常糟糕的主意（特别是如果您不完全了解那些“大多数情况”是什么）。

但是，看起来您的函数run是基于. 如果这是一个并行化的好地方，那么你很幸运，因为从循环的每次迭代中创建一个并行任务正是最擅长的。例如，这段代码：for i in items:packfuturesmultiprocessing

results = []
for i in items:
    result = dostuff(i)
    results.append(result)

……当然可以写成：

results = map(dostuff, items)

它可以简单地并行化，甚至不必了解期货是关于什么的，例如：

pool = concurrent.futures.ProcessPoolExecutor()
results = pool.map(dostuff, items)
于 2013-01-29T22:07:03.797 回答