Блог

Главная - Вопросы по программированию - производительность scala против java для задачи «Минимальные шаги в бесконечной сетке» (закрыть)

производительность scala против java для задачи «Минимальные шаги в бесконечной сетке» (закрыть)

#java #scala

#java #scala

Вопрос:

У меня есть 2 функции, выполняющие ту же логику в Scala и Java.

Я написал решение на Scala:

 def coverPoints(A: Array[Int], B: Array[Int]): Int = {
    def diff(x1: Int, x2: Int, y1: Int, y2: Int): Int = Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2))

    @tailrec
    def coverPoints(total: Int, arr1: List[Int], arr2: List[Int]): Int =
      if (arr1.length <= 1) total else coverPoints(total   diff(arr1(0), arr1(1), arr2(0), arr2(1)), arr1.tail, arr2.tail)

    coverPoints(0, A.toList, B.toList)
  }

Но это решение срабатывает Time Limit Exceeded . Затем я написал это с помощью Java:

 private int diff(int x1, int y1, int x2, int y2) {
    return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2));
}

public int coverPoints(int[] a, int[] b) {
    if (a == null || a.length <= 1) {
        return 0;
    }
    int distant = 0;
    for (int i = 0; i < a.length - 1; i  ) {
        distant  = diff(a[i], b[i], a[i   1], b[i   1]);
    }
    return distant;
}

Но система говорит мне, что производительность кода Scala недостаточно хороша. И Java проходит проверку производительности. Как можно оптимизировать производительность этой функции Scala?

Комментарии:

1. Вероятно, потому, что версия Scala использует рекурсию и гораздо больше создания объектов, в то время как версия Java использует цикл и не создает объект при повторении цикла.

2. Но, как я знаю, компилятор scala изменит @tailrec на цикл for и list.tail не создает новый объект

3. Сейчас у меня нет времени проводить тесты, но я подозреваю, что, возможно, доступ к элементам списка по индексу происходит медленно. Можете ли вы изменить свою coverPoints версию на версию, используя сопоставление с образцом? @tailrec def coverPoints(total: Int, arr1: List[Int], arr2: List[Int]): Int = (arr1, arr2) match { case (List(_), _) => total case (x1 :: x2 :: xs, y1 :: y2 :: ys) => coverPoints(total diff(x1, x2, y1, y2), xs, ys) } . Может быть, это помогло бы 😉

4. TLE специфичен для сайтов кодирования. Какой из них вы используете? У большинства есть панель обсуждения для каждого вопроса — вы проверили там?

Ответ №1:

Я не знаю, почему вы меняете Array параметры на List параметры. Индексирование списка, arr1(1) , и получение длины списка, arr1.length , являются линейными операциями. Обе эти операции выполняются намного быстрее в массиве.

Кроме того, вам вообще не нужно выполнять рекурсию.

 def coverPoints(a: Array[Int], b: Array[Int]): Int =
  a.indices.init.fold(0){ case (acc,idx) =>
    acc   Math.max(Math.abs(a(idx) - a(idx 1)), Math.abs(b(idx) - b(idx 1)))
  }
Метки: