Разбираемся в алгоритмах и структурах данных. Доступно и понятно

Всем привет. Меня зовут Адам Леос, и я Senior Software Engineer в PlutoTV. Кроме основной работы, я активно участвую в развитии IT-сферы и повышении уровня разработчиков в целом. Например, я принимаю участие в хакатонах (как участник и как судья), пишу технические статьи, провожу вебинары и выступаю с докладами как приглашенный технический специалист в компаниях и как спикер на конференциях.

Темы для своих презентаций я подбираю так, чтобы это был не пиар себя/компании/технологии, а чтобы материал привнес что-то нужное, был полезен разработчику (желательно непосредственно сразу). Одна из таких тем — необходимость знания алгоритмов и структур данных. По определенным причинам среди разработчиков из стран СНГ бытует мнение, что эти знания не нужны и не важны. Спойлер! Это не так.

Для кого предназначена эта статья? Она будет полезна каждому, кто желает добиться одной (или нескольких, можно всех) из следующих целей:

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

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

Выступление на JSFest 2019 в Киеве

Статья будет базироваться на двух тезисах (и опровергать их):

  1. Первый — «Знать алгоритмы и структуры данных не нужно. Никакой пользы разработчик от этих знаний не получит». Мы поймем, почему это не так, и разберем примеры из реальной жизни, как я применял эти знания в нескольких компаниях и получал огромный прирост в производительности.
  2. Второй тезис для разработчиков, которые ушли немного дальше и считают так: «Вроде польза и может быть, но, чтобы ее получить, необходимо потратить очень много времени на изучение материала, который к тому же очень сложный». Для этого мы усвоим базовые знания и все необходимые вещи в самом начале этой статьи (поговорим о сложности алгоритма, нотации Big O, сортировках, самых популярных структурах данных и их использовании для оптимизации проекта).

Сложность алгоритма

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

Сразу обращу ваше внимание на «ресурсы». Какими ресурсами мы оперируем в разработке? Очевидно, это время (то, насколько быстро будет выполняться наш алгоритм: дольше выполняем — больше времени тратим © Кэп). Но, к возможному удивлению многих разработчиков, еще один ресурс, которым мы часто оперируем (да, и во front-end-разработке тоже), — это память. Безусловно, работая за свеженьким MacBook Pro под последним Chrome, вы можете никогда и не столкнуться с проблемами перерасхода памяти (хотя и с таким неоднократно сталкивался, разработчики могут создать утечек от души), но память — такой же ценный ресурс, как и время. Особенно остро я ощутил это в последних нескольких компаниях, занимаясь разработкой под разные платформы типа Smart TV, игровых приставок и прочего, обладающего очень слабым железом (телевизор за $20 000 будет слабее вашего смартфона, что уж говорить о более дешевых моделях).

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

function sumNumbersInArray(array) {
  let sum = 0;

  array.forEach(number => sum += number);

  return sum;
}

Здесь мы получили массив, объявили переменную-сумму, изначально равную 0, и запустили итерацию по массиву, беря каждый элемент массива и добавляя его к сумме. Все просто. Теперь давайте проанализируем: что будет, если мы вызовем эту функцию с массивом из пяти чисел [1, 2, 3, 4, 5]? Очевидно, мы сделаем пять итераций — за каждый элемент в массиве, чтобы взять его и добавить к сумме. А что, если массив будет состоять из десяти чисел? Логично, что потребуется десять итераций.

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

Нотация Big O

Лучше всего зависимости можно увидеть на графиках, и для описания таких зависимостей существует нотация Big O (это те самые O(n), O(log n) и прочие, которые мы рассмотрим чуть дальше). Если выразить, что это такое, одним предложением, то это будет звучать так: функция, которая описывает рост сложности алгоритма. Что за сложность алгоритма и как она может расти, мы примерно себе представили. Big O — это функция, которая этот рост описывает. Единственное уточнение: функция фигурирует здесь в математическом смысле, то есть как функция, которая используется для построения графика.

Давайте возьмем наш синтетический код из примера выше и построим график зависимости размера входных данных от количества итераций. По оси X (горизонтальной) мы возьмем рост входных данных от 0 до какого-то конечного числа n. Основными точками пускай будут 1, 100, 1000 и 10 000 единиц (элементов в массиве). По оси Y (вертикальной) будет рост количества операций также от 0 вверх с основными точками в 1, 100, 1000, 10 000 операций. Остается только провести линию по зависимости, что была у нас в алгоритме.

Как вы помните, на каждый элемент в массиве нам необходимо сделать дополнительную операцию сложения. Значит, если нам пришло 100 элементов, делаем 100 операций. Приходит 10 000 элементов — делаем 10 000 операций. Приходит n элементов — делаем n операций. Вот и та самая n в сложности O(n), которая также называется линейной. Все очень просто.

График линейной функции, или О(n)

Здесь все классно, но надо посмотреть с разных сторон и на других примерах, чтобы закрепить. Рассмотрим новый пример простойПосчитать (simpleCalculate). Мы ничего не принимаем и выполняем какие-то операции: вычисляем переменные, выводим что-то в консоль (просто чтобы было больше операций) и возвращаем разницу.

function simpleCalculate() {
  const a = 1 + 2;
  const b = 3 + 4;

  console.log('calculating...');

  return b - a;
}

Сложность такого алгоритма O(1) — постоянная, или константная. Здесь тоже все примитивно: наш алгоритм вообще ничего не принимает, поэтому никак не зависит от входных данных. Соответственно, даже если бы по какой-то причине в него передавали различные значения, он бы постоянно выполнял одни и те же операции, никак не увеличивая и не уменьшая расход ресурсов, поэтому сложность постоянная. На графике это показано еще доступнее:

График константной функции, или O(1)

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

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

function simpleCalculate(number) {
  const a = 1 + 2;
  const b = 3 + 4;

  console.log('calculating...');

  return b - a + number;
}

Сложность этого алгоритма также будет O(1). Несмотря на то что мы уже принимаем аргумент и используем его, все, что мы делаем, — одну дополнительную операцию по сложению. Какое бы большое, маленькое, дробное или отрицательное число ни было, мы всегда просто берем его и складываем одной операцией (естественно, при условии, что оно помещается в память, но это уже совсем другая история), то есть количество операций постоянно и не зависит от инпута.

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

function simpleCalculate(array) {
  const a = 1 + 2;
  const b = 3 + 4;
  let additionalNumber = 0;

  array.forEach(num => additionalNumber += num);

  return b - a + additionalNumber;
}

Здесь-то у нас уже появляется снова линейная зависимость от размера входных данных, знакомая нам по первому примеру. Больше массив — больше операций мы делаем для вычисления дополнительного слагаемого. Помните сложность такого алгоритма? O(n).

Отлично, сейчас многим может показаться, что они раскусили систему: если входные данные — это массив, то сложность всегда линейная, О(n), и думать здесь нечего. Но мы можем посмотреть на такую версию предыдущего кода.

function simpleCalculate(array) {
  const a = 1 + 2;
  const b = 3 + 4;
  const additionalNumber = array.length;

  return b - a + additionalNumber;
}

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

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

function notSoSimpleCalculate(array) {
  for (let i = 0; i < array.length; i++) {
	for (let j = 0; j < array.length; j++) {
  	  array[i] = array[i] + array[j];
	}
  }

  return array;
}

Сложность такого алгоритма уже значительно выше, за каждый элемент массива нам нужно сделать полную итерацию по массиву. То есть, имея лишь массив из пяти элементов [1, 2, 3, 4, 5], мы проделаем 25 операций. Применив простейшую математику, мы можем прийти к тому, что нам требуется квадрат операций на наш размер входных данных. Эта сложность называется квадратичной и обозначается О(n^2). График демонстрирует резко растущий расход ресурсов такого алгоритма.

График квадратичной функции, или О(n^2)

И если с вложенными циклами это очевидно, то здесь разработчика может поджидать резкое увеличение сложности, казалось бы, на ровном месте.

function mightBeSimpleCalculate(array) {
  let total = 0;

  array.forEach(num => {
    const additional = array.indexOf(num) > 5 ? 5 : 1;

    total = total + num + additional;
  });

  return array;
}

Как вы уже догадались, сложность такого алгоритма — O(n^2). По сути, здесь присутствует тот же вложенный цикл. Реализация метода indexOf под капотом — это обычный цикл, обход массива: так как индексы каждого элемента в массиве не хранятся, то его надо найти. Само собой, опытный разработчик об этом знает. Правда, если при этом опытный разработчик не знает алгоритмов, то, скорее всего, он этот код так и оставит. К слову, оптимизация здесь была бы суперпростой. В методе forEach второй аргумент — это индекс итерируемого элемента, и легким движением руки квадратичная сложность превращается в линейную, потенциально сохраняя нам большое количество ресурсов на выполнение.

function mightBeSimpleCalculate(array) {
  let total = 0;

  array.forEach((num, index) => {
    const additional = index > 5 ? 5 : 1;

    total = total + num + additional;
  });

  return array;
}

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

function notSoSimpleCalculate(array) {
  // дополнительно выводим каждый элемент в консоль
  array.forEach(num => console.log(num));

  for (let i = 0; i < array.length; i++) {
	for (let j = 0; j < array.length; j++) {
  	  array[i] = array[i] + array[j];
	}
  }

  return array;
}

Сложность этого алгоритма будет не O(n + n^2), а просто квадратичная, O(n^2) — как раз потому, что квадрат будет расти несоизмеримо быстрее, делая влияние линейной сложности нерелевантным.

Пример роста в цифрах

Чтобы увидеть разницу, полезно взглянуть на сравнение количества операций в зависимости от сложности с одинаковыми размерами входных данных. Давайте смоделируем ситуацию, когда у нас на вход приходит массив с 10 000 (десятью тысячами) элементов, и определим, сколько операций проделают разные сложности:

  • O(1), константная — 1 (одна) операция;
  • O(log n), логарифмическая (например, бинарный поиск) — ~13 (чуть более тринадцати) операций;
  • О(n), линейная — 10 000 (десять тысяч) операций;
  • О(n^2), квадратичная — 100 000 000 (сто миллионов) операций;
  • O(n^3), кубическая (если бы у нас был тройной вложенный цикл) — 1 000 000 000 000 (один триллион) операций;
  • O(n!), факториал от числа n (поиск всех перестановок, пример — наивное решение очень популярной задачи коммивояжера) — 10 000 000 000 000 000 000 000 000... и еще очень много нулей. Для сравнения времени выполнения: вначале умрет Вселенная, через триллионы лет, и только потом алгоритм закончит выполнение.

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

Image Source

Несколько полезных комментариев к картинке:

  • Обратите внимание на зеленую зону, там присутствует как константная сложность, так и логарифмическая. Как вы уже видели выше в примере с числами, логарифмическая сложность очень эффективна. Она почти так же хороша, как и константная.
  • Сложность O(n * log n) — это лучшая сложность универсальных сортировок. Мы к этому еще вернемся.
  • Несмотря на то что квадратичная сложность находится в красной зоне («ужасной»), правильно будет упомянуть, что задачи бывают разные. И иногда вы ну никак не можете достать что-то из своих данных эффективнее, чем за двойной обход. Но это будет как раз тем местом, куда вы должны смотреть, когда захотите оптимизировать участки логики для повышения производительности. О методах и подходах мы поговорим чуть дальше.
  • Важный момент — начало всех графиков. Очевидно, что все они начинаются из одной точки и их рост при небольших значениях еще не так сильно заметен и критичен. Именно поэтому необходимо тестировать свои алгоритмы не на одном пользователе/товаре/записи, а на максимально приближенном к реальности (а лучше на еще большем, с запасом). Иначе и O(1), и O(n^2), и даже О(n!) дадут вам один результат (единица в квадрате — единица, факториал единицы — единица).

Структуры данных

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

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

Какие основные операции мы проворачиваем с данными? Все задачи в основном сводятся к следующим операциям:

  • доступ (получить данные);
  • поиск (найти данные);
  • вставка (добавить данные);
  • удаление (удалить данные).

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

Image Source

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

Дальше давайте поговорим о самых ярких представителях жанра в ежедневной разработке и об их грамотном использовании.

Массивы

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

const arr = [1, 2, 3];

Что мы можем с ним делать? Очевидно, получить какой-то из элементов по индексу.

arr[1]; // 2

Как считаете, какова сложность этой операции? Кто предположил (или знал), что это O(1), оказался прав. Мы можем мгновенно по уникальному идентификатору (индексу) получить любой элемент массива (даже которого там нет, просто получим undefined). Так же можно и записывать по индексу.

arr[0] = 4; // [4, 2, 3]

Так делать (обычно) все же не стоит, ибо это чревато последствиями: можно получить «дырки» в массиве и прочие радости мутаций. Но это уже другая тема.
Ладно, давайте о методах: например, добавление элемента в конец массива.

arr.push(4); // [1, 2, 3, 4]

Сложность такой операции будет O(1).

Примечание. Добавление элемента в конец списка в JavaScript — константная операция, только не обычная, а «амортизированная». Что это значит? В JS мы не управляем памятью напрямую, но в языках программирования, где мы ей управляем, создание массива под наши нужды будет немного отличаться. Нам будет необходимо выделить память под массив определенного размера. То есть выделив память на массив длиной в 20 элементов и захотев добавить 21-й, мы будем вынуждены выделять еще память, что является О(n)-операцией. Несмотря на то что мы не делаем такого в JavaScript, это происходит «под капотом». И хотя преимущественно мы будем вставлять элементы в О(1), иногда могут быть «скачки», когда под наш новый элемент выделяется больше памяти. Так что эта операция как бы константная, но амортизированная.

Что у нас с удалением с конца массива?

arr.pop(); // [1, 2, 3]

Здесь мы имеем также O(1). Хорошо, а что с задачами добавления и удаления с начала массива?

arr.shift(); // [2, 3]
arr.unshift(4); // [4, 2, 3]

Как многие знают (или догадались по подводке), здесь мы имеем другую картину. Вставка и удаление элемента с начала списка имеют сложность О(n). Все потому, что, манипулируя элементами в начале списка, мы должны обновить индексы всех последующих элементов. Если произошло удаление, то элемент, который был вторым, должен стать первым, вторым станет третий и т. д. То же самое происходит при вставке в начало: требуется обновить индексы всех последующих элементов.

Это, как вы сами видите, значительно менее эффективно. Именно поэтому разнообразные реализации стеков (stack) базируются на push & pop, а не на unshift & shift. Немного о стеках. Представьте стопку документов на подпись: тот, что лежит сверху, и берем первым для подписи. Если мы что-то добавляем, то кладем поверх всех, и он становится первым для следующей подписи. Это еще называется LIFO — last in, first out (последним вошел — первым вышел). Самым популярным применением в программировании будут разнообразные стеки операций: например, стек изменений в редакторе кода, чтобы иметь возможность быстро отменять изменения и возвращаться к предыдущим состояниям, или стек передвижения по страницам в браузере, чтобы быстро переходить по страницам.

Напоследок обязательно стоит упомянуть другие методы работы с массивами, которые имеют О(n)-сложность (как в примере с indexOf). Это будут практически все методы по работе с массивами — все, где мы что-то фильтруем, ищем, перебираем, переворачиваем и даже превращаем в строку (toString) — все это имеет O(n)-сложность.

Объекты

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

const obj = {
  id: 1,
  name: 'Adam',
};

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

obj.id // 1
obj['name'] // ‘Adam’

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

obj.surname = 'Leos';
obj['name'] = [];

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

Object.keys(obj) // ['id', 'name']
Object.values(obj) // [1, 'Adam']

Как вы можете догадаться, сложность этих методов — О(n): надо пройти по всем значениям, создавая из них массив.

Именно благодаря тому, что каждое свойство объекта — уникальный идентификатор и по этому уникальному ID мы можем мгновенно получать, записывать, удалять и обновлять данные, объекты часто используются как вспомогательная структура для многих оптимизаций через маппинг. Для многих это может быть знакомо по аналогам из других языков: словарю (dictionary) или «карте» (map). К слову, в ES2015 в JS тоже добавили объект Map — как раз для такого использования. Кто не знаком, он предоставляет методы для всех тех манипуляций, которые мы проводили раньше с объектом, имитируя Map. Например:

  • Проверить, есть ли запись (has), вместо сравнения с undefined.
  • Получить по ключу (get) и записать (set).
  • Применить forEach сразу к map, итерируя на месте по связкам (ключ, значение).
  • Прочие удобности.

Теперь давайте взглянем на применение. Начнем с решения очень популярной на собеседованиях задачи (например, ее устное решение спрашивали у меня в Microsoft). Задача — посчитать количество уникальных символов в строке. Решение тривиально и работает с любыми символами:

function countSymbols(string) {
  // наша вспомогательная структура - карта уникальных символов
  const map = new Map();


  // запускаем обход по строке
  for (let i = 0; i < string.length; i++) {
    const char = string[i]; // берем каждый итерируемый символ
    let newValue = 1; // и сколько раз мы его встретили, по-умолчанию один
    
    // а если символ уже встречался, т.е. записан в карту, увеличиваем
    if (map.has(char)) newValue += map.get(char)


    // обновляем сколько раз текущий символ встретился
    map.set(char, newValue);
  }

  return map;
}

Результатом вызова с какой-либо строкой будет карта по уникальным символам и их количеству:

Map(3) { a → 2, d → 1, m → 1 } // 'adam'
Map(4) { m → 1, i → 4, s → 4, p → 2 } // 'mississippi'
Map(10) { "Х" → 1, "а" → 1, 0 → 3, "с" → 1, " " → 1, "р" → 1, "@" → 1, "з" → 1, "н" → 1, "г" → 1 } // 'Ха0с р@зн0г0'

То есть мы создали карту и заполнили символами из строки, где каждый символ — уникальный идентификатор. Так мы могли мгновенно проверить его наличие в карте, получить значение и перезаписать его. И это работало для любого символа любого языка, специальных символов и даже пробелов. В общем, идею маппинга вы уловили: это создание вспомогательной структуры для определенных операций за О(1). Теперь давайте перейдем к их применению в реальной жизни.

Полезный маппинг в реальном мире

Здесь я хотел бы привести один из примеров, где я применял это в одной из предыдущих компаний. Почему именно его? Потому что это очень наглядная демонстрация ситуации, когда незнание алгоритмов и их сложности ведет к огромному падению производительности на ровном месте при приличном, на первый взгляд, коде. Здесь четко показано, как можно при минимальных усилиях (за полчаса) получить большой прирост производительности (почти в 100 раз).

Краткое описание проекта: делал я как-то видеостриминговое приложение на ReactJS + Node.js для альтернативных платформ типа Smart TV и игровых приставок.

«Типа Netflix», только еще с телевизионными Live-каналами

Была там одна задача, которую решили еще до моего прихода на проект. Ситуация была следующая. У нас в приложении есть тысячи шоу: какие-то сериалы, фильмы — весь видеоконтент приложения со следующей структурой (все упрощено и переименовано в угоду простоте восприятия и для удовлетворения NDA, все совпадения случайны):

const shows = [
  {
    id: 1,
    name: 'Rick and Morty',
    categories: [
      'Comedy',
      'Animated',
      'Science',
    ],
    data: 1001010101001011,
  },
  {/.../},
  {/.../},
  {/.../},
  {/.../},
];

То есть массив из множества объектов, представляющих отдельное шоу и хранящих информацию по этому шоу, — стандартные ID, name и прочее.

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

const bannedShows = [
  {
    id: 1,
    categories: [
      'Comedy',
      'Animated',
      'Science',
    ],
  },
  {/.../},
  {/.../},
  {/.../},
];

И вот код, как это было решено:

function ineffectiveBanning(shows) {
  // начинается обход всех шоу
  shows.forEach(show => {
    // берется ID каждого
    const { id: showID } = show;

    // запускается обход забаненных шоу
    bannedShows.forEach(bannedShow => {
      // теперь берем ID каждого забаненного
      const { id: bannedShowID } = bannedShow;

      // сравниваем ID и если совпадение - помечаем шоу как забаненное
      if (showID === bannedShowID) {
        show.isBanned = true;
      	}
     });
  });
};

Что здесь происходит? Начинается цикл по всем шоу, берется ID каждого из этих шоу и запускается обход забаненных шоу с целью найти совпадения. Если совпадение есть, шоу должно быть забанено (условно помечаем флагом isBanned).

Чей-то опытный глаз уже мог заметить проблему (и возможно, нервно задергаться). Вообще, здесь совершается слишком много ненужных операций: мы для каждого шоу запускаем итерацию по забаненным, это очень большая и лишняя нагрузка. А ведь оптимизируется это очень легко, нам нужна лишь карта забаненных ID, с помощью которой мы бы могли мгновенно проверять, забанено шоу или нет. Реализовать это можно как с помощью обычных объектов, так и с помощью Map или даже Set (Set — это просто набор, то есть оперируем как с Map, только никаких значений записям не присваиваем, просто добавляем уникальные ключи, чтобы они были в наборе, и выполняем мгновенные проверки на их наличие):

function effectiveBanning(shows) {
  const bannedShowsIDs = new Set();


  // наполнили Set забаненными ID
  bannedShows.forEach(({ id }) => bannedShowsIDs.add(id);

  shows.forEach(({ id }) => {
    // если ID текущего шоу присутствует в сете забаненных - помечаем его
    if (bannedShowsIDs.has(id)) show.isBanned = true;
  });
};

Что изменилось: мы вынесли вложенный цикл итерирования по забаненным шоу наружу и проходим по нему всего один раз для заполнения нашего Set, который будет набором всех забаненных ID с возможностью мгновенно проверять, есть ли там определенная запись. В итоге мы не запускаем множество ненужных циклов внутри обхода всех шоу, а делаем лишь мгновенную проверку на наличие итерируемого шоу в списке (Set) забаненных. И если совпадение есть, то шоу должно быть помечено как забаненное.

Это можно реализовать как еще короче, так и более развернуто и доступно. Можно использовать объект вместо Set и просто делать запись в объект, где ключом будет тот же уникальный ID забаненного шоу, а значением — что угодно, то же булево true. И затем для проверки, забанено ли итерируемое шоу, достаточно «постучаться» в объект по ID, и мы получим либо true, что будет значить, что шоу надо банить, либо undefined, а значит, шоу в забаненных нет, пропускаем.

Отлично. Если с оптимизацией времени вроде бы все понятно (делай меньше операций, опирайся на сложность, и будет тебе благо), то что же с памятью?

Память в реальном мире

А с памятью все тоже просто (хоть и менее прозрачно). В качестве примера я буду использовать оптимизацию, которую я сделал уже на текущем проекте в PlutoTV (тоже видеостриминговое приложение на React под телевизоры и приставки).

Был вот такой красивый и функциональный код:

function enhanceApiResponse(apiResponse) {
  const channels = apiResponse.channels
    .filter(filterEmptyTimelines)
    .map(addIdentificator)
    .map(modifyImages)
    .map(removeParams)
    .map(setSession)

  // more code
}

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

Кто уже увидел проблему для памяти? Что делают методы filter и map? Возвращают новый массив, под который необходимо выделить память, возможно, много (возможно, непозволительно много для некоторых платформ). А существует этот массив лишь для того, чтобы по нему запустить новый цикл и провернуть другую операцию с теми же элементами, что и в предыдущем цикле. Какое расточительство памяти на ровном месте!

Исправить это можно очень просто, заменив все на один обход. Например, с помощью reduce:

function enhanceApiResponse(apiResponse) {
 const channels = apiResponse.channels.reduce((acc, channel) => {
   if (!hasEmptyTimelines(channel.timelines)) {
     acc.push(
       setChannelURL(reduceImagesObject(addIDToChannel(channel))); 
     ); 
   }

   return acc;
 }, []);

 // more code
}

Идея, как видите, очень проста. Мы имеем один reduce (можно даже заменить фильтрацию, просто не наполняя аккумулятор по условию). Естественно, можно записать как короче, так и размашистее, кто как любит. Суть в том, что мы не выделяем кучу памяти под новые массивы, которые даже толком не используем. Эта маленькая оптимизация позволила сохранить от 10% до 30% расхода памяти приложения в зависимости от старины девайса. Что очень много: 30% для одного места, когда все приложение еще должно где-то работать.

Сортировки

Еще очень полезно будет разобраться с сортировками. Сразу скажу, что необходимость реализовывать какую-то свою уникальную сортировку у вас будет появляться крайне редко (а то и вовсе не случится за всю карьеру), так как в каждом языке программирования присутствуют довольно хорошо оптимизированные методы сортировки (отличным примером будут оптимизации array.sort() в JavaScript, которые мы обязательно разберем дальше). Но сортировки вне зависимости от необходимости их реализовывать — это очень классный пример алгоритмов и балансировки между расходами времени и памяти. Так что давайте взглянем на две самые популярные сортировки с очень разными расходами ресурсов.

Первым делом мы посмотрим на знакомую многим сортировку пузырьком (Bubble Sort). Идея этой сортировки в том, чтобы, проходя по массиву, находить самый большой элемент и «протаскивать» его до конца массива. Очевидно, чтобы отсортировать таким образом, когда за один обход мы дотаскиваем только один самый большой элемент, нам потребуется n обходов массива (где n — длина массива). А когда нам необходимо сделать n обходов, каждый из которых заключается в полном обходе массива, это O(n^2)-сложность. Ну вы и сами уже знаете.

Давайте посмотрим на визуализацию, а затем погрузимся в реализацию.

Сортировка пузырьком, O(n^2)

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

В коде все будет тоже очень просто.

function bubble(arr) {
 const length = arr.length;

 for (let i = 0; i < length; i++) {
   for (let j = 0; j < length - i - 1; j++) {
     const current = arr[j]; // текущий элемент
     const next = arr[j + 1]; // следующий


     // если текущий больше следующего, меняем их местами
     if (current > next) {
       arr[j] = next;
       arr[j + 1] = current;
     }
   }
 }

 return arr;
}

Бесполезна ли эта сортировка, имеющая аж квадратичную сложность, когда есть более быстрые универсальные сортировки? Отнюдь. Как мы могли наблюдать, у сортировки пузырьком (как и у подобных ей, типа сортировки вставками) есть одно довольно важное преимущество — расход памяти. Здесь нам требуется лишь одна вспомогательная переменная для смены мест двух элементов, то есть константная сложность по памяти. Это огромная разница по сравнению со следующей быстрой универсальной сортировкой — сортировкой слиянием. Давайте взглянем на нее.

Сортировка слиянием, O(n * log n)

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

Благодаря постоянной разбивке пополам и попарному слиянию сложность этой сортировки — O(n * log n), то есть длина массива (надо как минимум раз полностью пройти по массиву), умноженная на логарифм от длины (сложность постоянного деления пополам). Сейчас взглянем на код и на еще одну визуализацию, и все должно стать понятно.

Здесь основной код, который будет в то же время использоваться рекурсивно, для разбивки массива пополам и сортировки этих двух половин. (Сам метод сортировки разберем немного позже).

function mergeSort(unsortedArray) {
  // условие выхода из рекурсии
  // если переданный массив имеет менее двух элементов - нечего сортировать
  if (unsortedArray.length < 2) {
    return unsortedArray;
  }


  // находим центр при помощи побитовой операции сдвига на один бит вправо
  // аналог деления на два и округления вниз, только эффективнее и элегантнее
  const middle = unsortedArray.length >> 1;
  const left = unsortedArray.slice(0, middle); // левая часть
  const right = unsortedArray.slice(middle); // правая часть


  // вся магия сортировки в этом методе merge
  return merge(
    mergeSort(left), mergeSort(right)
  );
}

Посмотрим на еще одну визуализацию, на которой хорошо видно, как массивы разбиваются и затем попарно сливаются обратно. Сразу после визуализации перейдем к методу merge.

Еще одна отличная визуализация сортировки слиянием

В чем будет заключаться наша логика слияния? У нас приходят два массива: левый и правый. Оба либо уже отсортированы (см. логику выше), либо просто состоят из одного элемента. Теперь нам нужно начать обход по обоим (достаточно одного обхода с двумя указателями: первый указывает на итерируемый элемент левого массива, второй — на итерируемый элемент правого массива) и брать меньший из двух элементов, закидывая его в новый массив, который мы вернем как отсортированный.

function merge(left, right) {
 const resultArray = []; // отсортированный массив, который мы наполним и вернем
 let leftIndex = 0; // указатель для обхода левого массива
 let rightIndex = 0; // указатель для обхода правого массива


 // обходим, пока не закончили хотя бы один из массивов
 // (значит во втором все оставшиеся элементы точно больше)
 while (leftIndex < left.length && rightIndex < right.length) {
   // если левый элемент меньше правого
   if (left[leftIndex] < right[rightIndex]) {
     resultArray.push(left[leftIndex]); // добавляем его в массив
     leftIndex++; // инкрементируем указатель, чтобы ссылаться на следующий эл-нт
   } else { // иначе правый эл-нт больше, делаем тоже самое, только с правым
     resultArray.push(right[rightIndex]);
     rightIndex++;
   }
 }


 // возвращаем массив, что мы наполняли и добавляем в него все, что не допрошли
 return resultArray
   .concat(left.slice(leftIndex))
   .concat(right.slice(rightIndex));
}

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

Сейчас вы и сами видите, что более быстрая сортировка требует значительно больше памяти (выделяется большое количество памяти под все эти новые массивы, которое не идет ни в какое сравнение с константным расходом сортировки пузырьком).

Так что теперь мы можем качественно понять, что за оптимизации скрыты под капотом у array.sort(). Несмотря на то что имплементации могут отличаться от браузера к браузеру (и даже от версии к версии), глобальная идея заключается в том, чтобы использовать сортировку слиянием и быструю сортировку (также O(n * log n)) в зависимости от типа данных в массиве. Но массив не разбивается на подмассивы до одного элемента, как в нашей реализации. Вместо этого разбивание останавливается на 10 элементах, и уже к этим массивам из 10 элементов применяется сортировка вставками (аналог пузырьковой, O(n^2)). И лишь после этого начинается алгоритм слияния / быстрой сортировки. Таким образом, экономится очень много памяти (не создается целая куча лишних массивов) и практически нет проигрыша по быстродействию (сортировка вставками довольно эффективна на небольших массивах). Вот и чудесный пример балансировки между быстродействием и расходом памяти.

Важное послесловие о сортировках: я не просто так несколько раз писал, что сортировка слиянием и быстрая сортировка — это лучшие универсальные сортировки. То есть они будут стабильно хорошо работать в любых ситуациях с любыми данными (естественно, в пределах разумного). Хотя да, существуют разные сортировки со сложностью лучше, чем O(n * log n): например, radix sort. Но их применение специфично и не является универсальным. Хотя такие сортировки, само собой, широко применяются, просто они эффективны в конкретных ситуациях.

Выводы

  • Вам не нужно знать все алгоритмы и структуры данных. Самые необходимые знания, дающие больше всего пользы, в то же время являются и самыми простыми в освоении.
  • Нет необходимости помнить все реализации, вы даже можете забыть какие-то самые важные. Достаточно один раз разобраться в них, чтобы иметь представление о возможностях.
  • Анализируйте ваши алгоритмы. Задумывайтесь над их эффективностью. Чем более эффективный код вы создаете, тем производительнее и надежнее будет ваш продукт (и тем круче вы станете как разработчик).

Полезные материалы

Теория:

Практика:


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

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU

👍ПодобаєтьсяСподобалось26
До обраногоВ обраному151
LinkedIn



Найкращі коментарі пропустити

Неужели хорошая техническая статья на доу?
Спасибо, просто топ в этом году!)

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

автор, ты решил вместить в статью тему, которую некоторые авторы раскрывают в своих толстых книгах, мое почтение.

Хорошая статья, правда, как гласит мудрость «с годами железо становится быстрее и дешевле, а программисты дороже и ленивей» :)

Написано на языке, понятном даже гуманитариям. Спасибо большое.

135 коментарів

Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.

Всем привет! Спасибо автору за статью. Я так понимаю в варианте оптимизации в решении с забаненными шоу => м ы все равно перебираем forEach все шоу и потом каждый id проверяем на contains в списке set с забаненными шоу.. Но ведь метод contains has a time complexity O(n) соотвественно тут квадратическая сложностоь получается. Или я не правильно понял? Если я верно понимаю, то тут нужно все шоу как объекты хранить в мапе и потом за один проход по set с забаненными шоу просто по уникальному ключу зесетить значения в этой мапе showIsBanned = true? Может чуть ниже автор это и имел в виду? Может кто-то пояснить пожалуйста!?

Сначала строится Map’а с ключами забаненых шоу — O(b).
Потом цикл по всем шоу O(s) и проверка has в мапе O(1)

O(b + s * 1)
в итоге O(max(b,s)) — то-есть какой из массивов больше и скорее всего массива с шоу, тогда просто O(s)

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

Потому что оба начальных списка это List’ы и нужно сделать из одного (любого) Map с ключами, а по другому пройтись и проверить наличие ключа за константное время.

Хоть так, хоть этак — сложность алгоритма и количество итераций будет одинаковым.

А будет статья которая объясняет что такое переменная ?

Таблица «Common data structure operations»: кто автор и почему такие странные значения?

Stack: insertion, deletion — не отражена специфика вершины стека. Insertion в вершину — O(1), но в произвольное место — до O(n). То же для удаления. Это полагая стек на списке. Стек на массиве — другие показатели: реаллокация массива приведёт к эпизодическому O(n) даже для вершины.
Очередь: аналогично, надо понимать конкретный вариант дизайна.
И для списков сделаны аналогичные чрезмерные упрощения: надо разделять манипуляции с головой, с произвольным местом уже зная его, и с необходимостью ещё и найти ссылку. Удаление из односвязного списка никак не может быть Θ(1), если это не голова списка и если нет заранее каким-то образом известного указателя на предыдущий элемент.
Hash table: worst insertion O(n) это про что? Коллизии или ремап? Если ремап, то никто не обязан его производить одним рывком. Если коллизии, то никто не обязан держать линейный список элементов корзины (Java >=8 применяет тут вложенное RB-tree от 8 элементов в корзине). И что такое average/worst access — N/A??? Not available? Not applicable?

Лучше таки проверяйте источники — и замените тут данные на нормальные, чтобы «доступность» и «понятность» не оказались в ущерб здравому смыслу и соответствию реальности.

Вставка и удаление в произвольное место Стека и Очереди, гениально.
Стек и Список — это идея как стандарт С++, реализация предполагается адекватная. А давайте еще автор опишет сложность вставки в Стек с реализацией в виде двух Очередей?

Удаление элемента может быть О(1) в произвольном месте кроме хвоста, в виде мутации текущего элемента значением следующего.

Вставка и удаление в произвольное место Стека и Очереди, гениально.
Стек и Список — это идея как стандарт С++, реализация предполагается адекватная.

Если вы о таком никогда не слышали, это только ваша проблема.
Например, в Forth для стека есть операции доступа к элементу на заданной глубине и ротации группы по кругу. В Erlang — process mailbox это FIFO очередь, но с возможностью извлечения из произвольного места по шаблону (и грабли от перехода от Θ(1) к O(n) от этого — очень больно бьют по выступающим местам). Откуда «идея как стандарт C++» взялась, если никакого уточнения на эту тему не было (а примеры вообще на JS)?

А давайте еще автор опишет сложность вставки в Стек с реализацией в виде двух Очередей?

Ну если хотите — просите, почему нет? Хотя мне сложно понять, зачем стеку такая реализация. И я такого не прошу — я просто удивляюсь источнику таблицы. Может, в конкретном исходном месте с уточнениями, какие именно операции имеются в виду, там это и уместно, но тут — выглядит, как корова в церкви — просто и непритязательно ©.

И вы взяли от всех названных проблем таблицы — 1/5 и вцепились в них. Ну да, это так удобно объявить своё понимание стека единственно правильным...

Удаление элемента может быть О(1) в произвольном месте кроме хвоста, в виде мутации текущего элемента значением следующего.

Теперь вы ввели умолчание в виде возможности переместить значение элемента списка. А как же

Стек и Список — это идея как стандарт С++

если по C++ для списка перемещаемость элемента никак не обязательна (более того, на практике в std::list и складывают то, что перемещать нельзя)?

кроме хвоста

Ну всё равно особый случай получается. Ой не сходится...

Если вы о таком никогда не слышали, это только ваша проблема

Так что давайте теперь описывать в каждой статье любую реализованную функцию с библиотеки и выдавать ее за обязательную. Стек = peek, pop, push, остальные — производные.

Теперь вы ввели умолчание в виде возможности переместить значение элемента списка. А как же

Ничего я не вводил и не писал что это можно всегда сделать, а просто что такая возможность есть после "

даление из односвязного списка никак не может быть Θ(1)

"

А мне вот стало интересно: в чём у вас, автор, разница между «доступно» и «понятно», если доступно оно в 100500 источников и без этой статьи?

программитов

Понравилось, заберу :)

В моїй практиці був випадок, коли оптимальним виявилося сортування саме бульбашкою.

Для боротьби із спамом був заведений список регекспів, по якому проганялись листи, аби відсікати на ранніх підступах завідоме лайно. Аби не ганять по всьому списку (а в ньому було кілька тис. регекспів) був задіяний статпідхід. Всі листи проганялись по перших 100 регекспах за популярністю, половина — по наступних 100, чверть по наступних 100 етц. При попаданні в регексп лічильник попадань регекспа інкрементувався, і порівнювався з попереднім. Якщо був більшим — регекспи свопались в списку. В результаті в середньому кожен лист проганявся трошки менше, ніж по 200 регекспах, а список завжди був відсортований за популярністю.

В данном случае, всё же не была полная сортировка всего списка, а обновление позиции одного элемента. Что даёт в худшем случае сложность О(n).

Вот если бы был список из десятков тысяч регэкспов и эвристика не просто +1, а в каком-то диапазоне +1..+N, тогда наверное Max Heap с его О(lg n) был более эффективным.

Но да, сразу усложнять смысла нет, тоже сделал бы сразу просто сравнение с соседом.

Автор красава) теперь и я приобщусь к миру знаний в области алгоритмов и сортировок))

Тогда для закрепления
Изи leetcode.com/...​sorted-lists/submissions
Хард leetcode.com/...​ems/merge-k-sorted-lists

Мне как-то попалась вторая задача, но я не знал, что она хард)

Отдельный респект за анимашную визуализацию сортировок...

По определенным причинам среди разработчиков из стран СНГ бытует мнение, что эти знания не нужны и не важны.

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

Куда донатить за продолжение?

До речі, слушна думка. Весь матеріал пройшов, наче художній твір, а не технічну статтю. Набагато простіше, ніж у Кормена та інших джерелах, що мені траплялися. Може цим циклом публікацій нарешті позатуляю проґалини у фундаментальних знаннях, які утворилися ще в університеті)

Написано на языке, понятном даже гуманитариям. Спасибо большое.

автор, ты решил вместить в статью тему, которую некоторые авторы раскрывают в своих толстых книгах, мое почтение.

не раскрывают а наоборот скрывают! (( они ведь знают что толстые книги сейчас не читает никто

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

Принципова різниця між Вашим дописом і формальними, часто канцелярськими, джерелами — це жива мова і приклади з практики. А канцеляризм проявляється, зокрема, у «літрах води», яким, можливо, і самі автори не раді, але змушені «наливати», щоб вписатися у формат.
Приклад елементарний: у підручнику на оцінку складності алгоритмів виділяється цілий розділ, і по параграфу на кожну з них. З точки зору студента це передвіщає наступний алгоритм: прочитати і нічого не зрозуміти -> Перечитати ще раз -> Вивчити визначення, термінологію, формули -> Переписати код з книжки/Написати власну реалізацію/Спробувати оцінити вже написані алгоритми -> Перейти до наступного параграфу. На кожне «О» може піти більше години. Потім йде окремий розділ по структурах даних. Потім — по сортуванню тощо.
Тут же, буквально в кількох абзацах, приведено, які бувають складності і від чого вони залежать. Тут же показано практичне застосування щойно отриманих знань при виборі структур. Тут же — застосування структур у алгоритмах сортування. І демонстрація роботи цих алгоритмів у практичних задачах.
Буквально двадцять хвилин читання для комплексного розуміння дисципліни. Далі можна і поглиблювати, але вже не тільки для того, щоб закрити сесію.

Хорошая статья, правда, как гласит мудрость «с годами железо становится быстрее и дешевле, а программисты дороже и ленивей» :)

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

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

много таких, которые не могут развернуть строку?

Задача: переставити символи рядка у зворотньому порядку.
Студент молодших курсів: переставляє усі символи з першого до останнього, дивиться на код і не розуміє про яку помилку його питають.
Студент старших курсів: переставляє усі символи з першого до середини рядка, не розуміє для чого це на вхід можуть подати nullptr.
Джун: переставляє усі символи з першого до середини рядка, перевіряє вхідні параметри, не розуміє питання про ефективніше використання кешу процесора.
Мідл: хитрує і створює новий рядок в який копіює символи в зворотньому порядку, не розуміє питання про час життя і володіння ресурсом.
Сеньойр: пише strrev(), не розуміє чому має імплементувати ще раз те що було зроблено 50 років тому.
Принципал: не пише нічого, пробує з’ясувати яку бізнес-задачу намагається вирішити інтерв’юер, не розуміє чому його просять писати якийсь код.
Партнер: розвиває ідею про сервіс реверсування рядку за місячну підписку по $9.99, не розуміє чому той хто сидиться навпроти нього намагається його перебити.
Tecnical fellow: поблажливо посміхається і мрійливо закривши очі в стелю розказує про свою ідею нової ОС StrRevOS написаній мовою програмування GoStrRev++ з використанням фреймворку StrRev.NET JVM.

Колись була ще така стаття на схожу тему:
dou.ua/...​ticles/startup-interview

Прошло почти 12 лет, мало что поменялось.

Я могу развернуть строку. У меня Gold Level на HackerRank и я все равно не понимаю, нафига это нужно в обычной работе. Ну вот нанимаете вы водолаза для подводной работы, спросили его, а как пошить костюм для глубоководного погружения, а какой принцип работы компрессора. А он нырнул и утонул. Потому что как он плавает — вы не проверили.

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

ps: давать тестовое — как по мне это перебор. Намного проще потратить 15-30 минут интервью на решение задач и обсуждение их решений, чем надеяться что кандидат напишет тестовое когда-то там в свое свободное время.

Это кстати хороший вопрос. Я вот не понимаю нежелание разработчиков не делать тестовое задание. Amazon вам дает тестовое задание. Microsoft тоже в зависимости от команды. Старт-апы часто дают вам тестовое задание на 20-30 минут. Часто такие задания довольно интересные. А вот задачи на собеседовании по повороту строки мало говорят о кандидате.

амазоны, майксофт и прочие фейсбуки дают не совсем тестовое задание, а ссылку на hackerrank (и подобное) с 2-3-мя алгоритмическими задачами и строгим лимитом времени, до 2-х часов.

Никто не даёт сделать какой-то crud со свистелками, падающим снегом и «чтоб похоже на gmail» с фразой — наш тех.лид считает что это можно сделать за час.

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

Амазон дает ссылку на свой портал. Где вы можете решить задачку — да, она похожа на HackerRank (даже больше, чем leetcode). Вот я вам дам сейчас задачку развернуть матрицу. Вы ее за сколько решите ? Я решу ее тремя строками (правда на Go) и все, что это говорит обо мне — что я ее уже решал.

Да, я проходил успешно 2 раза такие амазоновские этапы с задачами.

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

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

Technical fellow — это реприза на BolgenOS?

Це скоріше про тих хто вигадують нові проривні мови, фреймворки та ОС і намагаються всіх переконати, що конче треба терміново все переписати.

а в fellow их задвигают, чтобы таки не начали переписывать?

Вони на той час як правило вже і не можуть нічого написати і вимагають команду з 12 архітекторів і 2 сеньйорів.

не розуміє для чого це на вхід можуть подати nullptr.

это не респонсибилити разворачивания строки. Если ты подаёшь nullptr то ты сам себе злобный буратина. Не хочешь ловить неприятностей связанных с этим — делай тип который не допускает наллов.

не розуміє питання про ефективніше використання кешу процесора.

пусть этим занимается компилятор или делайте адекватное API к эффективному использованию кеша процессора а не вот это всякое неявное что ++i работает быстрее i++.

Слова не хлопчика, а джуна!

Какая разница? Я привожу этот пример как две совершенно равноправные конструкции в принципе могут иметь совершенно разные результаты по производительности. И вообще С++ это красноречивый пример, когда люди сначала делают, потом думают.

Они не равноправные, а в разные в С++.

синтаксически выглядят очень похоже, значит семантически должны делать одно и то же.

Но, нафига тебе это, ты же

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

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

Каждый понимает всё в меру своей, продолжение известно.

Формошлёпством имеет предельно мало отношения к тому чем я занимаюсь. Все формошлёпские технологии, что С# WF, WPF, ASP.NET, что html/\css+надстройки/\$(название любого фронтенд фреймворка из самых популярных), что свинг, что Qt, что питонячьи поделки имеют огромное количество фундаментальных недостатков, которые в принципе новой версией исправить нельзя. По каждой технологии можно написать страниц по 10 почему они плохие и как можно было лучше, но никакого времени на это не хватит.

Я вполне в состоянии освоить эти все извращения, чай не дифференциальная геометрия, не топология и не функан, но я не хочу тратить своё время на колупание в этой гадости. Ибо гадость — мастдай.

Вперед на литкод, проверять решение на валидность!
leetcode.com/problems/reverse-string

ітіть-калатіть, я ще не зовсім забув STL :)
leetcode.com/...​issions/detail/284877891

Runtime: 44 ms, faster than 91.36% of C++ online submissions for Reverse String.
Memory Usage: 15.3 MB, less than 57.32% of C++ online submissions for Reverse String.

404. Если хвастаетесь, то дайте доступ :)

спробував пошукати — без логінації не дає дивитись
але там великого секрету нема, ось таке було:

class Solution {
public:
    void reverseString(vector<char>& s) {
        unsigned half_len = s.size() / 2;
        vector<char>::iterator _left = s.begin();
        vector<char>::reverse_iterator _right = s.rbegin();
        for(unsigned i = 0; i < half_len; ++i, ++_left, ++_right){
            char c = *_left;
            *_left = *_right;
            *_right = c;
        }
    }
};

Випередив))
Теж збирався з силами останніх пару місяців сісти і написати статтю по алгоритмам для ДОУ.

Неплохое видео по расчету O(n) алгоритма
www.youtube.com/watch?v=ZRdOb4yR0kk

Неужели хорошая техническая статья на доу?
Спасибо, просто топ в этом году!)

0.1 + 0.2 !== 0.3

Розслабся, це джаваскріпт

floating point arithmetic же ж чувак ))

ЗЫ: эх прикол старый но всё равно всё так же ж хороший и правда 0.30000000000000004 против 0.29999999999999999 ))

ЗЫ: недавно встал вопрос об привидениях так я #внезапно вспомнил что арифметика то сопроцессора 80-битная т.е. у него честных 64 битных значащих а вот у double всего 52 т.е. по сути при попытке привести целое 64 бит которых мы печёмся всеми значащими сопроцессор таки это дело осилит а вот при сохранении та же ж винда си++ его уже потеряет потому что она умеет только 64-битные double как переменные в памяти а за сопроцессор она уже не знает ничего и long double такой же ж double тех же ж 64 бита и 52 бит значащих ))

в SSE же уже 80 бит нету вроде как?

An exception is Microsoft Visual C++ for x86, which makes long double a synonym for double.

я х.з. зачем ты мне это пишешь )) ты наверное хочешь мне рассказать что и fpu больше нет?

Если это будет написано на таком же уровне — почему бы и нет. Например, написание функции для суммирования чисел, и это будет интересно и полезно, особенно если писать на js

Я Вас шукав. Чесно, ще не читаючи статті, очікував побачити купу гнівних коментарів на тему: «кеп», «баян», «це і так всі знають» тощо. А знайшов перший такий десь внизу, та й то у вкладенні. Невже я переоцінив вміст жовчі у наших краях?

Неужели на компьютер сайнс в Сумском университете это не учат на первом же курсе?

нужна статья «как правильно бухать, типовые алгоритмы». А то современные «аутсорсеры» даже бухать-то толком не умеют

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

Это будет на следующем раунде

малость «классики»: предки завещали, и со слов начинали «пивка для рывка, водочки для заводочки...»
Все зависит от целей. Ежли, к примеру, ситуация сложилась как на партсобрании, когда и пить обязан, и поболтать не с кем, тогда правила: градус только по наростающей, и не запивать (особенно газировкой). Желательно перед пьянкой сьесть чего-то жирного.

Кстати, за минимальное к-во дегустаций «однопартейцы» смотрели «косо», и вполне можно было нарваться на «оргвыводы»

Лол, можно подумать, что в штатах ситуация иная

ну в общем как ни странно скорее таки да ((

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

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

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

Ну так зп условного айтишника в США так же выше средней. Конечно, не в N раз, как у нас, но тем не менее. Плюс порог входа на порядок ниже, чем у врачей и финансистов, вот и идут люди девелопить.

дык у врачей и финансистов ещё выше уже программистской и то сразу в н раз ))

я думаю по комбинации легкости порога вхождения и бенефита ойти в штатах на первом месте

я думаю это потому что ты уже знаешь вайти и тебе кажется что легче или наоборот на самом деле не знаешь и потому тебе кажется ))

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

Это ознакомительная лекция, week 0. Много ли вы видели ознакомительных лекций по программированию, где бы сходу объяснили binary search? А зная образовательную систему США, где студенты сами выбирают курсы, можно понять преподавателя, который пытается их заинтересовать. А делает он это, надо сказать, блестяще. Также вы опускаете, что помимо лекций есть учебные материалы, а сам курс называется CS50’s Introduction to Computer Science.

можно понять преподавателя, который пытается их заинтересовать.

Заинтересованного умного человека дополнительно заинтересовывать не надо.

А делает он это, надо сказать, блестяще.

Мне кажется, «сделай шоу» — это кредо США. Особенно в южной части. Но касательно учебы — это лишнее, на мой взгляд.
Вернее, это нормально, когда цель — заработать денег, но лишнее, когда нужно набрать только умных людей, не привлекая «посредственностей».

Мне кажется, «сделай шоу» — это кредо США. Особенно в южной части. Но касательно учебы — это лишнее, на мой взгляд.

наличие целой толпы успешных университетов и вполне себе толпы средних но хороших как бы б этот тезис никак не подтверждает на практике ))

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

вы нимношко преувеличиваете но ради интереса можно просто набрать баллов на школьном тесте достаточных для прохождения в тот же ж гарвард на технологию

наличие целой толпы успешных университетов и вполне себе толпы средних но хороших как бы б этот тезис никак не подтверждает на практике ))

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

«так ведь других нет!?» (к)

При том, что в з.п. от местных не особо отличается.

я так понимаю вы вообще не в курсе и правда «почему тогда» ))

Мне кажется

Перекрестись.

Я вам скажу в чем разница с США — ты не найдёшь в сша чувака с университетским дипломом в компьютер сайнс и не знающего описанных в статье базовых основ. А на украинских галерах хватает всяких магистров ничего про это толком не знающих.

Зря вы так. В любой индустрии есть профессионалы, есть любители и есть начинающие. Это только в фильмах так, кнопку нажали и оп-па, «я знаю кунг-фу». Или я пропустил момент, когда аудиторию DOU ограничили сеньорами и людьми с профильным образованием?

«тут» — это в Минске?

Ну вот, например, отличается в наличии жизни для профессионалов. Вы утверждаете, что в Минске для них жизни есть, я вам верю. Однако со своей стороны я вижу, что в Киеве для профессионалов жизнь есть. Вот мы и нашли отличие.

Ты написал

Для профессионалов тут больше жизни нет.

потом написал

И в Минске тоже.

а фантазии у меня?

Это твои проблемы, чувак, что ты сидишь в Минске и судишь другие страны по Минску. И чтоб тебе не было уныло в Минске ты ищешь на доу — форуме, который в Украине не воспринимают всерьез — подветрждения того, что в Украине так как в Минске.

Ты, наверное, считаешь, что раскрываешь на тут глаза, режешь правду матку, разбиваешь розовые очки. Но на самом деле твои каменты в каждой ветке — это нытье беларуса, который сидит на форуме украинцев. И каждый твой ноющий камент(как, в принципе, любой другой ноющий камент) — он не о том, как плохо всем нам — он о том, как плохо лично тебе.

Ну пока что из профессионалов, которых могу оценить — вижу тут Горчака, но он не в Украине.
Еще был (по менеджменту) Железняк, но он туда же.

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

На мій подив, цю статтю з очевидними основами досить тепло зустріли. Я думав буде гірше.
Але так, погодитись на публікацію на Доу — все одно, що підписати контракт з дияволом. Ти знаєш, на що йдеш. Потім не скигли.

Мій принцип використання інтернету, сформований за багато років, полягає у наступному: завантажую сайт із закладинок, збережених раніше, і проглядаю список публікацій. Якщо тема, з якихось причин, мене зацікавила, я відкриваю її у новій вкладці. Для цього достатньо клацнути посилання колесиком миші. Після ознайомлення з усіма новинами, доступними на головній сторінці, закриваю її і переходжу до вивчення вмісту сусідніх вкладок.
Навіть не уявляю собі сценарія, за яким би витрачав час на нецікаву мені статтю і, тим більше, написання під нею коментарів.

Сподіваюсь, мій досвід стане вам у пригоді. Зберігайте до обраного і користуйтесь на здоров’я. ;)

хотел бы еще рассказать о графах, деревьях, поиске

после «Искусство программирования» Кнута т.3, тут сложно что-то будет добавить

Круто. С радостью прочитаю следующие статьи!

Очень хорошая статья — спасибо за труд!

Жаль что тут нельзя «лойсы» статьям ставить. Спасибо за прописные истины, но в местных реалиях (UA), эти знания практически никто не спрашивает.

Так я себя и не ограничиваю )

Можно ставить ⭐ как на GitHub.

Таки да, читал про такую фичу, но что-то не могу найти эту кнопку.

Есть такое, спасибо. Но мои adblock’s это удаляют автоматом.

Очень нужный контент!!! Спасибо автору

Підписатись на коментарі