Во-первых, позвольте мне сказать, что, как вы используете List - в изменяемом версии - ужасно. List имеет отвратительную производительность для индексированного доступа, который вы используете много. Для индексированного доступа используйте вместо этого Vector. Или Array, так как он изменен в любом случае.
На неизменной версии вы также используете length, что является O (n) для List, на каждой итерации. Просто позвонив length один раз за пределы цикла и сохранив его, чтобы повысить производительность. Вы также можете сделать это:
List(w.head._2+1,data.length - w.last._2).min
который вроде медленно по сравнению с просто
(w.head._2+1) min (data.length - w.last._2)
И, конечно, вы должны либо изменить структуру данных в Vector или заменить data.length с чем-то присвоенной только один раз.
Теперь я вижу два способа обойти это. Один из них заключается в том, чтобы пройти по карте двумя способами и получить минимум, как и вы, а другой - пройти его только один раз, как som snytt. Для первого вам действительно нужно изменить тип на Vector.Второй будет отлично работать с List.
Начнем с первого, который ближе к тому, что вы сделали. Я вообще не стремлюсь к никакой изменчивости, как упражнение. На практике я, вероятно, использовал бы var неизменяемого Map вместо рекурсии.
def dogTimes(data: IndexedSeq[Int], typeSum: Int): Map[Int, Int] = {
import scala.annotation.tailrec
val unwantedKey = typeSum/2
val end = data.length
val halfway = end/2
@tailrec
def forward(result: Map[Int, Int], i: Int): Map[Int, Int] = {
if (i > halfway) result
else if (data(i) == unwantedKey) forward(result, i + 1)
else if (result contains data(i)) forward(result, i + 1)
else forward(result updated (data(i), i + 1), i + 1)
}
@tailrec
def backward(result: Map[Int, Int], i: Int): Map[Int, Int] = {
println(s"$i ${data(i)} $result")
if (i < halfway) result
else if (data(i) == unwantedKey) backward(result, i - 1)
else if (result contains data(i)) backward(result updated (data(i), result(data(i)) min (end - i)), i - 1)
else backward(result updated (data(i), end - i), i - 1)
}
// forward has to be computed first
val fwd = forward(Map.empty[Int, Int], 0)
val bwd = backward(fwd, end - 1)
bwd
}
Это в значительной степени функциональной версия вашего изменяемого кода - это многословная и не реально использовать любого из методов сбора, чтобы помочь работе. Его также можно упростить - например, data.length % 2 не требуется, поскольку код внутри него всегда будет работать, будь то data.length четным или нечетным. И тесты contains также можно удалить, используя getOrElse в обновлениях.
Он также возвращает стандартную карту, а не стандартную. После этого вы можете добавить значение по умолчанию.
Другим способом было бы более или менее решение som snytt, но я предпочел бы сделать его немного проще из-за того, что в этом решении не требуется min. Здесь я принимаю Seq, который будет работать для List.
def dogTimes(data: Seq[Int], typeSum: Int): Map[Int, Int] = {
import scala.annotation.tailrec
val unwantedKey = typeSum/2
val half = data.length/2 + 1
val vs = (data.view take half zip data.view.reverse).zipWithIndex
val result = vs.foldLeft(Map.empty[Int, Int]) {
case (map, ((x, y), i)) =>
val m1 = if (map.contains(x) || x == unwantedKey) map else map.updated(x, i + 1)
if (m1.contains(y) || y == unwantedKey) m1 else m1.updated(y, i + 1)
}
result
}
Я держал сома snytt-х view, но я подозреваю, что его выступление на обратном будет очень плохо для List. Это должно быть нормально для Vector, но я думаю, что удаление второго вызова view должно сделать это быстрее для List.
Отметьте, что я не использую min в этом коде, и причина проста: поскольку я перемещаюсь от самого низкого индекса к самому высокому индексу для прямого и обратного в одно и то же время, всякий раз, когда ключ находится на карте, я знайте, что он должен иметь индекс ниже или равен настоящему.
Также обратите внимание, что я выбираю half + 1 - это гарантирует, что я обработаю средний элемент в списках нечетного размера. Я не отбрасываю элементы перед их реверсированием, потому что zip всегда выбирает самый маленький размер.
Если мы решим требовать индексированные seqs, следующий, вероятно, быстрее:
def dogTimes(data: IndexedSeq[Int], typeSum: Int): Map[Int, Int] = {
import scala.annotation.tailrec
val unwantedKey = typeSum/2
val end = data.length
val halfway = end/2
val result = (0 to halfway).foldLeft(Map.empty[Int, Int]) {
case (map, i) =>
val x = data(i)
val y = data(end - i - 1)
val m1 = if (map.contains(x) || x == unwantedKey) map else map.updated(x, i + 1)
if (m1.contains(y) || y == unwantedKey) m1 else m1.updated(y, i + 1)
}
result
}
Заметим также, что я предпочитаю в обоих примерах, чтобы предотвратить нежелательный ключ от попадания в карты вместо того, чтобы удалить его впоследствии. Это может быть плохое решение, но тривиально изменить код, чтобы удалить его в конце, поэтому я решил представить вам альтернативу.
Почему вы создаете карту дважды в функциональной версии? Я имею в виду, что у вас есть карта в 'tempDogTimes', а затем вы создаете _another_ map в' dogTimes' с первого. Зачем? –
@ DanielC.Sobral Мне нужно удалить ключ типаSum/2 с карты, которая невозможна в неизменяемой карте. –
На самом деле, вы можете создать новую неизменяемую карту с переопределенным значением - это использует структурный обмен, который является целым рядом постоянных неизменных структур данных. –