有时对于类里面某些处理函数,我们希望它可以使用多线程技术以加速其执行速度(当我做力扣, 发现提交超时时,我就超想通过多线程的方法用以解决超时的问题,但通常该超还是超,毕竟不知道力扣背后的平台是什么,哈哈哈哈)。对于Python来说,十分的简单。先举一道力扣上的题:
560. 和为K的子数组
给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
以下是我的Python使用多线程的解法
class Solution:
from threading import Lock
start = 0
ret = 0
lock1 = Lock()
lock2 = Lock()
def threadSum(self, nums, k):
while self.start < len(nums):
i = 0
tmp = 0
with self.lock1:
i = self.start
self.start = self.start + 1
while i < len(nums):
tmp = tmp + nums[i]
if tmp == k:
with self.lock2:
self.ret = self.ret + 1
i = i + 1
def subarraySum(self, nums: List[int], k: int) -> int:
from threading import Thread
self.start = 0
self.ret = 0
t1 = Thread(target=self.threadSum, args=(nums, k,))
t2 = Thread(target=self.threadSum, args=(nums, k,))
t3 = Thread(target=self.threadSum, args=(nums, k,))
t4 = Thread(target=self.threadSum, args=(nums, k,))
t1.start()
t2.start()
t3.start()
t4.start()
t1.join()
t2.join()
t3.join()
t4.join()
return self.ret
程序运行没有任何问题,解题的答案也正确,不过毫无疑问,最终提交还是超时了,哈哈哈
但是当我用C++的多线程去解答这道题时,居然编译都没有通过。(多线程什么的,我以后还是用Python了)
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
using namespace std;
class Solution {
mutex mtx1;
mutex mtx2;
int start;
int ret;
vector<int>threadnums;
void multiSum(int k)
{
while(start < threadnums.size())
{
int i = 0;
mtx1.lock();
i = start;
start++;
mtx1.unlock();
int tmp = 0;
while(i < threadnums.size())
{
tmp += threadnums[i];
if(tmp == k)
{
mtx2.lock();
ret++;
mtx2.unlock();
}
i++;
}
}
}
public:
int subarraySum(vector<int>& nums, int k)
{
start = 0;
ret = 0;
threadnums = nums;
thread t1(multiSum, k);
thread t2(multiSum, k);
thread t3(multiSum, k);
thread t4(multiSum, k);
t1.join();
t2.join();
t3.join();
t4.join();
return ret;
}
};
int main()
{
vector<int>testcase1{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,3,3,3,1,1,1,5};
int k = 5;
Solution *mysolution = new Solution();
cout << "test case result is: " << mysolution->subarraySum(testcase1, k) << endl;
return 0;
}
那么为什么C++会出现这种情况呢?
C++之所以不能直接像Python的代码一样直接使用多线程技术,是因为C++类的成员函数的函数指针不能直接做为参数传到thread当中, 因为C++成员函数指针带有类命名空间,同时成员函数末尾是会被C++编译器加上可以接收对象地址的this指针参数,因此需要将成员函数做一定的转化,将其转化成不被编译器加上this指针,而由我们自己来为该函数维护”this”指针即可,其中一个办法就是在函数之前添加this指针,令类的成员函数变成静态成员函数。需要注意的是,因为静态成员函数不允许访问类中的非静态成员变量(因为没有this指针),所以在线程函数中,在参数中传入this指针。
修改后的代码如下
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
using namespace std;
class Solution {
mutex mtx1;
mutex mtx2;
int start;
int ret;
vector<int>threadnums;
static void multiSum(void* _this, int k)
{
//this指针是当前对象的首地址,可以通过类型转换来使用
Solution *obj = (Solution *)_this;
while(obj->start < obj->threadnums.size())
{
int i = 0;
obj->mtx1.lock();
i = obj->start;
obj->start++;
obj->mtx1.unlock();
int tmp = 0;
while(i < obj->threadnums.size())
{
tmp += obj->threadnums[i];
if(tmp == k)
{
obj->mtx2.lock();
obj->ret++;
obj->mtx2.unlock();
}
i++;
}
}
}
public:
int subarraySum(vector<int>& nums, int k)
{
start = 0;
ret = 0;
threadnums = nums;
thread t1(multiSum, (void*)this, k);
thread t2(multiSum, (void*)this, k);
thread t3(multiSum, (void*)this, k);
thread t4(multiSum, (void*)this, k);
t1.join();
t2.join();
t3.join();
t4.join();
return ret;
}
};
int main()
{
vector<int>testcase1{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,3,3,3,1,1,1,5};
int k = 5;
Solution *mysolution = new Solution();
cout << "test case result is: " << mysolution->subarraySum(testcase1, k) << endl;
return 0;
}
现在可以编译通过,也是可以得到正确的结果,不过最后的提交依旧还是超时。
所以在C++的类内开发多线程函数时,需要注意以下几点
- 将线程函数声明为静态函数
- 创建线程时传递this指针进去(静态成员函数时不存在this指针的)
- 在线程函数中使用传进来的this指针调用类的成员,特别注意调用类的成员函数时要避免segmantation fault错误。
除了转换成static成员函数的方法外,采用友元函数也是可以的。通过定义线程函数为类的友元函数,令线程函数可以像类自己的成员函数一样访问其成员变量和成员函数。(类的友元函数是定义在类外部,但有权访问类的所有私有成员和保护成员)