Самый быстрый способ собрать уникальные данные из списка в Java

Question

Основы моего вопроса заключаются в том, что при наличии объекта List в Java, какой самый быстрый способ вернуть коллекцию только уникальных данных?

Более конкретная версия заключается в том, чтоУ меня есть 2d ArrayList (воспринимайте его как таблицу), и я хочу пройтись по заданному индексу столбца и вернуть уникальные данные.

Вот мои текущие настройки:

public Set<Object> getDistinctColumnData( int colIndex ) { 

    //dataByIndex = List<List<Object>>

    Set<Object> colDistinctData = new HashSet<Object>( dataByIndex.size() + 1, 1f ) ;

    for( List<Object> row : dataByIndex ) { 
        colDistinctData.add( row.get( colIndex ) ) ;
    }

    return colDistinctData ; 

}

Я получил небольшой прирост производительности, когда я установил начальную емкость плюс один размер неотличимого набора и коэффициент загрузки равный 1 (я думал, что ему не нужно будет расти, пока он не достигнет 100%, и это не должнопроизойдет, даже если исходный набор уже на 100% отличается (или я ошибаюсь?)).

Есть ли более быстрый способ?

Answer 1

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

Answer 2

Вероятность дальнейшего повышения производительности (в среднем) возрастет, если вы увеличите начальную емкость HashSet еще больше. Это связано с тем, что распределение значений хеш-функции объектов в вашем списке может быть таким, чтобы коллизии были более вероятными.

Например, с учетом следующего списка, все, кроме первой вставки, приведут к коллизии, несмотря на отсутствие повторяющихся значений. (Хеш-функция Java для целых чисел является значением самого целого числа, а HashSet использует открытую адресацию и линейное зондирование в случае коллизии).

[0,10,1,2,3,4,5,6,7]

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

[0, 5, 25, 125]

В последнем примере 0 помещается в индекс 0. 5 первоначально идет в индекс 0, так как 5% размера (т. Е. 5) равно 0, поэтому затем идет в индекс 1. 125 перейдет в индекс 0, но 0 - в индекс 0, 5 для индекса 1 и 25 для индекса 2. Это означает, что после трех проверок 125 может наконец быть вставлен в индекс 3.

Если вы увеличите начальную пропускную способность, это уменьшит вероятность столкновений (в среднем) и уменьшит количество проверок, требуемых в случае столкновения (в среднем также). По умолчанию java использует коэффициент загрузки 0,75 как хороший баланс между производительностью и использованием памяти. Поэтому разделите на коэффициент нагрузки 0,75 и добавьте 1, чтобы получить хорошую начальную емкость.

Answer 3

Я думаю, что было бы намного быстрее, если бы у вас было только две уникальные коллекции.Поддерживайте свой список dataByIndex, но также поддерживайте коллекцию dataSet (Set).Когда вы вставляете в свой список dataByIndex, также помещаете в свой набор данных.Тогда просто используйте свой набор данных, где это необходимо.Набор будет сохранять уникальность по своей природе.