|
精华帖 (1) :: 良好帖 (0) :: 新手帖 (11) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-10-09
J-catTeam 写道 niveko 写道 我觉得可以这样，
如果3000万数据在一个文件里面的话，可以用RandomAccessFile来读文件，每次读的时候数据小于2G内存就可以。然后用一个TreeMap(红黑树的实现)往里面一直放最多50条记录，当然每条记录需要实现Comparator接口，这样才能比较每条记录。放完了记录再接着往下读就可以，这样读一遍就可以选出前50条记录。也可以再针对这50条记录排序就行。 朋友··你看··jvm在windows上能控制的内存是在1.6g左右的，这里面肯定还有其他的开销，最后真正能放置数据的内存量是小于1.6g的，如果真的是把全部数据都往内存里面读（读到内存可以接受的最大值）···系统会很慢的，几乎被占完了~ 当然你的思路是很好的哈~~~ 你在linux下就可以超过2G，当然你读数据肯定不能按这个大小来读，你还得预估其他计算的开销，比如TreeMap的大小，还有数据的解码需要的内存等，我只是说说大体的思路， 
|
| 返回顶楼 | |
|
发表时间：2009-10-09
niveko 写道 J-catTeam 写道 niveko 写道 我觉得可以这样，
如果3000万数据在一个文件里面的话，可以用RandomAccessFile来读文件，每次读的时候数据小于2G内存就可以。然后用一个TreeMap(红黑树的实现)往里面一直放最多50条记录，当然每条记录需要实现Comparator接口，这样才能比较每条记录。放完了记录再接着往下读就可以，这样读一遍就可以选出前50条记录。也可以再针对这50条记录排序就行。 朋友··你看··jvm在windows上能控制的内存是在1.6g左右的，这里面肯定还有其他的开销，最后真正能放置数据的内存量是小于1.6g的，如果真的是把全部数据都往内存里面读（读到内存可以接受的最大值）···系统会很慢的，几乎被占完了~ 当然你的思路是很好的哈~~~ 你在linux下就可以超过2G，当然你读数据肯定不能按这个大小来读，你还得预估其他计算的开销，比如TreeMap的大小，还有数据的解码需要的内存等，我只是说说大体的思路， 嘿嘿~~~是哈 |
| 返回顶楼 | |
|
发表时间：2009-10-10
lnaigg 写道 我想的：
a. 3000w数据，分成3000组，每组1000条。分组不用占内存，前提是数据是顺序数据。 如果是顺序数组，，，直接取最后50条不就得了…… |
| 返回顶楼 | |
|
发表时间：2009-10-10
rrsy23 写道 这个题目 其实 没有什么标准 答案；
肯定看你怎么考虑的； 要是 我每条记录有个图像都是几M怎么办？ 呵呵！ 我们只能忽略每条记录列的大小；简单理解没条记录暂用很少空间； 3000w的数据再那里，在硬盘，已经在内存，在内存怎么存放？ 如果在硬盘，你读进来这么存放？ 读取I/O效率怎么样？ 很多问题要考虑； 其实是解决问题 思考问题能力； 要是我遇见这样题目，我肯定列出N种可能； 每种可能 什么思路？ 如果数据是存放在文件里的，就很好办了啊，保存一个50个数的最小堆，一路遍历就好了。 |
| 返回顶楼 | |
|
发表时间：2009-10-10
如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。
|
| 返回顶楼 | |
|
发表时间：2009-10-10
云中苍月 写道 如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。
自己犯傻，被2G内存的条件忽悠了。 其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。 这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。 |
| 返回顶楼 | |
|
发表时间：2009-10-10
云中苍月 写道 云中苍月 写道 如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。
自己犯傻，被2G内存的条件忽悠了。 其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。 这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。 朋友 你这样好像是不可行的 1：你50条数据的堆是吧，请问你50条数据你放什么数据？随意放置么？如果随意放置你怎么确定这50条数据在3000w数据中存在.当然你会说先select出来是吧，你觉得花多少时间? 2：你说50条数据每一条对比3000w的数据那么最后对比的次数就是3000w*50就是15亿次是吧？ 你觉得会花多少时间 我测试过，3000w的数据我要得到其中的一条数据要花我30秒的时间（至少），那么算算一共会花多少时间啊？ 当然，你的思路和别人不一样哈 |
| 返回顶楼 | |
|
发表时间：2009-10-11
J-catTeam 写道 云中苍月 写道 云中苍月 写道 如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。
自己犯傻，被2G内存的条件忽悠了。 其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。 这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。 朋友 你这样好像是不可行的 1：你50条数据的堆是吧，请问你50条数据你放什么数据？随意放置么？如果随意放置你怎么确定这50条数据在3000w数据中存在.当然你会说先select出来是吧，你觉得花多少时间? 2：你说50条数据每一条对比3000w的数据那么最后对比的次数就是3000w*50就是15亿次是吧？ 你觉得会花多少时间 我测试过，3000w的数据我要得到其中的一条数据要花我30秒的时间（至少），那么算算一共会花多少时间啊？ 当然，你的思路和别人不一样哈 1.这样做是肯定可以的，想想看大学课程里的外部排序是怎么做的。这道题目只是一个简化了的外部排序过程。 2.第二个问题我不想回答你，因为你没有明白我描述算法的意思，我的语文不太好所以建议你去读一下《计算机编程艺术》关于外部排序的章节。 考虑算法题的时候把什么数据库，什么select语句都扔掉，正常情况下考官不会要这样的答案。 |
| 返回顶楼 | |
|
发表时间：2009-10-12
云中苍月 写道 J-catTeam 写道 云中苍月 写道 云中苍月 写道 如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。
自己犯傻，被2G内存的条件忽悠了。 其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。 这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。 朋友 你这样好像是不可行的 1：你50条数据的堆是吧，请问你50条数据你放什么数据？随意放置么？如果随意放置你怎么确定这50条数据在3000w数据中存在.当然你会说先select出来是吧，你觉得花多少时间? 2：你说50条数据每一条对比3000w的数据那么最后对比的次数就是3000w*50就是15亿次是吧？ 你觉得会花多少时间 我测试过，3000w的数据我要得到其中的一条数据要花我30秒的时间（至少），那么算算一共会花多少时间啊？ 当然，你的思路和别人不一样哈 1.这样做是肯定可以的，想想看大学课程里的外部排序是怎么做的。这道题目只是一个简化了的外部排序过程。 2.第二个问题我不想回答你，因为你没有明白我描述算法的意思，我的语文不太好所以建议你去读一下《计算机编程艺术》关于外部排序的章节。 考虑算法题的时候把什么数据库，什么select语句都扔掉，正常情况下考官不会要这样的答案。 目前 貌似我只看懂了的做法， 前面大家说的都没明白！ 我的理解是 3000W条 无序数据，取某个条件的 前50条 一定至少 历便一次! 事先准备 一个 放50个“顺续”盒子， 然后依次读 3000w中的数据，每次仅仅读 内存允许的数据量，在拿这条数据 和 50个盒子里的数据对比，确定该数据能不能放进盒子， 直到数据循环完填满盒子。 这是一个单线程的做法。 如果是多线程的话， 就每个线程 读取指定“开始位置”和“结束位置”的数据，放入属于自己的盒子。 所有线程都完成后， 在对比 每个线程中 选出的50个盒子中的数据集合，放入最终的50个盒子.这样是不是会快些 |
| 返回顶楼 | |
|
发表时间：2009-10-12
云中苍月 写道 J-catTeam 写道 云中苍月 写道 云中苍月 写道 如果可以使用外部存储（文件/数据表）进行辅助的话可以分批排序再用堆排序合并，堆排序只需要输出前50条就可以了。
自己犯傻，被2G内存的条件忽悠了。 其实这道题只要在内存里做一个大顶堆，堆里面只有50条数据，遍历所有数据，如果当前数据大于堆顶值则直接看下一条，否则将堆顶的值替换出来并重新组合堆……遍历结束后堆里面留下的值自然是前五十项。 这题目的解法和N个数据中取出最小（大）的X个值的做法完全一样。 朋友 你这样好像是不可行的 1：你50条数据的堆是吧，请问你50条数据你放什么数据？随意放置么？如果随意放置你怎么确定这50条数据在3000w数据中存在.当然你会说先select出来是吧，你觉得花多少时间? 2：你说50条数据每一条对比3000w的数据那么最后对比的次数就是3000w*50就是15亿次是吧？ 你觉得会花多少时间 我测试过，3000w的数据我要得到其中的一条数据要花我30秒的时间（至少），那么算算一共会花多少时间啊？ 当然，你的思路和别人不一样哈 1.这样做是肯定可以的，想想看大学课程里的外部排序是怎么做的。这道题目只是一个简化了的外部排序过程。 2.第二个问题我不想回答你，因为你没有明白我描述算法的意思，我的语文不太好所以建议你去读一下《计算机编程艺术》关于外部排序的章节。 考虑算法题的时候把什么数据库，什么select语句都扔掉，正常情况下考官不会要这样的答案。 你不回答我可以，但是我可以继续问吧，我还是那个意思 堆里面的50条数据你从哪里来？ 如果你要select出来我可以告诉你至少时间要花40秒左右（假设数据在一张表中）， 好吧 你现在有了数据了你又说要比较，再交换。朋友你试着写过么？要花多少时间。这道题考虑的肯定是以性能为主。我可以很负责任的告诉你我试过，mysql里面放3000w的数据一条select语句搞出来几条数据大概就是一分钟，如果按照你的这中思路，你觉得会花多长时间，每一个人提出来的想法都是可以实现的。我一条select *id from table order by ** limit0，50都能搞出来~ 所以关键是性能。 当然 只是论题 不论人·呵呵 |
| 返回顶楼 | |
