首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 腾讯笔试题
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wpp_zyt
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    • 揭贴率：
    发表于：2007-10-14 13:02:43 楼主
    一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数
    20  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • foxqwx
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-10-14 14:10:391楼 得分:0
    4个字节表示的整数，总共只有2^32约等于4G个可能。
    为了简单起见，可以假设都是无符号整数。
    分配500MB内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为１，处理完40G个数后，对500M的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。
    算法流程：
    １）分配５００ＭＢ内存buf，初始化为０
    ２）unsigned int x=0x1;
      for each int j in file
      buf=buf|x < <j;
      end
    (3) for(unsigned int i=0; i <= 0xffffffff; i++)
          if (!(buf & x < <i))
          {
              output(i);
              break;
          }
    以上只是针对无符号的，有符号的整数可以依此类推。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • wpp_zyt
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-10-14 14:50:362楼 得分:0
    楼上的思想我都领会了，但是这个含有40亿个整数的文件太大了，读入内存会溢出啊！怎么解决，是分块吗？
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • xdspower
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-10-14 20:05:233楼 得分:0
    文件可以分段读啊，这个是O（2n）算法，应该是很快的了，而且空间也允许的。
    不过还可以构造更快的方法的，更快的方法主要是针对定位输出的整数优化算法。
    思路大概是这样的，把值空间等分成若干个值段，比如值为无符号数，则
    00000000H-00000FFFH
    00001000H-00001FFFH
    ......
    0000F000H-0000FFFFH
    .....
    FFFFF000H-FFFFFFFFH
    这样可以订立一个规则，在一个值段范围内的数第一次出现时，对应值段指示值Xn=Xn+1，如果该值段的所有整数都出现过，则Xn=1000H，这样后面输出定位时就可以直接跳过这个值段了，因为题目仅仅要求输出一个，这样可以大大减少后面对标志数值的遍历步骤。
    理论上值段的划分有一定的算法可以快速的实现，比如利用位运算直接定位值段对应值进行计算。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • foxqwx
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-10-14 20:49:234楼 得分:0
    楼上的回答好
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • xuegao007
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-10-15 09:19:375楼 得分:0
    文件可以分段读啊，这个是O（2n）算法，应该是很快的了，而且空间也允许的。
    不过还可以构造更快的方法的，更快的方法主要是针对定位输出的整数优化算法。
    思路大概是这样的，把值空间等分成若干个值段，比如值为无符号数，则
    00000000H-00000FFFH
    00001000H-00001FFFH
    ......
    0000F000H-0000FFFFH
    .....
    FFFFF000H-FFFFFFFFH
    这样可以订立一个规则，在一个值段范围内的数第一次出现时，对应值段指示值Xn=Xn+1，如果该值段的所有整数都出现过，则Xn=1000H，这样后面输出定位时就可以直接跳过这个值段了，因为题目仅仅要求输出一个，这样可以大大减少后面对标志数值的遍历步骤。
    理论上值段的划分有一定的算法可以快速的实现，比如利用位运算直接定位值段对应值进行计算。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tsasdf
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-10-15 15:10:096楼 得分:0
    1楼的做法很好。至于读取文件可以只申请一个整数单元的空间就行了，一个一个的读，又不是一次把所有读进内存。
    至于读取文件的函数怎么关联到外存文件，操作系统会帮我们解决的。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • longtrue
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2007-10-25 15:11:127楼 得分:0
    1楼结合6楼的算法应该是可行的，但512M的内存如何以位为单元来寻址？我的想法是：
    假设分配的内存从begin开始，先以8-bit为单位寻址，再以1-bit为单位，例如整数X就由
    (begin + X/8) |= (1 < < x%8) 来标志。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • liug0330
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-14 16:28:468楼 得分:0
    首先，我想问下楼上：
    1、4字节所能表示的无符号是0~2^32-1  （0~4294967295）  500M可表示为0~500 * 2^20 -1（0~4194303999）
        我读数时如果读入一个中4194303999~4294967295的数你怎么办？请不要说分512M（那就正好了）
    2、我的内存一共就1G，你一下就要500M（可能是512M）请问你的申请方法是什么，我的系统等不要内存吗？
      1G的内存你真正能用到的有多少呢？还有你的500M（或512M）还是连续的吧不连续吧
      你是怎么分出500M连续内存的啊，我也是1G的内存，怎么我申请100M连续内存都不行啊


    所以你还是老实的去做外部排序吧
    1、文件外部升序排序（略）
    2、读入第一个数，如不是0则0（含）到这个数（不含）之间数没出现过，记录该数（lNumberA）
    3、读第二数（lNumberB）,如lNumberB-lNumberA不是1则两数（不含）间的数没出现
    4、重复3，到最后一个数
    5、如最后的数不是4294967295，则最后的数+1到4294967295全没有出现过
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • liug0330
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-14 16:50:249楼 得分:0
    注：4步之前要改变lNumberA，lNumberB的值，让他们总是相邻的数（把前次的lNumberB给lNumberA，lNumberB去读下个数）
    外部升序排序太多了，去找下很方便的
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • liug0330
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-14 16:52:4410楼 得分:0
    lNumberA和lNumberB要相等则全向后走
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • liug0330
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-14 16:55:3411楼 得分:0
    读入时要一段一段的不要一个一个的读
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Vitin
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-14 16:58:5112楼 得分:0
    8楼的做法不可取。对这么大的文件做排序是很低效的方法。
    内存可以通过静态分配完成，不需要在堆里动态分配，后者低效且可能无法成功。
    如果内存不够，可以将这512M位图作成硬盘文件，这样也比原始文件排序快很多。在追求效率的项目中可以用有限的内存做缓冲，自己编写缓冲方案（会比操作系统自带的更有针对性、更高效）。此外，可以对位图分块并设置标志位（形成一个小的位图），如果块中全为1了就不再换入换出，这样可以提高后期的效率，如此等等。
    总之位图的方案肯定是好的，对于特定的运行环境可以采用一些技术来适应。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • pdfccc1
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-14 17:34:3913楼 得分:0
    没说不能用外部存储器，鉴定完毕。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • Vitin
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-14 17:40:0214楼 得分:0
    分块形成高层位图，也就是3楼提供的技术，是提高效率的经典技术，值得广泛使用。

    一般而言，算法首先需要一个大致的思路（比如本题中的位图或排序），然后再考虑实现上的细节（比如算法的具体过程，对内存不足的处理，高效的输入输出方法，等等）。前者大体决定了算法的效率，后者则提供有力的支持和补充。不管是总体思路还是实现技术，都值得学习掌握，并可以相互组合，形成针对各种具体问题的解决方案。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • liug0330
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-15 13:19:0015楼 得分:0
    是的位图的方案肯定是好，可是要有我也是这么认为的，可是空间有限就要别行考虑了512M位图作成硬盘文件是一个方法，可是要是选的好的排序不一定比这个慢，还有主要的是512M位图作成硬盘文件也要频繁的读也要时间，也有个选取问题，选好了是快的，我上面说的只是一个方法，不一定是最优的，只是看那人上来就申请500M内存太看不下去了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tailzhou
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2
    发表于：2008-02-15 13:23:2616楼 得分:0
    4个字节的所有整数个数大于40G个，所以肯定有不包含的数；

    假定为无符号整数,数组为num[40G]；

    申请一个2^16大小的数组count[2^16];
    1）扫描一遍num数组，count[num[i] & 0xffff]++;
    2) 扫描一遍count数组，查找一个元素x1=count[i1]，x1满足条件x1 <2^16;
    3) count数组清0，扫描一遍num数组;
      if ((num[i] & 0xffff)==x1)
      {
        count[(num[i]>>16) & 0xffff]++;
      }
    4) 扫描一遍count数组，查找一个元素x2=count[i2]，x满足条件x==0;

    那么数 i2 < <16 & x 既为所求结果；
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • tailzhou
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2
    发表于：2008-02-15 13:41:3817楼 得分:0
    一个文件中有40亿个整数，每个整数为四个字节，内存为1GB
    题目既然这样说，肯定是假设可以申请到1G可用内存的；

    一楼的就是效率很好的方法了。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • RobertBaker
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-16 23:18:1118楼 得分:0
    分配两部分内存，A 设置为0, B 用于分批读取文件数据，
    同时，用多个 Hash 函数，计算数据的多个 Hash 值 Value，并且设置 A[Value] = 1,(以 bit 算)，
    这样，处理文件完毕以后，找到 A[X] = 0，中的 X，反向计算 Hash 函数，可得文件中没有的数据，
    如果，没有找到 A[X] = 0 的 X, 则可由程序自己生成(方法自定)一个数，用以上方法可验证其是否在文件中。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • jmulxg
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-19 17:43:3719楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhongteng
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-21 14:12:1120楼 得分:0
    在32位操作系统中，虚拟内存是4G，在Windows环境中，在堆上实际可以分配的最大内存也是差不多2.8G，所以分配512M内存根本算不上什么
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • 无心人
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-02-22 10:26:0321楼 得分:0
    呵呵

    延续你们的思路，这么做
    4G数字做成个内存映射文件，按bit存储，是512M
    都映射到内存，占用也不会是512M，是很少的

    然后查找，置位

    然后查bit为0的，就这么简单
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • soulnew
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-03-31 21:05:4822楼 得分:0
    A1= 已知的 40亿-1 个数加起来
    A2=(40亿+1)×20亿
    A3 =A1-A2 这个就是少了的数
    然后是超大数的加减问题，这个自己设计合适的数据结构解决。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • aayzaayz
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-08 15:55:0623楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • barenx
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-08 22:39:0224楼 得分:0
    引用 21 楼 无心人 的回复:
    呵呵

    延续你们的思路，这么做
    4G数字做成个内存映射文件，按bit存储，是512M
    都映射到内存，占用也不会是512M，是很少的

    然后查找，置位

    然后查bit为0的，就这么简单


    一个比较好的思路，让操作系统来帮程序做磁盘缓冲，
    但是这个空间要映射到程序的地址空间内
    读数据文件的时候就只剩下500M的可用空间了
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • zhengaw
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-09 08:29:0725楼 得分:0
    4byte的整数如果假设都是无符号数，范围是0-2^32-1（4294967295），可以用2分来做，首先选择（0+4294967295)/2作为partition的参照，每次读入一个数与该书比较分别统计大于（0+4294967295)/2和小于（0+4294967295)/2的数个数，如果在(0,(0+4294967295)/2)的个数小于（0+4294967295)/2则选择（0+（0+4294967295））/2作为参照在这个子区间进行情面的过程，重复上面过程直到找到一个区间内的数不存在为止。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • xdspower
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-09 11:43:0026楼 得分:0
    这个其实是比较好处理的，因为只有4字节，也就是2^32个标志位来代表某个数是否有，这需要4G位，这样才4G/8=512MB
    算法：
    初始化位标记数组 unsign char B[2^28]=0;
    内存完全够用了，这样仅仅需要一次遍历40G数据，把对应位置1，
    传入数字A
    B[A>>4]=B[A>>4]|( 1 < <(A&0x0F) );
    捡出未出现数字，遍历B，捡出B[x]!=0xFF 的，则数字为
    Ax= x < <4 | testbit(B[x]);

    testbit（y）= y中的第n位不为1，0 <=y <8

    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • xdspower
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-09 11:53:3227楼 得分:0
    因为还有那么多内存可用，所以算法可以再优化：
    优化1：
    剩余内存对B是否已经全部置位进行分组标记，比如对B数组可以再分成X个小组，申请一个64M的标志组C
    如果B[A>>4]==0xFF则
    C[A>>8]=C[A>>8] | (1 < <( (A>>4)&0x0F ) );
    这样在后面置位时可以先检测C再判断是否需要再判断，后面捡出时也可以更快。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • lineuser
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-30 09:02:3628楼 得分:0
    mark
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • rodney1983
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-04-30 09:31:2129楼 得分:0
    mark
    修改 删除 举报 引用