Coding 极简派

一次不懈的速率优化-3Sum

Posted on | In

关于2Sum

Two sum是一个很简单的问题,给定一个乱序列和一个target,找到两个数的和等于target.
只要先sort然后用首尾两个pointers 反向逼近直到找到所求就可以了.可以找到所有符合要求的tuple,这里简化为解决第一个遇到的符合条件的tuple,找到全部组合见下面3sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
'''
这里是题目的要求:
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
'''
  
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums)<2:
            return []
        backup = nums[:]    
        list.sort(nums)
        i = 0
        j = len(nums)-1
        while i<j:
            if (nums[i]+nums[j])<target:
                i=i+1
            elif (nums[i]+nums[j])>target: 
                j=j-1
            else:
                if nums[i]==nums[j]:
                    index1 = backup.index(nums[i])
                    backup.remove(nums[i])
                    return [index1+1,backup.index(nums[j])+2]    
                else:
                    index1 = backup.index(nums[i])+1
                    index2 = backup.index(nums[j])+1
                    return [min(index1,index2),max(index1,index2)]

3sum-摘掉面具

Three sum 与two sum类似,是数组中找出所有三个数的组合加和为target.
它穿了一层马甲,我们摘掉他的面具, 将3Sum转化为解决了的2Sum问题,只要从0 loop 到 length-2 (设为x),对剩余数组找target-x,就转化成了twoSum.

不同的一点是要找到全部组合,同时要排重.

我的第一个解法是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums)<3:
            return []
        result = []    
        list.sort(nums)    
        for x in range(len(nums)-2):
            target = -nums[x]
            rs = self.twoSum(nums[x+1:],target)
            if(rs!=[]):
                for r in rs:
                    if [nums[x]]+r not in result:
                        result.append([nums[x]]+r)
        return result
        
            
    def twoSum(self,nums,target):
        i = 0
        j = len(nums)-1
        tmprs = []
        flag = 0
        while(i<j):
            if nums[i]+nums[j]<target:
                i = i+1
            elif nums[i]+nums[j]>target:
                j = j-1
            else:
                if [nums[i],nums[j]] not in tmprs: 
                    tmprs.append( [nums[i],nums[j]])
                i=i+1
                j=j-1
                continue
        return tmprs

trivial. 然而速率却很慢,在使用python的人群中只beats about 30%.
Could stand? No.
开始优化.

while True: optimize()

排重优化0x00

第一个想法是先从排除重复结果上来优化.
在这个解法之前我试用完全得到包含重复的结果来2 pass 排重 会造成time exceed.因为这个排重过程已经是O(n^2)
这里用了 not in the list 来排重,O(n)的time complexity.想到可以用查询时间为O(1)的set来排重,然而list是unhashable的.

我尝试了化成string然后hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
strset = set()     
if str(tmp) not in strset:
	result.append(tmp)
	strset.add(str(tmp))
	
	
	
	class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        hashset = set()    
        result = []    
        list.sort(nums)    
        for x in range(len(nums)-2):
            target = -nums[x]
            rs = self.twoSum(nums[x+1:],target)
            for r in rs:
                if str([nums[x]]+r) not in hashset:
                    result.append([nums[x]]+r)
                    hashset.add(str([nums[x]]+r))
    
        return result
        
            
    def twoSum(self,nums,target):
        i = 0
        j = len(nums)-1
        tmprs = []
        while(i<j):
            if nums[i]+nums[j]<target:
                i = i+1
            elif nums[i]+nums[j]>target:
                j = j-1
            else:
                if [nums[i],nums[j]] not in tmprs: 
                    tmprs.append( [nums[i],nums[j]])
                i=i+1
                j=j-1
                continue
        return tmprs

然而并未卵,之后怀疑是转化为str太慢吗,tuple结果一样.
…
被没有显著的变化.

排重优化0x01

要减小排重带来的overhead. 上面的思路一直是在得到搜索结果之后再排重,那么一个反向的想法是我应该在搜索之前就排重,想如果第一个数是一样的化,之后twoSum的结果也是相同的,那么这次twoSum 的搜索就是没有意义的,于是我记录之前第一个数prev,就继续找下一个起点

改进如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums)<3:
            return []
        result = []    
        list.sort(nums)
        
        prev = None
        for x in range(len(nums)-2):
            target = -nums[x]
            if target == prev:
                continue 
            prev = target
            rs = self.twoSum(nums[x+1:],target)
            for r in rs:
                result.append([nums[x]]+r)
        return result
        
            
    def twoSum(self,nums,target):
        i = 0
        j = len(nums)-1
        tmprs = []
        while(i<j):
            if nums[i]+nums[j]<target:
                i = i+1
            elif nums[i]+nums[j]>target:
                j = j-1
            else:
                if [nums[i],nums[j]] not in tmprs: 
                    tmprs.append( [nums[i],nums[j]])
                i=i+1
                j=j-1
                continue
        return tmprs

这样就可以减调每次的线性排查 if [nums[x]]+r not in result:

performance有了进步,达到了50%左右.

排重优化0x02

在外围即第一个数事先排重之后,在twoSum搜索中也应该事先排重,
之前的loop是i++,j– 来前进一步,然而很有可能依然有重复值. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums)<3:
            return []
        result = []    
        list.sort(nums)
        
        prev = None
        for x in range(len(nums)-2):
            target = -nums[x]
            if target == prev:
                continue 
            prev = target
            rs = self.twoSum(nums[x+1:],target)
            for r in rs:
                result.append([nums[x]]+r)
        return result
        
            
    def twoSum(self,nums,target):
        i = 0
        j = len(nums)-1
        tmprs = []
        while(i<j):
            if nums[i]+nums[j]<target:
                i = i+1
            elif nums[i]+nums[j]>target:
                j = j-1
            else:
                     
                while i<j and nums[i]==nums[i+1]:
                    i =i+1
                while i<j and nums[j]==nums[j-1]:    
                    j =j-1
                    
                tmprs.append( [nums[i],nums[j]])    
                i=i+1
                j=j-1
                continue
        return tmprs

nice, 速率达到了60%多.

接下来该优化哪里呢?
我开始到处放空枪,看有没有机会打下一只鸟.

0x03 去除method call

我开始想在dynamic programming中反复recruisive call 造成的overhead. 于是我省去另建函数twoSum. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums)<3:
            return []
        result = []    
        list.sort(nums)
        
        prev = None
        for x in range(len(nums)-2):
            target = -nums[x]
            if target == prev:
                continue 
            prev = target
            nums1 = nums[x+1:]
            i = 0
            j = len(nums1)-1
            tmprs = []
            while(i<j):
                if nums1[i]+nums1[j]<target:
                    i = i+1
                elif nums1[i]+nums1[j]>target:
                    j = j-1
                else:
                    while i<j and nums1[i]==nums1[i+1]:
                        i =i+1
                    while i<j and nums1[j]==nums1[j-1]:    
                        j =j-1
                    tmprs.append( [nums1[i],nums1[j]])    
                    i=i+1
                    j=j-1
                    continue
            for r in tmprs:
                result.append([nums[x]]+r)
        return result

一声空响.

每次function被放在stack上,用后即delete, 和recuisive call 造成的overhead无法相提并论.

0x04 去除list copy

突然意识到我每次都copy了后段list来传入twoSum,造成了很大浪费,应该只传入原list,只要改变index就可以了,这样才不违背在最开始时候就进行sort的初衷. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums)<3:
            return []
        result = []    
        list.sort(nums)
        
        prev = None
        for x in range(len(nums)-2):
            target = -nums[x]
            if target == prev:
                continue 
            prev = target
            i = x+1
            j = len(nums)-1
            tmprs = []
            while(i<j):
                if nums[i]+nums[j]<target:
                    i = i+1
                elif nums[i]+nums[j]>target:
                    j = j-1
                else:
                    while i<j and nums[i]==nums[i+1]:
                        i =i+1
                    while i<j and nums[j]==nums[j-1]:    
                        j =j-1
                    tmprs.append( [nums[i],nums[j]])    
                    i=i+1
                    j=j-1
                    continue
            for r in tmprs:
                result.append([nums[x]]+r)
        return result

速率达到了80%-90%

0x05 last shot

统一了外部的事先排重,这里的一个教训是对于有序数列来说,排重是很有优势的,应该利用order事先排除,loop until 一个不同的值出现.

而我之前的做法其实是浪费已排序的这个已知信息资源.

对于未消逝的变量,根本没有必要每次记录history.

改进如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums)<3:
            return []
        result = []    
        list.sort(nums)
        
        for x in range(len(nums)-2):
            target = -nums[x]
            if x>0 and target == -nums[x-1]:
                continue 
            i = x+1
            j = len(nums)-1
            while(i<j):
                if nums[i]+nums[j]<target:
                    i = i+1
                elif nums[i]+nums[j]>target:
                    j = j-1
                else:
                    while i<j and nums[i]==nums[i+1]:
                        i =i+1
                    while i<j and nums[j]==nums[j-1]:    
                        j =j-1
                    result.append([nums[x],nums[i],nums[j]])    
                    i=i+1
                    j=j-1
                    continue
        return result

bingo! 速率达到了 python人群的 90% 左右.

0x06 Not the end

这一定不是终结,还没有想到进一步的优化方式,先用一个法则来自我安慰:

Hill’s law

Simple and Dumb can be better

…lol

Never stop optimizing until you give out your all.
However, don’t forget the Hill’s law.

xubing wechat
奇闻共欣赏,疑义相与析.欢迎来我的微信公众号