一个文件里32亿32位整数，求其中重复的数

Question

这个应该怎么求啊？？

Answer 1

int[] Integer32 = 32亿个int;
int[] integer = new int[Integer32.Length];
int couter;for (uint  i = 0 ; i <= 320000000;i++)
{
  couter = 0;
  foreach (int j in Integer32)
  {
    if (Integer32[i] == j)
    {
      couter++;
      if (couter >1)
      {
        integer[couter-2] = j;
      }
    }
  }
}

Answer 2

http://forum.csdn.net/SList/ST_Arithmetic/

Answer 3

有将近24G的数据。这么大的数据量，如果是无索引地被存储了，说明前面的路走错了。
不过即到这一步只有往下走了。1. 如果重复的数特别多，可以用三楼的办法，分段。重复的数不多的话，不行。
2. 如果某数特别多，直接删除这个数。
3. 想想有没有其它的规律。
4. 如果实在没有什么规律，可以新建一个文件，大小是0xffffffff*4，正好能装下所有的32位整数, 从原文件中取数，存到这个数对应的位置。完成后把所有的零删掉。（保留第一个零）。
5. 借鉴排序算法。
6. 前面的路走错了，后面就不好办了，把前面的程序改一改吧。

Answer 4

用MATLAB就简单了，一个命令而已

Answer 5

我的办法:因为数量极大，在内存中直接处理是不现实的，但是可以利用这道题的特点。
因为只需要知道哪些数是重复的，而不需要知道重复多少次，所以，我们可以利用bit来记录。首先创建一个390625K大小的文件（称为bit文件），也就是32亿个bit（如果内存够大，也可以直接开1亿个int型数组，在内存里操作速度要快得多）。
然后开始读取文件中的数值，读取到一个数值后，根据这个数值定位到指定bit的位置，设置该bit的值为1（初始值都是0），循环执行，直到全部读完。
最后，从bit文件（或内存数组）中一次读取bit信息，根据bit的位置即可知道相应的数值是多少，如果该bit的值为1，则输出该数字（表示该数字重复）。完成。

Answer 6

改正，如果开内存的话，应该是1亿个uint类型数组

Answer 7

又发现错误了：（应该创建512M大小的文件，或开2亿个uint数组，因为数据的数量是32亿，但数值范围是int（4G/8=512M），所以必须按照数值范围设定bit的个数而不是按照数据的数量来设定。

Answer 8

有意思，好大好多,题目不太清楚我觉得 复杂度O(n)就可以数据[32亿]
结果[32亿]for ( i=0;i<32亿；i++)
{
结果[数据[i]]++;
}结果[32亿]=所有数字重复数 只要有硬盘空间没什么大问题。

Answer 9

32亿。。
不要说在文件里，即使是放在本地sql server的表里，用sql语句查重复数也会死上N久的吧

Answer 10

这道题我觉得很有意思。我觉得问题的关键是平衡时间和空间的复杂度。[Code=C# Code]
const int Groups = 10000; // 将32亿数据分组，这个数可以调整，但应当能够被32亿整除byte exist[32亿 / Groups]; // 0: 不存在；1：找到1个；2找到多个// 分组后（注：将32位整数看做无符号的，不会影响计算结果）
// 第0组范围exist.Length * 0 ~ exist.Length * 1 (不包含右边的值)
// 第1组范围exist.Length * 1 ~ exist.Length * 2 (不包含右边的值)
// ....
// 最后1组的范围exist.Length * (Groups - 1) ~ exist.Length * Groups (不包含右边的值)for (int g = 0; g < Groups; g++)
{
  for (int n = 0; n < result.Length; n++)
  {
    exist[n] = 0;
  }  // 第g组的范围
  uint minValue = exist.Length * g;
  uint maxValue = (exist.Length * g - 1) + exist.Length; // 不要用exist.Length * (g + 1) - 1，否则运算结果会溢出  // 每次从磁盘读入1MB的数据，并转换为256 * 1024个无符号整数(数量同样可以调整)
  [byte buffer[1024 * 1024] => uint data[256 * 1024]]  foreach (int value in data)
  {
    // 分析本次分组范围内的数据
    if ((value >= minValue) && (value <= maxValue))
    {
      // 找到第1个
      if (exist[value - minValue] == 0)
      {
        exist[value - minValue] = 1;
        continue;
      }      // 找到第2个(后面再找到不需要再处理了)
      if (exist[value - minValue] == 1)
      {
        exist[value - minValue] = 2;        output: value
        continue;
      }
    }
  }
}[/Code]上面的算法中核心概念是分组处理，并且有两处可调整的大小，能够很好的平衡时间和空间的关系。

Answer 11

这道题我觉得很有意思。我觉得问题的关键是平衡时间和空间的复杂度。 [C# Code] 
const int Groups = 10000; // 将32亿数据分组，这个数可以调整，但应当能够被32亿整除 byte exist[32亿 / Groups]; // 0: 不存在；1：找到1个；2找到多个 // 分组后（注：将32位整数看做无符号的，不会影响计算结果） 
// 第0组范围exist.Length * 0 ~ exist.Length * 1 (不包含右边的值) 
// 第1组范围exist.Length * 1 ~ exist.Length * 2 (不包含右边的值) 
// .... 
// 最后1组的范围exist.Length * (Groups - 1) ~ exist.Length * Groups (不包含右边的值) for (int g = 0; g < Groups; g++) 
{ 
  for (int n = 0; n < [Color:#00000FF]exist.Length[/Color]; n++) 
  { 
    exist[n] = 0; 
  }   // 第g组的范围 
  uint minValue = exist.Length * g; 
  uint maxValue = (exist.Length * g - 1) + exist.Length; // 不要用exist.Length * (g + 1) - 1，否则运算结果会溢出   // 每次从磁盘读入1MB的数据，并转换为256 * 1024个无符号整数(数量同样可以调整) 
  [byte buffer[1024 * 1024] => uint data[256 * 1024]]   foreach ([Color:#00000FF]uint[/Color] value in data) 
  { 
    // 分析本次分组范围内的数据 
    if ((value >= minValue) && (value <= maxValue)) 
    { 
      // 找到第1个 
      if (exist[value - minValue] == 0) 
      { 
        exist[value - minValue] = 1; 
        continue; 
      }       // 找到第2个(后面再找到不需要再处理了) 
      if (exist[value - minValue] == 1) 
      { 
        exist[value - minValue] = 2;         output: value 
        continue; 
      } 
    } 
  } 
} [/C# Code] 上面的算法中核心概念是分组处理，并且有两处可调整的大小，能够很好的平衡时间和空间的关系。

Answer 12

分页处理是你自己想象的吧。我曾经有一个程序，4G内存，SQL大约占了1.8G，其他程序大约几百M，剩下的空间都归我，我的程序占内存比较厉害，开到大约1.6-1.7G左右就崩溃。后来改了程序，换了别的办法，不开那么多内存了才好的。（Win2003企业版，IBM服务器，4核心Xeon）程序能开的内存似乎是有限制的。

Answer 13

我的办法（增强改错版）: 因为数量极大，在内存中直接处理是不现实的，但是可以利用这道题的特点。 
因为只需要知道哪些数是重复的，而不需要知道重复多少次，所以，我们可以利用bit来记录。 首先创建一个512M大小的文件（称为bit文件），也就是32亿个bit（如果内存够大，也可以直接开2亿个int型数组，在内存里操作速度要快得多）。 
然后开始读取文件中的数值，读取到一个数值后，根据这个数值定位到指定bit的位置，读取该位置的bit值，如果设置该bit的值为1（初始值都是0），则输出该数字（或保存到另一个文件中），否则设置该bit的值为1，循环执行，直到全部读完，重复数字也就出来了。 完成。至于说用排序的办法，我觉得是浪费资源。一是在这里顺序无意义，二是排序需要多次的倒来倒去，需要的时间更多，而且排完序以后，仍然要将这些数据重新读一遍，并判重和输出，多干了很多事。

Answer 14

这个方法是有问题的，因为BIT的2个状态是不够用的，请参考我在22楼写的代码。实际上需要保持3个状态：
(1) 计数为0个；(2) 计数为1个；(3)计数为多个按照Foxer的算法，计数1个时置1，计数2个时输出，那么计数3个、4个时同样也只能输出，因为你不知道自己是第几次重复，是不是这样？

Answer 15

const int Groups = 10000; // 将32亿数据分组，这个数可以调整，但应当能够被32亿整除 byte exist[32亿 / Groups]; // 0: 不存在；1：找到1个；2找到多个 // 分组后（注：将32位整数看做无符号的，不会影响计算结果） 
// 第0组范围exist.Length * 0 ~ exist.Length * 1 (不包含右边的值) 
// 第1组范围exist.Length * 1 ~ exist.Length * 2 (不包含右边的值) 
// .... 
// 最后1组的范围exist.Length * (Groups - 1) ~ exist.Length * Groups (不包含右边的值) for (int g = 0; g < Groups; g++) 
{ 
  for (int n = 0; n < exist.Length; n++) 
  { 
    exist[n] = 0; 
  }   // 第g组的范围 
  uint minValue = exist.Length * g; 
  uint maxValue = (exist.Length * g - 1) + exist.Length; // 不要用exist.Length * (g + 1) - 1，否则运算结果会溢出   // 每次从磁盘读入1MB的数据，并转换为256 * 1024个无符号整数(数量同样可以调整) 
  [byte buffer[1024 * 1024] => uint data[256 * 1024]]   foreach (int value in data) 
  { 
    // 分析本次分组范围内的数据 
    if ((value >= minValue) && (value <= maxValue)) 
    { 
      // 找到第1个 
      if (exist[value - minValue] == 0) 
      { 
        exist[value - minValue] = 1; 
        continue; 
      }       // 找到第2个(后面再找到不需要再处理了) 
      if (exist[value - minValue] == 1) 
      { 
        exist[value - minValue] = 2;         output: value 
        continue; 
      } 
    } 
  } 
}  上面的算法中核心概念是分组处理，并且有两处可调整的大小，能够很好的平衡时间和空间的关系。

Answer 16

前边都是高人 说的蛮多了我再给你说个变态的  用一个 SORTEDLIST<int，int>
吧你的数字都当做KEY，ADD进去（ADD前判断下KEY是否存在，存在就下一个)
hehe   也可以分段。

Answer 17

如果变态的话，为啥不用Dictrinary<int, byte>呢？怎么说也省不少内存空间呢，而且Dictionary比SortedList的性能还是要高一些的。

Answer 18

我偷懒：(1) 将32亿的整数全部写入数据库(仅一个整型列)，用Oracle（可能比SQL Server略快一些）
(2) 在该整型列上创建索引
(3) 剩下的事情就简单了，大家都会，不管你是去重，还是找重，数据库都能做得很好。海量数据如何存储？如何检索？数据库就是干这个的，不用我去动脑子。

Answer 19

如果本来就无序的话, 分段,多线程同时处理.比如 分成 10段 , 用 10个线程主界面用单独的线程, 以便使在数据处理时 界面有反应,比如加个进度条啥的
如果本来就有序的话,那还是比较容易的从原文件里,一个INT 一个INT的读一遍就是了, 遇到重复的扔掉, 当原,两个INT一读,三个INT一读 都未尝不可

Answer 20

数据量很大的时候 Dictrinary会更慢的  
32亿个啊

Answer 21

Dictrinary会慢?
好像除了HashedTable，Dictionary<>应该是最快的了，SortedList在各种排序表里倒是最慢的

Answer 22

不排序的话  DIC数据量小的时候是快 
但是数据量很大的话 查询和索引KEY的时候 SORTED才是快的 
这么简单的问题不用费劲吧 

Answer 23

我曾经看过有人测试100万数据，SortedList和Dictionary可是数量级上的差距。