logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
1G内存读10G文件
avatar
1G内存读10G文件# JobHunting - 待字闺中
m*1
1 楼
在看cracking的时候想到了这个东西，有一下几个不明白的地方：
1 假设有一个10G的文件里面都是string，怎么将所有的string全部排序，书上说
external sort，完了不停的merge，但是怎么split文件呢。
2 单纯的来说读大文件的问题，如果只有1G内存但是要读10G的文件，怎么搞。
求论坛上的大神们解释。
avatar
g*e
2 楼
os用virtual mem给你搞定了。当然你也可以自己分block读入

【在 m*******1 的大作中提到】
: 在看cracking的时候想到了这个东西，有一下几个不明白的地方：
: 1 假设有一个10G的文件里面都是string，怎么将所有的string全部排序，书上说
: external sort，完了不停的merge，但是怎么split文件呢。
: 2 单纯的来说读大文件的问题，如果只有1G内存但是要读10G的文件，怎么搞。
: 求论坛上的大神们解释。
avatar
m*1
3 楼
程序里面怎么分block实现？

os用virtual mem给你搞定了。当然你也可以自己分block读入

【在 g*****e 的大作中提到】
: os用virtual mem给你搞定了。当然你也可以自己分block读入
avatar
c*a
4 楼
read 1g data in to main memory and sort with some algorithm
write the sorted data on disk, repeat the step. then u have 10 files on the
disk, 1 g each
read first 90 mb of each file,total 900mb, sort them, the last 100mb for
output buffer , repeat......
这样行不行
avatar
m*1
5 楼
如何控制只读1g? 有什么stream控制器可以控制停在1G位置处，下一次接着读呢？还是
说有别的控制的方法？

the
for

【在 c*****a 的大作中提到】
: read 1g data in to main memory and sort with some algorithm
: write the sorted data on disk, repeat the step. then u have 10 files on the
: disk, 1 g each
: read first 90 mb of each file,total 900mb, sort them, the last 100mb for
: output buffer , repeat......
: 这样行不行
avatar
c*a
6 楼
c好像有个lseek什么的
avatar
f*n
7 楼
"read first 90 mb of each file,total 900mb, sort them"
But this is not necessarily the first 900mb of the sorted output.

the
for

【在 c*****a 的大作中提到】
: read 1g data in to main memory and sort with some algorithm
: write the sorted data on disk, repeat the step. then u have 10 files on the
: disk, 1 g each
: read first 90 mb of each file,total 900mb, sort them, the last 100mb for
: output buffer , repeat......
: 这样行不行
avatar
m*1
8 楼
在看cracking的时候想到了这个东西，有一下几个不明白的地方：
1 假设有一个10G的文件里面都是string，怎么将所有的string全部排序，书上说
external sort，完了不停的merge，但是怎么split文件呢。
2 单纯的来说读大文件的问题，如果只有1G内存但是要读10G的文件，怎么搞。
求论坛上的大神们解释。
avatar
g*e
9 楼
os用virtual mem给你搞定了。当然你也可以自己分block读入

【在 m*******1 的大作中提到】
: 在看cracking的时候想到了这个东西，有一下几个不明白的地方：
: 1 假设有一个10G的文件里面都是string，怎么将所有的string全部排序，书上说
: external sort，完了不停的merge，但是怎么split文件呢。
: 2 单纯的来说读大文件的问题，如果只有1G内存但是要读10G的文件，怎么搞。
: 求论坛上的大神们解释。
avatar
m*1
10 楼
程序里面怎么分block实现？

os用virtual mem给你搞定了。当然你也可以自己分block读入

【在 g*****e 的大作中提到】
: os用virtual mem给你搞定了。当然你也可以自己分block读入
avatar
c*a
11 楼
read 1g data in to main memory and sort with some algorithm
write the sorted data on disk, repeat the step. then u have 10 files on the
disk, 1 g each
read first 90 mb of each file,total 900mb, sort them, the last 100mb for
output buffer , repeat......
这样行不行
avatar
m*1
12 楼
如何控制只读1g? 有什么stream控制器可以控制停在1G位置处，下一次接着读呢？还是
说有别的控制的方法？

the
for

【在 c*****a 的大作中提到】
: read 1g data in to main memory and sort with some algorithm
: write the sorted data on disk, repeat the step. then u have 10 files on the
: disk, 1 g each
: read first 90 mb of each file,total 900mb, sort them, the last 100mb for
: output buffer , repeat......
: 这样行不行
avatar
c*a
13 楼
c好像有个lseek什么的
avatar
f*n
14 楼
"read first 90 mb of each file,total 900mb, sort them"
But this is not necessarily the first 900mb of the sorted output.

the
for

【在 c*****a 的大作中提到】
: read 1g data in to main memory and sort with some algorithm
: write the sorted data on disk, repeat the step. then u have 10 files on the
: disk, 1 g each
: read first 90 mb of each file,total 900mb, sort them, the last 100mb for
: output buffer , repeat......
: 这样行不行
avatar
s*2
15 楼
不知道string排序是什么意思
假设就是10G LW 整数，给一个4G内存空间对10G数排序，也假设有个subroutine能把1G
整数在4G内存中排序
1. read 1st 1G numbers from disk
2. sort using subroutine
3. read numbers from disk， make sure the smallest 1G number in ram and
write the larger ones back in disk
4. write the smallest 1G numbers back in disk
repeat 1 ~4 for the second 1G number till the end
Notes:
You may rescale the 4G memory to 1G or any other size
string 排序 要是指有index之类的结构 （比方每个string做hash），又可以基于此方
法对index操作

【在 m*******1 的大作中提到】
: 在看cracking的时候想到了这个东西，有一下几个不明白的地方：
: 1 假设有一个10G的文件里面都是string，怎么将所有的string全部排序，书上说
: external sort，完了不停的merge，但是怎么split文件呢。
: 2 单纯的来说读大文件的问题，如果只有1G内存但是要读10G的文件，怎么搞。
: 求论坛上的大神们解释。
avatar
f*n
16 楼
你这个“make sure the smallest 1G number in ram and write the larger ones
back in disk”打算具体怎么操作？什么复杂度？
还有，如果有n G，你要重复这个过程n次，每次要起码O(n)时间，那整个过程就起码要
O(n^2)。不是很好效率

1G

【在 s******2 的大作中提到】
: 不知道string排序是什么意思
: 假设就是10G LW 整数，给一个4G内存空间对10G数排序，也假设有个subroutine能把1G
: 整数在4G内存中排序
: 1. read 1st 1G numbers from disk
: 2. sort using subroutine
: 3. read numbers from disk， make sure the smallest 1G number in ram and
: write the larger ones back in disk
: 4. write the smallest 1G numbers back in disk
: repeat 1 ~4 for the second 1G number till the end
: Notes:
avatar
s*2
17 楼
我认为这道题的主要问题是对用户程序来说ram和disk都不是transparent，系统调用背
后实际上都是块操作，disk更是通过dma进行的，所以实际解决这个问题要用几个数据
结构rescaling和fine tuning每次传输的数据块的大小，才能提高效率/速度
单纯的强调操作次数是纯理论的，实际上根本不可能只对一个数在磁盘上改写，而这些
数又是随机的，所以必须首先对数据结构化，最基本的就是，划分1G内存，比如
- 读512M数进行排序
- 再每次从disk上读256M，
- 跟前面的512M数据比较，小的留下，大的存在一个临时的buffer，size 4K～256K，
这样可以一边比较一边把大的数回写到磁盘上
- 像你说的，这个可能O(n^2)，但这是cpu比较的次数，磁盘的读写要少的多，cpu比起
disk要便宜的多
我前面说的是一个大概的思路，实际实现要看具体数据内容，你有好的方法不妨说一下

【在 f*******n 的大作中提到】
: 你这个“make sure the smallest 1G number in ram and write the larger ones
: back in disk”打算具体怎么操作？什么复杂度？
: 还有，如果有n G，你要重复这个过程n次，每次要起码O(n)时间，那整个过程就起码要
: O(n^2)。不是很好效率
:
: 1G
avatar
S*1
18 楼
Unix has file descriptor, and use lseek such kind of thing so you can
control the size you want to read.
Not sure if it is in this case.
avatar
f*n
19 楼
你这个“跟前面的512M数据比较，小的留下”很容易需要O(n * 512mb)

【在 s******2 的大作中提到】
: 我认为这道题的主要问题是对用户程序来说ram和disk都不是transparent，系统调用背
: 后实际上都是块操作，disk更是通过dma进行的，所以实际解决这个问题要用几个数据
: 结构rescaling和fine tuning每次传输的数据块的大小，才能提高效率/速度
: 单纯的强调操作次数是纯理论的，实际上根本不可能只对一个数在磁盘上改写，而这些
: 数又是随机的，所以必须首先对数据结构化，最基本的就是，划分1G内存，比如
: - 读512M数进行排序
: - 再每次从disk上读256M，
: - 跟前面的512M数据比较，小的留下，大的存在一个临时的buffer，size 4K～256K，
: 这样可以一边比较一边把大的数回写到磁盘上
: - 像你说的，这个可能O(n^2)，但这是cpu比较的次数，磁盘的读写要少的多，cpu比起
avatar
s*2
20 楼
512M是sorted，是拿新的block 256MB 或 whatever 跟这个512M 里的数比，等512M排
好序，就被写回disk，下次就10G-512MB，以此类推 9G，8.5G, 。。。
当然就比较次数上算还是太复杂，但强调这个没有太多意义
还要看，这10G里的内容是什么，比方要是纯32bits整数肯定有重复的，就要看它们的
发布等等，而要是100个100MB的video就简单多了

【在 f*******n 的大作中提到】
: 你这个“跟前面的512M数据比较，小的留下”很容易需要O(n * 512mb)
相关阅读
RT请教公司内换title能要求多涨点工资吗？老板说不能一年内给同一个人发1099和W2让我还钱，请教1099和W2的问题uber 在中国被判了死刑[A家]空气床和早餐家一道onsite 题目面经加求建议有什么题比较体现水平但是国人比较会做的Startup offer求教Java/Web Developer Job in Silver Spring, MD湾区混startup，注意backdoor background check ...请教一下flamingos和其他大侠这个weblink失效了。。。国女在IT确实混的比国男强求 REDHAT MA 内推lc的题目质量越来越差了吧为什么recruiter把12月份的offer推到1月说一个我知道的国内码农的CASE吧 (转载)我发现准备面试的最好方法就是参加面试请教一个PERM期间换项目的问题狗家牛在Xoogler遍布各大IT公司高层【南湾】Milpitas主街1b1b出租 $1100
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。