用k个线程完成一个多线程并行化过程

Question

3sum问题定义为给定：一个正整数 k≤20、一个正整数 n≤104 和 k 个大小为 n 的数组，其中包含从 −105 到 105 的整数。

Return：For each array A[1..n]，输出三个不同的索引1≤p<q<r≤n使得A[p]+A[q]+A[r]=0如果存在，否则"-1"。

Sample Dataset
4 5
2 -3 4 10 5
8 -6 4 -2 -8
-5 2 3 2 -4
2 4 -5 6 8

Sample Output
-1
1 2 4
1 2 3
-1

但是我想使用线程加速代码，为此我正在应用 python 代码

def TS(arr):
    original = arr[:]
    arr.sort()
    n = len(arr)        
    for i in xrange(n-2):
        a = arr[i]
        j = i+1
        k = n-1
        while j < k:
            b = arr[j]
            c = arr[k]
            if a + b + c == 0:
                return sorted([original.index(a)+1,original.index(b)+1,original.index(c)+1])
            elif a + b + c > 0:
                k = k - 1
            else:
                j = j +1
    return [-1]

with open("dataset.txt") as dataset:
   k = int(dataset.readline().split()[0]) 
   for i in xrange(k):
       aux = map(int, dataset.readline().split())
       results = TS(aux)
       print ' ' . join(map(str, results))

我正在考虑创建 k 个线程和一个全局数组输出，但是不知道如何继续开发这个想法

from threading import Thread

class thread_it(Thread):
    def __init__ (self,param):
        Thread.__init__(self)
        self.param = param
    def run(self):
        mutex.acquire()
        output.append(TS(aux))
        mutex.release() 


threads = []  #k threads
output = []   #global answer
mutex = thread.allocate_lock()
with open("dataset.txt") as dataset:
       k = int(dataset.readline().split()[0]) 
       for i in xrange(k):
           aux = map(int, dataset.readline().split())           
           current = thread_it(aux)
           threads.append(current)
           current.start()
           
       for t in threads:
           t.join()

在线程中获取 results = TS(aux) 然后等到所有线程都完成然后对所有线程完成 print ' ' . join(map(str,results)) 的正确方法是什么？

更新

当来自控制台的运行脚本时出现此问题

Answer 1

首先，正如@Cyphase 所说，由于 GIL，您无法使用 threading 加快速度。每个线程都将运行在同一个核心上。考虑使用 multiprocessing 来利用多核，multiprocessing 与线程非常相似 API。

其次，即使我们假装 GIL 不存在。将所有内容都放在受 mutex 保护的临界区中，您实际上是在序列化所有线程。您需要保护的是对 output 的访问，因此将处理代码放在临界区之外，使它们并发运行：

def run(self):
    result = TS(aux)
    mutex.acquire()
    output.append(result)
    mutex.release()

但不要重新发明轮子，python标准库提供了一个线程安全的队列，使用它：

try:
    import Queue as queue  # python2
except:
    import queue
output = queue.Queue()

def run(self):
    result = TS(self.param)
    output.append(result)

使用多处理，最终代码如下所示：

from multiprocessing import Process, Queue
output = Queue()

class TSProcess(Process):
    def __init__ (self, param):
        Process.__init__(self)
        self.param = param
    def run(self):
        result = TS(self.param)
        output.put(result)

processes = []  
with open("dataset.txt") as dataset:
       k = int(dataset.readline().split()[0]) 
       for i in xrange(k):
           aux = map(int, dataset.readline().split())           
           current = TSProcess(aux)
           processes.append(current)
           current.start()

       for p in processes:
           p.join()
       # process result with output.get()

用k个线程完成一个多线程并行化过程

Complete a multithreading parallelize process with k threads

python

multithreading

thread-safety

更新