存放范围为0~FFFFFF中100个数字到1MB的文件中去？

onlyxuyang

回复 10# linux_c_py_php

system call是真的很慢啊,要走vfs的flow,每次新建文件的话还要建新的dentry,inode,file struct, balabalabala...

最好少从userspace进到kernel...

   

linux_c_py_php

... 你吹毛求疵了, 我不懂你欺负我就是了 -#-

我给楼主这个题目的一个可行方案是, 快慢根本不是需要考虑的问题, 如果这也算慢, 那么Mysql可以洗洗睡了:

1, 文件lseek到4 + 4 * 20 - 1 = 84 - 1 = 83B的偏移量, write 1 byte将文件扩充到84字节, 可以容纳记录当前元素个数的int, 以及40个int的存储空间.
2, mmap将84字节映射到内存, 进行初始化操作, 比如将计数设置为0, 40个槽位设置为-1.(进程共享访问需要做shared mutex以及使用S_IXOTH初始化锁编程技巧, 不懂你可以追问)
3, 查询:计数0, 直接返回, 非0, 遍历40个槽位即可.
4, 插入:遍历找一个空槽位, 计数+1.
5, 删除:遍历找到数值, 设置-1, 计数-1.

onlyxuyang 发表于 2012-09-20 22:45
回复 10# linux_c_py_php

system call是真的很慢啊,要走vfs的flow,每次新建文件的话还要建新的dentry,i ...

evaspring

坐看掐架

isscc

对范围建bitmap就好了。
因为数字的个数在100左右，假设数字的个数小于128个
把0-16M的范围分成256个块，每个块的地址空间为64K，因为数字的个数<128，所以，最多只有128个块里面有数字，所以至少有128个块里面没数字，那些没有数字的块是不需要存储的，也就是文件里面只需要最多不超过1M(64K * 12bit)的空间

内存中建一个索引，索引的内容为256个逻辑的块对应磁盘上实际的块的编号的映射，考虑到全部建到内存中，则至少需要256 * 7bit(寻址128bit共224个字节，内存中放不下，考虑对索引进行压缩

考虑把每8个逻辑块作为一个逻辑的单元，第一个字节用来存储这个逻辑单元对应的实际的物理地址的最小的那个(只需要7个bit)和一个标记位，该标记位用来表示该逻辑单元里面是否每个逻辑的块都存储对应着物理的块，用3个bit（0-7）来存储每个逻辑的块是该逻辑单元总第几个实际存在物理块的块，如果一个逻辑块不存在则设置为7.(如果一个逻辑的块的内部编号是7的话则根据前面说的1bit的flag来判断是不存在还是真实为7)。这样的话，索引总共需要128个字节。

在查询的时候，先映射到一个逻辑的块，把逻辑的块映射到逻辑单元里面，根据内部位图判断该逻辑块是否存在，如果存在则根据内部位图+起始地址算成实际的地址，然后去磁盘上取实际地址对应的bitmap

如果假设还需要预留一些内存用来存储从磁盘中读取的数据或者中间结果，对压缩部分做一些改进即可。在压缩的时候，第二个字节的8位分别用来存储逻辑单元中的8个块是否在实际的物理块上存在，一个逻辑块的物理地址可以根据起始地址+该编号前面有多少个1存在算出来(1次加法加上3,4次位运算)。因此总共需要64个字节的内存

这样的实现，查询是会比较快，但是插入绝对是一个悲剧