Установите vs List при необходимости как уникальных элементов, так и доступа по индексу

Ответ 1

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

public class MyContainer<T> {
    private final Set<T> set = new HashSet<>();
    private final List<T> list = new ArrayList<>();

    public void add(T e) {
        if (set.add(e)) {
            list.add(e);
        }
    }

    public T getRandomElement() {
        return list.get(ThreadLocalRandom.current().nextInt(list.size()));
    }
    // other methods as needed ...
}

Ответ 2

HashSet и TreeSet расширяют AbstractCollection, включая toArray(), как показано ниже:

public Object[] toArray() {
    // Estimate size of array; be prepared to see more or fewer elements
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    return it.hasNext() ? finishToArray(r, it) : r;
}

Как вы можете видеть, он отвечает за выделение пространства для массива, а также за создание объекта Iterator для копирования. Таким образом, для a Set добавление O (1), но получение случайного элемента будет O (N) из-за операции копирования элемента.

A List, с другой стороны, позволяет вам быстро получить доступ к определенному индексу в массиве поддержки, но не гарантирует уникальность. Вам нужно будет повторно реализовать add, remove и связанные с ним методы, чтобы гарантировать уникальность при вставке. Добавление уникального элемента будет O (N), но поиск будет O (1).

Таким образом, это действительно зависит от того, какая область является вашей потенциальной высокой точкой использования. Могут ли быть использованы методы добавления/удаления, а произвольный доступ используется экономно? Или это будет контейнер, для которого извлечение является самым важным, поскольку несколько элементов будут добавлены или удалены в течение всего жизненного цикла программы?

Если первый, я бы предложил использовать Set с toArray(). Если последнее, вам может быть полезно реализовать уникальный список, чтобы воспользоваться быстрым извлечением. Значительный недостаток add содержит множество краевых случаев, для которых стандартная библиотека Java проявляет большую осторожность в работе с эффективным образом. Будет ли ваша реализация соответствовать тем же стандартам?

Ответ 3

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

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

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class SetVsListTest<E> {
    private static Random random = new Random();
    private Set<E> elementSet;
    private List<E> elementList;

    public SetVsListTest() {
        elementSet = new HashSet<>();
        elementList = new ArrayList<>();
    }

    private void listAdd(E element) {
        if (elementList.indexOf(element) == -1) {
            elementList.add(element);
        }
    }

    private void setAdd(E element) {
        elementSet.add(element);
    }

    private E listGetRandom() {
        return elementList.get(random.nextInt(elementList.size()));
    }

    @SuppressWarnings("unchecked")
    private E setGetRandom() {
        return (E) elementSet.toArray()[random.nextInt(elementSet.size())];
    }

    public static void main(String[] args) {
        SetVsListTest<Integer> test;
        List<Integer> testData = new ArrayList<>();
        int testDataSize = 100_000;
        int[] addToRetrieveRatios = new int[] { 10, 100, 1000, 10000 };

        for (int i = 0; i < testDataSize; i++) {
            /*
             * Add 1/5 of the total possible number of elements so that we will
             * have (on average) 5 duplicates of each number. Adjust this to
             * whatever is most realistic
             */
            testData.add(random.nextInt(testDataSize / 5));
        }

        for (int addToRetrieveRatio : addToRetrieveRatios) {
            /*
             * Test the list method
             */
            test = new SetVsListTest<>();
            long t1 = System.nanoTime();
            for(int i=0;i<testDataSize; i++) {
                // Use == 1 here because we don't want to get from an empty collection
                if(i%addToRetrieveRatio == 1) {
                    test.listGetRandom();
                } else {
                    test.listAdd(testData.get(i));
                }
            }
            long t2 = System.nanoTime();
            System.out.println(((t2-t1)/1000000L)+" ms for list method with add/retrieve ratio "+addToRetrieveRatio);

            /*
             * Test the set method
             */
            test = new SetVsListTest<>();
            t1 = System.nanoTime();
            for(int i=0;i<testDataSize; i++) {
                // Use == 1 here because we don't want to get from an empty collection
                if(i%addToRetrieveRatio == 1) {
                    test.setGetRandom();
                } else {
                    test.setAdd(testData.get(i));
                }
            }
            t2 = System.nanoTime();
            System.out.println(((t2-t1)/1000000L)+" ms for set method with add/retrieve ratio "+addToRetrieveRatio);
        }
    }
}

Выход на моей машине:

819 ms for list method with add/retrieve ratio 10
1204 ms for set method with add/retrieve ratio 10
1547 ms for list method with add/retrieve ratio 100
133 ms for set method with add/retrieve ratio 100
1571 ms for list method with add/retrieve ratio 1000
23 ms for set method with add/retrieve ratio 1000
1542 ms for list method with add/retrieve ratio 10000
5 ms for set method with add/retrieve ratio 10000

Ответ 4

Вы можете расширить HashSet и отслеживать изменения в нем, поддерживая текущий массив всех записей.

Здесь я сохраняю копию массива и настраиваю его каждый раз, когда изменяется набор. Для более надежного (но более дорогостоящего) решения вы можете использовать toArray в своем методе pick.

class PickableSet<T> extends HashSet<T> {
    private T[] asArray = (T[]) this.toArray();

    private void dirty() {
        asArray = (T[]) this.toArray();
    }

    public T pick(int which) {
        return asArray[which];
    }

    @Override
    public boolean add(T t) {
        boolean added = super.add(t);
        dirty();
        return added;
    }

    @Override
    public boolean remove(Object o) {
        boolean removed = super.remove(o);
        dirty();
        return removed;
    }
}

Обратите внимание, что это не будет распознавать изменения в наборе, если их удалить с помощью Iterator - вам придется обращаться с этим другим способом.

Ответ 5

Итак, мой вопрос в том, какой способ был бы более эффективным?

Довольно сложный вопрос для ответа в зависимости от того, что делает больше, вставлять или выбирать наугад?

Нам нужно посмотреть Big O для каждой из операций. В данном случае (лучшие случаи):

• Установить: Вставить O (1)
• Set: toArray O (n) (предположим)
• Массив: доступ O (1)

против

• Список: содержит O (n)
• Список: Вставить O (1)
• Список: Доступ O (1)

Итак:

• Set: Insert: O (1), Access O (n)
• Список: Вставка: O (n), Доступ O (1)

Таким образом, в лучшем случае они очень многозначительны с установкой выигрыша, если вы вставляете больше, чем вы выбираете, и List, если верно обратное.

Теперь злой ответ - выберите один (тот, который лучше всего представляет проблему (так что установите IMO)), оберните его и запустите с ним. Если он слишком медленный, тогда общайтесь с ним позже, и когда вы справитесь с ним, посмотрите на проблемное пространство. Часто ли ваши данные меняются? Нет, кешируйте массив.

Ответ 6

Это зависит от того, что вы цените больше.

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

Set реализация в Java в основном использует массив, метод hashCode и метод equals. Таким образом, набор больше налогов, когда вы хотите вставить, но список козырей, когда дело доходит до поиска элемента. Поскольку набор не гарантирует порядок элементов в структуре, вы не сможете получить элемент по индексу. Вы можете использовать упорядоченный набор, но это приводит к задержке вставки из-за сортировки.

Если вы собираетесь работать с индексами напрямую, вам может понадобиться использовать List, потому что порядок, в который элемент будет помещен в Set.toArray(), изменяется при добавлении элементов в Set.

Надеюсь, что это поможет:)