变种2-SUM问题——优化O(n)算法中的常数

Algorithms: Design and Analysis, Part 1 这门课的第六个编程作业的第一道题，之前的编程作业题都比较直观，而这一题需要用到一点简单的优化，相比其他的题目有意思多了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

题目描述：
输入文件每一行有一个数字（可能有重复），在这所有的数字中，任选不想等的两个数字x和y，并令t=x+y，求问在[-10000, 10000]区间中存在多少这样的t。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

这个题目的难度在于输入数据的规模，也就是文件行数（输入数字数）n，网站给出的输入文件有100w行，其中不重复的数字也有99.9w多个，如果采用最暴力的二重循环枚举的计算方法，n²的复杂度足以让你在等待运行结果的时间里来趟港澳台自由行了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

这个O(n²)的算法可以很简单的优化为一个O(n)的算法：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

#算法一

for each input x {
    for t in -10000..10000 {
        y = t - x
        if y exists in the input {
            add t to result list
        }
    }
}

由于哈希查询的复杂度是1，所以整个算法的操作复杂度是20000*n，是一个O(n)的算法。试着运行一下，发现这个算法需要预计12个小时才能运行完成，同O(n²)的暴力算法一样都是令人难以接受的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

想要进一步缩减运行时间，则必须优化20000*n中的那个20000。对输入数据进行观察、统计，发现这100w个输入数据中最小值只有-99,999,887,310，而最大值则高达99,999,662,302，如果把这100w个数字排一下序，那么相邻两个数字之间的平均间隔高达199,999。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

对于数列中任意一个数字x而言，如果存在y，使的两者之和在区间[-10000, 10000]之内，那么y必定满足 -x-10000 < y < -x+10000，也就是说y存在于一个长度为2w的区间之内，通过之前对输入数据的分析我们可知，整个输入数据是松散的分布在一个长度为200亿的区间之内的，相邻两个数字的平均间隔为20w，也就是说整个200亿的区间内，存在有许多长度为2w的区间不包含任何输入的数字。所以在我们之前的算法实现中，对大多数x而言，内层循环的2w次查找都是无功而返的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

为了减少不必要的查询，我们做一次压缩，把整个200亿长度的区间分割为长度为5w的子区间，并用一个布尔值表征输入数据中有没有数字落在这一区间内。区间的分割从原点开始：...[-5w, 0), [0, 5w), [5w, 2*5w)...，其中区间[0,5w)的索引值为0，[5w, 10w)的索引值为1。我们用h1来存储这个压缩结果，那么h1[0]为真就表示输入数据中至少有一个数字存在于区间[0, 5w)之内。在算法1的内存循环中，查询区间长度为2w，也就是说最多查询两个h1的值便可以确定不存在与x相对应的y了（但是不能确定存在，也不能确定y的具体值）。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

修改算法一，使用h1过滤掉不存在y的情况：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

#算法二

for each input x {
    a = (-x-10000)/5w
    b = (-x+10000)/5w
    if h1[a] || h1[b] {
        check if y really exists
    }
}

算法二可以跳过大多数x不必检查，对于那些需要检查的，逐一遍历每一个y检查是否存在。注意在检查的时候，并不总是需要检查2w长度的区间，如果y的可能区间为49000~69000，跨越了h1[0]和h1[1]两个子区间，然而h1[0]为true，h1[1]为false，在这种情况下我们只需要检查49000~49999即可。在实际的运行中，算法二可以跳过大约70%的输入数据，然而运行仍需比较久的时间，主要是因为我们虽然花费了极小的代价就确定了一个x不存在相应的y，但在可能存在相应的y的时候，我们依然要花较大的精力找到y的具体数值，按照30%的计算量来估计的话，算法二的运行时间大约是4个小时。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

如果进行一些取舍，把区间长度缩小，那么在不存在与x相对应的y的情况下，我们可能会稍微多花一些功夫去排除，但如果存在与之匹配的y，我们可以在更小的区间中进行查找，减少搜索开销。因此，合理的子区间长度应该是小于2w的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

考虑到输入数据的稀疏性，我们可以合理的假设一个2w长度的子区间内只有一个y，我们假定新的子区间长度为L，如果y不存在，我们需要进行2w/L次查询来排除，如果y存在，那么除了2w/L次查询以外，我们还需要额外进行L次查询来，由之前只有30%的x可能有相应的y，我们针对每个x的查询次数的期望大约是(2w/L+0.3L)，该期望在L大约等于sqrt(2w)时最低。取L=150，对算法二稍作修改，然后再次运行，运行时间为147s。这里我也尝试了L=200，运行时间是129.18s，反而比理论值高，问题应该出在30%这个数据之上，之前有30%的x可能存在y这一数据是在5w的区间长度上测出来的，误差较大，在区间缩小之后应该不足30%的x需要验证y。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

以上算法还可以进一步优化，我们可以结合长区间和小区间，长区间用来快速过滤y不存在的情况，小区间用来快速对y进行定位。之前选取的5w实在是没有必要，这里我们只要保证大区间的查询次数少，而小区间的遍历长度小即可。在实际的实现中，我选取了大区间长度为5000，小区间长度150，程序运行时间45.37s。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

经过最终的算法和算法一的复杂度都是O(n)，但运行时间相差非常多，主要就是优化了时间复杂度cn中的常数c，虽然优化后复杂度没有变化，但是运行速度会快很多。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

附上代码（Ruby实现）：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

h = Hash.new false
h1 = Hash.new false
h1step = 5000
h2 = Hash.new false
h2step = 150
sum = Hash.new false

File.open(ARGV[0]).each do |xx|
    x = xx.to_i
    h[x] = true
    h1[x/h1step] = true
    h2[x/h2step] = true
end

h.keys.each do |x|
    # detect whether a possible number exists with h1

    s1 = (-x-10000)/h1step
    t1 = (-x+10000)/h1step
    (s1..t1).each do |j|
        unless h1[j] then 
            next
        end

        a1 = b1 = 0
        if s1 == t1 then
            # -x-10000 .. -x+10000
            a1 = -x-10000
            b1 = -x+10000
        elsif j==s1 then
            # -x-10000 .. (s1+1)*h1step-1
            a1 = -x-10000
            b1 = (s1+1)*h1step-1
        elsif j==t1 then
            # t1*h1step .. -x+10000
            a1 = t1*h1step 
            b1 = -x+10000
        else
            a1 = j*h1step 
            b1 = (j+1)*h1step-1
        end
        # detect that a number exists at [a1..b1]
        # the length of [a1..b1] may varies from 1 to h1step

        # further refine the range [a1..b1] with h2
        s2 = a1/h2step
        t2 = b1/h2step
        (s2..t2).each do |i| 
            unless h2[i] then 
                next
            end

            a2 = b2 = 0
            if s2==t2 then 
                a2 = a1 
                b2 = b1
            elsif i==s2 then 
                # a1 .. (s2+1)*h2step-1
                a2 = a1
                b2 = (s2+1)*h2step-1
            elsif i==t2 then
                # t2*h2step .. b1
                a2 = t2*h2step 
                b2 = b1
            else
                # i*h2step .. (i+1)*h2step-1
                a2 = i*h2step 
                b2 = (i+1)*h2step-1
            end

            # lengh of [a2..b2] should be less than h2step
            (a2..b2).each do |y|
                if h[y] then 
                    sum[x+y] = true
                end
            end
        end
    end
end

puts "Size:#{sum.size}"