Работает ли метод ArrayList has () быстрее, если ArrayList упорядочен?

Question

Я подозреваю, что это не так. Если я хочу использовать тот факт, что список упорядочен, должен ли я реализовать свой собственный метод contains(), например, с помощью бинарного поиска? Существуют ли методы, которые предполагают , что список упорядочен?

Этот вопрос отличается от возможного дубликата, потому что другой вопрос не задает о методе contains().

Answer 1

Просто для простоты.

Если у вас есть массив [5,4,3,2,1] и вы заказываете его в [1,2,3,4,5], он разветвляется быстрее, если вы ищете 1, но поиск займет больше времени 5. Следовательно, с математической точки зрения, если вы заказываете массив, для поиска элемента внутри все равно потребуется цикл от 1 до, в худшем случае, n.

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

1. если ваш массив не слишком маленький
2. хотите избежать дополнительных затрат на сортировку для каждой новой записи в массиве
3. Вы просто хотите быстро найти объект
4. Вы знаете свойства объекта, которые ищете

Вы можете создать KeyObject, содержащий свойства, которые вы ищете, реализует equals & hashCode для него и затем сохранить ваши элементы на карте. Использование Map.containsKey (новый KeyObject (prop1, prop2)) в любом случае будет быстрее, чем зацикливание массива. Если у вас нет реального объекта, вы всегда можете создать поддельный KeyObject, заполненный ожидаемыми свойствами, чтобы проверить карту.

Answer 2

Работает ли метод ArrayList has () быстрее, если ArrayList упорядочен?

Это не так. Реализация ArrayList не знает, упорядочен ли список или нет. Так как он не знает, он не может оптимизировать в случае, когда он заказан. (И проверка исходного кода подтверждает это.)

Может ли (гипотетическая) реализация списка на основе массива знать? Я думаю «нет» по следующим причинам:

1. Без Comparator или требования, согласно которому элементы реализуют Comparable, концепция упорядочения не определена.

2. Стоимость проверки заказа списка составляет O(N). Стоимость поэтапной проверки того, что список все еще упорядочен, составляет O(1) ... но все равно один или два вызова compare при каждой операции обновления. Это значительные издержки ... для структуры данных общего назначения, которая может возникнуть в надежде на оптимизацию (всего лишь) одной операции в API.

Но это нормально. Если вы (программист) способны гарантировать (в идеале эффективными алгоритмическими средствами), что список всегда упорядочен, то вы можете использовать Collections.binarySearch ... с нулевыми дополнительными проверочными издержками в операциях обновления.

Answer 3

Нет, потому что ArrayList поддерживается массивом и внутренне вызывает метод indexOf(Object o), где выполняется последовательный поиск. Таким образом, сортировка не имеет к этому отношения. Вот исходный код:

/**
     * Returns the index of the first occurrence of the specified element
     * in this list, or -1 if this list does not contain the element.
     * More formally, returns the lowest index <tt>i</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     */
    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

Answer 4

Нет. contains использует indexOf:

public boolean contains(Object var1) {
    return this.indexOf(var1) >= 0;
}

и indexOf просто перебирают внутренний массив:

for(var2 = 0; var2 < this.size; ++var2) {
    if (var1.equals(this.elementData[var2])) {
        return var2;
    }
}

Collections.binarySearch - это то, что вы ищете:

Выполняет поиск в указанном списке указанного объекта с использованием двоичного файла алгоритм поиска. Список должен быть отсортирован в порядке возрастания в соответствии с естественным порядком его элементов (как в sort(List) метод) до совершения этого вызова. Если он не отсортирован, результаты не определены.

Акцент мой

Также рассмотрите возможность использования SortedSet, такого как TreeSet, который обеспечит более надежные гарантии того, что элементы хранятся в правильном порядке, в отличие от List, который должен полагаться на контракты с абонентами (как указано выше)

Answer 5

Использовать бинарный поиск коллекций для поиска в упорядоченном списке массивов

Collections.<T>binarySearch(List<T> list, T key)

Arraylist.contains будет рассматривать это как обычный список, и это займет столько же времени, сколько и любой неупорядоченный список O (n), тогда как сложность бинарного поиска в худшем случае будет O (logn)