Вариации для вычисления результатов из последовательностей в Scala

Вступление

Распространенный вопрос от студентов, которые являются новичками в Scala: какова разница между использованием функции карты в списках, использованием выражений и циклов foreach? Один из основных источников путаницы в отношении этого вопроса заключается в том, что выражение для языка Scala не является эквивалентом циклов for в таких языках, как Python и Java, — вместо этого, эквивалент циклов for является foreach в Scala. Это различие подчеркивает важность понимания того, что значит возвращать значения, а не полагаться на побочные эффекты для выполнения определенных вычислений. Это также помогает закрепить некоторые моменты о фиксированных и переназначаемых переменных и неизменных и изменяемых структурах данных.

Задача и ее функциональное решение

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

Мы можем вычислить два списка, сопоставляя список слов следующим образом.

Ну это все. Однако давайте сделаем это без использования различных вызовов функции map (или нескольких циклов foreach , как мы увидим ниже). Самый простой способ сделать это — сопоставить каждое слово с кортежем, содержащим длину и логическое значение, указывающее, является ли его первый символ прописным; это создает список кортежей, который мы распаковываем, чтобы получить кортеж из списков.

Ключевым моментом здесь является то, что функция map превращает слова List [String ] в List [(Int, Boolean)], то есть возвращает значение. Мы можем присвоить это значение переменной или использовать его немедленно, вызвав для него unzip , который, в свою очередь, возвращает значение Tuple2 (List [Int], List [Boolean]) .
Прежде чем двигаться дальше, давайте определим простую функцию для отображения результатов выполнения этих вычислений, которые мы будем делать различными способами (и которые все дают точно такие же результаты).

Вызывая эту функцию с результатом сопоставления и разархивирования, как указано выше, мы получаем следующий вывод.

Хорошо, теперь давайте начнем делать это трудным путем. Вместо того чтобы отображать исходный список, мы зациклим список с помощью foreach и выполним расчет побочных эффектов, который строит две результирующие последовательности. Это то, что обычно делается в нефункциональных языках с циклами for , поэтому в Scala используется foreach . Мы рассмотрим каждый из них по очереди.

Второй вариант: использовать переназначаемые, неизменяемые списки

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

Обратите внимание, что мы строим списки, добавляя их, что означает, что они выходят из цикла в обратном порядке и, следовательно, должны быть перевернуты перед отображением. Конечно, вы можете добавить к списку, создав единый список и объединяя два списка с помощью оператора ::: .

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

Третий вариант: использовать не переназначаемые, изменяемые (растущие) ListBuffers

Затем мы можем использовать ListBuffer, который представляет собой изменяемую структуру данных последовательности, которая также поддерживает операции добавления с постоянным временем. Таким образом, мы можем объявить его как val , а затем использовать метод append, чтобы изменить последовательность так, чтобы в конце у нее был новый элемент. Таким образом, переменные, относящиеся к последовательностям, не могут быть переназначены, но их значения являются изменяемыми.

Обратите внимание, что мы должны преобразовать ListBuffers в Lists для отображения вызова, чтобы иметь правильные типы в качестве аргументов этой функции.
Поскольку они могут эффективно расти (т. Е. Становиться длиннее), ListBuffers — хороший выбор для многих задач, когда нам нужно накапливать набор результатов, особенно когда мы не знаем, сколько результатов мы будем накапливать. Однако, если вы знаете количество результатов, которые вы будете накапливать, вероятно, лучше использовать массивы, как показано ниже.

Четвертый вариант: использовать не переназначаемые, изменяемые (но фиксированной длины) массивы

Обе из вышеперечисленных альтернатив, вероятно, выглядят немного странно для людей, приходящих с Java В Java вы, скорее всего, сделаете императивное решение, которое включает в себя инициализацию массивов, имеющих такую ​​же длину, что и слова, а затем, при необходимости, заполнение соответствующих индексов. Для этого используйте Array.fill ( lengthOfArray ) ( initialValue ) .

Мы просматриваем индексы и для каждого вычисляем значение и присваиваем его соответствующему индексу в соответствующем массиве. Опять же, нам нужно преобразовать результаты в списки перед вызовом display . Метод индексов делает именно то, что вы ожидаете — он дает вам индексы списка.

Проблема с вышеуказанным циклом foreach заключается в том, что он требует индексации в списки, что, как правило, является плохой идеей. Почему? Потому что для получения i-го элемента из списка требуется время, пропорциональное операциям i . Почему? Поскольку реализация для получения предмета по определенному индексу, я включает в себя снятие с головы списка, чтобы получить его хвост, а затем поиск i-1-го предмета хвоста, который требует снятия его головы и затем поиска I-2-й пункт и так далее. Итак, если вы хотите получить 10000- й элемент в списке, вам нужно выполнить 10 000 операций, чтобы получить его. Если бы в списке слов было 10 000 элементов, теперь вы можете увидеть, что вы выполняете 10000 базовых вычислений только на foreach , и для каждого элемента вы выполняете 2 * операции с индексами, чтобы получить слово с этим индексом, что означает выполнение 20 000 операций с последний индекс один.
Обратите внимание, что индексирование в Arrays — это операция с постоянным временем, поэтому нет проблем с левой стороной назначений в вышеуказанном цикле.
Вы можете подумать, что можете добиться большего успеха, сначала запомнив слово, а затем дважды его применив, например,

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

Так как этот тип паттерна довольно распространен, Scala предоставляет удобный метод для последовательностей, называемый zipWithIndex, который возвращает список оригинальных элементов в паре с их индексами.

Таким образом, мы можем создать цикл foreach для таких пар. В этих случаях удобно использовать возможности сопоставления с образцом в циклах foreach , используя сопоставление регистров для пар, как показано ниже.

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

Индексированные последовательности (векторы)

Стоит отметить, что когда вы хотите неизменную последовательность, которая позволяет эффективно индексировать, вы должны использовать Векторы.

Если у вас есть список в руках, но вы хотите многократно индексировать его, вы можете преобразовать его в вектор с помощью toIndexedSeq .

IndexedSeq — это супертип последовательностей, которые разработаны для эффективной индексации, а Vector является реализацией «поддержки» по умолчанию, когда вы вызываете toIndexedSeq в List .
Конечно, если вы когда-либо просматриваете все элементы последовательности по порядку, то списки, вероятно, будут предпочтительнее, поскольку они имеют немного меньше накладных расходов и обладают некоторыми хорошими свойствами для сопоставления с образцом в операторах сопоставления.

Использование предопределенных функций для отображения последовательности

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

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

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

Для выражений

Обратите внимание, что все предыдущие циклы были foreach , тогда как Java-программисты и Pythonistas будут использоваться для циклов. В Scala нет циклов — есть выражения . Общий вопрос: в чем разница? Что такое выражение для for и почему это не цикл for ? Разница в том, что выражение возвращает значение , поэтому, хотя foreach позволяет вам просматривать последовательность и выполнять некоторые операции с каждым элементом, выражение for позволяет вам возвращать значение для каждого элемента. Рассмотрим следующее, в котором мы получаем квадрат каждого целого числа в List [Int] .

Мы получаем результат, тогда как цикл foreach просто выполняет вычисления и ничего не возвращает.

Ключ в том, что мы вырабатываем значение для каждого элемента в выражении for . В этом случае это в основном эквивалентно использованию карты . Вот это в контексте примера бегущих слов .

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

Я думаю, что обычно лучше использовать цикл foreach для таких случаев, чтобы было ясно, что вы выполняете только побочные эффекты, такие как печать, переназначение значений переменных var или изменение изменяемых структур данных. Однако в некоторых случаях выражение for может быть более удобным, например, при работе с несколькими списками и выполнении различных операций фильтрации. Вот быстрый пример, чтобы дать представление об этом. Учитывая два списка, мы можем перечислить перекрестное произведение всех их элементов

Вы также можете фильтровать эти значения, чтобы ограничить вывод только некоторым сокращенным набором элементов inter (est.

Это намного больше, но я оставлю это здесь, поскольку использование выражений таким образом является достаточно богатой темой для нескольких постов самого по себе. Также есть подробное обсуждение этого в книге Одерского, Ложки и книги Веннера «Программирование в Scala».

Пятый вариант: используйте рекурсивную функцию

Стоит указать еще один способ построения списков длин и заглавных букв. Рекурсивные функции — это функции, которые смотрят на свои входные данные и затем либо возвращают результат для базового случая, либо вычисляют результат, а затем вызывают себя с этим результатом. Это довольно стандартная вещь, которую любят компьютерные ученые, и которая имеет тенденцию гораздо больше привыкать к функциональному программированию, чем к императивному программированию. Здесь я покажу, как выполнить ту же задачу, выполненную перед использованием рекурсии, но без подробного объяснения, поэтому либо вы уже знаете, как выполнять рекурсию, и вы можете увидеть ее в Scala для того же контекста проблемы, что и выше. или вы мало что знаете о рекурсии, но можете использовать это как пример того, как она используется для задачи, которую вы уже поняли из преимуществ, приведенных выше. Итак, в последнем случае, надеюсь, это будет полезно в сочетании с другими уроками по рекурсии.
Во-первых, нам нужно определить рекурсивную функцию, приведенную ниже. Он имеет три параметра: один для списка слов, один для уже вычисленных длин и другой для уже вычисленных заглавных букв. Он возвращает пару, у которой сначала есть список длин с одним дополнительным элементом перед ним, а затем список значений заглавных букв с одним дополнительным элементом перед ним. Предварительно добавленные элементы вычисляются из заголовка списка inputWords .

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

Чтобы получить результат, достаточно просто вызвать эту функцию с помощью нашего списка слов .

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

Вывод

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

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

Весь код из приведенных выше фрагментов собран в Github gist ListComputations.scala . Вы можете сохранить его в виде файла и запустить как « scala ListComputations.scala », чтобы просмотреть вывод и поиграть с изменениями кода.

Справка: Варианты для вычисления результатов из последовательностей в Scala от нашего партнера JCG