Коллекции Java содержат все поведение Weired - PullRequest
1 голос
/ 25 января 2011

У меня есть следующий код, где я использую superList и subList, я хочу проверить, что subList на самом деле является подсписком superList.

Мои объекты не реализуют методы hashCode или equals.Я создал похожую ситуацию в тесте.Когда я запускаю тест, результат показывает очень большую разницу в производительности между результатами из коллекции JDK и общих коллекций. После запуска теста я получаю следующий вывод.

Время истекло с API сбора Java 8953 MilliSeconds & Result trueВремя, прошедшее с API коллекции Commons 78 MilliSeconds & Result true

У меня вопрос, почему сборка java так медленная в обработке операции containsAll.Я что-то там не так делаю?Я не контролирую типы коллекций, которые я получаю из старого кода.Я знаю, что если я использую HashSet для superList, то получу большой прирост производительности, используя операцию JDK containsAll, но, к сожалению, это невозможно для меня.

package com.mycompany.tests;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;

import org.apache.commons.collections.CollectionUtils;
import org.junit.Before;
import org.junit.Test;

public class CollectionComparison_UnitTest {

    private Collection<MyClass> superList = new ArrayList<MyClass>();
    private Collection<MyClass> subList = new HashSet<MyClass>(50000);

    @Before
    public void setUp() throws Exception {

        for (int i = 0; i < 50000; i++) {
            MyClass myClass = new MyClass(i + "A String");
            superList.add(myClass);
        subList.add(myClass);
    }
}

@Test
public void testIt() {
    long startTime = System.currentTimeMillis();
    boolean isSubList = superList.containsAll(subList);
    System.out.println("Time Lapsed with Java Collection API "
            + (System.currentTimeMillis() - startTime)
            + " MilliSeconds & Result is " + isSubList);

    startTime = System.currentTimeMillis();
    isSubList = CollectionUtils.isSubCollection(subList, superList);
    System.out.println("Time Lapsed with Commons Collection API "
            + (System.currentTimeMillis() - startTime)
            + " MilliSeconds & Result is " + isSubList);
}

}

class MyClass {String myString;

MyClass(String myString) {
    this.myString = myString;
}

String getMyString() {
    return myString;
}

}

Ответы [ 3 ]

4 голосов
/ 25 января 2011

Различные алгоритмы:

ArrayList.containsAll() предлагает O (N * N) , а CollectionUtils.isSubCollection() предлагает O (N + N + N) .

3 голосов
/ 25 января 2011

Вы должны хотя бы попробовать тесты в обратном порядке.Ваши результаты могут очень хорошо показать, что JIT-компилятор хорошо выполняет свою работу: -)

2 голосов
/ 25 января 2011

ArrayList.containsAll наследуется от AbstractCollection.containsAll и представляет собой простой цикл, проверяющий все элементы в строке.Каждый шаг - это медленный линейный поиск.Я не знаю, как работает CollectionUtils, но нетрудно сделать это намного быстрее, чем с помощью простого цикла.Преобразование второго Списка в HashSet - это верный выигрыш.Сортировка обоих списков и параллельный просмотр их могут быть еще лучше.

РЕДАКТИРОВАТЬ:

Исходный код CollectionUtils проясняет ситуацию.Они конвертируют обе коллекции в «карты кардинальности», что является простым и общим способом для многих операций.В некоторых случаях это может быть плохой идеей, например, когда первый список пуст или очень короткий, вы фактически теряете время.В вашем случае это огромный выигрыш по сравнению с AbstractCollection.containsAll, но вы могли бы сделать еще лучше.

...