要守恒也是：时、空、算法的守恒 <- 中国开发网

账号

中国开发网: 论坛: 程序员情感CBD: 贴子 255901

haitao · 2005-12-09 11:50:38 · 阅读: 958

要守恒也是：时、空、算法的守恒

花费同样的空间，不同的算法的时间开销是可能大不相同的
所以只有2个参数的守恒公式是不存在的了

相关信息:

[技术贴]实现包含在一个文件中的文件系统 (107字) (holly [1660] 2005-12-08 11:02)
- vmware的虚拟硬盘就是这样的啊。。。 (24字) (haitao [1224] 2005-12-08 11:05)
  - 海涛同学又跑题了 (74字) (holly [984] 2005-12-08 11:07)
    - 动态增长，如果要求节省空间，就要做一张映射表了，类似虚拟缓存的映射关系。 (空) (GoodHope [1108] 2005-12-08 11:09)
      - 接下来就是文件碎片，整理，空间回收，etc (空) (Miracle [949] 2005-12-08 23:51)
    - 先把什么样（需求）的明确了，才可以放心地讨论怎么做到这样。。。 (21字) (haitao [1049] 2005-12-08 11:11)
      - 是啊, 问题在于你还没仔细看前面的描述就开始想想了 (54字) (holly [931] 2005-12-08 11:15)
        
        一语中的。 (空) (ycm0263 [854] 2005-12-08 11:18)
        
        马屁贴，鉴定完毕。 (空) (GoodHope [924] 2005-12-08 11:20)
        ╭∩╮（︶︿︶）╭∩╮ (空) (ycm0263 [811] 2005-12-08 11:24)
        
        嗯，这个是个问题。。。我照自己的思路，也是尽量找最简单、常见的东西 (104字) (haitao [967] 2005-12-08 11:21)
        
        说了等于没说阿 (空) (Miracle [905] 2005-12-08 23:51)
        
        就是先找出大家共同认可的基础啊 (55字) (haitao [970] 2005-12-09 08:46)
        
        最主要的问题就在于 (40字) (holly [1062] 2005-12-09 10:11)
        
        说实话，到现在我也不敢确定是否理解你的需求 (196字) (haitao [991] 2005-12-09 10:32)
        
        你的理解果然有问题 (501字) (holly [1046] 2005-12-09 10:58)
        
        我的意思就是先找现成的借鉴，它们应该都遇到过大多数的问题 (26字) (haitao [1053] 2005-12-09 11:15)
        
        说你只管朝自己的思路理解吧 (23字) (holly [802] 2005-12-09 11:19)
        
        早说嘛 (76字) (haitao [1046] 2005-12-09 11:28)
        
        我以为 (38字) (holly [792] 2005-12-09 11:32)
- 把整个文件映射成一个分区的逻辑结构 (空) (GoodHope [1061] 2005-12-08 11:07)
  - 不需要做到跟操作系统集成的. (44字) (holly [899] 2005-12-08 11:10)
    - 不用和操作系统集成？动态增长不难。要解决删除文件留下的空洞到比较罗嗦。 (空) (GoodHope [1013] 2005-12-08 11:11)
    - 没有大小限制？其实应该也是有限制的吧 (35字) (haitao [995] 2005-12-08 11:16)
      - 呵呵, 这里根本就没有分区这个概念存在 (35字) (holly [999] 2005-12-08 11:19)
        
        不一定是分区，但是文件总要分块吧。。。除非真的不考虑效率 (52字) (haitao [1059] 2005-12-08 11:24)
        
        你这里的文件指宿主文件? 内部的逻辑文件? (空) (holly [903] 2005-12-08 11:25)
        
        当然是内部的逻辑文件了 (35字) (haitao [988] 2005-12-08 11:28)
    - 当然要集成也不过就是写一个 driver. (176字) (pcplayer [1006] 2005-12-08 11:23)
      - 新闻联播说的技术也信的话基本上就是圈外人士了 (空) (holly [992] 2005-12-08 11:26)
        
        所以你搞一个 Driver，也可以上新闻联播了啊！ (19字) (pcplayer [982] 2005-12-08 11:28)
        
        别, 偶还不想被大多数人民群众 bs (空) (holly [960] 2005-12-08 11:36)
        
        哪怕是这样，你也还离芙蓉JJ十万八千里呢，你就放心被bs吧，不会出人命的 (空) (Miracle [929] 2005-12-09 00:11)
- 你不是玩过了吗？ (空) (品雪 [916] 2005-12-08 11:07)
- 如果不考虑性能的话，链表，大量的链表 (76字) (GoodHope [1057] 2005-12-08 11:19)
  - 不知道说明白了没有？ (32字) (GoodHope [965] 2005-12-08 11:21)
    - 性能当然要考虑的. 你当然不能从第一逻辑块到最后一逻辑块来线性搜索某个文件 (空) (holly [924] 2005-12-08 11:24)
      - 偶只管实现，性能可以用Cache和Defrage来提升。 (135字) (GoodHope [1089] 2005-12-08 11:30)
  - 文件数据动态增长好办，直接往后面追加数据就行了。但文件名/大小/数据位置等信息，得放到某个能找得到的地方，才能找到文件的实际数据 (空) (pcplayer [1002] 2005-12-08 11:31)
- 此人在发明轮子 (4字) (黄黑黄 [985] 2005-12-08 11:22)
  - 而且是方轮子 (空) (holly [867] 2005-12-08 11:24)
    - 为什么不是三角的呢？多稳定啊 (空) (GoodHope [899] 2005-12-08 11:31)
- 都是大牛。俺来个偷懒的BT方法 (11字) (pcplayer [1065] 2005-12-08 11:26)
  - 请看俺昨天写的 blog (空) (holly [934] 2005-12-08 11:27)
    - url？ (844字) (haitao [942] 2005-12-08 11:31)
      - 不是这个 (12字) (holly [928] 2005-12-08 11:32)
        
        我靠，你每次不是要通过Google上自己的Blog吧 (空) (GoodHope [1054] 2005-12-08 11:33)
        
        家里机器里在浏览器的历史记录里呢 (空) (holly [877] 2005-12-08 11:34)
    - 你的Blog (7字) (GoodHope [939] 2005-12-08 11:31)
      - 一半一半吧 (空) (holly [875] 2005-12-08 11:32)
        
        那也得给出URL来啊 (空) (GoodHope [914] 2005-12-08 11:32)
        
        俺真的记不住啊 (8字) (holly [836] 2005-12-08 11:33)
        
        唉，我最近连7位的电话号码都记不住了。 (空) (GoodHope [896] 2005-12-08 11:35)
        BS，大牛的Blog的URL都记不住：http://www.freecoder.org/mt/blogs/lee/ (空) (sealw [1034] 2005-12-08 11:35)
        
        记性真好! (6字) (holly [888] 2005-12-08 11:37)
        
        严重怀疑使用了书签 (空) (GoodHope [879] 2005-12-08 11:37)
        
        . (空) (GoodHope [982] 2005-12-08 11:37)
    - 建议修改： (121字) (sealw [996] 2005-12-08 11:37)
      - CRUD又是什么？ (空) (GoodHope [1906] 2005-12-08 11:39)
        
        Create, Replace, Update, Delete. 好象是这样 (空) (holly [958] 2005-12-08 11:40)
        
        ……………………………………………………………………………………………………………………………………………………………… (空) (GoodHope [947] 2005-12-08 11:41)
        R好像是Read (空) (sealw [928] 2005-12-08 11:41)
        
        。。 (空) (nostalgic [854] 2005-12-08 11:43)
        
        嗯, 应该是 Read (空) (holly [937] 2005-12-08 11:43)
        
        这个是偶的强项 (空) (nostalgic [825] 2005-12-08 11:42)
        
        如果仅仅用CRUD还不行 (15字) (haitao [963] 2005-12-08 11:46)
        R = Retrieve (空) (Miracle [805] 2005-12-08 23:50)
        
        这个是正解 (空) (sealw [894] 2005-12-09 10:28)
        
        为什么 R 不是 Run？ (空) (Fish [885] 2005-12-09 00:13)
        
        NB! (空) (黄黑黄 [852] 2005-12-08 12:07)
      - 嗯, 可能我还是高估了 (空) (holly [866] 2005-12-08 11:39)
      - ... (7字) (nostalgic [892] 2005-12-08 11:44)
      - 批判，在那个口气里明显带有一种高某些程序员一等的优越感 (空) (Miracle [882] 2005-12-08 23:55)
        
        批判，在老 M 的口气里明显带有一种以为能批判某些程序员的优越感 (空) (holly [871] 2005-12-09 10:12)
    - 又被大牛BS了。 (空) (pcplayer [762] 2005-12-08 11:46)
      - 被大牛BS的又不是你一个人 (空) (nostalgic [1020] 2005-12-08 11:50)
- 完全模拟一个现成的文件系统，只要把文件分配表中的硬块逻辑位置改成对应文件里的开始位置即可。如果要不限长度，就要把目录结构和文件分配表结构改为链表或其他可不限长的数据机构 (空) (李战 [1199] 2005-12-08 11:34)
  - 文件分配表本身的大小是否是固定的？ (13字) (pcplayer [1023] 2005-12-08 11:35)
    - 要求当然是一切都不能固定 (空) (holly [898] 2005-12-08 11:37)
      - ACID是什么？ (9字) (GoodHope [1373] 2005-12-08 11:38)
        
        。 (空) (nostalgic [867] 2005-12-08 11:40)
    - 有文件分配表，就走入歧途了。 (空) (GoodHope [970] 2005-12-08 11:37)
      - 用链表来模拟文件分配表，不就可以不限大小了。 (空) (pcplayer [918] 2005-12-08 11:41)
        
        这样还要文件分配表干嘛？ (空) (GoodHope [932] 2005-12-08 11:43)
        好处是可以利用别人写好的文件系统啊。又可以偷懒了。 (空) (pcplayer [949] 2005-12-08 11:47)
- linux下有个cramfsck.和mkcramfs 正好满足你的要求. (空) (bjwf [2127] 2005-12-08 11:44)
  - 不对, 那是需要大小的 (空) (holly [815] 2005-12-08 11:45)
    - 改一下应该能满足 (空) (bjwf [832] 2005-12-08 11:46)
- 曾经参考Google File System做一个分布式文件系统来者，有一点很浅的探究，也需要在本地机做一个虚拟的文件系统，可惜当时所有的这一切都是我一个人在做，没多久俺就闪人了，…… (186字) (周星驰 [2052] 2005-12-08 12:09)
  - 对它这个分布式磁盘系统有兴趣。可惜没时间去深入研究。 (空) (pcplayer [871] 2005-12-08 15:12)
- N年以前，Norton里面的 Diskreet 就是干这个的 (空) (Fish [896] 2005-12-08 13:04)
  - 那个是有大小限制的。 (空) (ycm0263 [764] 2005-12-08 13:10)
    - 是有限制，并且狠危险。文件一被删除，就啥都木有了 (空) (Fish [931] 2005-12-08 13:34)
      - 它本来就是只防被盗取 (7字) (haitao [861] 2005-12-08 13:40)
- 偶的看法，比较肤浅。。。 (128字) (mhappy [998] 2005-12-08 13:22)
  - 因为holly同学想走上一条与大家不同的路 (空) (李战 [838] 2005-12-08 14:34)
  - 没错，就是要研究一下各种实现啊，讨论一下，有何不可呢，光看书不行，现在不是在提问题么 (空) (Miracle [934] 2005-12-09 00:00)
- 还有个BT的办法 (17字) (pcplayer [971] 2005-12-08 13:45)
  - 够变态 (空) (李战 [837] 2005-12-08 14:35)
    - 技术上还是可以做得出来的嘛。 (空) (pcplayer [973] 2005-12-08 15:06)
  - 理论上可以这么做，但是你想过没有，当文件尺寸扩充的时候，你应该怎么分配空间，虽然是xml (60字) (Miracle [996] 2005-12-08 23:49)
- 有没有程序阿？我也需要一个类似的系统来管理ramdisk (空) (MaoMao [981] 2005-12-08 14:58)
  - 我也想要一个，自己写灭有时间，而且也没什么好的方案能象大牛说的不限大小 (空) (pigprince [950] 2005-12-08 15:10)
  - win2k/linux都有现成的吧 (57字) (haitao [903] 2005-12-08 15:12)
- 忍不住了，告诉你吧，自己做用IFS DDK来写，现成的代码可以看TrueCrypt (158字) (只谈技术 [3044] 2005-12-08 18:38)
  - 明显文不对提 (空) (holly [891] 2005-12-08 20:13)
  - 修改过，好像又不合了。。。。 (空) (周星驰 [944] 2005-12-08 20:17)
  - 有趣有趣，有马甲要给大牛上课了，搬凳子先 (空) (品雪 [868] 2005-12-09 10:55)
- 要求不是很高的话，Windows下倒是有现成的structured storage (空) (Miracle [974] 2005-12-08 19:16)
  - 那是 COM 的. 偶希望跨平台的 (33字) (holly [990] 2005-12-08 20:14)
    - 我觉得应该让大家想一些BT的办法。太正统的没意思。 (空) (pcplayer [927] 2005-12-08 21:26)
      - 嗯, 有理. 我也希望看到谁能 bt 得更出色 (空) (holly [854] 2005-12-08 23:53)
        
        其实我看你的需求，和做一个以单一文件为数据库库文件的大型数据库差不多。 (空) (pcplayer [930] 2005-12-08 23:57)
        
        因此，可以拿一个开源的数据库对库文件的管理方式来模仿。 (空) (pcplayer [886] 2005-12-08 23:58)
        
        归根结底，BT的方向是 (133字) (Miracle [1070] 2005-12-09 00:04)
    - 还是数据库吧，不一定是RDBMS (空) (Fish [897] 2005-12-09 00:03)
    - 嘿嘿，明白，你就是要一个general idea，看看大家的想法，对问题的挖掘深度，地球人都知道 (16字) (Miracle [1271] 2005-12-09 00:05)
      - 磁盘不比内存。磁盘上保存的数据不是说干掉就干掉的。干掉也就四做个标记，留个空洞。否则没效率可言。 (46字) (pcplayer [1005] 2005-12-09 00:11)
        
        空洞可以重复使用的 (空) (holly [854] 2005-12-09 00:14)
        要么刚好要写入空洞那么大个数据，要么还要留下小空洞。好象FAT处理这个问题也没处理好。 (空) (pcplayer [900] 2005-12-09 00:17)
        
        FAT 处理得可以了。 (35字) (ycm0263 [929] 2005-12-09 00:19)
        
        可以智能一点：不只是找空洞来写数据，在写数据的同时也顺便搬一点小数据，做一点小的碎片整理。 (空) (pcplayer [877] 2005-12-09 00:27)
        
        pcplayer 同学有很多很不错的想法 (空) (holly [834] 2005-12-09 00:36)
      - BT点的做法是，最好可以不单是把数据追加到文件的结尾，还可以加到文件的前头。 (54字) (pcplayer [978] 2005-12-09 00:15)
- 有一本书，叫《linux文件系统》 (空) (leejd [968] 2005-12-09 09:39)
  - 这本书写得恶烂 (空) (holly [844] 2005-12-09 10:08)
- 其实就是如何平衡空间和时间的关系。总之不是空间换时间，就是时间换空间。 (39字) (pcplayer [1092] 2005-12-09 10:39)
  - pcplayer 同学说的都是公理啊 (17字) (holly [1266] 2005-12-09 11:09)
  - 其实就是如何平衡命和钱的关系。总之不是拿命换钱，就是拿钱换命。 (39字) (pcplayer [3] 今天 10:39) (空) (sealw [914] 2005-12-09 11:12)
    - 嘿嘿, 拿命换钱可以, 拿钱换命太难了 (空) (holly [792] 2005-12-09 11:22)
      - 不可逆啊 (16字) (haitao [830] 2005-12-09 11:33)
    - 钱和命不是守恒的，命可以换钱，但死了之后就钱就换不回来了 (空) (李战 [867] 2005-12-09 11:24)
  - 我把这个称为编程中的“时空守恒定律” (空) (李战 [945] 2005-12-09 11:21)
    - 这2个也不是守恒的 (62字) (haitao [1278] 2005-12-09 11:35)
      - 这只能说明时间和空间的转换不成比例而已，你可以去把转换公式研究出来了，就像爱因斯坦的E=MC2，但质能还是守恒的。 (空) (李战 [1186] 2005-12-09 11:40)
        
        要守恒也是：时、空、算法的守恒 (47字) (haitao [957] 2005-12-09 11:50)
- 种大树 (161字) (pcplayer [922] 2005-12-10 00:36)
  - 要是分文件何苦来呢，直接利用操作系统的文件系统好了。 (109字) (GoodHope [1051] 2005-12-10 00:57)
  - 说对了, 就是玩数据结构那些东西 (30字) (holly [980] 2005-12-10 01:01)
    - 这个数据结构的条件也太古怪了 (空) (GoodHope [899] 2005-12-10 01:05)
      - 其实在实际中很有用的 (空) (holly [893] 2005-12-10 01:07)
        
        除了锻炼人的逻辑能力，暂时看不到有什么需求这么变态。 (空) (GoodHope [960] 2005-12-10 01:14)
      - 其实所有的考虑都是基于磁盘的数据是串行传输这个事实。 (71字) (pcplayer [918] 2005-12-10 01:11)
        
        你还是串行的啊 (26字) (holly [847] 2005-12-10 01:15)
        
        一个页面就N百G了，再读N个页面出来。拿什么装啊。 (空) (GoodHope [972] 2005-12-10 01:22)
        
        少了随机和分块啊 (26字) (GoodHope [775] 2005-12-10 01:15)
        
        在一片磁盘上，数据的读和写是串行的。当然可以多个盘片一起来。但这个也并不了多少。 (65字) (pcplayer [1027] 2005-12-10 01:20)
        
        你对串行传输理解有偏差 (45字) (GoodHope [965] 2005-12-10 01:24)
        
        我说的是读写，不是传输。 (空) (pcplayer [808] 2005-12-10 01:27)
        
        文件读写也不是串行传输 (11字) (GoodHope [872] 2005-12-10 01:32)
  - 种大树 (空) (zengr [861] 2005-12-10 16:42)
- 说来说去，什么碎片空洞，都是在那个文件内部，逻辑上的。物理上，数据是否在硬盘的一个连续的块上，没法保证。 (32字) (pcplayer [1100] 2005-12-10 11:07)
  - 这个思路既没有必要 (20字) (老玉米 [1019] 2005-12-10 11:16)
    - 如果数据吞吐量很大，这是很有必要的。 (空) (pcplayer [868] 2005-12-10 11:30)
    - 必要是有的。 (空) (空山新雨 [731] 2005-12-10 15:33)
  - 像很多数据库一样，直接操作裸盘吧 (空) (leejd [931] 2005-12-10 11:25)
    - 直接操作裸盘就没法利用文件系统的 cache 了 (4字) (holly [906] 2005-12-10 16:48)
      - 能自己直接操作裸盘的，就有能力自己实现一套cache机制的了 (48字) (haitao [1030] 2005-12-10 17:32)
        
        那些自己操作 raw disk 自己控制 cache 的 RDBMS system 这么做的原因是 (30字) (holly [868] 2005-12-10 17:39)
      - 用缓存也是有坏处的 (27字) (leejd [947] 2005-12-10 17:36)
        
        一般的硬盘本身就是有内部缓存的 (39字) (haitao [1008] 2005-12-10 17:39)
        
        硬盘控制器还有缓存呢. (7字) (holly [948] 2005-12-10 17:40)

欢迎光临本社区，您还没有登录，不能发贴子。请在这里登录

页面内容处理时间: 0.026 - 747680