一个临界点的问题

假设有一组值(大于等于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问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
临界点问题思考
零界点问题思考nn背景: n公司项目年度活动,需求如下:nnn1.用户给主播送礼,每收一个礼物获得一积分 n2.活动持续15天 每天主播会进行排名,根据排名进行晋级,未晋级的主播视为淘汰,不再记录积分。第一天N进50 ,第二天50进30……n3.每次晋级后积分重新计算nnnnnnn整体流程nnnn礼物处理流程:前端-&amp;amp;gt;nginx负载-&amp;amp;gt;直播间服务模块-&amp;amp;gt;礼物Mq-&amp;amp;gt;活动服务...
经典谷歌面试题-扔鸡蛋问题
假如有100层楼,总共有2个鸡蛋。需要多少次才能试探出临界点,比如,在第三层扔下去,不碎;在第四层扔下去,碎了,那第三层和第四层就是临界点。 n  如果之前没准备过的话,大概第一个想到的就是二分法。nn1. 二分法nn  首先在第50层丢第一个鸡蛋,若鸡蛋碎了,则在第一层开始往上丢鸡蛋,最坏情况是试探49+1次,为什么要从第一层开始尝试呢,因为只有2个鸡蛋;若鸡蛋没碎,则在75层丢第二次,若碎了则...
两个玻璃球求临界楼层问题
问题描述:rn有一栋100层高的大楼,给你两个完全相同的玻璃球。假设从某一层开始,丢下玻璃球会摔碎。那么怎么利用手中的两个球,用什么最优策略知道这个临界的层是第几层。rnrnrnrn问题答案:rn考虑best-worse case最坏情况下最优。也就是说假如你的算法是从第一楼逐楼往上试,那么相应最坏的情况是在100楼破,相应的是一百次。rn这种情况下最优策略也就是从14楼开始递减间隔的办法,wor
接口限流算法(关于临界点处理)
关于接口限流算法总结
临界点--跨过这个槛,你就成功了|多元思维模型No.13
n n n 每天智慧一点点,这里是大辉总结的多元思维模型的第13篇。n冰在超过0℃之后就化成了水,水在超过100℃之后又变成了水蒸气。因此,0℃是水和冰的临界点,100℃是液态水和水蒸气的临界点。自然界的物理变化过程中存在这样的临界点,其前后物质的性质发生了很大的变化。n这给我们的启示就是:临界点很重要,有时候再坚持一下,到了临界点,就会发生质的变化。n临界点的定义:...
Integer临界点
Integer临界点,也可以说Integer在128这里会开辟新的空间,integer在一段内是相等的,在另一段中却是不等的。n如下代码:nInteger m = 127;nInteger n = 127;n在这里 n == m。nnInteger m = 128 ;nInteger n = 128;n这里 n!=m。nn如果Integer m = new Integer(1);n Integer...
中国微生物组计划—农作物微生物组:跨越转化临界点的现代生物技术
农作物微生物组:跨越转化临界点的现代生物技术白 洋1** 钱景美1 周俭民1 钱 韦2** n1 中国科学院遗传与发育生物学研究所 北京 100101 n2 中国科学院微生物研究所 北京 100101摘要在微生物组技术体系中,农作物微生物组具有较好的研究基础和广阔的应用前景,已经处于从基础研究成果向田间应用转化的关键时期。目前,该领域在农作物-微生物组-土壤环境
图的遍历-邻接矩阵-dfs
图的遍历-邻接矩阵的深度优先搜索
angular学习之ng-bloak 解决闪屏问题;
&amp;lt;!doctype html&amp;gt;n &amp;lt;html lang=&quot;en&quot;&amp;gt;n &amp;lt;head&amp;gt;n &amp;lt;meta charset=&quot;UTF-8&quot;&amp;gt;n &amp;lt;title&amp;gt;Document&amp;lt;/title&amp;g
继续学习FreeRTOS~
写在前面:杰杰这个月很忙~所以并没有时间更新,现在健身房闭馆装修,晚上有空就更新一下!其实在公众号没更新的这段日子,每天都有兄弟在来关注我的公众号,这让我受宠若惊,在这里谢谢大家的支持啦!!谢谢^nn在这里我们就跟着火哥的书来学习一下FreeRTOS的消息队列,这本书我觉得写得很好,基本都讲解到了,关于什么是消息队列,就请大家去看书,基础知识我暂时不说了。n声明:本书绝大部分内容来自《FreeR...
如何有效突破DevOps转型的临界点.pdf
如何有效突破DevOps转型的临界点.pdf
100层楼和两个玻璃球的问题
问题:n有一栋100层高的大楼,给你两个完全相同的玻璃球。假设从某一层开始,丢下玻璃球会摔碎。n那么怎么利用手中的两个球,用什么最优策略知道这个临界的层是第几层?nnnn解决:
MACD波段操作的运用
1、DIF快线的运用n1.1、DIF波段操作要点nnnnDIF与0轴的关系n行情分析n持仓建议nnnnn0轴之上nDIF在0轴之上,并向上移动是多头上涨行情n持仓为主nnn0轴之下nDIF在0轴之下,并向下移动是空头下跌行情n空仓为主nnn0轴之上n0轴之上,但向下移动,防止随时进入空头而失去利润,此时结合波浪理论和成交量综合判断,在放量上涨中的第三浪和第...
奇点真的存在吗?面对强人工智能我们应该乐观还是悲观?
n n n nnnnnimagenn大数据文摘出品n编译:Zoe Zuo、王一丁、蒋宝尚n随着人工智能的不断发展,几十年后,人工智能在人类生活中将扮演何种角色一直是学术界和商业界讨论的焦点。n在未来,AI是帮助人类完成了终极进化,还是给我们带来了毁灭?《终结者》系列以及最近热播的《西部世界》第二季呈现的剧情在一定程度上也反映了人类的思考。nnnnnnimagenn西部...
hover样式不停地触发
hover样式不停地触发n让外层的元素触发伪类,里面的元素进行动画即可。n一般简单的动画效果都可以这样操作,父元素触发,子元素进行动画。n举个例子:n下面我想做一个倒三角,当鼠标移动上去,三角反转的效果。nn这是刚开始的样子nn这是鼠标移上去的样子。n然后html部分:nn结果问题就出来了。就是当移动到一个临界点时,三角不停地闪动,因为截图不了,就没有放图了。n后来发现原因,像hover一般是给父...
云端转型突破临界点,金蝶云加速企业云服务落地
作者:刘学习  | 小编:小葱任何事务都有临界点,不管是云计算、大数据、物联网、人工智能、区块链等技术,还是企业数字化转型与管理重构,当超过了某个临界点时,一切都将改变。“数字化的爆发式增长才刚刚开始,新技术、新链接、新服务、新生态、新模式不断涌现。”3月30日,“金蝶云——无限可能”全国巡展来到了北京,金蝶云事业部副总经理韩革缨在主题演讲中说。韩革缨接受中国软件网记者的采访韩革缨在随后接受记者采
临界点理论 张恭庆 经典
这是学习临界点理论的经典书籍,是张恭庆院士80年代的书,非常经典
单体应用缺陷与微服务特点
单体应用(All in one) 程序缺陷1. 先天性缺陷:难以分布式部署和扩容n2. 系统性风险:一个组件的缺陷导致真个进程崩溃n3. 运维风险:系统升级、Bug修复、故障排查存在风险n4. 难以可持续发展:业务范围拓展后,难以复用原有的服务,又要重新开发n微服务特点1. 先天分布式:每个微服务能独立部署和提供服务,通常部署多个实例n2. 无状态:微服务基本都是无状态服务,容易平滑扩容n3. 积木
功能测试用例测试点 - 整理
web功能测试点:nn一、输入框nn字符型输入框:n (1)字符型输入框:英文全角,英文半角,数字,空或者空格,特殊字符(共32个,特别要注意单引号,下划线,双引号,&amp;amp;),禁止直接输入特殊字符时,使用“粘贴”、“拷贝”功能尝试输入。n (2)长度检查:最小长度,最大长度,最小长度-1,最大长度+1,输入超长字符。n (3)空格检查:输入的字符间有空格,字符后有空格,字符前后有空格。n (4...
二分查找及引申问题
1.在有序不重复元素中查找:nnnpublic int BS(int[] num,int x) {n int low = 0,high = num.length;n int mid;n while(low &amp;lt;= high){n mid = (low + high)/2;n if(x == num[mid]) return mid;n ...
Logistic回归(1)
什么是回归?rn假设现在有一些数据点,我们用一条直线对这些点进行拟合(该线称为最佳拟合直线),这个拟合过程就称作回归。rn rn涉及到回归问题,我们借助Sigmoid函数来处理,Sigmoid函数:rnrnrnrnx=0时,函数值是0.5,x越大函数值越趋近于1,x越小函数值越趋近于0。rn如果x的刻度足够大Sigmoid函数也可以堪称一个单位阶跃函数。之所以采用Sigmoid来解决回归问题,是因
能量泛函和变分法
首先了解“泛函数”概念:rn        rnrn通常的函数在 R或C(n是自然数)中的集合上定义。泛函数常在函数空间甚至抽象空间中的集合上定义,对集合中每个元素取对应值(实数或复数)。通俗地说,泛函数是以函数作为变元的函数。泛函数概念的产生与变分学问题的研究发展有密切关系。rnrn传统上,泛函通常是指一种定义域为函数,而值域为实数的“函数”。换句话说,就是从函数组成的一个向量空间到实数的一个映
matlab分布临界点与假设检验的关系
运用matlab演示假设检验的临界值及与置信水平、显著性水平之间的关系。通过图一眼就可以看出何时在拒绝域。
Natural 自然语言处理(NLP)「全解析」
原文来源: 机器人圈概要:在自然语言处理方面的研究已经延续了五十多年,而随着计算机的兴起,它的发展也早已超出了语言学的范畴。提起AI,你可能会不假思索的想到自然语言处理、人脸识别、无人驾驶等。那么,你对这些真的了解吗?接下来,我们就以自然语言处理为例,来仔细说一说。自然语言处理(Natural Language Processing),简称NLP,广义上定义为通过软件对诸如语音和文本这样的自然语言
数据结构(15)——--邻接矩阵存储练习
A - 邻接矩阵存储练习Descriptionn 给定一个无向连通图,顶点编号从0到n-1,用广度优先搜索(BFS)遍历,输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点,节点编号小的优先遍历)nInputn 输入第一行为整数n(0< n <100),表示数据的组数。 n 对于每组数据,第一行是三个整数k,m,t(0<k<100,0<m<(k-1)*k/2,0< t<k),表示有m条边,
最优阈值迭代实现图像分割
使用寻求最优阈值的方法,找到最佳的图像二值化分割的临界点灰度值
清晰解题:扔鸡蛋问题
一幢 100 层的大楼,给你两枚鸡蛋。假设,在第 n 层扔下鸡蛋,鸡蛋不碎,那么从第 n-1 层扔鸡蛋,鸡蛋也不会碎。两个鸡蛋一模一样,不碎的话可以扔无数次。目标是利用这两个鸡蛋找出临界楼层 t , 使得鸡蛋从 t 层扔下不会碎, 从 t+1 层扔下会碎。 nn现要求回答, 最少需要多少次尝试, 才能保证在最坏的情况下,找到楼层 t , 且需要给出尝试的策略。 nnn明确问题nn题目要求是考虑 在...
jQuery实现图片移动效果
实现双图片的左右移动效果。到达临界点后反向移动。
谷歌公司经典面试题扔鸡蛋的详细解读(一)
首先说一下大概的题目 rn题目:扔鸡蛋问题rnrn有2个鸡蛋,从100层楼上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎了,那么鸡蛋不会摔碎的临界点就是9层。rnrn问:如何用最少的尝试次数,测试出鸡蛋不会摔碎的临界点?rnrnrnrn  可以想象,最关键的地方有两个,一个是如何尝试的次数最少,还有最最重要的一点,你只有两个鸡蛋,都碎了就没办法找了这个地方也是我一开始忽略的地方,导致我不明...
系统规划--成本效益分析
rn一、系统规划系统成本:rn1、固定成本rn2、变动成本rn3、混合成本rn二、系统规划系统收益:rn1、有型收益rn2、无型收益rn三、盈亏临界分析rn利润 = (销售单价-单位变动成本)*销售量-总固定成本rn盈亏临界点销售量 = 总固定成本/(销售单价-单位变动成本)rn盈亏临界点销售额 =  总固定成本/(销售单价-总变动成本/销售收入)rn三、净现值分析rn1、公式:NPV = ∑(C...
进程与线程之生产者和消费者问题
    在学习进程和线程的过程中,毫无疑问肯定会学到多线程、进程间通信等相关问题。而这也是学习进程和多线程方面的一个重点。这篇文章主要介绍的是利用互斥量、锁以及使用Pthread库来实现生产者和消费者问题。1、临界区    临界区指的是共享内存进行访问的程序片段。在实现线程间同步就必须只有一个线程访问临界区。上图中进程A在T1时刻进入临界区,当运行到T2时刻的时候进程B试图进入临界区。因为此时进程...
欧拉-拉格朗日方程【转】
最近在看RGBD-Flow的文章,因为opticalnflow的思想中用了变分,所以需要了解一些泛函分析求极值的东西,这篇欧拉拉格朗日的文章是作者从wiki转载,留下来以备后用,话说最近看论文头好大,各种数学概念,讨厌微积分还做图像的孩纸伤不起啊~n文章转自拼装小火车博客http://www.cnblogs.com/summerRQ/articles/2396747.htmlnn 研究过程中常用到
CSS3 - 响应式表格项目实战
index.htmll<!doctype html>n<html>n<head>n<meta charset="utf-8">n<title></title>n<link href="https://cdn.bootcss.com/normalize/7.0.0/normalize.min.css" rel="stylesheet">n<link href="begin.css" rel="styl
前端-响应式布局
nnnn响应式基本语法n响应式外部样式nnnnnnnnnnnn响应式基本语法nn响应式布局的优缺点nnn 优点:面对不同分辨率设备,灵活性强,能够快捷地解决设备显示适应问题n n 缺点:兼容各种设备时所需工作量大丶效率低下丶代码累赘,会隐藏无用的元素,加载时间延长, n 其实这是一种折中性质的设计解决方案,由于多方面元素影响而达不到最佳效果,在一定程度上 n 改变了网站原有的布局结构,会...
数据
注 :关于邻接表的创建,输出链接rnhttps://blog.csdn.net/qq_42146775/article/details/84898997rn理解DFS/BFSrnrn算法rnvoid BFS(这个节点)rn{rn 标记这个节点rn 指向这个节点的第一个临界点rn while(节点!=NULL)rn {rn if(节点没有标记) BFS(这个节点)rn 标记过 则 指向下一个节点rn }rn}rnvoid D...
智能家居的现状与发展
智能家居的现状与发展 智能家居作为一个新生产业,处于一个导入期与成长期的临界点,市场消费观念还未形成,但随着智能家居市场推广普及的进一步落实,培育起消费者的使用习惯,智能家居市场的消费潜力必然是巨大的,产业前景光明。
张乐-如何有效突破DevOps转型的临界点
张乐-如何有效突破DevOps转型的临界点.pdf 高效运维社区合伙人、DevOps时代联合创始人 前百度资深敏捷教练、DevOps专家 国内首批Certified DevOps Master 全球TOP外企,国内一线互联网
oracle 分页大于等于小于分页临界点
正确的:rn[code=&quot;sql&quot;]rnSELECT * FROM (SELECT A.*,ROWNUM RN FROM ( rnselect * from t_agent t where t.agent_parent = 20020 rnand t.agent_state = 0 rnrn) A WHERE ROWNUM 0;rn[/code]rn错误的:这样只会取出21条数据,到临界点,...
【连载】临界点-产品思维与设计思维(7)
n n n 做产品的过程,本质是在和用户的心智进行交互,我们在不断努力尝试推动用户沿着期待的轨道和方向上走。既然是在推动,就一定存在一个点,用户可能过去,也可能不过去,需要我们以产品设计的方式提供推力或者拉力,这就是临界点。临界点就是压倒骆驼的最后一根稻草。是什么让用户决定注册产品开始使用的?往往就是多动那么一下手指、多学习思考一小下,用户就从门口溜走了。临界点往往是...
C#超市商场促销折扣满减
超市收银满减折扣小demo
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 区块链问题 ios视频开发问题