Scala native, JUnit, Leetcode

[vak]

Читаю книжку по третьей Скале, всё нравится. Но теория одно дело, а надо же инструментарий освоить. Минимальный набор практических навыков: создать проект, скомпилировать, добавить юнит тесты, протестировать. То, что для Си/Си++ решается через make/cmake/gtest, здесь делается посредством утилиты sbt.

В качестве задачки, чтобы долго не гадать, взял #1 с Leetcode. Есть такой сайт leetcode.com, где предлагается решать программистские задачки на разных языках. Полезно для самообразования, да и работодатели часто дают задания через Leetcode при отборе кандидатов. Задачи там подобраны вполне неплохие. Самая первая из них называется Two-Sum: найти в массиве пару чисел с заданной суммой. Условие смотрите здесь: https://leetcode.com/problems/two-sum/

Scala мне не всякая годится, а только native. Вообще обычно Скалу применяют на виртуальной машине JVM, или через JavaScript в веб-браузере. В моей области всё это не годится. Но есть третий способ: компиляция в native код. Ровно то что нужно (scala-native.org).

Для юнит тестов в Скале есть несколько пакетов, но native работает только JUnit. Нормальная вещь, годится. Подробности здесь: scala-native.org/en/stable/user/testing.html

Собрал я всё это дело в кучу, готовый проект выложил на Гитхабе: two-sum-native. Основная ценность в файлах конфигурации: build.sbt, project/plugins.sbt.

Само решение задачки я честно нагуглил в интернете, маленько приспособив под себя. Вот первый вариант: решение в лоб, медленное, со сложностью O(n²). Зато красивый функциональный стиль. Можно вообще в одну строчку записать, но малопонятно будет. Комментарии мои.

object Solution {
    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        // Pair each number with it's index.
        // For example: Array((2,0), (7,1), (11,2), (15,3))
        val withIndex = nums.zipWithIndex

        // Compute all the possible combinations of two elements from the array.
        val comb = withIndex.combinations(2)

        // Find an item which has a required sum of numbers.
        // The result is Option[Array[(Int, Int)]].
        val find = comb.find(_.map(_(0)).sum == target)
    
        // We've been told our input has a solution.
        // So extract it from the option.
        // We get something like: Array((2,0), (7,1))
        val res = find.get
     
        // Get indices from the result.
        // For example: Array(0, 1)
        val idx = res.map(_(1))
    
        idx
    }
}

Вот второй вариант, рекурсивный но быстрый, с линейной сложностью O(n).

    def twoSum(nums: Array[Int], target: Int): Array[Int] = {
        import scala.collection.immutable.HashMap
 
        def run(index: Int, map: HashMap[Int, Int]): Array[Int] = {
            val value = nums(index)
            map get (target - value) match {
                case Some(foundInd) => Array(foundInd, index)
                case None => run(index + 1, map + (value -> index))
            }
        }
        run(0, HashMap())
    }

Вот тесты. Данные для тестов взяты с сайта Leetcode.

import org.junit.Test
import org.junit.Assert._
        
class TwoSum {
    // Example 1:
    //       Input: nums = [2,7,11,15], target = 9
    //      Output: [0,1]
    // Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
    @Test def Example_1(): Unit = {
        val result = Solution.twoSum(Array(2, 7, 11, 15), 9)
        assertEquals(2, result.length);
        assertEquals(0, result(0));
        assertEquals(1, result(1));
    }
        
    // Example 2:
    //  Input: nums = [3,2,4], target = 6
    // Output: [1,2]
    @Test def Example_2(): Unit = {
        val result = Solution.twoSum(Array(3, 2, 4), 6)
        assertEquals(2, result.length);
        assertEquals(1, result(0));
        assertEquals(2, result(1));
    }
    
    // Example 3:
    //  Input: nums = [3,3], target = 6
    // Output: [0,1]
    @Test def Example_3(): Unit = {
        val result = Solution.twoSum(Array(3, 3), 6)
        assertEquals(2, result.length);
        assertEquals(0, result(0));
        assertEquals(1, result(1));
    }
}

Запускаем:

$ sbt test
[info] welcome to sbt 1.6.2 (Homebrew Java 19.0.1)
[info] loading settings for project two-sum-native-build from plugins.sbt ...
[info] loading project definition from ./two-sum-native/project
[info] loading settings for project two-sum-native from build.sbt ...
[info] set current project to two-sum-native (in build file:./two-sum-native/)
[info] compiling 1 Scala source to ./two-sum-native/target/scala-3.1.3/classes ...
[info] compiling 1 Scala source to ./two-sum-native/target/scala-3.1.3/test-classes ...
[info] Linking (1152 ms)
[info] Discovered 1346 classes and 8489 methods
[info] Optimizing (debug mode) (1188 ms)
[info] Generating intermediate code (1158 ms)
[info] Produced 16 files
[info] Compiling to native code (9584 ms)
[info] Linking native code (immix gc, none lto) (182 ms)
[info] Total (13302 ms)
[info] Starting process './two-sum-native/target/scala-3.1.3/two-sum-native-test-out' on port '56379'.
[info] Starting process './two-sum-native/target/scala-3.1.3/two-sum-native-test-out' on port '56381'.
[info] Test run started
[info] Test TwoSum.Example_2 started
[info] Test TwoSum.Example_1 started
[info] Test TwoSum.Example_3 started
[info] Test run finished: 0 failed, 0 ignored, 3 total, 0.002s
[info] Passed: Total 3, Failed 0, Errors 0, Passed 3
[success] Total time: 17 s, completed Dec 11, 2022, 11:10:46 PM

Надо признаться, тормозная эта тулза по самое не могу. На сборку простейшего проекта уходит 17 секунд. Тесты почему-то запускаются через TCP-сервер. Но в целом работает, больших претензий нет.

Comments

Сложность

[flamedancerii]

Я не очень понимаю, почему у оптимального решения сложность заявляется O(N)
Да, я прочитал https://leetcode.com/problems/two-sum/solutions/127810/official-solution/
Но, поиск/вставка в map/hash table тоже имеет сложность, пусть O(Log(N))
Т.е. я оцениваю сложность оптимального решения как O(N * Log(N)) плюс O(N) по памяти
А лобовой подход - O(N * N/2) => O(N2) плюс 0 по памяти
Edit:
Разобрался благодаря https://softwareengineering.stackexchange.com/questions/258509/algorithms-how-do-i-sum-on-and-onlogn-together
Большая сложность поглощает меньшую при суммировании, т.е. O(N) поглощает Log(N) и
O(N + Log(N)) == O(N)
Это то да, но все же умножение а не сложение в нашем случае,
O(N * Log(N)) != O(N)

Re: Сложность

[vak]

HashMap имеет сложность O(1). Операции вставки и поиска выполняются за одинаковое время, практически не зависящее от количества элементов N.