0

我的问题是将包含无符号整数的巨大文本文件（UTF-8 -1byte（ANSI））在升序中没有重复项放入数组中。快速地！所以我打算这样做：

while(scan.hasNextInt()) x.add(scan.nextInt());

但是，无论我使用 ArrayList、Vectors 还是包含数百万个整数的文件的普通数组，明智的做法是确定避免以后增加数组大小所需的最大容量。

使用 File.length() 我将获得文件中的位数 + 换行符。

在最坏的情况下，它会从 0 开始，并且在每一行中只增加 1。
我认为最大值。容量可以使用组合数学计算，但我处于死胡同。较小的数字不会被零（002）填充的事实不知何故让我失望。

考虑到第一个 Int 的大小，我认为一个也可以更接近实际数量。

所以我最重要的问题是计算所需的近似 [in O(1)] 最大容量。

此外，考虑到这个相当独特的问题，我问我自己 scan.hasNextInt() 和 scan.nextInt() 是否是最快的，如果通过线程并行化可以更快地加快进程（考虑到从硬盘读取的特性可能不是）。

问候光环

4

1 回答 1

1

假设只有一个字节用于分隔两个数字（例如'\n'），我们有

  • 10 个数字，1 个数字 -> 20 个字节
  • 90 个 2 位数字 -> 270 字节
  • 900 个 3 位数字 -> 3600 字节
  • ...你得到了模式

如果您的文件大小现在是 1000 字节，那么您可以拥有的最大值是 10 个 1 位，90 个两位数，剩下 710 个字节用于 3 位数字。710/4 = 177.5，最多有 10+90+177 = 277 个数字。

于 2013-01-13T20:39:57.783 回答