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)
相关阅读
和熟人做生意的技巧，不只是对做生意有用辞职HR要求你退还年终奖，什么逻辑关系为何国内的人都怕打电话做背调？Uber 自动车撞人录像ZT (转载)请问哪位大神可以帮忙推一下lyft?现在公司女同事比赛看谁能钓到富二代男同事一年的哪个时候加入谷歌比较好？G家做产品的组必须是美国公民，绿卡不行如何回答面试官问你为何从上一家公司离职关于印度和中国H1B的比较极品领导居然做了这么令人感动的事儿AspenTech (Bedford, MA): hiring Principal software develop被雷后, 什么时候去新公司上班谁需要的话给我站内信求亚麻的组照内部转组SDE1的【工作机会】Data Scientist/Operations Research Scientist O职场最大的不公平就是薪酬倒挂，让人火大面试通过跟刷题无关，只看外表气质和谈吐我是不是太敏感了
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。