Как эффективно преобразовать многомерную коллекцию 2 разных типов в многомерный список - PullRequest
Новая
       39

Как эффективно преобразовать многомерную коллекцию 2 разных типов в многомерный список

1 голос
/ 27 января 2020

У меня есть следующий HashSet, который должен иметь TreeSets в качестве элементов: 

HashSet<TreeSet<Integer>> hash=new HashSet<TreeSet<Integer>>();

Я хочу иметь возможность хранить упорядоченные элементы в TreeSet, порядок также важен, следовательно, выбор TreeSet. Эти элементы сами должны быть упорядочены, но не обязательно отсортированы. Но я должен вернуть: 

List<List<Integer>>

Какой самый эффективный способ преобразовать мои га sh в список из списка целых чисел с точки зрения производительности?

Спасибо

Ответы [ 2 ]

4 голосов
/ 27 января 2020

Для эффективного способа вы должны проверить их, используя JMH . Я могу дать вам метод конвертации, но он также должен работать:

У вас обычный старый java l oop, например: 

HashSet<TreeSet<Integer>> hash=new HashSet<TreeSet<Integer>>(); 
List<List<Integer>> list = new ArrayList<>(hash.size());
for (Set<Integer> a : hash) {
  list.add(new ArrayList<>(a));
}

Это займет O(n²) .

И у вас есть тот, который использует Stream, который также O(n²): 

hash.stream()
    .map(ArrayList::new)
    .collect(toList());

Разница во второй версии заключается в том, что вы можете в конечном итоге распараллелить Stream, используя parallelStream(): здесь вы можете повысить производительность (но вам все равно придется тестировать с использованием JMH).

2 голосов
/ 15 февраля 2020

Вам все еще нужно перебрать коллекцию и преобразовать внутренние наборы в списки. Хотя, если производительность имеет наибольшее значение, рассмотрите возможность использования сторонних библиотек, которые обеспечивают некоторую оптимизацию.

1. Тесты

Я написал несколько простых тестов, используя JMH, чтобы сравнить их с ванильным java решением: 

public class Set2ListTest {

    private static final int SMALL_SET_SIZE = 10;
    private static final int LARGE_SET_SIZE = 1000;

    public static void main(String[] args) throws RunnerException {
        Options options = new OptionsBuilder()
                .include(Set2ListTest.class.getSimpleName())
                .forks(1)
                .threads(8)
                .warmupIterations(1)
                .measurementIterations(1)
                .build();
        new Runner(options).run();
    }

    @State(Scope.Benchmark)
    public static class Provider {

        Set<Set<Integer>> smallSet = new HashSet<>(SMALL_SET_SIZE);
        Set<Set<Integer>> largeSet = new HashSet<>(LARGE_SET_SIZE);

        @Setup
        public void setup() {
            fillSet(smallSet, SMALL_SET_SIZE);
            fillSet(largeSet, LARGE_SET_SIZE);
        }

        private void fillSet(Set<Set<Integer>> set, int count) {
            Random random = new Random();
            for (int i = 0; i < count; i++) {
                Set<Integer> innerSet = new TreeSet<>();
                for (int j = 0; j < count; j++) {
                    innerSet.add(random.nextInt(Integer.MAX_VALUE));
                }
                set.add(innerSet);
            }
        }

    }

    @Benchmark
    public void small_plainJava(Provider provider, Blackhole blackhole) {
        List<List<Integer>> list = new ArrayList<>(SMALL_SET_SIZE);
        for (Set<Integer> set : provider.smallSet) {
            list.add(new ArrayList<>(set));
        }
        blackhole.consume(list);
    }

    @Benchmark
    public void large_plainJava(Provider provider, Blackhole blackhole) {
        List<List<Integer>> list = new ArrayList<>(LARGE_SET_SIZE);
        for (Set<Integer> set : provider.largeSet) {
            list.add(new ArrayList<>(set));
        }
        blackhole.consume(list);
    }

    @Benchmark
    public void small_guava(Provider provider, Blackhole blackhole) {
        List<List<Integer>> list = new ArrayList<>(SMALL_SET_SIZE);
        for (Set<Integer> set : provider.smallSet) {
            list.add(com.google.common.collect.Lists.newArrayList(set));
        }
        blackhole.consume(list);
    }

    @Benchmark
    public void large_guava(Provider provider, Blackhole blackhole) {
        List<List<Integer>> list = new ArrayList<>(LARGE_SET_SIZE);
        for (Set<Integer> set : provider.largeSet) {
            list.add(com.google.common.collect.Lists.newArrayList(set));
        }
        blackhole.consume(list);
    }

    @Benchmark
    public void small_commons(Provider provider, Blackhole blackhole) {
        List<List<Integer>> list = new ArrayList<>(SMALL_SET_SIZE);
        for (Set<Integer> set : provider.smallSet) {
            List<Integer> innerList = new ArrayList<>(SMALL_SET_SIZE);
            CollectionUtils.addAll(innerList, set);
            list.add(innerList);
        }
        blackhole.consume(list);
    }

    @Benchmark
    public void large_commons(Provider provider, Blackhole blackhole) {
        List<List<Integer>> list = new ArrayList<>(LARGE_SET_SIZE);
        for (Set<Integer> set : provider.largeSet) {
            List<Integer> innerList = new ArrayList<>(LARGE_SET_SIZE);
            CollectionUtils.addAll(innerList, set);
            list.add(innerList);
        }
        blackhole.consume(list);
    }

    @Benchmark
    public void small_eclipse(Provider provider, Blackhole blackhole) {
        List<List<Integer>> list = FastList.newList();
        for (Set<Integer> set : provider.smallSet) {
            list.add(FastList.newList(set));
        }
        blackhole.consume(list);
    }

    @Benchmark
    public void large_eclipse(Provider provider, Blackhole blackhole) {
        List<List<Integer>> list = FastList.newList();
        for (Set<Integer> set : provider.largeSet) {
            list.add(FastList.newList(set));
        }
        blackhole.consume(list);
    }

}

2. Результаты

Результаты следующие: 

Benchmark                      Mode  Cnt        Score   Error  Units
Set2ListTest.large_commons    thrpt           183.205          ops/s
Set2ListTest.large_eclipse    thrpt           219.068          ops/s
Set2ListTest.large_guava      thrpt           178.478          ops/s
Set2ListTest.large_plainJava  thrpt           148.058          ops/s
Set2ListTest.small_commons    thrpt       2140560.198          ops/s
Set2ListTest.small_eclipse    thrpt       2619862.935          ops/s
Set2ListTest.small_guava      thrpt       2720692.868          ops/s
Set2ListTest.small_plainJava  thrpt       2472748.566          ops/s

3. Обсуждение

Для измерения производительности использовались два различных размера Set с: 10 наборов размера 10 (100 элементов) и 1000 наборов из 1000 элементов (1 000 000 элементов).

Для небольших Set коллекции Eclipse превзошли другие инструменты. Обычное java кажется самым медленным решением.

В случае больших Set гуава дает наилучшие результаты.

Очевидно, что размер коллекций имеет большой влияет на производительность и может повлиять на лучший выбор среди этих библиотек. Я не знаю размер ваших данных, но моя цель не дать вам лучшую библиотеку коллекций, а дать вам инструмент для ее поиска.

4. Дополнительные примечания

Я не считаю себя специалистом в какой-либо из структур коллекций, и, возможно, есть лучший способ их использования.

Если эти результаты не являются удовлетворительными, вы можете использовать примитивные наборы, чтобы выделять гораздо меньше памяти. Это приведет к значительному увеличению производительности.

Обратите внимание, что если вы хотите поэкспериментировать с предоставленными тестами, важно сравнить реализации друг с другом, а не с результатами, которые я получил, потому что это может быть аппаратным.

...