Как перемещаться по массиву слева направо и справа налево?

Question

Предположим, что у меня есть императив алгоритм, который держит два индекса left и right и перемещает их слева направо и справа налево

var left = 0 
var right = array.length - 1 
while (left < right) { .... } // move left and right inside the loop 

Теперь я хотел бы написать этот алгоритм без изменяемых показателей. Как я могу это сделать? Есть ли у вас примеры таких алгоритмов? Я бы предпочел нерекурсивный подход.

Answer 1

Вы можете отобразить пары элементов между вашим списком и реверсом, затем идут слева направо через этот список пара и продолжать принимать до тех пор, как ваше условие:

val list = List(1, 2, 3, 4, 5) 
val zipped = list zip list.reverse 
val filtered = zipped takeWhile { case (a, b) => (a < b) } 

Значение filtered является List((1, 5), (2, 4)). Теперь вы можете делать все, что вам нужно с этими элементами:

val result = filtered map { 
    case (a, b) => 
    // do something with each left-right pair, e.g. sum them 
    a + b 
} 

println(result) // List(6, 6) 

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

EDIT:

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

val list = List(1, 2, 3, 4, 5) 
val zipped = list.view.zipWithIndex 
val filtered = zipped takeWhile { case (a, index) => (a < list(list.length - 1 - index)) } 

println(filtered.toList) // List((1, 0), (2, 1)) 

val result = filtered map { 
    case (elem, index) => // do something with each left-right pair, e.g. sum them 
    val (a, b) = (elem, list(list.length - 1 - index)) 
    a + b 
} 

println(result.toList) // List(6, 6) 

Answer 2

Используйте reverseIterator:

scala> val arr = Array(1,2,3,4,5) 
arr: Array[Int] = Array(1, 2, 3, 4, 5) 

scala> arr.iterator.zip(arr.reverseIterator).foreach(println) 
(1,5) 
(2,4) 
(3,3) 
(4,2) 
(5,1) 

Этой функция эффективные на IndexedSeq коллекциях, которые Array неявно конвертируется в.

Answer 3

Это действительно зависит от того, что нужно делать на каждой итерации, но вот о чем подумать.

array.foldRight(0){case (elem, index) => 
    if (index < array.length/2) { 
    /* array(index) and elem are opposite elements in the array */ 
    /* do whatever (note: requires side effects) */ 
    index+1 
    } else index // do nothing 
} // ignore result 

Поверхность: перемещайте массив только один раз и не изменяйте переменные.

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