March 19th, 2021

Учебник по JavaScript: ч.1, Типы данных: строки, массивы

Читаю пятый раздел («Типы данных») первой части («Язык программирования JavaScript») учебника по JavaScript.

https://learn.javascript.ru

Часть 1. Язык программирования JavaScript (в т.ч. 93 подраздела)

Разделы:

5. Типы данных (12 подразделов)

5.3 Строки
5.4 Массивы
5.5 Методы массивов

В этом разделе статьи гораздо больше по объему, чем предыдущие. Но задач по-прежнему маловато, только в подразделе «Методы массивов», наконец, дано достаточное число задач (12).

Понравилось, что в подразделе «Строки» рассказано про разные языки, в том числе при сравнении строк. Еще понравилась часть статьи про Юникод («Как всё устроено, Юникод»), там есть кое-что про суррогатные пары, диакритические знаки и нормализацию.

В русском алфавите, кстати, букв с диакритическими знаками две — это «Ё» и «Й». При этом в Юникоде, что интересно, «Й» находится в правильном месте (между буквами «И» и «К»), а буква «Ё» — нет. Заглавная «Ё» находится перед всеми заглавными русскими буквами (то есть ее код меньше кода любой русской буквы), а строчная «ё» находится после всех строчных русских букв (то есть ее код больше кода любой русской буквы). Это нужно учитывать при сравнении строк.

В подразделах про массивы понравилось несколько задач:

Подмассив наибольшей суммы:
https://learn.javascript.ru/task/maximal-subarray

Тут сложность не в том, чтобы найти подмассив с наибольшей суммой, а в том, как это сделать с наименьшими временными затратами. Сама задача интересная, а вот решение, предложенное авторами, мне не понравилось: как я понял, они просто исключили поиск подмассива наибольшей суммы в случае, когда все элементы отрицательные (по-моему, это слегка жульничество... :).

Создать расширяемый калькулятор
https://learn.javascript.ru/task/calculator-extendable

Любопытная идея. Программист получает объект, созданный функцией-конструктором «Calculator». У этого объекта есть только два метода: 1) вычислить; 2) добавить математическую операцию. Только что созданный объект не может ничего вычислить. Однако, далее программист может использовать второй метод объекта, чтобы добавлять различные математические операции в наш объект в виде дополнительных методов, тем самым как бы обучая объект математическим вычислениям. Например:

let calc = new Calculator;            // создаем калькулятор

alert( calc.calculate("3 * 7") );     // возвращает NaN, так как не умеет умножать

calc.addMethod("*", (a, b) => a * b); // обучаем умножению

alert( calc.calculate("3 * 7") );     // возвращает 21

Перемешайте массив
https://learn.javascript.ru/task/shuffle

Сложность тут не в том, чтобы просто перемешать. По условиям задачи любая из возможных смесей должна быть равновероятна. К примеру, есть массив [1, 2, 3]. Всего есть 6 вариантов перемешивания: 123, 132, 213, 231, 321, 312. Авторы задания при изложении решения дали проверочную программу, которая запускает функцию, написанную учеником, миллион раз и показывает, сколько раз выпала каждая комбинация из вышеперечисленных. При равновероятности этих комбинаций число выпадения каждой из них должно быть примерно (не точно) одинаковым.

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

function shuffle(array) {
    let temp_array = array.slice();
	
    for (let i = 0; i < array.length; i++) {
        let random_index = Math.floor(Math.random() * temp_array.length);
        array[i] = temp_array.splice(random_index, 1)[0];
    }
}

Возможно, это тот же метод, только «другими словами». Мне кажется, у меня получилось понятнее.

Сначала я создаю массив-копию (temp_array) заданного массива.

Из этого массива-копии я забираю (splice) элемент со случайным индексом (random_index, это случайное целое число из интервала от 0 включительно до array.length - 1 включительно) и помещаю этот элемент в начало исходного массива (затирая элемент, который там был).

Из оставшихся в массиве-копии элементов я снова забираю случайный и снова помещаю его в исходный массив следом за размещенным ранее (справа от него).

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

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

Вариант решения от авторов задания:
function shuffle(array) {
    for (let i = array.length - 1; i > 0; i--) {
        let j = Math.floor(Math.random() * (i + 1));
        [array[i], array[j]] = [array[j], array[i]];
    }
}
Авторы ссылаются на Тасование Фишера-Йетса.