Сложность List.reverse?

В Scala существует метод reverse для списков. В чем сложность этого метода? Лучше просто использовать исходный список и всегда помнить, что список обратный тому, что мы ожидаем, или явно использовать reverse перед его работой.

EDIT: меня действительно интересует, чтобы получить последние два элемента исходного списка (или первые два из перевернутого списка).

Итак, я бы сделал что-то вроде:

val myList = origList.reverse
val a = myList(0)
val b = myList(1)

Это не в цикле, просто одно время в моей библиотеке... но если кто-то другой использует библиотеку и помещает ее в цикл, это не под моим контролем.

Ответы

Ответ 1

Посмотрев на источник, он O(n), как вы могли бы разумно ожидать:

override def reverse: List[A] = {
  var result: List[A] = Nil
  var these = this
  while (!these.isEmpty) {
    result = these.head :: result
    these = these.tail
  }
  result
}

Если в вашем коде вы можете перебирать список в обратном порядке с одинаковой стоимостью итерации в прямом порядке, то было бы более эффективно это делать, а не изменять список.

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

В целом, хотя я бы ожидал, что все, что вы меняете в списке, означает, что вы заботитесь об относительном упорядочении нетривиального количества элементов, и поэтому все, что вы делаете, по своей сути O (n) так или иначе. (Это может быть неверно для других структур данных, таких как двоичное дерево, но списки являются линейными, и в крайнем случае даже reverse . head не может быть выполнено в O (1) раз с односвязным списком.)

Итак, если вы выбираете между двумя опциями O (n) - для большинства приложений обширного, бритье нескольких наносекунд с момента итерации не принесет вам ничего. Следовательно, было бы "лучше" сделать ваш код максимально читаемым, что означает вызов reverse, а затем повторение, если это будет ближе всего к вашему намерению.

(И если ваше приложение слишком медленное, а профилирование показывает, что манипуляция списком является точкой доступа, то вы можете подумать о том, как сделать ее более эффективной.Когда к этому моменту может быть задействован другой вариант для обоих ваших текущих кандидатов, учитывая дополнительный контекст, который у вас будет в данный момент.)