版本 2-SUM 问题 - O(n) 算法中的优化常量

算法：设计与分析，第 1 部分 本课程第六个编程问题的第一题，编程问题的前面的问题都比较直观，但是这个问题需要一点简单的优化，这比其他问题有趣得多。

问题描述：
输入文件的每一行都有一个编号（可以重复）。在所有数字中，选出两个不想等待的数字x和y，令t=x+y，询问区间[-10000, 10000]内存在多少个这样的t。

这道题的难度在于输入数据的范围，即文件的行数（输入数字的个数）n。网站给出的输入文件有100万行，其中超过99900行是唯一数字。如果使用最暴力的方法双循环计数计算法，n2的复杂度足以在等待运行结果的同时免费去一趟港澳台。

这个 O(n2) 算法可以很容易地优化为 O(n) 算法：

#算法一

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(n2) 的暴力算法一样令人无法接受。

如果你想进一步减少运行时间，你需要在20000*n中优化20000。通过对输入数据进行观察和统计，我们发现100万条输入数据中最小值只有-99,999,887,310，最大值则高达99,999,662,302。如果我们对这100万个数字进行排序，两个相邻数字之间的平均间隔就有199,999之多。

如果对于序列中的任意数字x，都存在一个y，使得两者之和在区间[-10000, 10000]内，则y必须满足-x-10000 为了减少不必要的查询，我们进行压缩，将整个长度为200亿的区间划分为长度为5w的子区间，并用布尔值来表示输入数据中是否有数字落在这个区间内。区间划分从起始点开始：...[-5w, 0), [0, 5w), [5w, 2*5w)...，其中区间索引值为 [0,5w) 0 , [5w , 10w ) 的索引值为 1。我们用 h1 来存储这个压缩结果，那么 h1[0] 为 true，这意味着输入数据中至少有一个数字存在于区间 [0, 5w) 内。算法1的内存循环中，查询间隔的长度为2w，这意味着通过查询h1的最多两个值，可以确定x不对应于y（但不能确定存在） ，也无法确定y)的具体值。

更改算法一，使用 h1 过滤掉 y 不存在的情况：

#算法二

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 。在实际运行中，算法2可以跳过约70%的输入数据，但运行时间仍然较长，主要是因为即使我们花费很少的开销来确定x没有对应的y，但当可能有对应的y时， y，我们还得花很多功夫来求出y的具体值。如果按照30%的计算量估算，算法2的运行时间约为4小时。

如果我们做一些妥协，减少区间的长度，那么如果没有y匹配x，我们可能会花更多的精力来排除它，但是如果有匹配的y，我们可以在较小的区间可以降低搜索成本。因此，合理的子区间长度应小于2w。

考虑到输入数据的稀疏性，我们可以合理地假设长度为 2w 的子区间内只有一个 y。假设新子区间的长度为L。如果y不存在，我们必须执行2w/L次查询。为了排除 y 是否存在，除了 2w/L 查询之外，我们还需要执行 L 次附加查询。由于只有 30% 的 x 可以有先验对应的 y，因此我们对每个 x 的查询数量的期望约为 (2w/L+0.3L)，当 L 约等于 sqrt(2w) 时，期望最低。取L=150，稍微修改算法2，然后再次运行。操作时间为147s。这里我也尝试了L=200，运行时间为129.18s，超过了理论值。问题应该出在 30% 的数据上。之前，可能有30%x。该数据y位于长度为5w的区间内。上面测量的误差比较大。当区间变窄时，应检查小于 30% 的 x 的 y。

上述算法还可以进一步优化。我们可以将长间隔和短间隔结合起来。较长的区间用于快速过滤掉y的缺失，较小的区间用于快速定位y。之前选的5w实在是没有必要。这里，我们只需要保证大区间的查询次数少，小区间的遍历长度小即可。在实际实现中，我选择了大区间长度5000，小区间长度150，程序运行时间为45.37s。

最终算法和算法1的复杂度都是O(n)，但是运行时间却相差很大。主要原因是时间复杂度cn中常数c的优化。虽然优化后复杂度没有变化，但是运行时间快了很多。

附件是代码（Ruby 实现）：

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}"