1

私たちはJavaデータ構造のいくつかの経験的テストを行っており、適切に説明できないいくつかの結果を得ています。

たとえば、時間要件が一定である必要があるTreeSetのlast-methodをテストしている場合、TreeSetのサイズが30000を超えると、実行時間が長くなります。treeSetの要素数をサイズごとに1000回増やしてlast-methodを実行します。次に、結果の中央値を取得しました。

関連するコードは次のとおりです。

import java.io.IOException;
import java.lang.management.ManagementFactory;
import java.lang.management.ThreadMXBean;
import java.util.ArrayList;
import java.util.Collections;
import jxl.write.WriteException;

public class TestRunner {


public void test(Testable testeCase, String outputFileName, Integer... initArgs){
    ExcelWriter excel = null;
    try {
        excel = new ExcelWriter(outputFileName);
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
    ThreadMXBean threadMxBean = ManagementFactory.getThreadMXBean();
    int measurementsPoints = 35;
    //calculate median to every dataset size

    for(int j = 0; j < measurementsPoints; j++){
        int testCount = 1000;
        long startTime; 
        long endTime; 
        //double sum = 0;
        ArrayList<Integer> results = new ArrayList<Integer>();


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

            //initialize tested data structure
            testeCase.initTestRun(initArgs);

            startTime = threadMxBean.getCurrentThreadCpuTime();
            // run tested method
            testeCase.runTestMethod();
            endTime = threadMxBean.getCurrentThreadCpuTime();

            results.add((int)(endTime - startTime));

        }
        Collections.sort(results);
        excel.addNumber(j, 5, new Double(initArgs[0]));
        excel.addNumber(j, 6, new Double(results.get(testCount / 2)));

        //increase the size of the data structure 10, 15, 20, 30, 40, 60, 80...
        if(j % 2 == 0){
            initArgs[0]  = (int)(initArgs[0]  * 1.5);
        }
        else{
            initArgs[0] = (int)(initArgs[0]  / 3 * 4);
        }


    }
    try {
        excel.write();
    } catch (WriteException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    } catch (IOException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
}

import java.util.TreeSet;


public class TreeSetLastTest implements Testable {

private TreeSet<Integer> values;



@Override
public void initTestRun(Integer... integers) {
    Integer initialCapacity = integers[0];
    values = new TreeSet<Integer>();
    for(int i = Integer.MIN_VALUE; i < Integer.MIN_VALUE + initialCapacity; i++){
        values.add(i);
    }


}

@Override
public void runTestMethod() {
    values.last();
}

}

treeSetの要素数が10〜30000要素の場合、測定された中央値は3000nsです。treeSetのサイズが120000要素に増加すると、測定された中央値は13 000 nsに増加し、要素の数が100万を超えてもそこにとどまります。それで、増加を引き起こす理由は何でしょうか、または時間単位が非常に小さいため、実際には違いは無意味です。助けてくれてありがとう。

4

1 に答える 1

4

まあ、それは答える価値があると思います。

TreeSetaがO（1）を持っているというあなたの仮定last()は誤りです。まず、ドキュメントにはこの種のことは何も記載されていません。実際、TreeSetJavaTreeMapのaは、赤黒木の実装であるaを使用して実装されています。

赤黒木はAVLツリーに似ておりO(log n)、ルックアップを保証するという点でよく知られています。つまり、ツリーがリンクリストに縮退しないようにします。基本的に、last()ルックアップはO(log n)複雑であるため、大きくなるにつれて悪化します。

おそらくキャッシングが原因でO(log n)、ベンチマークに直接表示されないページング効果でさえあるかもしれません。

これはLinkedListsや配列に似ています-理論的にはリンクリストには多くのことがありますが、実際にはリンクリストは最新のCPUで使用できる最悪のデータ構造の1つです。結局のところ、定数係数は重要であり、メモリアクセスパターンは大きな定数係数です。

于 2012-05-08T10:08:34.333 に答える