一个临界点的问题

假设有一组值(大于等于0的数),总量级别:百万以上,需要求出总和在某个值(Y)的位置。实际情况中Y的值一般也是上万的。
比如:有 5,2,0,3,4,6,7,1,11,3 等求在Y=12的位置,
分析如下:
值: 5,2,0,3, 4, 6, 7, 1,11,3
累计:5,7,7,10,14,20,27,28,39,41
此时临界点在第4个数【3】那。如果是10的话,位置也是第4个数。
数据在数据库中,实际处理不考虑数据的排序问题,只需要从总量中找到一片数据总量接近或等于Y。

请教有何算法可以快速定位到临界点的位置.

已知道的算法,
1,逐条累计,可能需要较长时间
2,先按大到小排序,逐块累计,比上面快些。(操作是允许排序的)
3,类似2分的算法,直接对半,累加前半数据比较,大的话再减少一半,小的话加上剩余的一半。无限2分,直至累计值与Y的接近或等于。

这个算累计 我是在数据库ORACLE中做的。

0
jinnianshilongnian
jinnianshilongnian 序列长度固定吗
接近 7 年之前 回复

4个回答

1、原始表:
t_bill;字段:索引ID(number),分钟值talktime(varchar(40));
2、递归累加生成表:
t_bill_2 ;字段:索引ID(number),分钟值talktime(varchar(40));

递归累加生成表 talktime建立索引

两个表的id一样;

3、可以考虑根据递归累加生成表的talktime分表; 比如1--1000的在1表,依次类推;

4、根据根据Y值查分表编号,然后查

0
jinnianshilongnian
jinnianshilongnian 客气 很喜欢探讨这种问题 哈哈
接近 7 年之前 回复
weixin_42501429
weixin_42501429 谢谢认真的回答!
接近 7 年之前 回复
jinnianshilongnian
jinnianshilongnian 之前用过 不过按照我的理解也不会很快 因为毕竟要计算 而且要按条走 每次都需要这个流程 我的想法还是 先构建那种累加表 再查 就不那么麻烦了
接近 7 年之前 回复
weixin_42501429
weixin_42501429 select id from( select id,rownum r from ( select ID,talktime,sum(talktime) over (order by to_number(talktime) desc ) total from t_bill where to_number(talktime)>0 order by talktime desc ) x where x.total<=43210 order by x.total desc ) y where rownum=1 安装以上思路写的,其实我对于分析函数不懂的。 应该外挂一张表 可能查询会快些。
接近 7 年之前 回复
jinnianshilongnian
jinnianshilongnian 分析函数 不错 在程序中分页查 然后生成也行,,反正是累加 需要全表扫描 而且顺序
接近 7 年之前 回复
weixin_42501429
weixin_42501429 好吧 找到一个 类似累加的写法:select ID,talktime,sum(talktime) over (order by to_number(talktime) desc ) from t_bill
接近 7 年之前 回复
jinnianshilongnian
jinnianshilongnian 暂时没有想到更快的,我觉得这个表只要分的合理应该不慢 比较是局部查
接近 7 年之前 回复
weixin_42501429
weixin_42501429 我知道累加 是需要循环去累加的,不知道是不是还有更快的方法,如果有我也觉得这个会很快。
接近 7 年之前 回复
jinnianshilongnian
jinnianshilongnian 对, 递归累加生成表 这个是当添加序列时 自动构建的。 其实就是和序列表 一起生成的,而且只需生成一次,下次直接用即可
接近 7 年之前 回复
weixin_42501429
weixin_42501429 相当于加个累加字段total,(累加顺序规则 可能是 大小顺序 或者ID),这样是可以直接去查询到某个值接近Y;这个思路蛮好的,但我不知道,前面这步需要多长时间能做完?效率快吗? 不知道我理解对不对呢?
接近 7 年之前 回复

两个数比较比加运算要省时间,尽量减少加的运算次数,已知Y的值,那么也就是说必须一个一个计算累加到Y附近,这个运算至少要进行一次,则1和2的方法比3要快,最好是从大到小排序,这么的话尽量少的加运算就可以累加到Y值。

0
zyn010101
zyn010101 select sum(talktime) from table ,表有10w记录,你没有进行加计算,但是数据库依然进行了10w次加法才能返回给你这个结果
接近 7 年之前 回复
zyn010101
zyn010101 二分的话你把sum计算交给了数据库,数据库还是要全表扫描那些记录,你二分几次,它就累计加几次(几万连续累加)的计算,你的sql没有这个算法,不代表计算机不去执行这个算法,数据库的count,avg,sum都需要加计算,跟你用代码实现是一样的。
接近 7 年之前 回复
weixin_42501429
weixin_42501429 如果需要循环几万次的才能到结果,2分的话 可能需要100次,你觉得谁快呢?当然2分1次没有单纯的循环处理1条的快,但是但上W的级别,你还觉得一条条快?
接近 7 年之前 回复
zyn010101
zyn010101 没错,是要循环几万次,但你要明白,你用sum(talktime)的时候,这个是交个数据库来计算的,它依然要计算几万次不是?即便每次都采用2分法来sum(talktime),你进行的累加的计算更多,不是吗?
接近 7 年之前 回复
weixin_42501429
weixin_42501429 count(talktime) 写错, 是 sum(talktime)
接近 7 年之前 回复
weixin_42501429
weixin_42501429 偽代码: FOR i IN 1..321987 LOOP select count(talktime) into tmp from t_bill where rownum <=i order talktime desc ; --将tmp与总量对比 --如果临界值在几万条之后,那么岂不是要循环几万次?这个快?我是请教有无更快算法。我说的方法 我是感觉不快。 END LOOP;
接近 7 年之前 回复

假设有一组值(大于等于0的数),总量级别:百万以上,需要求出总和在某个值(Y)的位置。实际情况中Y的值一般也是上万的
1.
(1000000个数的和) / 1000000 = 一百万的数的平均值
2.
Y / 一百万的数的平均值=等于大约需要累加多少数,然后以这个位置开始判断
3
相差值不大的话就慢慢比较,比较大的话,就从这个位置开始,按步骤1,继续

0
cttnbcj
ccccj 1.(1000000个数的和) / Y = 以这个数为步长 2 每次按这些这个步长 把数加起来和Y比较 相差不大就一个个慢慢比较 相差大的话 跳转到1 ,按1方法比较。 这个问题的任何方法都只能是O(N) 但是我说的方法二能比较快的接近。 jinnianshilongnian 第三方用到数据库.....,这个。。。呵呵
接近 7 年之前 回复
weixin_42501429
weixin_42501429 你这个其实就类似2分的做法,不过比例去做很不准的。 因为单数据可能很小 也可能很大,当然先排序再去按比例 会好些把。
接近 7 年之前 回复

1.(1000000个数的和) / Y = 以这个数为步长
2 每次按这些这个步长 把数加起来和Y比较
相差不大就一个个慢慢比较 相差大的话 跳转到1 ,按1方法比较。

这个问题的任何方法都只能是O(N)
但是我说的方法二能比较快的接近。

jinnianshilongnian
第三方用到数据库.....,这个。。。呵呵

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!