Сравнение двух LinkedList‹String› с ListIterator по сравнению с циклом for и get(int index)

У меня есть два объекта LinkedList, которые всегда имеют одинаковый размер. Я хочу сравнить их, чтобы увидеть, идентичны ли они по содержанию. Каковы общие последствия для производительности и стиля создания ListIterator для каждого списка и использования цикла while hasNext по сравнению с использованием счетчика (int i) и итерации от 0 до linkedlist.size() с использованием linkedlist.get(i) для получения и сравнения ценности? Есть ли лучший способ, который я пропускаю?

Единственное, о чем я могу думать, так это о том, что метод ListIterator может быть лучше в том смысле, что мне будет легче заменить его другим списком Comparable позже (не то, чтобы я планировал это). Я не знаю, как они выглядят под капотом, поэтому я не уверен, как бы я сравнил их по производительности.


java comparison linked-list
person msilver    schedule 24.02.2010    source источник

Ответы (3)


arrow_upward
7
arrow_downward

Как оказалось, AbstractList.equals() (который использует LinkedList) сделает это автоматически, так что используйте это. Код:

public boolean equals(Object o) {
  if (o == this)
    return true;
  if (!(o instanceof List))
    return false;

  ListIterator<E> e1 = listIterator();
  ListIterator e2 = ((List) o).listIterator();
  while (e1.hasNext() && e2.hasNext()) {
    E o1 = e1.next();
    Object o2 = e2.next();
    if (!(o1 == null ? o2 == null : o1.equals(o2)))
      return false;
  }
  return !(e1.hasNext() || e2.hasNext());
}

Так что не изобретайте велосипед.

Последнее замечание: не используйте get(index) для перебора LinkedList. Это O(n) доступ (O(1) для ArrayList), поэтому обход LinkedList с использованием get(index) будет O(n2).

person cletus    schedule 24.02.2010
comment
Спасибо. Это похоже на то, что я использую. - person msilver; 24.02.2010
comment
Не лучше ли сразу вернуть false, когда два списка разного размера, вместо последнего условного возврата? - person Adeel Ansari; 24.02.2010
comment
Да, я думаю, что быстрая проверка размеров была бы хорошей идеей, чтобы предотвратить повторение списков разных размеров в первую очередь. Хороший улов. - person msilver; 24.02.2010

arrow_upward
5
arrow_downward

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

person Hank Gay    schedule 24.02.2010
comment
Спасибо, это имеет смысл. Я также только что понял, что пренебрег возможностью использования list1.equals(list2), который, согласно API, должен иметь ожидаемое поведение (и я предполагаю, что они реализовали его с помощью итераторов). - person msilver; 24.02.2010

arrow_upward
1
arrow_downward

get(n) для связанных списков не является постоянной операцией для классов, расширяющих AbstractSequentialList; это O(n). Из AbstractSequentialList#get(int индекс):

Эта реализация сначала получает итератор списка, указывающий на индексированный элемент (с listIterator(index)). Затем он получает элемент, используя ListIterator.next, и возвращает его.

Как правило, вы не хотите выполнять произвольный доступ к коллекциям, которые не реализуют интерфейс маркера java.util.RandomAccess.

Как правило, реализация List должна реализовывать этот интерфейс, если для типичных экземпляров класса этот цикл:

 for (int i=0, n=list.size(); i < n; i++)
     list.get(i);

работает быстрее, чем этот цикл:

 for (Iterator i=list.iterator(); i.hasNext(); )
     i.next();

Начиная с Java SE 6 реализующими классами являются ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector.

person polygenelubricants    schedule 24.02.2010