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

2019-05-3017:21:12数据结构与算法Comments2,820 views字数 3236阅读模式

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多个,如果采用最暴力的二重循环枚举的计算方法,n2的复杂度足以让你在等待运行结果的时间里来趟港澳台自由行了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html

这个O(n2)的算法可以很简单的优化为一个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
        }
    }
}
变种2-SUM问题——优化O(n)算法中的常数

由于哈希查询的复杂度是1,所以整个算法的操作复杂度是20000*n,是一个O(n)的算法。试着运行一下,发现这个算法需要预计12个小时才能运行完成,同O(n2)的暴力算法一样都是令人难以接受的。文章源自菜鸟学院-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

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

for each input x {
    a = (-x-10000)/5w
    b = (-x+10000)/5w
    if h1[a] || h1[b] {
        check if y really exists
    }
}
变种2-SUM问题——优化O(n)算法中的常数

算法二可以跳过大多数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

变种2-SUM问题——优化O(n)算法中的常数
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}"
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/13239.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/13239.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定