最快的方式来创建新的数组长度为n，并通过重复给定阵列填充 [英] Fastest way to create new array with length N and fill it by repeating a given array
本文介绍了最快的方式来创建新的数组长度为n，并通过重复给定阵列填充的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我要分配的长度为N的新数组，并通过重复给定阵列填满它。接口看起来是这样的：
I want to allocate a new array with the length N and fill it up by repeating a given array. The interface looks like this:
<T> T[] repeat(T[] array, int n);
要澄清我的意思是这里是一个小例子：
To clarify what I mean here is a small example:
String a = {"a", "b", "c"};
// b = {"a", "b", "c", "a", "b", "c", "a", "b", "c", "a"}
String b = repeat(a, 10);
大多数程序员会拿出下述溶液中（对数组代之所以选择特定类型的简单）：
Most of the programmer will come up with the following solution (for simplicity of array generation a specific type was chosen):
public String[] repeat(String[] array, int n) {
String[] repeated = new String[n];
for (int i = 0; i < n; i++) {
repeated[i] = array[i % array.length];
}
return repeated;
}
有一个更快的方法来做到这一点？
Is there a faster way to do this?
推荐答案
我想出了这个通用的解决方案：
I came up with this generic solution:
public static <T> T[] repeat(T[] arr, int newLength) {
T[] dup = Arrays.copyOf(arr, newLength);
for (long last = arr.length; last != 0 && last < newLength; last <<= 1) {
System.arraycopy(dup, 0, dup, (int) last, (int) (Math.min(last << 1, newLength) - last));
}
return dup;
}
论
System.arraycopy 是本机调用。因此，这是非常快的，但它并不意味着它是最快的方法。
Theory
System.arraycopy is a native call. Therefore it is very fast but it doesn't mean it is the fastest way.
每一个其他的解决办法copys通过元素的数组元素。我的解决方案copys更大的块。每次迭代复制数组中的现有元素，这意味着循环将最多运行的 LOG2（N）倍。
Every other solution copys the array element by element. My solution copys larger blocks. Every iteration duplicates the existing elements in the array which means the loop will run at most log2(n) times.
TEST_ARRAY = { "a", "b", "c", "d", "e", "f" }
NEW_LENGTH = 10000
下面是我的标杆code重现的结果：
Here is my benchmark code to reproduce the results:
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Threads;
import org.openjdk.jmh.annotations.Warmup;
@Fork(3)
@BenchmarkMode(Mode.AverageTime)
@Measurement(iterations = 10, timeUnit = TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
@Threads(1)
@Warmup(iterations = 5, timeUnit = TimeUnit.NANOSECONDS)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class MyBenchmark {
private static final String[] TEST_ARRAY = { "a", "b", "c", "d", "e", "f" };
private static final int NEW_LENGTH = 10_000;
@Benchmark
public String[] testNativeCall() {
String[] dup = Arrays.copyOf(TEST_ARRAY, NEW_LENGTH);
for (int last = TEST_ARRAY.length; last != 0 && last < NEW_LENGTH; last <<= 1) {
System.arraycopy(dup, 0, dup, last, Math.min(last << 1, NEW_LENGTH) - last);
}
return dup;
}
@Benchmark
public String[] testLoopModulo() {
String[] arr = new String[NEW_LENGTH];
for (int i = 0; i < NEW_LENGTH; i++) {
arr[i] = arr[i % TEST_ARRAY.length];
}
return arr;
}
@Benchmark
public String[] testArrayList() {
List<String> initialLetters = Arrays.asList(TEST_ARRAY);
List<String> results = new ArrayList<>();
int indexOfLetterToAdd = 0;
for (int i = 0; i < 10000; i++) {
results.add(initialLetters.get(indexOfLetterToAdd++));
if (indexOfLetterToAdd == initialLetters.size()) {
indexOfLetterToAdd = 0;
}
}
return results.toArray(new String[results.size()]);
}
@Benchmark
public String[] testLoopReset() {
String result[] = new String[NEW_LENGTH];
for (int i = 0, j = 0; i < NEW_LENGTH && j < TEST_ARRAY.length; i++, j++) {
result[i] = TEST_ARRAY[j];
if (j == TEST_ARRAY.length - 1) {
j = -1;
}
}
return result;
}
@Benchmark
public String[] testStream() {
String[] result = Stream.iterate(TEST_ARRAY, x -> x).flatMap(x -> Stream.of(TEST_ARRAY)).limit(NEW_LENGTH)
.toArray(String[]::new);
return result;
}
}
结果
Benchmark Mode Cnt Score Error Units
MyBenchmark.testNativeCall avgt 30 4154,553 ± 11,242 ns/op
MyBenchmark.testLoopModulo avgt 30 19273,717 ± 235,547 ns/op
MyBenchmark.testArrayList avgt 30 71079,139 ± 2686,136 ns/op
MyBenchmark.testLoopReset avgt 30 18307,368 ± 202,520 ns/op
MyBenchmark.testStream avgt 30 68898,278 ± 2488,104 ns/op
正如你可以看到本机调用的方法就是重复一个数组的最快方法。
As you can see the native call method is the fastest way to repeat an array.
另外，我被要求基准这些方法与不同的输入。
Further I was asked to benchmark these methods with various inputs.
// Array size not fixed anymore - filled with random elements
SIZE = { 100, 1000, 100000, 1000000 }
NEW_LENGTH = { 100, 1000, 100000, 1000000 }
这意味着有大小x NEW_LENGTH 测试和这里的结果：
Benchmark (NEW_LENGTH) (SIZE) Mode Cnt Score Error Units
MyBenchmark.testArrayList 100 100 avgt 30 706,274 ± 6,787 ns/op
MyBenchmark.testArrayList 100 1000 avgt 30 692,586 ± 15,076 ns/op
MyBenchmark.testArrayList 100 100000 avgt 30 685,214 ± 6,747 ns/op
MyBenchmark.testArrayList 100 1000000 avgt 30 685,333 ± 5,493 ns/op
MyBenchmark.testArrayList 1000 100 avgt 30 7170,897 ± 63,221 ns/op
MyBenchmark.testArrayList 1000 1000 avgt 30 7180,612 ± 93,280 ns/op
MyBenchmark.testArrayList 1000 100000 avgt 30 6818,585 ± 197,859 ns/op
MyBenchmark.testArrayList 1000 1000000 avgt 30 6810,614 ± 139,456 ns/op
MyBenchmark.testArrayList 100000 100 avgt 30 597614,173 ± 6446,318 ns/op
MyBenchmark.testArrayList 100000 1000 avgt 30 580696,750 ± 5141,845 ns/op
MyBenchmark.testArrayList 100000 100000 avgt 30 598657,608 ± 5126,519 ns/op
MyBenchmark.testArrayList 100000 1000000 avgt 30 595529,027 ± 4981,095 ns/op
MyBenchmark.testArrayList 1000000 100 avgt 30 6836746,484 ± 38848,467 ns/op
MyBenchmark.testArrayList 1000000 1000 avgt 30 6745066,786 ± 57971,469 ns/op
MyBenchmark.testArrayList 1000000 100000 avgt 30 7130391,072 ± 50583,914 ns/op
MyBenchmark.testArrayList 1000000 1000000 avgt 30 8791342,042 ± 172323,938 ns/op
MyBenchmark.testLoopModulo 100 100 avgt 30 301,252 ± 1,195 ns/op
MyBenchmark.testLoopModulo 100 1000 avgt 30 301,988 ± 2,056 ns/op
MyBenchmark.testLoopModulo 100 100000 avgt 30 299,892 ± 1,776 ns/op
MyBenchmark.testLoopModulo 100 1000000 avgt 30 300,468 ± 2,569 ns/op
MyBenchmark.testLoopModulo 1000 100 avgt 30 3277,018 ± 14,880 ns/op
MyBenchmark.testLoopModulo 1000 1000 avgt 30 3275,648 ± 21,742 ns/op
MyBenchmark.testLoopModulo 1000 100000 avgt 30 3258,570 ± 27,360 ns/op
MyBenchmark.testLoopModulo 1000 1000000 avgt 30 3259,617 ± 28,747 ns/op
MyBenchmark.testLoopModulo 100000 100 avgt 30 321483,331 ± 4320,938 ns/op
MyBenchmark.testLoopModulo 100000 1000 avgt 30 326319,662 ± 2419,602 ns/op
MyBenchmark.testLoopModulo 100000 100000 avgt 30 327027,966 ± 3174,011 ns/op
MyBenchmark.testLoopModulo 100000 1000000 avgt 30 319201,057 ± 4472,220 ns/op
MyBenchmark.testLoopModulo 1000000 100 avgt 30 3053122,364 ± 31814,342 ns/op
MyBenchmark.testLoopModulo 1000000 1000 avgt 30 3134151,676 ± 108227,023 ns/op
MyBenchmark.testLoopModulo 1000000 100000 avgt 30 3220082,188 ± 43925,401 ns/op
MyBenchmark.testLoopModulo 1000000 1000000 avgt 30 3204777,236 ± 25365,542 ns/op
MyBenchmark.testLoopReset 100 100 avgt 30 159,828 ± 1,107 ns/op
MyBenchmark.testLoopReset 100 1000 avgt 30 125,461 ± 0,881 ns/op
MyBenchmark.testLoopReset 100 100000 avgt 30 129,912 ± 7,801 ns/op
MyBenchmark.testLoopReset 100 1000000 avgt 30 134,503 ± 7,602 ns/op
MyBenchmark.testLoopReset 1000 100 avgt 30 1809,207 ± 93,642 ns/op
MyBenchmark.testLoopReset 1000 1000 avgt 30 1728,705 ± 70,808 ns/op
MyBenchmark.testLoopReset 1000 100000 avgt 30 1354,887 ± 9,631 ns/op
MyBenchmark.testLoopReset 1000 1000000 avgt 30 1350,327 ± 15,886 ns/op
MyBenchmark.testLoopReset 100000 100 avgt 30 159680,209 ± 2477,183 ns/op
MyBenchmark.testLoopReset 100000 1000 avgt 30 162030,985 ± 1949,660 ns/op
MyBenchmark.testLoopReset 100000 100000 avgt 30 149299,890 ± 1516,486 ns/op
MyBenchmark.testLoopReset 100000 1000000 avgt 30 136059,242 ± 3090,410 ns/op
MyBenchmark.testLoopReset 1000000 100 avgt 30 1407369,992 ± 12979,717 ns/op
MyBenchmark.testLoopReset 1000000 1000 avgt 30 1447001,173 ± 14979,769 ns/op
MyBenchmark.testLoopReset 1000000 100000 avgt 30 1463913,706 ± 12564,617 ns/op
MyBenchmark.testLoopReset 1000000 1000000 avgt 30 1404701,860 ± 21587,436 ns/op
MyBenchmark.testNativeCall 100 100 avgt 30 58,306 ± 0,669 ns/op
MyBenchmark.testNativeCall 100 1000 avgt 30 57,441 ± 0,590 ns/op
MyBenchmark.testNativeCall 100 100000 avgt 30 57,595 ± 0,386 ns/op
MyBenchmark.testNativeCall 100 1000000 avgt 30 60,196 ± 1,995 ns/op
MyBenchmark.testNativeCall 1000 100 avgt 30 450,808 ± 8,259 ns/op
MyBenchmark.testNativeCall 1000 1000 avgt 30 558,079 ± 5,724 ns/op
MyBenchmark.testNativeCall 1000 100000 avgt 30 557,246 ± 4,873 ns/op
MyBenchmark.testNativeCall 1000 1000000 avgt 30 565,005 ± 9,696 ns/op
MyBenchmark.testNativeCall 100000 100 avgt 30 73074,811 ± 3332,432 ns/op
MyBenchmark.testNativeCall 100000 1000 avgt 30 70970,603 ± 2693,394 ns/op
MyBenchmark.testNativeCall 100000 100000 avgt 30 69907,864 ± 2945,072 ns/op
MyBenchmark.testNativeCall 100000 1000000 avgt 30 74041,205 ± 2599,841 ns/op
MyBenchmark.testNativeCall 1000000 100 avgt 30 790679,353 ± 15672,480 ns/op
MyBenchmark.testNativeCall 1000000 1000 avgt 30 812660,137 ± 25490,999 ns/op
MyBenchmark.testNativeCall 1000000 100000 avgt 30 838094,181 ± 12374,194 ns/op
MyBenchmark.testNativeCall 1000000 1000000 avgt 30 925567,535 ± 19091,943 ns/op
MyBenchmark.testStream 100 100 avgt 30 810,262 ± 54,519 ns/op
MyBenchmark.testStream 100 1000 avgt 30 1344,998 ± 14,792 ns/op
MyBenchmark.testStream 100 100000 avgt 30 159901,562 ± 3453,210 ns/op
MyBenchmark.testStream 100 1000000 avgt 30 1407506,571 ± 419985,287 ns/op
MyBenchmark.testStream 1000 100 avgt 30 6464,099 ± 169,665 ns/op
MyBenchmark.testStream 1000 1000 avgt 30 5869,457 ± 260,297 ns/op
MyBenchmark.testStream 1000 100000 avgt 30 165394,656 ± 4943,362 ns/op
MyBenchmark.testStream 1000 1000000 avgt 30 1352900,959 ± 412849,634 ns/op
MyBenchmark.testStream 100000 100 avgt 30 423531,274 ± 3944,801 ns/op
MyBenchmark.testStream 100000 1000 avgt 30 391727,181 ± 5341,826 ns/op
MyBenchmark.testStream 100000 100000 avgt 30 427462,700 ± 7517,953 ns/op
MyBenchmark.testStream 100000 1000000 avgt 30 981304,769 ± 10206,849 ns/op
MyBenchmark.testStream 1000000 100 avgt 30 4528465,859 ± 72959,405 ns/op
MyBenchmark.testStream 1000000 1000 avgt 30 4121720,516 ± 60283,781 ns/op
MyBenchmark.testStream 1000000 100000 avgt 30 5920334,609 ± 63051,631 ns/op
MyBenchmark.testStream 1000000 1000000 avgt 30 6227476,270 ± 84066,493 ns/op
由于预期本机调用总是领先（除循环版本快约2倍）。
As expected the native call is always ahead (about 2 times faster than the loop version).
这篇关于最快的方式来创建新的数组长度为n，并通过重复给定阵列填充的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
