论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2012-09-20 10:52 |只看该作者 |倒序浏览

请问一下，如果要存放范围为0~FFFFFF中的大概100个数字（无重复）到一个文件中，数据插入删除操作远小于查找操作（内存只有128字节）文件大小限制在1MB之内，那么用方式来存储最好呢？

我现在想到的办法是用散列，请问还有没有什么更好的办法？如果用字典树的话，即使用一个位来标示一个数字是否存在，占用的空间也依然过大了。

文库|博客

linux_c_py_php

巨富豪门

论坛徽章:: 4

2楼 [报告]

发表于 2012-09-20 11:12 |只看该作者

本帖最后由 linux_c_py_php 于 2012-09-20 12:30 编辑

数据量: 100 * 4 = 400B.
内存量: 128B
磁盘量: 1MB

个人方案:
以数值为文件名, 在目录下建立对应文件即可.

例如: 有[1, 2, 3, 4]四个数字, 那么目录下存储1, 2, 3, 4为名字的四个文件即可.

查询操作: O(1), stat/access看是否存在对应名称的文件即可.
插入操作: O(1), creat建立对应文件即可.
删除操作: O(1), unlink删除对应文件即可.

----------------------------------------------------

至于楼主的需求, 说数据要在1M文件中, 也有方案(可以做成默认递增的, 也可以任意插入):

1, 文件按sizeof(int)分block, 预先开好100~200个block的大小(lseek + write(1)), 第一个block用来记录数据个数.
2, 查找:O(n), 因为没法一下装入内存中二分, 所以遍历即可 , 每次fread 4B.
3, 插入:O(n), lseek偏移到想插入的block, 循环逐个block向后挪动4字节, 将新数值写到当前block.
4, 删除:O(n), 一样, 不说了.

总之, 内存里始终只需要4B空间.

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

onlyxuyang

白手起家

论坛徽章:: 0

3楼 [报告]

发表于 2012-09-20 21:37 |只看该作者

-_- 我只想吐槽一下
“以数值为文件名, 在目录下建立对应文件即可.”
这个方案... linux_c_py_php同学研究过文件系统么...

查询操作: O(1), 插入操作: O(1), creat建立对应文件即可,删除操作: O(1)

这O(1)是从哪里得来的信心啊.... 就算不说实际文件系统的处理流程完全不止O(1)，

这些function是要调用system call陷入到kernel的啊... 这代价已经很高了啊！

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

linux_c_py_php

巨富豪门

论坛徽章:: 4

4楼 [报告]

发表于 2012-09-20 21:57 |只看该作者

本帖最后由 linux_c_py_php 于 2012-09-20 21:57 编辑

楼上的, 你这种回复本身就是在装逼, 好像你很懂内核的样子, 我是做应用层的, 一级目录不超过1024个子文件我都认为是没有压力的.

如果stat都不能调用, 那请问你还可以干什么? write也别调用了? OK? 装逼请在合适的地方装, 谢谢你.

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

linux_c_py_php

巨富豪门

论坛徽章:: 4

5楼 [报告]

发表于 2012-09-20 21:58 |只看该作者

还吐槽一下? 你有能力就给个方案, 觉得自己懂内核就给楼主一个高性能的解决方案, 还吐槽一下, 你够分量?

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

linux_c_py_php

巨富豪门

论坛徽章:: 4

6楼 [报告]

发表于 2012-09-20 21:59 |只看该作者

我以为CSDN这种装逼的多就算了, 来CU也遇到N多这种装逼的, 不装就没地位了?

onlyxuyang 发表于 2012-09-20 21:37
-_- 我只想吐槽一下
“以数值为文件名, 在目录下建立对应文件即可.”
这个方案... linux_c_py_php同学研究 ...

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

onlyxuyang

白手起家

论坛徽章:: 0

7楼 [报告]

发表于 2012-09-20 22:36 |只看该作者

似乎一不小心踩到小孩子的尾巴的感觉

这个题目刚好卡了文件大小的限制，要是文件大小限制在2M就刚好1024*8*2 =0xFFFFFF，直接用位图是最快的。

限制1M的话暂时没想到比较好的办法，另外，对文件进行频繁的小块读写的话，请使用mmap,不要用lseek,write,read之类的.

实战分享：从技术角度谈机器学习入门| 【大话IT】RadonDB低门槛向MySQL集群下战书 | ChinaUnix打赏功能已上线！ | 新一代分布式关系型数据库RadonDB知多少？

linux_c_py_php

巨富豪门

论坛徽章:: 4

8楼 [报告]

发表于 2012-09-20 22:37 |只看该作者

本帖最后由 linux_c_py_php 于 2012-09-20 22:39 编辑

位图是我最初考虑的, 但为了10个整数 , 开0xFFFFFF个bit去浪费空间, 值得? 磁盘能装下?

你这不就是在放屁? 你说的没一条可行的, 不是放屁是什么？装逼.?

好不容易学会个位图, 好不容易知道个mmap, 出来炫耀一下API ? 你暴露的太幼稚了.