(2015 年 9 月 4 日現在、再現可能なベンチマークと結論を含めるように修正されています)
もちろんvalues.clear()、新しいオブジェクトを作成するよりも高速です (最後のアイテムのインデックスをゼロに設定するだけです)。
ほぼ確実に、新しいオブジェクトを作成するよりも a のvalues.clear()方が高速です。最初に使用した の場合ArrayList、挿入インデックスをゼロに設定するだけです。
PD#1 でコメントしたように、 BitSetは、要素が整数であるこのケースでは最速のアプローチかもしれません(値の範囲が広すぎないと仮定します。しかし、それは他のタイプの要素には役に立たないかもしれません.
またが言ったように 私はAssyliasの答えと一致したので、 HashSetはArrayListよりも良い選択です（O（N）のパフォーマンスにつながらない適切な分布を与えると仮定しhashCode()ます）。
このHashSet場合、直観は、clear()（基本的HashSet#tableに「鳩の穴」の配列をnullに設定する）が、まったく新しいコレクションを構築するよりも高速であることを示唆します（いずれにしても、同じテーブルを初期化/ゼロにリセットする必要があります）。しかし、この特定のケースでは、逆のことが起こります。アッシリアスは彼の結果を発表しました。残念ながら、これがどのように発生するかを調べるために、ベンチマークを自分でコーディングする必要がありました。この問題については PD#3 で説明します
とにかく、これについての主なことは、パフォーマンスとリソースにもっと注意を払わなければならない場合を除いて、反復ごとに真新しい HashSet を作成しても実質的なペナルティがないため、そうするのが理にかなっているということです (より単純なので)。
パフォーマンスに関するもう 1 つの問題はI/Oです。サンプルSystem.out.println()コードではおそらくすべての行に対して実行され、ボトルネックが console/stdout にflush()自動的に移動します。回避策は、. その出力を熱心に待っているリーダー プロセスがない限り、ループの最後まで書き込みを遅らせることは理にかなっているかもしれません。StringBuffer
これは私の試みです：
Set<Integer> values = new HashSet<Integer>();
// (PD 1) Or new BitSet(max_x - min_x + 1);
// (PD 2) Or new HashSet((int)Math.ceil(n/0.75));
StringBuffer sb = new StringBuffer(); // appends row values for printing together.
for (int j = 0, x; j < m; j++) {
values.clear();
sb.setLength(0);
for (int i = 0; i < n; i++) {
x = X[i][j];
if (! values.contains(x)){
sb.append(x+"\n");
values.add(x);
}
}
System.out.print(sb);
}
PD1。の使用を検討する場合もBitSet。O(1)アクセス パフォーマンスを備えています (最悪の場合でも衝突がないため)。範囲が 0 で始まる整数 (そうでない場合は変換が必要になる場合があります) と、可能な分布内で十分に密度の高い実際の値の母集団に最適です。
- たとえば、Unicode コードポイントの発生を確認する場合、139,264 バイトの長さの配列 (17 (プレーン) * 2 16 (コードポイント/プレーン) / 8) が必要になります。100 文字の長さで 40 の異なる文字を使用している可能性があります。テキストメッセージ、それはやり過ぎかもしれません。しかし、ISO-Latin-1 内の 256 の可能な値に制限されているとします。(8 バイトのビットセット)、それは実際には完全に適合します。
PD2。また、Assylias が言うように、HashSet の初期サイズを設定すると役立つ場合があります。として、サイズ変更がないことを確認しthreshold = (int)(capacity * loadFactor)たい場合があります。initialCapacity=(int)Math.ceil(n/0.75) その懸念はAssyliaの投稿に属しており（私は自分で使用していません）、このように議論することは不適切です.
PD3 (2015 年 9 月: 3 年後)私はたまたまこの質問を再訪し、Assylas の結果に非常に興味をそそられたので、独自のマイクロベンチマークをコーディングしました (これを含めたので、誰でも複製できます)。これらは私の結論です：
- 私が提案した
BitSet(注: 非整数および非常にまばらにパックされたディストリビューションには適合しません) 明らかに、HashSet のすべてのフレーバーよりも優れています (密にパックされたディストリビューションでは約 4 倍高速です)。
- サイズが 1000 の非常に満たされたセットのテストでは、新しいコレクションを作成する方がわずかに有利であることがわかります (7.7 インチ対 9.8 インチ)。ただし、 vsの「予行演習」では反対の結果が返されます (9.5 インチ vs 7.5 インチ)。私の推測では、リセット時にキャッシュを無効にするというペナルティがあるためです(そうでない場所を設定します)。
HashSet#clear()new HashSet()HashSet.tablenullnull
- また、事前に最適なサイズを知っていることも大きな利点です(常に実行できるとは限りません)。この
HashSet.clear()アプローチはより適応性が高く、サイズの過小評価をより適切に許容します。過大評価はそれほど大きな違いを意味するわけではありませんが、メモリが問題になる場合は良い戦略ではないかもしれません.
- この結果は、現在、オブジェクトの作成とメモリの割り当てが大きな問題ではないことを明確に示しています( Programmers.SEを参照)。ただし、オブジェクトの再利用は、考慮すべきオプションです。たとえば、drmirror で、JDK 1.6 の進化後でも、インスタンス (CharBuffer) を再利用するとパフォーマンスが 2 倍になることを確認してください。
- また、Assylias が a を使用することの影響は何だったのだろうか
loadFactor==1.0f(HashSet は までサイズ変更size > table.length*loadFactorされません。これは私が彼に提案したものとは異なりますが、衝突がなければ完璧です)。loadFactor==0.75f25% の衝突を回避する代わりに、およそ1.33 倍のテーブル スペースが必要です。私のテストでは、このシナリオのデフォルト設定の利点は示されませんでした。
これが、テストに使用したクラスです。いくつかの面でオーバーシュートし、他の面で不足している可能性がある場合は申し訳ありません（ウォームアップはありません。実装が自分のゴミを詰まらせる可能性があるように、十分に長く実行してください）。
/**
* Messing around this StackOverflow question: https://stackoverflow.com/questions/11740013/fastest-way-to-recreate-the-arraylist-in-a-for-loop/ .
* Quite surprisingly new HashSet() (which should imply actual memory initialization) is faster than HashSet.clear() in the given scenario.
* Primary goal is to test this phenomenon (new vs clear) under different scenarios.
* Secondarily a bit about the BitSet and the HashSet loadFactor is tested.
* @author Javier
*/
public class TestSetClear2 {
public static interface MicroBenchmark {
public String getName();
/**
*
* @param dataSet Data set to insert in the collection
* @param initialSize Initial size for the collection. Can try to be optimal or try to fool.
* @param iterations Number of times to go through the dataSet over and over
*/
public void run(int[] dataSet, int initialSize, int iterations);
}
/** Bad initial case. Based in question code */
public static class MBList implements MicroBenchmark {
@Override public String getName() { return "ArrayList.clear()"; }
@Override public void run(int[] data, int initialSize, int n) {
// Not taking initial size into account may result in a resizing penalty in the first iteration
// But will have an adequate size in following iterations, and wont be fooled by bad estimations.
List<Integer> values = new ArrayList<Integer>();
for (int iter = 0; iter < n; iter++) {
values.clear();
for (int i = 0; i < data.length; i++) {
int x = data[i];
if (values.contains(x)) continue;
values.add(x);
}
}
}
}
/** new HashSet(N,1) for every iteration. Reported as best by assylias. */
public static class MBNewHashSetN1 implements MicroBenchmark {
@Override public String getName() { return "new HashSet(N,1)"; }
@Override public void run(int[] data, int initialSize, int n) {
for (int iter = 0; iter < n; iter++) {
Set<Integer> values = new HashSet<>(initialSize, 1.0f); // 1.0 loadfactor optimal if no collisions.
for (int i = 0; i < data.length; i++) {
int x = data[i];
if (values.contains(x)) continue;
values.add(x);
}
}
}
}
// No need to implement raw new HashSet() (reported as worse). Will be enough fooling to initialize to 16 so it succumbs to resizing.
/** HashsetClear for every iteration. Attempted by Assylias and Javier. Clear() does not perform as well as expected under basic tests. */
public static class MBHashSetClear implements MicroBenchmark {
private float loadFactor; // Allow loadFactor to check how much 1.0 factor affects if there are collisions.
private String name;
public MBHashSetClear(float loadFactor) {
this.loadFactor = loadFactor;
name = String.format(Locale.ENGLISH, "HashSet(N,%f).clear()", loadFactor);
}
@Override public String getName() { return name; }
@Override public void run(int[] data, int initialSize, int n) {
HashSet<Integer> values = new HashSet<>((int)Math.ceil(initialSize/loadFactor), loadFactor);// Just the size for loadfactor so it wont resize.
for (int iter = 0; iter < n; iter++) {
values.clear();
for (int i = 0; i < data.length; i++) {
int x = data[i];
if (values.contains(x)) continue;
values.add(x);
}
}
}
}
/** Javier BitSet. Might clearly outperform HashSet, but only on the very specific constraints of the test (non negative integers, not hugely big). */
public static class MBBitSet implements MicroBenchmark {
@Override public String getName() { return "BitSet.clear()"; }
@Override public void run(int[] data, int distributionSize, int n) {
BitSet values = new BitSet(distributionSize);
for (int iter = 0; iter < n; iter++) {
values.clear();
for (int i = 0; i < data.length; i++) {
int x = data[i];
if (values.get(x)) continue;
values.set(x);
}
}
}
}
public static void main(String[] args) {
final MicroBenchmark mbNew = new MBNewHashSetN1();
// Create with same loadFactor as MBNewHashSetN1. So we compare apples with apples (same size of handled table, same collisions).
final MicroBenchmark mbClear = new MBHashSetClear(1.0f);
final MicroBenchmark mbClear075 = new MBHashSetClear(0.75f);
final MicroBenchmark mbBitset = new MBBitSet();
final MicroBenchmark mbList = new MBList(); // Will have a taste of O(N) with a not too bit dataset.
// warmup. trigger the cpu high performance mode? Fill the heap with garbage?
//mbNew.run(dataSetE3xE3, 1000, (int)1e5); // Using new HS might give a bit advantage?
int timePerTest = 10000;
int distributionSize, initialCapacity, datasetLength;
// 1000 long and values 0..999 (1e3 x 1e3). Optimal initial capacity
distributionSize = 1000; datasetLength = 1000; initialCapacity = 1000;
final int[] dataSetE3xE3 = generateRandomSet(1000,1000);
runBenchmark("E3xE3", dataSetE3xE3, distributionSize, timePerTest, initialCapacity,
mbNew, mbClear, mbClear075, mbBitset);
// repeat with underestimated initial size. Will incur in resizing penalty
initialCapacity = 16; // Default initial
runBenchmark("E3xE3+underSize", dataSetE3xE3, distributionSize, timePerTest, initialCapacity,
mbNew, mbClear, mbBitset);
// repeat with overestimated initial size. larger garbage and clearing.
initialCapacity = 100000; // oversized will force to handle large tables filled with 0 / null.
runBenchmark("E3xE3+overSize", dataSetE3xE3, distributionSize, timePerTest, initialCapacity,
mbNew, mbClear, mbBitset);
// Dry run (not rum). what if we focus on the new and clear operations. Just 1 item so clear() is forced to traverse the table.
datasetLength = 1; distributionSize = 1000; initialCapacity = 1000;
runBenchmark("E3xE3-DryRun", generateRandomSet(datasetLength, distributionSize),
distributionSize, timePerTest, initialCapacity,
mbNew, mbClear);
// check for * 100 and / 100 sizes.
distributionSize = datasetLength = initialCapacity = 10;
runBenchmark("E1xE1",
generateRandomSet(datasetLength, distributionSize),
distributionSize, timePerTest, initialCapacity,
mbNew, mbClear, mbList);
distributionSize = datasetLength = initialCapacity = 100000;
runBenchmark("E5xE5", generateRandomSet(datasetLength, distributionSize),
distributionSize, timePerTest, initialCapacity,
mbNew, mbClear);
// Concentrated distributions might behave as with oversized?
datasetLength=10000; distributionSize=10; initialCapacity=Math.min(datasetLength, distributionSize);
runBenchmark("E4xE1",
generateRandomSet(datasetLength, distributionSize),
distributionSize, timePerTest, initialCapacity,
mbNew, mbClear);
// Sparse distributions might allow mild collision. Also adverse for BitSet.
// TODO Generate a greater/known amount of collisions
datasetLength=10000; distributionSize=(int)1e6; initialCapacity=Math.min(datasetLength, distributionSize);
runBenchmark("E4xE6",
generateRandomSet(datasetLength, distributionSize),
distributionSize, timePerTest, initialCapacity,
mbNew, mbClear, mbClear075);
}
private static void runBenchmark(String testName, int[] dataSet, int distributionSize, int timePerTest
, int initialCapacity, MicroBenchmark ... testees /* not testes */) {
// How many iterations? Will use first testee to callibrate.
MicroBenchmark curTest = testees[0];
long t0 = System.nanoTime();
long ellapsed = 0L;
final long minToCallibrate = (long)0.5e9; // half second
int iterations = 1;
while (ellapsed < minToCallibrate) {
curTest.run(dataSet, initialCapacity, iterations);
iterations *= 2; // same as <<= 1
ellapsed = System.nanoTime() - t0;
}
// calculation is not laser-sharp precise (actually executed iterations -1, and some extra initializations).
final int nIterations = (int) ((double)iterations * timePerTest * 1e6 /* nanos/millis */ / ellapsed);
// Do actual benchmark
System.out.printf(Locale.ENGLISH, "dataset:{name=%s,length:%d,distrib:%d,capacity0:%d,iterations:%d}\n",
testName, dataSet.length, distributionSize, initialCapacity, nIterations);
for (MicroBenchmark testee : testees) {
t0 = System.nanoTime();
testee.run(dataSet, initialCapacity, nIterations);
ellapsed = System.nanoTime() - t0;
System.out.printf(Locale.ENGLISH, "%s : %5.3f\n", testee.getName(), ellapsed/1e9 );
}
}
private static int[] generateRandomSet(int lengthOfSet, int distributionSize) {
Random r = new Random();
int[] result = new int[lengthOfSet];
for (int i = 0; i < lengthOfSet; i++) {
result[i] = r.nextInt(distributionSize);
}
return result;
}
}
これが私の結果です（JDK 1.8.0_31 - 64 ビット - Windows 7 を使用）
dataset:{name=E3xE3,length:1000,distrib:1000,capacity0:1000,iterations:514241}
new HashSet(N,1) : 7.688
HashSet(N,1.000000).clear() : 9.796
HashSet(N,0.750000).clear() : 9.923
BitSet.clear() : 1.990
dataset:{name=E3xE3+underSize,length:1000,distrib:1000,capacity0:16,iterations:420572}
new HashSet(N,1) : 9.735
HashSet(N,1.000000).clear() : 6.637
BitSet.clear() : 1.611
dataset:{name=E3xE3+overSize,length:1000,distrib:1000,capacity0:100000,iterations:143032}
new HashSet(N,1) : 9.948
HashSet(N,1.000000).clear() : 10.377
BitSet.clear() : 0.447
dataset:{name=E3xE3-DryRun,length:1,distrib:1000,capacity0:1000,iterations:18511486}
new HashSet(N,1) : 9.583
HashSet(N,1.000000).clear() : 7.523
dataset:{name=E1xE1,length:10,distrib:10,capacity0:10,iterations:76177852}
new HashSet(N,1) : 9.988
HashSet(N,1.000000).clear() : 10.521
ArrayList.clear() : 7.915
dataset:{name=E5xE5,length:100000,distrib:100000,capacity0:100000,iterations:2892}
new HashSet(N,1) : 9.764
HashSet(N,1.000000).clear() : 9.615
dataset:{name=E4xE1,length:10000,distrib:10,capacity0:10,iterations:170386}
new HashSet(N,1) : 9.843
HashSet(N,1.000000).clear() : 9.708
dataset:{name=E4xE6,length:10000,distrib:1000000,capacity0:10000,iterations:36497}
new HashSet(N,1) : 9.686
HashSet(N,1.000000).clear() : 10.079
HashSet(N,0.750000).clear() : 10.008