Какая большая разница между использованием содержит или цикл по списку?

Question

Производительность мудрая, действительно ли большая разница между использованием:

• ArrayList.contains (o) против foreach | итератор
• LinkedList.contains (o) против foreach | итератор

Конечно, для циклов итератора foreach | мне придется явно сравнивать методы и возвращать соответственно true или false.

Объект, который я сравниваю, является объектом, в котором equals() и hashcode() правильно переопределены.

РЕДАКТИРОВАТЬ: В конце концов, вам не нужно знать о containsValue, извините за это. И да, я глупый ... Я понял, насколько глупым был мой вопрос о «содержит ключ» и «foreach», не говоря уже об этом, я не знаю, о чем думал. Я в основном хочу знать о вышеупомянутых (отредактированных других).

Answer 1

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

С новой формой вопроса, больше не включающей HashMap и TreeMap, мой ответ совершенно другой. Я сейчас говорю нет .

Я уверен, что другие люди ответили на это, но и в LinkedList, и в ArrayList содержит () просто вызывает indexOf (), который перебирает коллекцию.

Возможно, что есть небольшие различия в производительности, как между LinkedList и ArrayList, так и между содержимым и foreach, больших различий нет.

Answer 2

Это не делает различий, поскольку содержит (o) вызовы indexOf (o), который просто зацикливается следующим образом:

for (int i = 0; i < size; i++)
    if (o.equals(elementData[i]))
       return i;

(Проверено в ArrayList)

Answer 3

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

Для 1 и 2 не нужно вызывать методы итератора.Может зацикливаться внутри.И ArrayList, и реализация LinkedList содержат в терминах indexOf

1. ArrayList - indexOf - это цикл в стиле C для резервного массива.
2. LinkedList - indexOf переходит по связанному списку в цикле for в стиле C.

Для 3 и 4 вы должны различать containsKey и containsValue.

3. HashMap , содержит ключ O (1).Это работает путем хеширования ключа, получения связанного сегмента, а затем обхода связанного списка.containsValue равно O (n) и работает, просто проверяя каждое значение в каждом сегменте во вложенном цикле for.

4. TreeMap , содержит ключ O (log n).Он проверяет, находится ли он в диапазоне, затем ищет красно-черное дерево.containsValue, которое является O (n), использует обход дерева по порядку.

Answer 4

ArrayList.contains делает

return indexOf(o) >= 0;

, где

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;
}

Это похоже на LinkedList, только он использует .next () для итерации по элементам, так что особой разницы нет.

public int indexOf(Object o) {
    int index = 0;
    if (o==null) {
        for (Entry e = header.next; e != header; e = e.next) {
            if (e.element==null)
                return index;
            index++;
        }
    } else {
        for (Entry e = header.next; e != header; e = e.next) {
            if (o.equals(e.element))
                return index;
            index++;
        }
    }
    return -1;
}

HashMap.containKey использует хеш ключа для извлечения всех ключей с этим хешем (что быстро), а затем использует равные только для этих ключей, так что есть улучшение; но containsValue () проходит через значения с for.

TreeMap.containsKey, кажется, выполняет информированный поиск, используя компаратор, чтобы найти Ключ быстрее, так что еще лучше; но свойство hasValue по-прежнему проходит через все три, пока не найдет значение.

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

Answer 5

Обход контейнера через foreach / итератор всегда O (n) раз. Поиск ArrayList / LinkedList также является O (n).

HashMap.containsKey () равно O (1) амортизировано время.

TreeMap.containsKey () - время O (log n).

И для HashMap, и для TreeMap containsValue () имеет значение O (n), но могут быть реализации, оптимизированные для containsValue (), так же быстро, как containsKey ().

Answer 6

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

Спасибо, Кришна