考虑内存和CPU的问题,用程序写一个从1亿个数字中取出前100个最大的程序,大家可以试试看,然后把自己的程序运行时间打印出来,说说自己的思路,不限语言。

2011-01-04 22:41:53

7 Answers

思路是:每次在所有数据集中选出最大的数字,并将该数字设置一个标志位,已免下次遍历最大值的时候重复选中该数字。为避免查找算法的额外开销,设置标志位的方法比较重要,如果这些数据全部是整数,我们可以用位运算处理;如果是浮点数,我们可以先将这些数据放大,在一定精度范围内将其转化为整数,再使用位运算处理(当然,应该有其他的处理方式)

C代码:

#include "stdlib.h" #include "stdio.h" #include "time.h" #define MAX_BIT 0x8000 /*屏蔽的最大比特位,也可以是0x40, 0x800等*/ #define MARK(x) ((x) |= MAX_BIT) /*即(x) | = 0x8000*/ #define IS_MARK(x) ((x) & MAX_BIT) /*即(x) & 0x8000*/ #define UNMARK(x) ((x) & (MAX_BIT-1)) /*即(x) | 0x7FFF*/ #define MAX_DATA (MAX_BIT - 1) /*即0x7FFF*/ #define TOP_NUM 100 /*找出前N个最大值*/ #define TOTAL_NUM 100000000 /*总个数*/ void main( void ) { int i, j; int data[TOTAL_NUM]; /*存储所有数据*/ int result[TOP_NUM]; /*存储查找结果*/ int max, temp; int index; /*确保总个数不小于TOP个数*/ if (TOP_NUM > TOTAL_NUM){ printf("Please make sure TOP_NUM <= TOTAL_NUM"); return; } /*以时间为种子,生成随机数*/ srand( (unsigned)time( NULL ) ); /* 生成 TOTAL_NUM个小于MAX_DATA的随机数*/ for (i=0; i<TOTAL_NUM; i++){ do { temp = rand(); }while(temp > MAX_DATA); data[i] =temp; printf("%6d/n", temp); } /*查找最大的TOP_NUM个数字*/ for (i=0; i<TOP_NUM; i++){ max = 0; index = -1; for (j=0; j<TOTAL_NUM; j++){ if (!IS_MARK(data[j])){ /*避免重复选取*/ temp = UNMARK(data[j]); if (temp > max){ max = temp; index = j; } }//end if }//end for if (index >= 0){ /*找到最大的,标记*/ result[i] = data[index]; MARK(data[index]); } else{ break; } }//end for printf("Top %d Number:/n", TOP_NUM); for (i=0; i<TOP_NUM; i++){ printf("%6d/n", result[i]); } } // end main

2011-01-05 01:11:18

简单的说,用一个候选集保存前100个数,并集合内排好序。然后遍历剩下的数,例如取得数A,拿去跟集合内的最小值(不妨设为M)比较,如果A>M,则去掉M,插入A,更新集合内的顺序。

其中关键在于候选集内的数据结构。如果是链表,则每次插入需要o(n)时间。如果用小顶堆,则只需要o(lgn)。

其实,这是烂大街的面试题了。但是@李小蔚希望大家给出程序和运行时间,那么希望能提供数据集。这样大家在一样的数据下运行得到的时间才有比较的意义。

2011-01-05 02:25:08

bit[一亿] 开始全为0 读取数据i bit[i] = 1 读完数据后, n = 一亿 bit[--n] == 1 则输出n, 并记录输出的数据个数 这样就可以完成一亿个数字中取前100个最大值 了

2011-01-05 03:31:31

我觉可以用除10的方法来过滤小的数据,首先遍历一次,区分出正负数, 如果正数个数大于100,就丢弃所有负数,然后对正数部分进行筛选,反之,取正数后再筛选需要的负数个数,正负数选取规则如下:
对所有数进行除10操作, 如果大于1的数超过100,丢弃小的数,依次类推,最后不够在小的数中补充,补充规可按数值大小取(9-0)

2011-01-05 05:41:02

对于多核cpu 取得前100个数 用最优排序算法进行排序 不过其中改变一下 将类似合并排序的最优排序分成的两部分用两个线程进行排序 然后 前100个是有序的了 只要继续从101-1亿往这一百个中插 与这100个中最小的进行比较 如果小于 直接抛弃 如果大于 就用二分法插入进去 抛弃最小的数 如此反复 利用cpu多核设计 如果2个核 创建2个线程 其中均保存前100排序副本
然后 将(101-1亿)的数据分成两份 分别在两个线程中插入 这样最后得到2个排好序的100个元素 然后利用插入算法中 从大的一端开始比较 当比较100次后 即可得到最大的100个数

这道题目本省求最大数 我的做法 只要排序前100个 然后后面的遍历一遍 然后用二分法插入前100个中
考虑到多线程 可以设计n个线程 将(101-1亿)/n这样 效率会高 考虑到负载平衡问题 可以利用c++0x种引入的OpenMP 总之 这么我写了这么多 一个评论都没有么 那我可以去死了

2011-01-05 07:09:34

我的思路是:通过一个容量为100的小顶堆来实现。先把前100个数据放入小顶堆,然后每读入一个数据,就与堆顶进行比较。如果比堆顶大,则去除堆顶元素,并把该数据加入小顶堆,并调整;否则直接舍弃,读入下一个数据。这样空间复杂度和时间复杂度都不会太大。
这是我来“德问”回答的第一个问题,如果有什么遗漏的地方,还望大家多多包涵。大家共同努力,一起学习和提高!

2011-01-05 08:27:30
您不能回答该问题或者回答已经关闭!

相关文章推荐

  • C#开发中的反射机制

    反射的定义:审查元数据并收集关于它的类型信息的能力。元数据(编译以后的最基本数据单元)就是一大堆的表,当编译程序集或者模块时,编译器会创建一个类定义表,一个字段定义表,和一个方法定义表等

  • C#实例解析适配器设计模式

    将一个类的接口变成客户端所期待的另一种接口,从而使原本因接口不匹配而无法在一起工作的两个类能够一起工作

  • C#中using指令的几种用法

    using + 命名空间名字,这样可以在程序中直接用命令空间中的类型,而不必指定类型的详细命名空间,类似于Java的import,这个功能也是最常用的,几乎每个cs的程序都会用到

  • C#协变和逆变

    “协变”是指能够使用与原始指定的派生类型相比,派生程度更大的类型,“逆变”则是指能够使用派生程度更小的类型

  • C#运行时相互关系

    C#运行时相互关系,包括运行时类型、对象、线程栈和托管堆之间的相互关系,静态方法、实例方法和虚方法的区别等等

  • 使用托管C++粘合C#和C++代码(二)

    本文实现一下C++代码调用C#代码的过程。我构造一个简单并且直观的例子:通过C++ UI 触发C# UI.

  • C#开发高性能Log Help类设计开发

    项目中要在操作数据库的异常处理中加入写Log日志,对于商业上有要求,写log时对其它操作尽可能影响小,不能因为加入log导致耗时太多

  • C#中的索引器的简单理解和用法

    C#中的类成员可以是任意类型,包括数组和集合。当一个类包含了数组和集合成员时,索引器将大大简化对数组或集合成员的存取操作

  • Async和Await使异步编程更简单

    C#5.0中async和await两个关键字,这两个关键字简化了异步编程,之所以简化了,还是因为编译器给我们做了更多的工作

  • 使用托管C++粘合C#和C++代码(一)

    C#在xml读写,数据库操纵,界面构造等很多方面性能卓越;C++的效率高,是底层开发的必备武器

  • C#基础概念之延迟加载

    延迟加载(lazy load)是Hibernate3关联关系对象默认的加载方式,延迟加载机制是为了避免一些无谓的性能开销而提出来的,所谓延迟加载就是当在真正需要数据的时候,才真正执行数据加载操作

  • 深入C# 序列化(Serialize)、反序列化(Deserialize)

    C#中的序列化和反序列化,序列化是.NET运行时环境用来支持用户定义类型的流化的机制