Новый язык выбора

Я начал использовать Kotlin для соревновательного программирования несколько месяцев назад. Я наконец могу наслаждаться процессом решения проблем, не теряясь в синтаксисе или настройке. Я пишу эту статью, чтобы вдохновить вас попробовать Kotlin и в соревновательном программировании.

Если вы уже воодушевлены, вам следует вместо этого почитать эту статью:



Настройка рабочего процесса для соревновательного программирования на Kotlin
Начните за считанные минуты! blog.kotlin-academy.com



У сотрудников JetBrains действительно есть страница, посвященная Kotlin для соревновательного программирования; но мне кажется, что содержание этой страницы немного продвинуто, особенно для людей, которые только начинают. Надеюсь, эта статья может послужить более мягким введением.

Я разбил эту статью на два раздела:

  1. Вначале я поделюсь некоторыми примерами решений, которые я написал на Kotlin. Я выбрал эти примеры, чтобы охватить несколько различных функций Kotlin, которые я считаю очень полезными.
  2. Во втором я подробно расскажу, как Kotlin сравнивается с другими популярными языками, используемыми в соревновательном программировании.

Примеры

Давайте нырнем!

Пример 1: Дети с наибольшим количеством конфет

Если вам нужно обратиться к исходной постановке проблемы, вот ссылка:



Дети с наибольшим количеством конфет - LeetCode
Учитывая массив конфет и целое число extraCandies, где candy [i] представляет количество конфет, которое ребенок… leetcode.com



Входные данные для каждого тестового примера:

  1. Массив целых чисел, обозначающий количество конфет, которые есть у каждого ребенка.
  2. Целое число, обозначающее количество дополнительных конфет.

Проблема сводится к следующему: для каждого ребенка вам нужно определить, даст ли ребенку все дополнительные леденцы наибольшее количество конфет в группе. Нам нужно вывести массив логических выражений. Сигнатура функции:

fun kidsWithCandies(candies: IntArray, extraCandies: Int): BooleanArray

В Kotlin мы можем решить эту проблему двумя строками:

fun kidsWithCandies(candies: IntArray, extraCandies: Int): BooleanArray {
    val maxCandies = candies.max()

    return BooleanArray(
        candies.size,
        { index -> candies[index] + extraCandies >= maxCandies!! }
    )
}

В последней строке происходит вся магия:

return BooleanArray(
    candies.size,
    { index -> candies[index] + extraCandies >= maxCandies!! }
)

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

BooleanArray(size: Int, init: (Int) -> Boolean)

Первым аргументом конструктора является размер массива - в данном случае candies.size. Второй аргумент - это функция init с типом (Int) -> Boolean - она ​​принимает Int (индекс) и выводит Boolean (значение для заполнения в этом индексе). Во втором аргументе мы можем инкапсулировать абсолютно любую логику инициализации, какую захотим.

Обратите внимание, насколько это удобно… Kotlin дает нам возможность элегантно создавать и любой массив с помощью одной строчки кода!

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

Передача конечных лямбда-выражений - … если последний параметр функции является функцией, то лямбда-выражение, переданное в качестве соответствующего аргумента, можно поместить за скобки.

Итак, мы можем упростить это:

return BooleanArray(candies.size) { index ->
    candies[index] + extraCandies >= maxCandies!!
}

Неявное имя одного параметра - «Очень часто лямбда-выражение имеет только один параметр… Параметр будет неявно объявлен под именем it '

Итак, мы можем еще больше упростить это:

return BooleanArray(candies.size) {
    candies[it] + extraCandies >= maxCandies!!
}

Это последний код. Уделите несколько секунд тому, чтобы понять и усвоить синтаксис.

fun kidsWithCandies(candies: IntArray, extraCandies: Int): BooleanArray {
    val maxCandies = candies.max()

    return BooleanArray(candies.size) {
        candies[it] + extraCandies >= maxCandies!!
    }
}

Пример 2: повар и контроль цен

Вот ссылка на проблему:



Страница конкурса | CodeChef
CodeChef - платформа для начинающих программистов CodeChef был создан как платформа, чтобы помочь программистам добиться успеха в… www.codechef.com



Вход:

  1. Массив целых чисел, обозначающий исходные цены продажи набора товаров.
  2. Целое число, обозначающее новый потолок цен, который должен применяться ко всем товарам.

Нам необходимо подсчитать общие потери из-за введения потолка цен. Проблема сводится к следующему: для каждого товара, если потолок ниже исходной цены, нам нужно вычислить разницу между исходной ценой и потолком цены, а затем вывести сумму этих значений:

fun solve(prices: IntArray, priceCeiling: Int): Int

Это однострочное решение:

fun solve(prices: IntArray, priceCeiling: Int): Int {
    return prices.fold(0) { agg, e ->
        agg + (e- minOf(priceCeiling, e))
    }
}

Функция fold позволяет агрегировать значения в массиве; fold выполняет итерацию по массиву и применяет предоставленную функцию к агрегированному значению agg и следующему элементу e. Первый аргумент fold - это то, чем инициализируется агрегированное значение - в данном случае 0.

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

Пример 3: Середина связанного списка

Нулевые значения играют важную роль во многих структурах данных. Например, в двоичном дереве, когда узел не имеет левого / правого дочернего элемента, значение атрибута _18 _ / _ 19_ node устанавливается равным нулю. Точно так же вы знаете, что достигли последнего узла связанного списка, когда следующий узел имеет нулевое значение.

Иногда у людей возникает ощущение, что в Котлине нет нулей. Но это не так. Kotlin требует только, чтобы вы явно указали нули в вашей программе. В официальной документации Kotlin о нулевой безопасности говорится:

Система типов Kotlin направлена ​​на устранение опасности нулевых ссылок из кода.

Всякий раз, когда вы назначаете переменную выражению, которое может быть нулевым, тип переменной должен быть допускающим значение NULL:

>>> val x = 3
>>> var y: Int = if (x>2) x else null
error: null can not be a value of a non-null type Int
>>> var y: Int? = if (x>2) x else null
>>> print(y)
3

Здесь Int? - это версия Int, допускающая значение NULL.

Также есть способы удалить из вашей программы нулевые значения. Один из таких способов - использовать оператор elvis, обозначенный ?::

>>> var z: Int = y ?: 0
>>> print(z)
3

Обратите внимание, что, несмотря на то, что y имеет тип Int?, допускающий значение NULL, z имеет тип Int. Как объяснено в документах:

Оператор Элвиса - Если выражение слева от ?: не равно нулю, оператор элвиса возвращает его, в противном случае оно возвращает выражение справа. Обратите внимание, что выражение в правой части оценивается только в том случае, если левая часть равна нулю .

На самом деле, правая часть ?: не обязательно должна быть выражением, и вам также не нужно назначать переменную:

>>> y ?: print("y is null")
3
>>> y = null
>>> y ?: print("y is null")
y is null

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



Середина связанного списка - LeetCode
Повысьте свои навыки программирования и быстро получите работу. Это лучшее место, чтобы расширить свои знания и подготовиться… leetcode.com



Нам нужно вернуть средний узел односвязного списка с учетом заголовка. Нам также предоставляется этот стартовый код:

class ListNode(var value: Int) {
    var next: ListNode? = null
}

Свойство next имеет тип, допускающий значение NULL. Это потому, что для последнего узла next должно быть нулевым.

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

Мы инициализируем медленный указатель на первом узле, а быстрый - на втором:

fun middleNode(head: ListNode?): ListNode? {
    var slow = head
    var fast = head?.next ?: return head
    // TODO...
}

Мы должны сделать «безопасный вызов» с помощью head?.next, а не просто head.next, потому что head может иметь значение NULL (это тип, допускающий значение NULL); но не беспокойтесь об этом слишком сильно - Intellisense предложит вам внести это изменение автоматически. Важно отметить, как мы используем оператор elvis. Если после head узла нет, мы знаем, что у нас есть связанный список первого размера, и можем просто вернуть head.

Для всех остальных неугловых случаев у нас есть цикл while:

fun middleNode(head: ListNode?): ListNode? {
    var slow = head
    var fast = head?.next ?: return head
    while(true) {
        slow = slow?.next
        fast = fast.next?.next ?: return slow
    }
}

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

Найдите минутку, чтобы понять и усвоить приведенный выше синтаксис.

Котлин против других языков

Теперь, когда мы рассмотрели несколько примеров, давайте более подробно обсудим, как Kotlin сравнивается с другими языками, обычно используемыми в соревновательном программировании.

Котлин против Java

Kotlin по сути является улучшением Java. Он работает на JVM точно так же, как Java, но расширяет многие классы Java, особенно библиотеку Java Collections, и устраняет необходимость в большом стандартном коде.

Рассмотрим, например, Java ArrayList<Integer>. Каждый раз, когда вы хотите добавить int к ArrayList, вам сначала нужно преобразовать его в объект Integer. Это особенно неприятно, когда вы находитесь в середине конкурса.

Kotlin, с другой стороны, имеет очень простую в использовании систему массивов. Для каждого массива примитивных типов есть встроенный класс, а также параметризованный тип Array<T>, и все они поставляются полностью загруженными функциями удобства и расширения, как мы видели в примерах.

Для более полного сравнения вы можете обратиться к этой странице официального сайта.

Котлин против Python

Все мы знаем фундаментальную проблему использования Python для соревновательного программирования - это очень медленно. Поскольку он не компилируется в исполняемый файл, он запускается построчно (это то, что люди имеют в виду, когда говорят, что Python является «интерпретируемым» языком). Это вызывает очень большие накладные расходы на производительность. Код Kotlin компилируется и запускается в JVM, поэтому он работает намного быстрее.

Но мы не используем Python, потому что он быстрый; мы используем его, потому что его легко писать. "Это в основном английский!" мы говорим. Что ж, я надеюсь, что примеры убедили вас в том, что синтаксис Kotlin довольно интуитивно понятен и похож на английский. Что еще более важно, Kotlin удается делать это, будучи типобезопасным (в отличие от Python, где вы часто будете ломать голову, задаваясь вопросом, принимала ли написанная вами функция список или кортеж в качестве аргумента).

Котлин против C ++

Я знаю, что C ++ сильно изменился за последние годы, и его синтаксис стал намного выразительнее. Несмотря на это, я бы посоветовал Kotlin иметь по крайней мере два явных преимущества перед C ++:

  1. Функциональный синтаксис Kotlin исключительно элегантен. Судя по тому, что я нашел в Интернете, он намного превосходит C ++.
  2. В Kotlin есть REPL (как и в консоли Python)! Вы можете использовать его для быстрого тестирования фрагментов кода. В C ++ это просто невозможно без создания исполняемого файла или запуска отладчика.

Котлин против C ++: производительность

Можно с уверенностью сказать, что если вы ищете чистую скорость, на данный момент нет лучшего варианта, чем C ++. После того, как вы преодолеете начальную кривую обучения и начнете бороться за несколько лучших мест в соревнованиях, вы должны перейти на C ++.

Основная причина того, что C ++ так быстр, заключается в том, что он компилируется в исполняемый файл, который является «родным» для системы. Поэтому, если ваш онлайн-судья запускает ваш код C ++ на сервере Linux, этот код компилируется, а затем запускается самим Linux (поэтому Windows и Linux поставляются с разными компиляторами C ++ - MSVC и g ++ соответственно). Kotlin, с другой стороны, компилирует код до уровня JVM (которая работает поверх ОС). JVM вводят абстракции, позволяющие запускать один и тот же код Java в любой ОС; К сожалению для нас, эти абстракции вызывают накладные расходы на производительность.

Но это может измениться в будущем. Существует набор компиляторов Kotlin / Native, которые компилируют код Kotlin в исполняемый файл ОС. В настоящее время существуют компиляторы Kotlin / Native для Windows, Mac и Linux! К сожалению, почти все онлайн-судьи запускают код Kotlin в JVM. Если это изменится в будущем, Kotlin станет действительно сопоставимым с C ++ в конкурентном программировании… даже для профессионалов!

Заключение

Я надеюсь, что эта статья вдохновила вас начать соревновательное программирование на Kotlin. Для начала предлагаю вам прочитать эту статью:



Настройка рабочего процесса для соревновательного программирования на Kotlin
Начните за считанные минуты! blog.kotlin-academy.com