Учим строки

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

Что вообще есть в скоупе строк?

- Кавычки. Три варианта: "str", 'str', интерполяция. Третий - для шаблонных строк.
- Спецсимволы. Всегда экранируются \. Перевод каретки, кавычки внутри строк, знак экранирования и т.д.
- Длина строки. Свойство length.
- Доступ к символам.
str[Index: int] -> char | undefined
str.charAt(index: int) -> char | ""
- Перебор (без преобразования в массив): for...of
- Иммутабельность. Строки нельзя мутировать - можно только заменять, как массивы в Реакте.
- Работа с регистром (капслок): toLowerCase, toUpperCase.

- Поиск подстроки:
- IndexOf и lastIndexOf. Принимает искомую подстроку и начальный индекс, возвращает индекс первого символа (включая 0, который неявно приводится к false) найденной подстроки или -1. Может работать в цикле. Первый ищет с начала строки, второй - с конца.

indexOf(target: string, startIndex: int) -> int | -1
lastIndexOf(target: string, position: int) -> int | -1
~str.indexOf(…) -> -int | 0 // побитовый трюк для легаси-кода

- includes, startsWith, endsWith
Сигнатурно аналогичны indexOf. Возвращают булево значение в зависимости, найдено совпадение или нет.

Получение подстроки. Возвращает результат поиска.

- slice(start: int, end: int) -> string | ""
возвращает подстроку, включая start, но не включая end. Может принимать отрицательные числа для поиска с конца.

- substring(start: int, end: int) -> string | ""
возвращает подстроку между start и end. Не понимает отрицательных чисел.

- substr(start: int, length: int) -> string | ""
принимает начальный индекс и длину искомого отрезка. Умеет искать с конца (отрицательный индекс).

- Триммер: trim(). Удаляет пробелы по обе стороны строки.
- Повторитель: repeat(count). Повторяет строку count раз.

Бонус: иллюстрация работы метода slice :)

What's next?

Нет ничего плохого, чтобы не знать чего-либо. Что действительно плохо - не стремиться учиться и не осознавать слабых сторон в своих знаниях.

Вот что я хочу освежить, дополнить или изучить в этом году:

- Тестирование. Jest, разные виды тестирования компонентов и сопутствующих систем. TDD.
- Бандлинг. Webpack и аналоги.
- Typescript. Узнать его глубже. Дженерики и другие сложные элементы типизации. Разработка от интерфейсов.
- Верстка. Словить тренды, вспомнить старое.
- Middleware. Танки, саги, вот это всё.
- Авторизация. JWT и подобное.
- Архитектура. Чтобы делать проекты с нуля, руководить их разработкой, общаться с бизнесом.
- UI/UX. Чтобы аргументированно общаться с дизайнерами.
- Ну и пару книг об искусстве переговоров.

Список неполон, но это и не обязательно. Во фронте вообще планы должны быть гибкими :)

Аgile. От хаоса к решению.

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

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

Цикл повторяется, масштабируясь до отдельных фич.
Таким образом команды вступают в борьбу с хаосом - с неопределенностью, непониманием, расплывчатыми перспективами - и приходят к четким решениям.

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

Помогает, кстати, во всех областях жизни, где присутствует хаос.

Учим относительные единицы по эджайлу

Изучим относительные единицы измерения по методике работы с хаосом.

Шаг 1. Бизнес-задача: изучить востребованную на рынке часть modern CSS - относительные единицы: em, rem и другие.

Шаг 2. Поставим вопросы:

- Что это?
- Какие задачи решает?
- В чём выгода использования?
- Как использовать?

Шаг 3. Ответы, кейсы.
Это относительные единицы размерности:
Em - emphemeral unit,
rem - root em,
vh - viewport height,
vw - viewport width.

Используется для адаптивной / мобильной верстки.
Облегчает адаптивную верстку. Параметры, указанные в этих единицах, управляются от размера шрифта. Таким образом, передавая только размер шрифта таким элементам, мы управляем, например, их отступами и размерами. Rem - облегчает управление глобальной размерностью шрифтов для лучшей доступности контента.

Шаг 4. Детали реализации. Эти единицы устанавливаются относительно некоего абсолютного указателя - размерности шрифта или размера viewport:
Установленная браузером по умолчанию (16px) (em)
Унаследованная от родительского блока (em)
Переданная напрямую (em)
Унаследованная от переменной :root (rem)
Установленная реальной шириной экрана (vw)
...высотой (vh)

Книга “Css для профи“ советует:
“Если сомневаетесь, используйте rem для размера шрифта, пиксели - для border-ов, а em - для большинства других свойств”.

Простейший кейс с em: https://codepen.io/gretten/pen/dyRdWQK

Задача выполнена. Остальное - вопрос опыта.

Собеседования. Личный опыт.

Что я понял за множество собеседований.

1. Я задавал вопросы о проектах и компаниях ради самих вопросов. Я гуглил их и задавал, не осмысляя и не рефлексируя, исходя из того, что компании хотят видеть заинтересованность. Это была ошибка. Я понял, что нужно задавать вопросы, исходя из реальных перспектив.

Что я начал спрашивать:
- Какая часть проекта уже сделана. Это нужно, чтобы понять объем легаси на проекте и готова ли архитектура.
- Из кого состоит команда. Хочешь быть архитектором, верстальщиком, дизайнером и фронтом в одном лице? Это круто, но может жопа порваться. Нужно понимать ожидания компании от тебя.
- Какие технологии юзают - и будут юзать - на конкретном твоем проекте. Успеешь подтянуть не наугад.
- Как в компании можно развиваться. От оплаты курсов до того, с кем потолковать, если хочешь взять больше ответственности.
- Как повышать доход, оставаясь в компании.
Это лишь то, что я вывел для себя. Есть много полезных вопросов, которые описаны в книгах по этой теме.

2. Первое собеседование в оффлайне - повод отказаться. Это неоправданное вложение времени. Компания смотрит множество кандидатов - и твои шансы пропорциональны этому количеству. Ты можешь быть лучшим технически, но какой-то парень просто будет веселее и непринужденнее :) Или наоборот. Или компания просто возьмет самого дешевого.

3. Крупные компании лучше малых. Там уже отлажены процессы. Твоя роль более узка, чем в малых (а многозадачность, как известно, миф). Ты знаешь, к чему готовиться. И никто не урежет тебе зарплату за месяц, чтобы оплатить аренду офиса, если что-то пойдет не так. Зато в малых все более человечно.

Потом еще че-нить добавлю.

Мантра программиста

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

Сейчас я не буду писать, как предотвращать переусложенение систем. Расскажу, как найти силы бороться с текущей.

Это своего рода хакерская мантра:

Пределы сложности не бесконечны. Изучи задачи, которые решает проект, - и осознаешь систему.

Глобально фронтенд решает только одну задачу - рисовать интерфейс. Проект строится только для этого. Он бьётся на подзадачи, каждая из которой - решать глобальную задачу.
Например, Реакт отвечает за компонентный подход. Редакс - за хранение глобального стора. Апи - за работу с сетью. Тайпскрипт строго типизирует параметры подсистем.

Я открываю компонент - и ничего в нём не понимаю. Код абстрактен, незадокументирован, плохо проименован. Работать с ним сложно. Но я говорю себе: он выполняет узкий спектр задач. Я подхожу к нему как исследователь. Я думаю, какова его глобальная задача, на какие подсистемы он может быть разбит. Откуда могут приходить данные, как их дебажить.

И со временем удается все осознать.

Функциональное программирование. Начало.

Прежде всего - зачем?

1. React в 2021 - функциональный.
2. RxJs и в целом реактивный подход - это функциональщина. В наше время реактивность наращивают популярность.
3. В целом во фронте используется смешанный стиль. И хотелось бы части, написанные на ФП, писать более профессионально.

Quick Sort. Часть 1: зачем?

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

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

Временная сложность этого алгоритма:
Худший случай: O(n2).
Средний: O(n log n).
Лучший: O(n log n).

Сложность алгоритма по памяти:
С сортировкой на месте: O(log n).
Без: O(n).

Обычно его делают через рекурсию. Итеративный метод со стеком любопытные могут погуглить или попросить о нем ИИ.

В следующем посте опишу декомпозицию алгоритма для лучшего осознания и запоминания.

Quick Sort. Часть 2: декомпозиция.

Речь пойдет об алгоритме с сортировкой на месте и средним элементом массива в качестве опорного.

Для удобства понимания делю на четыре части: |

- quickSort,
Главная функция.
Принимает и возвращает массив. Вызывает вспомогательную функцию. Опционально проверяет массив на минимальную длину.
Сигнатура: (array) => array (sorted);

- quickSortHelper.
Вспомогательная функция, вызываемая внутри quickSort.
Принимает три аргумента: массив и начальные указатели.
Сигнатура:

(array, leftIndex, rightIndex) => void;

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

(array, leftIndex, rightIndex) => leftIndex;

- swap.
Переставляет элементы массива.
Сигнатура:

(array, leftIndex, rightIndex) => void;

В следующем посте напишу реализацию части алгоритма с комментариями.

Quick Sort. Часть 3: реализация.

1. Напишем главную функцию:

const quickSort = (arr) => {
    if(arr.length < 2) { // если длина массива меньше 2, запуск алогоритма не имеет смысла - вернем сам массив. 
        return arr;
    }
    quickSortHelper(arr, 0, arr.length - 1); // изначальные аргументы всегда 0 и arr.length-1. Они означают первый и последний индексы в массиве.
    return arr; // массив сортируется на месте и возвращается после всех рекурсивных вызовов.
}

2. Теперь напишем функцию quickSortHelper:

const quickSortHelper = (arr, left, right) => {
    if(left >= right) { // условие для выхода из рекурсии.
        return arr;
    }

    const partitionIndex = partition(arr, left, right); // вызывается для каждого массива, начиная с изначального и заканчивая единичными.

    quickSortHelper(arr, left, partitionIndex-1); // вызов для левой части с числами меньше опорного элемента. 
    quickSortHelper(arr, partitionIndex, right); // вызов для правой части с числами больше опорного элемента. 
}

3. Теперь - функция partition:

const partition = (arr, left, right) => {
    const pivot = arr[Math.floor((left + right) / 2)]; // опорный элемент определяем как средний. Опорный элемент - значит, тот, с которым сравниваются все остальные элементы при сортировке. 

    while (left <= right) { // двигаем указатели, пока они не сойдутся.
        // cравниваем с опорным элементом и передвигаем указатель до тех пор, пока не выполнится условие.
        while(arr[left] < pivot) { 
            left++; 
        }
        // то же, что в предыдущем случае, но после левого указателя.
        while(arr[right] > pivot) { // то же, что в предыдущем случае.
            right--;
        }

        // если элементы равны, просто передвигаем указатели, не вызывая swap. Это немного оптимизирует алгоритм.
        if(arr[left] === arr[right]) {
            left++;
            right--;
            continue; // важно, чтобы не выполнился swap.
        }

        swap(arr, left, right)
    }
    return left;
}

4. Наконец, напишем swap:

const swap = (arr, left, right) => {
[arr[left], arr[right]] = [arr[right], arr[left]];
}

Quick Sort. Часть 4: оптимизации и тест-кейсы.

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

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

Теперь соберите алгоритм сами и попробуйте на тест-кейсах :)

export const cases = [
    [],
    [1],
    [2, 1],
    [1,2,3],
    [3,1,2,4],
    [5,4,3,2,1],
    [116, 90, 89, 70, 65, 30, 25, 16, 9, 1, 4, 0, -1, -9],
    [1, 27, 5, 16, 3, 11, 8],
    [1, 27, 116, 9, 5, 16, 3, 2, 11, 8],
    [9,8,5,2,1],
    ['string', { object: true }],
    [undefined, undefined]
]

В качестве бонуса - алгоритм без оптимизаций:

const quickSort = (array) => {
    if(array.length <= 1) {
        return array;
    }

    const left = [];
    const right = [];
    const middleIndex = Math.floor(array.length / 2);
    const pivot = array[middleIndex];

    for(let i = 0; i < array.length; i++) {
        if(i === middleIndex) {
            continue;
        }
        if(typeof array[i] !== "number") return null;
        if(array[i] > pivot) {
            right.push(array[i]);
        } else {
            left.push(array[i]);
        }
    }

    return [...quickSort(left), pivot, ...quickSort(right)]
}

В чём разница между arr.length и arr.length-1?

Всё просто:

- arr.length возвращает общее количество элементов в массиве. Например, length для [1,2,3] будет 3.

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

Поэтому любой код, где нужен последний элемент массива, пользуется записью arr.length - 1.

Запомни это, чтобы избежать распространенной ошибки :)

Бинарный поиск. В чем суть?

Представьте линейку школьников, где дети выстроены по росту - от самых низких до самых высоких. Физрук ищет ученика определенного роста.

Первая мысль - измерить всех. Это метод brute force. Физруку придется поработать над каждым из учеников - даже над теми, кто точно выше или ниже нужного.

Вместо этого физрук прибегает к методу бинарного поиска:

1. Переходит в центр колонны.
2. Измеряет ученика. Если ученик подходит - заканчивает подбор. Если нет - смотрит, выше ученик или ниже.
3. Отбрасывает половину с теми, кто ниже или выше.
4. Переходит в середину оставшихся.
5. Повторяет цикл, пока не найдет нужного.
6. Если не находит - идет пить пиво :)

Это и есть алгоритм бинарного поиска. Всё просто!

Вот реализация на JS. Проследите, как в коде описаны шаги электронного физрука :)

const binarySearch = (array, target) => {
    let left = 0;
    let right = array.length-1;

    while(left <= right) {
        const pivotIndex = Math.floor((left + right) / 2);
        let pivot = array[pivotIndex];

        if(pivot === target) {
            return pivotIndex;
        }

        if(pivot < target) {
            left = pivotIndex+1;
        }

        if(pivot > target) {
            right = pivotIndex-1;
        }
    }

    return -1;
}

Задача структур данных.

Структуры данных придуманы не только для того, чтобы бросать вызов кандидатам на интервью в бигтехи. :) У них, как явления, есть конкретная задача.

О любой структуре данных полезно думать с позиции всего четырёх операций:

- добавление элемента.
- удаление элемента.
- поиск элемента.
- хранение элементов.

Array - одна из первых структур данных - появился, чтобы удобно (непрерывно) хранить данные одного типа, быстро получать к ним доступ по индексам и выполнять над ними вычисления.

Singly Linked List (однонаправленный связный список), появившийся следом, отличался тем, что более эффективно использовал память, а также вставлял элементы в начало и конец за O(1). Массивы изначально были статическими: размер задавался заранее и не мог быть изменен. Чтобы добавить новые элементы, приходилось создавать новый массив - уже с новым элементов.

Любопытная черта динамических массивов в том, что, когда добавляется новый последний элемент, структура выделяет новый блок памяти - что выполняется за O(n) - больший, чем необходимо для добавления одного элемента. Выделенные заранее ячейки памяти заполняются уже за O(1).

Думайте о структурах данных в этом ключе. Так проще поймете и их, и алгоритмы.

А в следующем посте я покажу простой вариант Singly Linked List на JS. Внутри будет любопытный пример работы со стеком. 😉

Singly Linked List. Реализация.

Далеко ходить не буду - вот код:

https://github.com/Gretten/SinglyLinkedList/blob/main/SingleLinkedList.mjs

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

Хеш-таблица. Что такое хеш-функция?

Как я уже сказал, можно думать о хеш-функции о черном ящике, который:

1. всегда принимает ключ (и текущую длину массива).
2. всегда возвращает индекс массива.

Не так важно, как он устроен. Важно, что это чистая функция с чётко определенной задачей.

Усвоив это, углубимся в реализацию.

Хеш-функции сравнивают по разным критериям, главными из которых я назвал бы:

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

Наименее качественная, но наиболее простая и наглядная реализация - арифметическая:

#h(key, tableLength) {
let ASCIICharKeysSum = 0;

for(let i = 0; i < key.length; i++) {
ASCIICharKeysSum += key[i].charCodeAt();
}

return ASCIICharKeysSum % tableLength;
}

Что здесь происходит?

Примем за условие, что ключи передаются строками или приравниваются к ним. Тогда строка:

- разбивается на символы
- возвращает свой индекс из ASCII-таблицы
- складывает индексы
- возвращает остаток от деления, который становится индексом массива.

Среди других реализаций есть криптографические, универсальные, с псевдослучайными числами и многие другие.

В следующем посте обсудим rehashing.

Хеш-таблица. Функция перераспределения, или rehashing.

Прежде чем разбираться, что такое рехешинг, ответим, зачем он нужен.

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

Rehashing решил эту проблему: в таблицах может храниться сколько угодно элементов - ценой сложности O(n).

Что, в сущности, такое рехешинг? Это просто создание нового массива, пересоздание хешей и перераспределение данных. Та же технология, что и в динамических массивах.

Но постойте, что значит сложность O(n)?! Где хваленый (O1)?

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

Вот реализация в моей хеш-таблице:

#allocateSpace() {
    const newTable = new Array(this.table.length * 2) // таблица при каждом вызове увеличивается вдвое
        .fill(null)
        .map(_ => new LinkedList()); // каждый бакет использует связанный список

    const bucketNodes = [];

    for(const bucket of this.table) {
        bucket.traverse((node) => { // метод traverse обходит связанный список, используемый в бакете
            if(node) bucketNodes.push(node.value);
        })
    }

    for(const node of bucketNodes) {
        const newHash = this.#h(node.key, newTable.length);
        newTable[newHash].append({
            key: node.key,
            value: node.value,
        });
    }

    this.table = newTable;
}

А в следующем посте поговорим про коллизии :)

Хеш-таблица. Коллизии.

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

Мы можем либо разрешить, либо запретить это.

- Стратегия "разрешить" называется "chaining".
- Стратегия "запретить" называется "открытая адресация".

Chaining: элементы массива хранят структуры данных, в которые при коллизии добавляются новые значения.
Достоинства чейнинга - в относительной простоте и избегании проблем, которые приносит стратегия "запретить".
Недостаток - в том, что, в худшем случае (если для всех ключей будет вычислен одинаковый хеш), сложность поиска и удаления станет O(n).
Для оптимизации поиска вместо простого связанного списке могут использоваться более сложные структуры данных, включая двоичные деревья. В связке с ними используют рехешинг.

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

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

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