如何最快地设置数组中的所有值？

Question

我有一个char []数组，我想将每个索引的值设置为相同的char值。
有一种显而易见的方法可以做到这一点（迭代）：

  char f = '+';
  char [] c = new char [50];
  for(int i = 0; i < c.length; i++){
      c[i] = f;
  }

但是我想知道是否有一种方法可以利用System.arraycopy或类似的东西来避免需要迭代。有什么办法可以做到这一点吗？

编辑： 来自Arrays.java

public static void fill(char[] a, int fromIndex, int toIndex, char val) {
        rangeCheck(a.length, fromIndex, toIndex);
        for (int i = fromIndex; i < toIndex; i++)
            a[i] = val;
    }

这完全是相同的过程，这表明可能没有更好的方法来完成这项任务。
给建议使用fill的每个人+1 - 你们都是正确的，谢谢。

- rtheunissen

---

你的附录中JDK代码的版本显示了一种“swizzle”，这在某些JDK版本中会执行：某个外部标志指示应该在方法中绕过数组边界检查，然后在循环之外添加一个显式的边界检查。这提供了显著的性能提升，因为边界检查不仅本身很昂贵，而且它还会使其他优化变得复杂。 - Hot Licks

@Bombe，这是为了自定义密码字段，因此我必须在文档中实时将每个char替换为'•'，这意味着它必须尽可能响应。你可能会问，为什么不在进行索引时设置每个值？这是为了与drawString一起使用，以便可以反走样•的文本。 fill看起来效果不错。 :) - rtheunissen

@paranoid-android，那你确实有一些用户能够每秒输入超过1000个字符吗？我很惊讶。 - Bombe

好的，我正在为超人编写代码。 - rtheunissen

我认为最好使用“fill”，因为它是内置类的标准方法，而且在运行时可以由JVM更改为更有效的实现。我甚至认为这是注定会发生的。Java从设计上不支持直接内存访问，但这并不意味着生成的代码不应该支持它。 - weaknespase

Answer 1

尝试使用Arrays.fill(c, f)：查看Arrays文档

- Kurt Du Bois

---

Arrays.fill的源代码表明它只是一个循环（事先加上一个范围检查）。应该进行基准测试以查看JVM是否会做一些聪明的优化。 - DNA

如果它是一个二维数组，该怎么办？ - Kuldeep Yadav

虽然这种方法简洁有效，但请看@RossDrew的下一个答案：与优化方法相比，这种方法极其缓慢。 - WestCoastProjects

Answer 2

作为另一种选择并且为了后代，我最近研究了这个问题，并找到了一个解决方案，它可以通过将一些工作交给System类来实现更短的循环（如果你正在使用的JVM足够聪明，它可以转换为memset操作）。

/*
 * initialize a smaller piece of the array and use the System.arraycopy 
 * call to fill in the rest of the array in an expanding binary fashion
 */
public static void bytefill(byte[] array, byte value) {
  int len = array.length;

  if (len > 0){
    array[0] = value;
  }

  //Value of i will be [1, 2, 4, 8, 16, 32, ..., len]
  for (int i = 1; i < len; i += i) {
    System.arraycopy(array, 0, array, i, ((len - i) < i) ? (len - i) : i);
  }
}

这个解决方案来自IBM研究论文"Java server performance: A case study of building efficient, scalable Jvms"，作者为R. Dimpsey，R. Arora和K. Kuiper。

简化说明

正如注释所示，它将目标数组的索引0设置为您的值，然后使用System类将一个对象即索引0处的对象复制到索引1，然后将这两个对象（索引0和1）复制到2和3，然后将这四个对象（0、1、2和3）复制到4、5、6和7，以此类推...

效率（写作时）

快速运行并在调用System.nanoTime()之前和之后进行计算，得出以下结果：

• 该方法： 332,617 - 390,262 （从10次测试中取得的最高 - 最低值）
• Float[] n = new Float[array.length]; //Fill with null ：666,650
• 通过循环进行设置：3,743,488 - 9,767,744 （从10次测试中取得的最高 - 最低值）
• Arrays.fill ：12,539,336

JVM和JIT编译

需要注意的是，随着JVM和JIT的演进，此方法可能会变得过时，因为库和运行时优化可能会使用fill()达到甚至超过这些数字。 在撰写本文时，这是我找到的最快选项。虽然有人提到现在可能不是这种情况，但我没有检查。这就是Java的美和诅咒。

- Ross Drew

---

这将是被接受的答案，Arrays.fill 在处理大型数组时速度较慢，如果你在追求速度，那么这个答案真的很有帮助。提问者指出“最快的方式”。 - M.E.

这不就是 Bill Tutt 已经发布的内容吗？ - timbo

@timbo，是的，这是相同的方法。我发布了我的答案，因为答案很简洁，链接已经失效。我发表了更深入的解释，包括完整引用名称的源研究链接，解释了它在当时的性能以及为什么以这种方式优化Java是过时的或将要过时的。我觉得需要一个更完整的答案，并根据我的赞数判断，这个答案是受欢迎的。 - Ross Drew

@RossDrew - 在过去的某个时候，有人拿走了你的代码并将其提交到了Apache POI代码库中 - 请参见https://bz.apache.org/bugzilla/show_bug.cgi?id=65796 - 是否可能获得您的许可以重用您的代码？对此给您带来的不便深感抱歉。 - PJ Fanning

@RossDrew 我们从Apache POI中删除了代码 - 原来在现代JVM中，Arrays.fill被优化了 (http://psy-lob-saw.blogspot.com/2015/04/on-arraysfill-intrinsics-superword-and.html) - 我使用jmh进行基准测试，并发现这是情况 (Zulu 1.8.0_302和17.0.0 JVMs)。 - PJ Fanning

@PJFanning 我写这篇文章的时候就知道这至少最终会成为事实。这就是我加上最后一部分的原因，以反映Java的巨大优势; 你的代码将变得更快。 - Ross Drew

Answer 3

使用 Arrays.fill

  char f = '+';
  char [] c = new char [50];
  Arrays.fill(c, f)

- soulcheck

Answer 4

Java程序员常见问题解答第B部分第6节建议:

public static void bytefill(byte[] array, byte value) {
    int len = array.length;
    if (len > 0)
    array[0] = value;
    for (int i = 1; i < len; i += i)
        System.arraycopy( array, 0, array, i,
            ((len - i) < i) ? (len - i) : i);
}

这基本上会使得log2（array.length）次System.arraycopy调用，希望能够利用优化后的memcpy实现。

然而，在现代的Java JIT(例如Oracle/Android JIT)上是否仍需要使用这种技术呢？

- Bill Tutt

---

我找到了教程，但没有找到具体的链接 - 你知道它在哪里吗？ - Karussell

我的回答中有链接，可以深入讨论@Karussell的这种方法。 - Ross Drew

Answer 5

截至Java-8，setAll方法有四种变体，使用提供的生成函数计算每个元素来设置指定数组的所有元素。

其中只有三种重载接受声明为原语类型的数组。

---

• setAll(double[] array, IntToDoubleFunction generator)

该方法将指定数组中的所有元素设置为由提供的生成器函数生成的值。其中，参数array是要设置的数组，参数generator是一个函数，它接受一个整数参数并返回一个double类型的值，用于生成数组的新值。

---

• setAll(int[]数组, IntUnaryOperator生成器)

---

• setAll(long[] array, IntToLongFunction generator)

（注：该文本为HTML代码，无法直接翻译，已保留原文）

---

以下是如何使用上述方法的示例：

// given an index, set the element at the specified index with the provided value
double [] doubles = new double[50];
Arrays.setAll(doubles, index -> 30D);

// given an index, set the element at the specified index with the provided value
int [] ints = new int[50];
Arrays.setAll(ints, index -> 60);

 // given an index, set the element at the specified index with the provided value
long [] longs = new long[50];
Arrays.setAll(longs, index -> 90L);

setAll方法提供的函数接收元素索引并返回该索引的值。

你可能会想到字符数组怎么办？

这就是第四个重载的setAll方法发挥作用的地方。由于没有消耗字符原语数组的重载，我们唯一的选择是将字符数组的声明更改为类型Character[]。

如果将数组类型更改为Character不合适，则可以退回到Arrays.fill方法。

使用Character[]的setAll方法的示例：

// given an index, set the element at the specified index with the provided value
Character[] character = new Character[50];
Arrays.setAll(characters, index -> '+'); 

虽然使用Arrays.fill方法比setAll方法更简单，但如果要设置特定值，则使用setAll方法有优势。

setAll方法的优点是可以将数组的所有元素设置为相同的值，或生成一个偶数、奇数或任何其他公式的数组:

例如：

int[] evenNumbers = new int[10]; 
Arrays.setAll(evenNumbers, i -> i * 2);

此外，parallelSetAll 方法还有几种重载形式，可以并行执行，但需要注意传递给 parallelSetAll 方法的函数必须是没有副作用的。

结论

如果您的目标仅是为数组的每个元素设置特定值，则使用 Arrays.fill 重载选项是最合适的选择。但是，如果您想要更灵活或按需生成元素，则使用 Arrays.setAll 或 Arrays.parallelSetAll（在适当情况下）将是更好的选择。

- Ousmane D.

---

我发现当将一个数组（大小为500）设置为默认值时，使用setall比使用fill要快大约3倍。 - Nrj

Answer 6

我认为System.arraycopy是最好的选择。如果有更好的方法，请告诉我。谢谢。

private static long[] r1 = new long[64];
private static long[][] r2 = new long[64][64];

/**Proved:
 * {@link Arrays#fill(long[], long[])} makes r2 has 64 references to r1 - not the answer;
 * {@link Arrays#fill(long[], long)} sometimes slower than deep 2 looping.<br/>
 */
private static void testFillPerformance() {
    SimpleDateFormat sdf = new SimpleDateFormat("HH:mm:ss");
    System.out.println(sdf.format(new Date()));
    Arrays.fill(r1, 0l);

    long stamp0 = System.nanoTime();
    //      Arrays.fill(r2, 0l); -- exception
    long stamp1 = System.nanoTime();
    //      System.out.println(String.format("Arrays.fill takes %s nano-seconds.", stamp1 - stamp0));

    stamp0 = System.nanoTime();
    for (int i = 0; i < 64; i++) {
        for (int j = 0; j < 64; j++)
            r2[i][j] = 0l;
    }
    stamp1 = System.nanoTime();
    System.out.println(String.format("Arrays' 2-looping takes %s nano-seconds.", stamp1 - stamp0));

    stamp0 = System.nanoTime();
    for (int i = 0; i < 64; i++) {
        System.arraycopy(r1, 0, r2[i], 0, 64);
    }
    stamp1 = System.nanoTime();
    System.out.println(String.format("System.arraycopy looping takes %s nano-seconds.", stamp1 - stamp0));

    stamp0 = System.nanoTime();
    Arrays.fill(r2, r1);
    stamp1 = System.nanoTime();
    System.out.println(String.format("One round Arrays.fill takes %s nano-seconds.", stamp1 - stamp0));

    stamp0 = System.nanoTime();
    for (int i = 0; i < 64; i++)
        Arrays.fill(r2[i], 0l);
    stamp1 = System.nanoTime();
    System.out.println(String.format("Two rounds Arrays.fill takes %s nano-seconds.", stamp1 - stamp0));
}

12:33:18
使用两个循环的Arrays方法需要133536纳秒。
使用System.arraycopy方法需要22070纳秒。
一个循环的Arrays.fill方法需要9777纳秒。
两个循环的Arrays.fill方法需要93028纳秒。

12:33:38
使用两个循环的Arrays方法需要133816纳秒。
使用System.arraycopy方法需要22070纳秒。
一个循环的Arrays.fill方法需要17042纳秒。
两个循环的Arrays.fill方法需要95263纳秒。

12:33:51
使用两个循环的Arrays方法需要199187纳秒。
使用System.arraycopy方法需要44140纳秒。
一个循环的Arrays.fill方法需要19555纳秒。
两个循环的Arrays.fill方法需要449219纳秒。

12:34:16
使用两个循环的Arrays方法需要199467纳秒。
使用System.arraycopy方法需要42464纳秒。
一个循环的Arrays.fill方法需要17600纳秒。
两个循环的Arrays.fill方法需要170971纳秒。

12:34:26
使用两个循环的Arrays方法需要198907纳秒。
使用System.arraycopy方法需要24584纳秒。
一个循环的Arrays.fill方法需要10616纳秒。
两个循环的Arrays.fill方法需要94426纳秒。

- odys

---

你的日志中每次运行都表明Arrays.fill(...)更快，为什么你选择使用System.arraycopy(...)？一般来说，Arrays.fill(...)的速度要快得多！ - ingyhere

对于阅读此答案的人，如果您错过了odys在方法开头的评论，请注意。一个 round 的 Arrays.fill 实际上是使用 Arrays.fill(Object[],Object)，它将用 r1 的引用填充外部数组（即设置 r2[i][j] = 42 后，所有 x 的 r2[x][j] = 42），这显然不是预期的行为。 - ggf31416

Answer 7

我对Ross Drew的答案有一个小改进。

对于一个较小的数组，简单的循环比使用System.arraycopy方法更快，因为使用System.arraycopy需要一些开销。因此，在填充数组的前几个字节时最好使用简单的循环，只有当填满的数组达到一定大小后再转向使用System.arraycopy。

当然，初始循环的最优大小将取决于JVM和系统的具体情况。

private static final int SMALL = 16;

public static void arrayFill(byte[] array, byte value) {
  int len = array.length;
  int lenB = len < SMALL ? len : SMALL;

  for (int i = 0; i < lenB; i++) {
    array[i] = value;
  }

  for (int i = SMALL; i < len; i += i) {
    System.arraycopy(array, 0, array, i, len < i + i ? len - i : i);
  }
}

- radfast

---

另一个小的改进可能是移除条件语句： for (int i = SMALL, mask; i < len; i += i) {mask = (len - i + i) >> 31; System.arraycopy(array, 0, array, i, ~mask & len - i | mask & i);}我没有在实践中进行基准测试，所以这可能不是最佳方案。 - RipeGorilla

有趣！原则上，当编译成本地代码时，我同意一些算术和位操作在现代CPU上可能比条件分支更快。但是，在System.arraycopy内部将会有条件分支，我们无能为力... - radfast

Answer 8

如果您有另一个字符数组char[] b，并且想要用b替换c，您可以使用c=b.clone();。

- Dragos

---

或者，如果您的数组长度是可变的，请创建一个“超长”原型并使用System.arraycopy。 任何一种方法都可以在底层有效地执行memcpy。 - Hot Licks

Answer 9

请查看Arrays.fill方法:

char f = '+';
char [] c = new char [50];
Arrays.fill(c, f);

- Mariusz Jamro

Answer 10

Arrays.fill(myArray, 'c');

Arrays.fill

虽然这很可能是在后台执行循环，因此与您拥有的代码相比并没有更高的效率（除了节省代码行数）。如果您真的关心效率，请尝试与上述内容进行比较：

int size = 50;
char[] array = new char[size];
for (int i=0; i<size; i++){
  array[i] = 'c';
}

注意上面的代码在每一次迭代中并没有调用 array.size() 方法。

- John B

---

对于数组长度的引用是廉价的（不是调用），并且很容易从循环中优化掉。 - Hot Licks

@HotLicks 你确定编译器会这样做吗？在循环中数组引用不可能改变（因此大小也会改变）吗？因此，编译器优化是否安全？我想，如果它足够聪明，能够确保循环内部不修改数组引用，那么它可以这样做。再次问一下，你有关于这种优化正在进行的知识吗？ - John B

@HotLicks，我可以假设你的陈述适用于数组但不适用于集合吗？ - John B

在循环中array没有被改变，这对编译器来说非常容易确定。而且arraylength字节码直接引用了数组对象中的数组大小字段，因此如果保留在循环中，它几乎和移出循环一样便宜。即使是Sun自己的代码（在我的帖子中）也不必担心将引用移出循环。最大的性能提升是在Paranoid原始版本的附录中展示的Sun代码的更优化版本中获得的——在该方法上有一个特殊/秘密标志关闭边界检查，并且显式边界检查在循环外执行。 - Hot Licks