LinkedList.contains скорость выполнения

Question

Почему метод LinkedList.contains () выполняется быстрее, чем такая реализация:

for (String s : list) 
   if (s.equals(element))
     return true;
return false;

Я не вижу большой разницы между реализацией (я считаю, что объекты поиска не равны NULL), тем же итератором и операцией equals

Answer 1

Давайте посмотрим исходный код (версия OpenJDK) java.util.LinkedList

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

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

Причиной этого будет то, что этот indexOf работает на внутренней структуре, используя прямой доступ к полю для итерации, в отличие от for-each, который использует Iterator<E>, чьи методы также должны дополнительно проверять такие вещи, как ConcurrentModificationException и т. Д.

Возвращаясь к источнику, вы обнаружите, что метод E next(), возвращаемый Iterator<E> из LinkedList, выглядит следующим образом:

private class ListItr implements ListIterator<E> {
   //...
   public E next() {
      checkForComodification();
      if (nextIndex == size)
      throw new NoSuchElementException();

      lastReturned = next;
      next = next.next;
      nextIndex++;
      return lastReturned.element;
  }
  final void checkForComodification() {
      if (modCount != expectedModCount)
         throw new ConcurrentModificationException();
  }

Это значительно "занят", чем e = e.next; в LinkedList.contains! iterator() из LinkedList на самом деле является ListIterator, который имеет более богатые возможности. Они не нужны в цикле «для каждого», но, к сожалению, вы все равно должны платить за них. Не говоря уже о том, что все эти защитные проверки для ConcurrentModificationException должны быть выполнены, даже если в список не будет внесено никаких изменений во время итерации.

---

Заключение

Так что да, итерация LinkedList в качестве клиента, использующего for-each (или, проще говоря, использование его iterator()/listIterator()) обходится дороже, чем то, что сам LinkedList может сделать внутри. Этого следовало ожидать, поэтому в первую очередь указывается contains.

Внутренняя работа дает LinkedList огромное преимущество, потому что:

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

Так что вы можете извлечь из этого? Ознакомьтесь с API! Посмотрите, какие функции уже предоставлены; скорее всего, они будут быстрее, чем если бы вам пришлось дублировать их в качестве клиента.

Answer 2

Я решил проверить это и получил интересный результат

import java.util.LinkedList;

открытый класс Содержит {

private LinkedList<String> items = new LinkedList<String>();

public Contains(){
    this.addToList();
}

private void addToList(){
    for(int i=0; i<2000; i++){
        this.items.add("ItemNumber" + i);
    }
}

public boolean forEachLoop(String searchFor){
    for(String item : items){
        if(item.equals(searchFor))
            return true;
    }

    return false;
}

public boolean containsMethod(String searchFor){
    if(items.contains(searchFor))
        return true;

    return false;
}

}

и контрольный пример JUnit:

import static org.junit.Assert.assertEquals;

import org.junit.Test;



public class ContainsTest {

    @Test
    public void testForEachLoop(){
        Contains c = new Contains();

        boolean result = c.forEachLoop("ItemNumber1758");

        assertEquals("Bug!!", true, result);
    }

    @Test
    public void testContainsMethod(){
        Contains c = new Contains();

        boolean result = c.containsMethod("ItemNumber1758");

        assertEquals("Bug!!", true, result);
    }
}

Забавно, что когда я запускаю тест JUnit, получаются следующие результаты: - testForEachLoop () - 0,014 с - testContainsMethod () - 0,025 с

Это правда или я что-то не так делаю?