add()与addall()在java priorityheap中的插入

qpgpyjmq  于 2021-06-03  发布在  Hadoop
关注(0)|答案(1)|浏览(330)

我正在研究在java中在堆中添加值的各种可能性。我用的是 PriorityHeap 班级。当我注意到我的应用程序运行缓慢时,我决定看看这个。我正在添加几千个,有时甚至数百万个自定义条目(我有一个自定义类,它有3个字段:int、longwritable和text,都来自hadoop.io;这个检测代理说我的记录平均有200个字节)。
使用 addAll() 而不是 add() 方法将条目放入堆将提高性能,因为这样可以避免 heapify 操作?
我使用以下新示例尝试了不同的策略:

package Sorting;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {

private static final int HEAP_SIZE = 1000000;
private static final int BULK_LIST_SIZE = HEAP_SIZE / 10;

private static String normal;
private static String bulk;
private static String fullBulk;

public static void main(String[] args) throws IOException {
normal = "";
bulk = "";
fullBulk = "";
long time = 0;

warmup();

normal = "";
bulk = "";
fullBulk = "";

for (int i = 0; i < 100; i++) {

    // Normal add time
    System.out.println("Normal starts...");
    time = normalExecution();
    System.out.println("Normal add time " + time);

    // Bulk add time
    System.out.println("Bulk starts...");
    time = bulk();
    System.out.println("Bulk add time " + time);

    // Bulk add time with list and heap with same size
    System.out.println("Full Bulk starts...");
    time = fullBulk();
    System.out.println("Full Bulk add time " + time);
}
System.out.println(normal);
System.out.println(bulk);
System.out.println(fullBulk);

}

private static long fullBulk() {
long time;
long start;
List<Double> fullBulkList = new ArrayList<Double>(HEAP_SIZE);
PriorityQueue<Double> fullBulkHeap = new PriorityQueue<Double>(HEAP_SIZE);

start = System.nanoTime();
for (int j = 0; j < HEAP_SIZE; j++) {
    if (fullBulkList.size() == HEAP_SIZE) {
    fullBulkHeap.addAll(fullBulkList);
    fullBulkList.clear();
    }
}
fullBulkHeap.addAll(fullBulkList);
time = System.nanoTime() - start;

fullBulk = fullBulk + "\t" + time;
fullBulkList = null;
fullBulkHeap = null;
return time;
}

private static long bulk() {
long time;
long start;
List<Double> bulkList = new ArrayList<Double>(BULK_LIST_SIZE);
PriorityQueue<Double> bulkHeap = new PriorityQueue<Double>(HEAP_SIZE);
start = System.nanoTime();
for (int j = 0; j < HEAP_SIZE; j++) {
    if (bulkList.size() == BULK_LIST_SIZE) {
    bulkHeap.addAll(bulkList);
    bulkList.clear();
    }
}
bulkHeap.addAll(bulkList);
time = System.nanoTime() - start;
bulk = bulk + "\t" + time;
bulkList = null;
bulkHeap = null;
return time;
}

private static long normalExecution() {

long time;
long start;
PriorityQueue<Double> normalHeap = new PriorityQueue<Double>(HEAP_SIZE);
start = System.nanoTime();
for (int j = 0; j < HEAP_SIZE; j++) {
    normalHeap.add(Double.MAX_VALUE);
}
time = System.nanoTime() - start;
normal = normal + "\t" + time;
normalHeap = null;
return time;
}

private static void warmup() {
System.out.println("Starting warmup");
for (int i = 0; i < 1000; i++) {
    normalExecution();
    bulk();
    fullBulk();
}
for (int i = 0; i < 1000; i++) {

    bulk();
    fullBulk();
    normalExecution();
}
for (int i = 0; i < 1000; i++) {

    fullBulk();
    normalExecution();
    bulk();
}
System.out.println("Warmup finished");
}

}

结果如下:

普通add方法第11次迭代中的巨大峰值可以通过一个gc调用来解释: [GC 1347684K->31354K(1446400K), 0.0331610 secs] .
mediam值分别为16049669、783724和800276。标准偏差为3512492.89、244374.17和33344.17。

pdtvr36n

pdtvr36n1#

PriorityQueue 不重写该方法 addAll 继承自 AbstractQueue .
AbstractQueue 这个方法看起来像这样。

public boolean addAll(Collection<? extends E> c) {
    if (c == null)
        throw new NullPointerException();
    if (c == this)
        throw new IllegalArgumentException();
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

如你所见,它只是循环和调用 add .
所以我不认为 addAll 会比以前有任何进步 add .

相关问题