`
J-catTeam
  • 浏览: 9539 次
  • 性别: Icon_minigender_1
  • 来自: 成都
文章分类
社区版块
存档分类
最新评论

3000w数据的表,取某项字段前50项数据 ,内存2g

阅读更多

偶然看到这个题,就想了一下怎么做,大体实现思路是这样子的,3000w的数据划分为1000段,也就是1-3w为一段,30001-6w项为第二段,依次类推,从每3w的数据中提取出前50条数据(这个根据sql排序就能取出来,2个g的内存够了),最后1000个50就会产生5w个数据,最后提取出来的5w的数据放置到ArrayList中去,最后5w的数据统一排序,取出前50条。5w*5w的对比与交换是可以搞定的。具体实现,等最近的项目完了 用多线程试试!~
分享到:
评论
33 楼 rrsy23 2009-10-07  
这个题目 其实 没有什么标准 答案;

肯定看你怎么考虑的;

要是 我每条记录有个图像都是几M怎么办?

呵呵!

我们只能忽略每条记录列的大小;简单理解没条记录暂用很少空间;

3000w的数据再那里,在硬盘,已经在内存,在内存怎么存放?

如果在硬盘,你读进来这么存放?

读取I/O效率怎么样?

很多问题要考虑;

其实是解决问题 思考问题能力;

要是我遇见这样题目,我肯定列出N种可能;

每种可能 什么思路?

32 楼 mikeandmore 2009-10-07  
liuxuan620 写道
最小堆的时间复杂度是O(nlogk),其中k=50,n=3000w
你说的遍历的时间复杂度是O(nk)
就单线程来说的话,用最小堆肯定是最优的


xiaokan 写道
其实最快的方法就是遍历整组数据,取最大值,然后删掉它,重复50次,每次时间代价为O(3000w),50次就是1.5billion,这个复杂度不错了,至少比那些O(n log n)的堆好


re
其实50对于30M来说,应该算是常数了,于是能算成 O(n)了。。。。
当然那个O(nk)的也就。。。。。。。。。

不过那个 O(nk)的肯定慢死了。。。光seek就能seek到死。。。

PS原来这里有人一帖多发啊。。。
31 楼 mikeandmore 2009-10-07  
J-catTeam 写道
GooHome 写道
xiaokan 写道
其实最快的方法就是遍历整组数据,取最大值,然后删掉它,重复50次,每次时间代价为O(3000w),50次就是1.5billion,这个复杂度不错了,至少比那些O(n log n)的堆好


我说了一个3000W和内存的分支点 大家都没有注意到吧。

一个算法的好与坏,不是算法的本身,而是算法的应用范围。oracle有什么成本优化什么的。

这道题目到底考什么,我想出题的公司比我们更了解。本身并不难的题目,被大家推成热点话题。
可能是大家没有真正接触过大数据量,3000W对于一般的大企业而言是一个很小的数据量,我接触过
的一个小型商品连锁零售商,全日本前3甲吧。一天的数据量都超过这个数目,就更别说大型连锁超市了。
分析最畅销的商品是什么?这就是题目实际应用的一种吧。

考的就是你的分析能力和基本计算机优化常识。

CPU >Cache>Mem>HDD 这是目前CPU优化的基本原则。

按照常识来讲,数据库存在硬盘上取数需要内存。
内存装不下,就要想办法 这是key 1

暂时走开暂存



内存不足的办法?
不是分批取么?

分页。。。。
这里可以偷懒直接mmap。。。。如果vm够的话
30 楼 liuxuan620 2009-10-06  
最小堆的时间复杂度是O(nlogk),其中k=50,n=3000w
你说的遍历的时间复杂度是O(nk)
就单线程来说的话,用最小堆肯定是最优的


xiaokan 写道
其实最快的方法就是遍历整组数据,取最大值,然后删掉它,重复50次,每次时间代价为O(3000w),50次就是1.5billion,这个复杂度不错了,至少比那些O(n log n)的堆好

29 楼 J-catTeam 2009-10-05  
GooHome 写道
xiaokan 写道
其实最快的方法就是遍历整组数据,取最大值,然后删掉它,重复50次,每次时间代价为O(3000w),50次就是1.5billion,这个复杂度不错了,至少比那些O(n log n)的堆好


我说了一个3000W和内存的分支点 大家都没有注意到吧。

一个算法的好与坏,不是算法的本身,而是算法的应用范围。oracle有什么成本优化什么的。

这道题目到底考什么,我想出题的公司比我们更了解。本身并不难的题目,被大家推成热点话题。
可能是大家没有真正接触过大数据量,3000W对于一般的大企业而言是一个很小的数据量,我接触过
的一个小型商品连锁零售商,全日本前3甲吧。一天的数据量都超过这个数目,就更别说大型连锁超市了。
分析最畅销的商品是什么?这就是题目实际应用的一种吧。

考的就是你的分析能力和基本计算机优化常识。

CPU >Cache>Mem>HDD 这是目前CPU优化的基本原则。

按照常识来讲,数据库存在硬盘上取数需要内存。
内存装不下,就要想办法 这是key 1

暂时走开暂存



内存不足的办法?
不是分批取么?
28 楼 GooHome 2009-10-05  
xiaokan 写道
其实最快的方法就是遍历整组数据,取最大值,然后删掉它,重复50次,每次时间代价为O(3000w),50次就是1.5billion,这个复杂度不错了,至少比那些O(n log n)的堆好


我说了一个3000W和内存的分支点 大家都没有注意到吧。

一个算法的好与坏,不是算法的本身,而是算法的应用范围。oracle有什么成本优化什么的。

这道题目到底考什么,我想出题的公司比我们更了解。本身并不难的题目,被大家推成热点话题。
可能是大家没有真正接触过大数据量,3000W对于一般的大企业而言是一个很小的数据量,我接触过
的一个小型商品连锁零售商,全日本前3甲吧。一天的数据量都超过这个数目,就更别说大型连锁超市了。
分析最畅销的商品是什么?这就是题目实际应用的一种吧。

考的就是你的分析能力和基本计算机优化常识。

CPU >Cache>Mem>HDD 这是目前CPU优化的基本原则。

按照常识来讲,数据库存在硬盘上取数需要内存。
内存装不下,就要想办法 这是key 1

暂时走开暂存


27 楼 xiaokan 2009-10-05  
其实最快的方法就是遍历整组数据,取最大值,然后删掉它,重复50次,每次时间代价为O(3000w),50次就是1.5billion,这个复杂度不错了,至少比那些O(n log n)的堆好
26 楼 rong889 2009-10-04  
C_J 写道
-堆排序是快速排序的基础么???我记得好像是不同的排序

-快速排序可以加分治,把数据拆分成很多块,然后分别排序...

-楼上几位仁兄的意思是不是以下这个意思??
如取个堆大小为N个节点的堆,先做一个最小堆排序,大致如:
           4
      5         6
  7      8    9    10

然后换掉底下的一层的某数 ,如换掉这里的7为3,然后再排个序..达到如下效果

第一趟:
             4
     3            6
5         8    9      10

第二趟:
            3
      4            6
5         8    9       10

当然内存里取50个节点浪费了内存.可以拆分30000个数据,用多线程分别排序,最后取最小的50个数据.

-那么,以把30000拆分成块,一点一点做,取最后取最小50个呢?这样很多排序都可以呀? 用快速排序,取小于2G的数据到内存,这批做完,释放heap上内存,然后再做下批,最后取最小50个,这完全用代码能现场写出来..


-如果是那意思的话,这题目30000的数据真忽悠人的...


-这职位月薪10K??




同意你的看法,如果只是排序的话,多大数据量都没问题。


另外之前碰到过这样一个题目,大家讨论一下:
一个8G的访问日志文件,每行一个URL,如何统计出访问量最高的10个URL(Top 10)?
25 楼 C_J 2009-10-04  
-堆排序是快速排序的基础么???我记得好像是不同的排序

-快速排序可以加分治,把数据拆分成很多块,然后分别排序...

-楼上几位仁兄的意思是不是以下这个意思??
如取个堆大小为N个节点的堆,先做一个最小堆排序,大致如:
           4
      5         6
  7      8    9    10

然后换掉底下的一层的某数 ,如换掉这里的7为3,然后再排个序..达到如下效果

第一趟:
             4
     3            6
5         8    9      10

第二趟:
            3
      4            6
5         8    9       10

当然内存里取50个节点浪费了内存.可以拆分30000个数据,用多线程分别排序,最后取最小的50个数据.

-那么,以把30000拆分成块,一点一点做,取最后取最小50个呢?这样很多排序都可以呀? 用快速排序,取小于2G的数据到内存,这批做完,释放heap上内存,然后再做下批,最后取最小50个,这完全用代码能现场写出来..


-如果是那意思的话,这题目30000的数据真忽悠人的...


-这职位月薪10K??


24 楼 downpour 2009-10-03  
最小化堆,能够找到一个数在一个序列中的位置。这个算法如果我没记错的话是快速排序的基础,学过数据结构的应该知道。

所以这个题很简单,只要每次在内存允许的范围内取数据放入内存,去做最小化堆的筛选。然后根据每次筛选的位置结果,把多余的数据去掉。然后重复多次即可。
23 楼 J-catTeam 2009-10-03  
lnaigg 写道
J-catTeam 写道
lnaigg 写道
我想的:
a. 3000w数据,分成3000组,每组1000条。分组不用占内存,前提是数据是顺序数据。
b. 每组数据找出最大值,并记录该组ID。找最大值的算法只需要1K内存,存各族最大值及组ID是3K内存。
c. 对各组的最大值进行排序,找出前50组ID。3K数据排序,内存需求也不高。
d. 排序前50组数据,总共就剩下5万条了,直接排序即可。
e. 5万条数据也可以再按之前方法细分一次。



朋友这个是有问题的,1000条里面你每个只找一条 如果莫一个1000条的第二大的数是整个3000w数据第2大的数,那么你不是取不到了么?


看清我的算法,明显不是简单地取每组最大那个数。


看到了哈,这个要复杂些
22 楼 lnaigg 2009-10-03  
J-catTeam 写道
lnaigg 写道
我想的:
a. 3000w数据,分成3000组,每组1000条。分组不用占内存,前提是数据是顺序数据。
b. 每组数据找出最大值,并记录该组ID。找最大值的算法只需要1K内存,存各族最大值及组ID是3K内存。
c. 对各组的最大值进行排序,找出前50组ID。3K数据排序,内存需求也不高。
d. 排序前50组数据,总共就剩下5万条了,直接排序即可。
e. 5万条数据也可以再按之前方法细分一次。



朋友这个是有问题的,1000条里面你每个只找一条 如果莫一个1000条的第二大的数是整个3000w数据第2大的数,那么你不是取不到了么?


看清我的算法,明显不是简单地取每组最大那个数。
21 楼 J-catTeam 2009-10-03  
kunee 写道
上学的时候没学过分冶还是咋地

分分不就出来了。。。

恩 忘记了 赐教?
20 楼 kunee 2009-10-03  
上学的时候没学过分冶还是咋地

分分不就出来了。。。
19 楼 J-catTeam 2009-10-02  
GooHome 写道
最小堆 大家知道吗? 分冶法呀!

按照pk顺序去取50(这样数据库不会排序,排序就是一个死)然后合并 砍掉50 继续去下面的50 复杂度 我就不说了。

这是简单的而且普遍的处理办法。


补充一点:
这里的3000W件 其实一个幌子,而且还是一个分支点。

如果 3000W条记录*行记录字节数>2G的临界 不能一次取得内存队列里 (注意伪列和排序问题)

分析问题要一步一步来,然后就是多线程问题 加什么该死的二分法呀什么的。

这道题目不值10K月薪。



朋友能解释的再详细一点么?
在上面有一个朋友提到了 他说这道题是考验算法的 如果真是考验数据量的话,数据库分层,切分表什么的就能做的 ,是DBA考虑的东西,
所以这道题 ··我已经有点晕了

你最后说的不值10k还是不止10k啊?
18 楼 GooHome 2009-10-02  
最小堆 大家知道吗? 分冶法呀!

按照pk顺序去取50(这样数据库不会排序,排序就是一个死)然后合并 砍掉50 继续去下面的50 复杂度 我就不说了。

这是简单的而且普遍的处理办法。


补充一点:
这里的3000W件 其实一个幌子,而且还是一个分支点。

如果 3000W条记录*行记录字节数>2G的临界 不能一次取得内存队列里 (注意伪列和排序问题)

分析问题要一步一步来,然后就是多线程问题 加什么该死的二分法呀什么的。

这道题目不值10K月薪。

17 楼 sky726 2009-10-02  
J-catTeam 写道
sky726 写道
恕我愚昧,不是很清楚题目意思
“取某项字段前50项数据”

比如这字段全部都是数字(1~3000w升序)
那题目做出来的结果,是不是1~50?
如果是这样,那分段来做结果怎么会对呢?

朋友你看哈 分成1000段 我取出来的是每段的前50条数据 这个样子就是为了避免 前面那位朋友出现的情况
···3000w的数据在数据库里面直接排序是不可能的~

原来如此,我想说的就是前面那位朋友的情况
16 楼 J-catTeam 2009-10-02  
sky726 写道
恕我愚昧,不是很清楚题目意思
“取某项字段前50项数据”

比如这字段全部都是数字(1~3000w升序)
那题目做出来的结果,是不是1~50?
如果是这样,那分段来做结果怎么会对呢?

朋友你看哈 分成1000段 我取出来的是每段的前50条数据 这个样子就是为了避免 前面那位朋友出现的情况
···3000w的数据在数据库里面直接排序是不可能的~
15 楼 J-catTeam 2009-10-02  
lnaigg 写道
我想的:
a. 3000w数据,分成3000组,每组1000条。分组不用占内存,前提是数据是顺序数据。
b. 每组数据找出最大值,并记录该组ID。找最大值的算法只需要1K内存,存各族最大值及组ID是3K内存。
c. 对各组的最大值进行排序,找出前50组ID。3K数据排序,内存需求也不高。
d. 排序前50组数据,总共就剩下5万条了,直接排序即可。
e. 5万条数据也可以再按之前方法细分一次。



朋友这个是有问题的,1000条里面你每个只找一条 如果莫一个1000条的第二大的数是整个3000w数据第2大的数,那么你不是取不到了么?
14 楼 boobmoom 2009-10-02  
题目确实写的不太清楚
对于我们这些小菜,不理解其中的一些默认条件
高手常常会把问题往难了想
我们就常常会把问题往简单了想

相关推荐

    access库转sqlite库

    电脑配置:cpu:E7500,内存2G 6、导入数据时,是一次性打开access表的,并循环一条条插入,如果有太多的数据,如百W,则没测试过 没启用成批插入数据,不知启用成批插入数据,性能会不会成倍的提升。 7、sqlite下,...

    数据库转sqlite数据库

    电脑配置:cpu:E7500,内存2G 6、导入数据时,是一次性打开access表的,并循环一条条插入,如果有太多的数据,如百W,则没测试过 没启用成批插入数据,不知启用成批插入数据,性能会不会成倍的提升。 7、sqlite下,...

    基于ARM架构服务器部署docker-compose

    基于arm64版本的docker-compose文件

    附件3-4:台区智能融合终端全性能试验增值税发票开具确认单.docx

    台区终端电科院送检文档

    埃夫特机器人Ethernet IP 通讯配置步骤

    埃夫特机器人Ethernet IP 通讯配置步骤

    rv320e机器人重型关节行星摆线减速传动装置研发.rar

    rv320e机器人重型关节行星摆线减速传动装置研发

    气缸驱动爬杆机器人的设计().zip

    气缸驱动爬杆机器人的设计().zip

    软件工程中期答辩1234567

    56tgyhujikolp[

    基于OpenCV的数字身份验证系统:人脸检测、训练与识别的Python实现

    内容概要:本文档提供了基于OpenCV的数字身份验证系统的Python代码示例,涵盖人脸检测、训练和识别三个主要功能模块。首先,通过调用OpenCV的CascadeClassifier加载预训练模型,实现人脸检测并采集多张人脸图像用于后续训练。接着,利用LBPH(局部二值模式直方图)算法对面部特征进行训练,生成训练数据集。最后,在实际应用中,系统能够实时捕获视频流,对比已有的人脸数据库完成身份验证。此外,还介绍了必要的环境配置如依赖库安装、文件路径设置以及摄像头兼容性的处理。 适合人群:对计算机视觉感兴趣的研发人员,尤其是希望深入了解OpenCV库及其在人脸识别领域的应用者。 使用场景及目标:适用于构建安全认证系统的企业或机构,旨在提高出入管理的安全性和效率。具体应用场景包括但不限于门禁控制系统、考勤打卡机等。 其他说明:文中提供的代码片段仅为基本框架,可根据实际需求调整参数优化性能。同时提醒开发者注意隐私保护法规,合法合规地收集和使用个人生物识别信息。

    Java并发编程面试题详解:123道经典题目解析与实战技巧

    内容概要:本文档详细介绍了Java并发编程的核心知识点,涵盖基础知识、并发理论、线程池、并发容器、并发队列及并发工具类等方面。主要内容包括但不限于:多线程应用场景及其优劣、线程与进程的区别、线程同步方法、线程池的工作原理及配置、常见并发容器的特点及使用场景、并发队列的分类及常用队列介绍、以及常用的并发工具类。文档旨在帮助开发者深入理解和掌握Java并发编程的关键技术和最佳实践。 适合人群:具备一定Java编程经验的研发人员,尤其是希望深入了解并发编程机制、提高多线程应用性能的中级及以上水平的Java开发者。 使用场景及目标:①帮助开发者理解并发编程的基本概念和技术细节;②指导开发者在实际项目中合理运用多线程和并发工具,提升应用程序的性能和可靠性;③为准备Java技术面试的候选人提供全面的知识参考。 其他说明:文档内容详尽,适合用作深度学习资料或面试复习指南。建议读者结合实际编码练习,逐步掌握并发编程技巧。文中提到的多种并发工具类和容器,均附有具体的应用场景和注意事项,有助于读者更好地应用于实际工作中。

    个人健康与健身追踪数据集,包含了日常步数统计、睡眠时长、活跃分钟数以及消耗的卡路里,适用于数据分析、机器学习

    这个数据集包含了日常步数统计、睡眠时长、活跃分钟数以及消耗的卡路里,是个人健康与健身追踪的一部分。 该数据集非常适合用于以下实践: 数据清洗:现实世界中的数据往往包含缺失值、异常值或不一致之处。例如,某些天的步数可能缺失,或者存在不切实际的数值(如10,000小时的睡眠或负数的卡路里消耗)。通过处理这些问题,可以学习如何清理和准备数据进行分析。 探索性分析(发现日常习惯中的模式):可以通过分析找出日常生活中的模式和趋势,比如一周中哪一天人们通常走得最多,或是睡眠时间与活跃程度之间的关系等。 构建可视化图表(步数趋势、睡眠与活动对比图):将数据转换成易于理解的图形形式,有助于更直观地看出数据的趋势和关联。例如,绘制步数随时间变化的趋势图,或是比较睡眠时间和活动量之间的关系图。 数据叙事(将个人风格的追踪转化为可操作的见解):通过讲述故事的方式,把从数据中得到的洞察变成具体的行动建议。例如,根据某人特定时间段内的活动水平和睡眠质量,提供改善健康状况的具体建议。

    《基于YOLOv8的港口船舶靠泊角度偏差预警系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    nginx 访问访问日志按天切割 shell脚本

    nginx

    《基于YOLOv8的核废料运输容器密封性检测系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    《基于YOLOv8的农业无人机播种深度监测系统》(包含源码、可视化界面、完整数据集、部署教程)简单部署即可运行。功能完善、操作简单,适合毕设或课程设计.zip

    资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。

    uniapp知识付费(流量主)demo

    模拟知识付费小程序,可流量主运营模式

    java高并发之分片上传

    什么是普通上传 调用接口一次性完成一个文件的上传。 普通上传2个缺点 文件无法续传,比如上传了一个比较大的文件,中间突然断掉了,需要重来 大文件上传太慢 解决方案 分片上传

    英二2010-2021阅读理解 Part A 题干单词(补).pdf

    英二2010-2021阅读理解 Part A 题干单词(补).pdf

    2023-04-06-项目笔记 - 第四百五十五阶段 - 4.4.2.453全局变量的作用域-453 -2025.04-01

    2023-04-06-项目笔记-第四百五十五阶段-课前小分享_小分享1.坚持提交gitee 小分享2.作业中提交代码 小分享3.写代码注意代码风格 4.3.1变量的使用 4.4变量的作用域与生命周期 4.4.1局部变量的作用域 4.4.2全局变量的作用域 4.4.2.1全局变量的作用域_1 4.4.2.453局变量的作用域_453- 2025-04-01

    友缘公司钢材管理平台微信小程序的设计与实现.zip

    微信小程序项目课程设计,包含LW+ppt

Global site tag (gtag.js) - Google Analytics