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

Question

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

РЕДАКТИРОВАТЬ: Что меня действительно интересует, так эточтобы получить последние два элемента исходного списка (или первые два из обращенного списка).

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

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

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

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

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

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

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

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

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