×Закрыть

Опановуємо основи алгоритмів, або Як прискорити код з 15 до 1000 запитів за секунду

У статті поговоримо про прикладне значення розуміння алгоритмів. Ви наочно побачите, як, маючи базові навички алгоритмічного аналізу, можна суттєво поліпшити роботу програм. Спочатку напишемо програму за неоптимальним алгоритмом, а потім крок за кроком будемо його поліпшувати, розглядаючи теорію складності алгоритмів, аналіз алгоритмів і структури даних. Пройдемо шлях від алгоритму, який опрацьовує 15 запитів на секунду, до алгоритму, який виконує 1000. Торкнемося теми розпаралелення задач. Стаття має бути цікавою як для бекенд, так і фронтенд-розробників різних рівнів.

У наступній статті ми розглянемо SOLID. Я покажу кілька прикладів з кодом, де принципи SOLID порушуються, поясню, до чого це може призвести в довгостроковій перспективі та як це виправити.

10 років тому я почав кар’єру в IT як .NET-розробник. Зараз співпрацюю з EPAM Systems як Solution Architect. Мій основний стек технологій: Node.js, React, React Native, AWS та GCP. Роблю проєктування високонавантажених систем, попереднє оцінювання та планування проєктів. Проводжу консультації щодо розв’язання проблем продуктивності та стабільної роботи систем. Проєктую та імплементую UI/UX для бізнес-процесів високої складності. Сьогодні активно займаюся вивченням роботи стартапів на ранніх етапах розвитку, а також DLT та Blockchain технологій для потреб бізнесу.

Передмова

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

Через своє швидке зростання та масштаб індустрія програмного забезпечення спонукає розробників добре опанувати насамперед фреймворки, спеціалізовані бібліотеки та шаблони проєктування. Це правильний та оптимальний підхід, оскільки він дає змогу швидко та прогнозовано розробляти програмні системи, уникаючи великої кількості помилок. Глибинне розуміння того, як працює технологія, на якій ведеться розробка, алгоритмічний аналіз та оптимізація відходять на другий план. Фокус змінюється в протилежний бік лише тоді, коли потрібно розробляти самі фреймворки та бібліотеки.

Оскільки зараз процесорний час порівняно дешевий і оперативна пам’ять також, від програмістів не вимагають писати супероптимальні програми. Бо порівняно з процесорним часом і оперативною пам’яттю час програміста дуже дорогий. Написання оптимізованих програм може тривати справді довго.

Гра починає змінюватися тоді, коли з’являється високе навантаження. Наприклад, є система, запущена на 10 000 віртуальних комп’ютерах (реальний випадок). 2000 з них — це вебсервери, решта — сервери з базами даних, розподіленими кешами та системами обміну повідомленнями. Зосередимось на вебсерверах. Припустимо це віртуальні комп’ютери з 4-ядерним процесором та 16 гігабайтами оперативної пам’яті. Місячна вартість роботи одного такого комп’ютера в AWS становить 70 доларів, а всіх 2000 комп’ютерів — 140 000 доларів. Тут вже стає цікавіше, адже якщо можна оптимізувати роботу програми хоча б на 10%, то на місяць досягнемо економії в 14 000 доларів, а на рік це 168 000.

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

Схожий випадок був на одному з проєктів, для якого я проводив консультацію. Команда прийшла з проблемою, що їй не вдається масштабуватися. Система під високим навантаженням вже за кілька секунд переставала відповідати. Як виявилось, причиною стало те, що на API виконувалося багато обчислень, але за неоптимальними алгоритмами. Система показувала себе добре на етапі розробки, бо тоді її навантаження становило не більше як 10 запитів за секунду. Коли під час навантажувального тестування пішли тисячі конкурентних запитів — система захлинулася.

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

  • оптимізовані оновлення DOM (тільки частини UI, які справді потребують оновлення);
  • правильна робота та організація стейту: нормалізація даних; селектори, які вміють кешувати денормалізовані дані або дані, які потребують розрахунків; забезпечення immutability;
  • Memoisation — кешування в пам’яті компонентів, які часто повторно використовуються;
  • Virtual Scroll — показ тільки тієї частини контенту, яку бачить користувач у певний момент;
  • Preload контенту і стратегії кешування запитів з API.

Звісно, весь цей список покривається фреймворками та бібліотеками. Ситуації, коли є певний функціонал і його не вдається покрити фреймворком або бібліотекою, трапляються рідко. Проте часто, коли робиш щось складне на UI, стикаєшся з тим, що:

  • вебсторінка фризиться;
  • минає багато часу, поки відбудеться перший рендер сторінки;
  • FPS дуже низький, коли скролиш сторінку або починаєш з нею якось взаємодіяти.

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

Хоча розуміння алгоритмів і структур даних не завжди в пріоритеті розробників, незнання базової теорії алгоритмів спричиняє серйозні ризики для проєкту. У свою чергу, знання алгоритмів підвищує ефективність роботи, оскільки мозок генеруватиме більше рішень, з-поміж яких можна вибрати краще та простіше водночас.

Опис задачі, в якій ми будемо оптимізувати алгоритм

Вибір завдання виявився не таким легким, як я вважав із самого початку. Потрібна була задача, яка легка для розуміння, до якої можна придумати кілька достатньо різних рішень, в кожному з яких розкривається той чи інший аспект алгоритмів чи структур даних. Крім того, кожне рішення має видавати відчутно кращий результат за попередній.

Я взяв за основу проблему з великою кількістю обчислень на API, яку описав вище, і ось що у мене вийшло. Є масив даних із 8 784 елементами, які містять дані про погоду кожної години протягом року для певного міста. Нам потрібно порахувати середню температуру за кожен день у році. Крім того, хочемо опрацьовувати 1000 запитів за секунду.

Створимо API-сервіс, який на початку роботи вичитує масив елементів, а тоді на кожен запит робить обчислення і повертає дані із середніми за день температурами. Сервіс буде запущений на Node.js. Всі запити будуть опрацьовуватися в Event Loop — це потік у Node.js процесі, який бере з черги запит, опрацьовує його і переходить до наступного. Потік Event Loop може бути тільки один на Node.js процес. Якщо якийсь запит опрацьовується дуже довго, це призводить до того, що в черзі накопичуються запити. З часом їх стає так багато, що ті, які надійшли пізніше, будуть відхилені через timeout, і клієнт отримає відповідь connection refused. Від того, наскільки оптимально написано версію алгоритму, буде залежати, скільки запитів буде опрацьовано, а скільки відхилено. Сервіс розроблятимемо на Nest.js мовою TypeScript.

Запуск сервісу

Вихідний код завантажимо з GitHub. Для запуску потрібно інсталювати Node.js. Після того як завантажили код, потрібно в корені каталогу запустити команду npm install. Коли всі пакети будуть завантажені, виконаємо команду npm start.

Кожна версія алгоритму буде доступна за адресою виду localhost:3000/v1 (/v2, /v3...). У відповіді міститимуться середні температури за день, а також час виконання запиту.

Вхідні дані взяті із сервісу OpenWeatherMap і збережені як JSON-файл.

Тестування ефективності

Для оцінювання ефективності запустимо load test:

  • Одночасно приходять 1000 користувачів.
  • Кожен з них робить по 10 запитів.

Тобто загалом буде створено 10 000 запитів, і наше завдання за одну секунду виконувати понад 1000 запитів. Для load test використаємо фреймворк Artillery.

Перший алгоритм

Опис

Почнемо з максимально неоптимального алгоритму.

  1. Елементи початкової колекції містять час виду 2019-01-01 00:10:00. Створимо нову колекцію (source), елементи якої міститимуть тільки дату виду 2019-01-01 і температуру.
  2. Тепер, коли у нас є лише дата, можна групувати за нею елементи source. Погруповані елементи збережемо у колекції groupedByDate, кожен елемент якої буде мати поля date та array. У полі array збережемо всі елементи source, які мають однакову дату.
  3. Групувати елементи source будемо так:
    • поки колекція source не порожня, беремо перший елемент (item) і шукаємо в колекції groupedByDate елемент, де поле date рівне item.date;
    • якщо такий елемент знайдено, додаємо в поле array знайденого елемента;
    • якщо такого елемента не існує, то в groupedByDate додаємо новий елемент, який буде містити дату, що дорівнює item.date, а також поле array, що буде містити масив з один елементом — item;
    • видаляємо перший елемент колекції source, оскільки ми його вже опрацювали, і переходимо до першого кроку.
  4. Залишилось знайти середнє арифметичне температур, які вже погруповані за датою. Для цього створимо нову колекцію meanTemperaturesByDate, кожен елемент якої матиме поля date і meanTemperature. В поле meanTemperature запишемо середнє арифметичне значення температур, які містяться в полі array, елементів колекції groupedByDate. Для цього їх просумуємо та поділимо на кількість.
  5. Повертаємо результат, який містить meanTemperaturesByDate.
   
    // we have a time field '2019-01-01 00:10:00'.
    // to make a grouping by date we need to cut '00:10:00' part, so leave only date.
    // let's create a new collection, which contains temperature and date
    const source = data.map(item => ({
      temperature: item.temperature,
      date: moment(item.time).format('YYYY-MM-DD')
    }));
 
    // in this collection we store items with the same date
    const groupedByDate: { date: string, array: IWeatherItem[] }[] = [];
 
    // take the first element, process it, and remove from the collection
    // stop processing once collection is empty
    while (source.length > 0) {
      const item = source[0];
 
      // check if we already have found items with date of the current element
      const match = groupedByDate.find(itemToFind => itemToFind.date === item.date);
 
      // if found
      if (match) {
        // add the current element to the array, which has elements with the same date
        match.array.push(item);
 
        // otherwise (if no elements with the date we are looking for)
      } else {
        // add new grouping with the current date
        groupedByDate.push({
          date: item.date,
          array: [item]
        })
      }
 
      // remove the first element, so we can process the next one on the following step
      source.splice(0, 1);
    }
 
    // count mean temperature for items with the same date
    const meanTemperaturesByDate: { date: string, meanTemperature: number }[] =
      groupedByDate.map(item => {
        return {
          date: item.date,
          meanTemperature:
            _.sumBy(item.array, item => item.temperature) / item.array.length
        }
      })
 
    return new Result(data.length, meanTemperaturesByDate, start);
 

GitHub-репозиторій

Результат виконання

localhost:3000/v1

{
  "count": 8784,
  "memoryUsed": "19.08Mb",
  "processingTime": "174ms",
  "pid": 15028,
  "meanTemperaturesByDate": [
    {
      "date": "2019-01-01",
      "meanTemperature": 8.441666666666663
    },
    {
      "date": "2019-01-02",
      "meanTemperature": 5.054166666666666
    },
    {
      "date": "2019-01-03",
      "meanTemperature": 4.724999999999999
    },

Для кожної версії будемо записувати, скільки часу виконується один запит. Це середнє значення для 5 викликів.


v1v2v3v4v5v6 pm2
Response time (single request) ms174




Load test

У нас загалом 10 000 запитів. У таблиці нижче порівняємо, скільки з них може опрацювати кожна версія і скільки запитів опрацьовується за секунду.


v1v2v3v4v5v6 pm2
Requests completed (10 000 total)565




Mean response/sec15.93




Як бачимо, перша версія змогла опрацювати лише 565 запитів із 10 000 (трохи більше як 5%). За секунду — майже 16 запитів. Спробуємо поліпшити ці показники у наступних версіях алгоритму.

Другий алгоритм. Пошук вузьких місць у програмі

Profiling

Profiling — це процес моніторингу роботи програми, під час якого ми діагностуємо, які частини коду займають найбільше процесорного часу. Саме вони мають бути основною ціллю оптимізації.

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

Профайлер працює так:

  1. Ставимо break point у тому місці, де починається процес виконання коду, який нас цікавить.
  2. Натискаємо кнопку Start Profiling.
  3. Активуємо процес, над яким відбувається профайлінг. У нашому випадку це надсилання запиту на localhost:3000/v1.
  4. Щойно виконання запиту закінчилося, зупиняємо профайлінг.

Після того як профайлер закінчив роботу, аналізуємо результати. Посортуємо їх за часом виконання:

Як бачимо, непомірно велику кількість процесорного часу займає виклик:

moment(item.time).format('YYYY-MM-DD')

У ньому виокремлюємо дату 2019-01-01 з поля time 2019-01-01 00:10:00. Оскільки moment вміє приймати на вхід безліч форматів дати та часу, то витрачає немало процесорного часу на те, щоб проаналізувати рядок з ними, перетворити їх у своє внутрішнє представлення, яке буде дозволяти, наприклад, знайти різницю з іншою датою або перетворити в інший формат, як ми робимо в нашому випадку.

Можемо прискорити виконання, передавши у функцію moment параметр, який вказує, у якому саме форматі у нас приходять дані. Тепер moment вже не буде підбирати формат, а буде використовувати заданий. Початково у нас було 174 мілісекунди, після задання вхідного формату даних отримуємо 150.

Але формат даних у нас завжди однаковий, і все, що потрібно, це отримати першу частину рядка, що містить дату. То чому замість виклику дорогого в часі методу moment не взяти перших 10 символів рядка? Спробуймо.

  const source = data.map(item => ({
      ...item,
      // date: moment(item.time).format('YYYY-MM-DD')
      // replace moment, since it decrease performance significantly
      date: item.time.substring(0, 10)
    }));

GitHub-репозиторій

Результат виконання

localhost:3000/v2

{
  "count": 8784,
  "memoryUsed": "23.77Mb",
  "processingTime": "26ms",
  "pid": 23508,
  "meanTemperaturesByDate": [
    {
      "date": "2019-01-01",
      "meanTemperature": 8.441666666666663
    },
    {
      "date": "2019-01-02",
      "meanTemperature": 5.054166666666666
    },
    {
      "date": "2019-01-03",
      "meanTemperature": 4.724999999999999
    },

v1v2v3v4v5v6 pm2
Response time (single request) ms17426



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

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

Load test


v1v2v3v4v5v6 pm2
Requests completed (10 000 total)5652380



Mean response/sec15.9348.7



Наш Load test теж демонструє явне поліпшення: з 10 000 запитів обробилося 2380, кількість відповідей за секунду зросла з 15.93 до 48.7.

Третій алгоритм. Оптимізуємо пошук. Як працює Hashmap

Алгоритмічна складність

Розглянемо код, де ми шукаємо елемент за датою:

const match = groupedByDate.find(itemToFind => itemToFind.date === item.date);

Ми послідовно йдемо по кожному елементу масиву і перевіряємо, чи його значення відповідає заданому. У найгіршому випадку треба перевірити всі елементи масиву, щоб знайти потрібний або сказати, що такого елемента в масиві не існує. Для оцінки алгоритмів використовують поняття «алгоритмічна складність». Вона показує залежність між кількістю елементів множини (n) та кроків алгоритму, необхідними для виконання задачі. У нашому пошуку елемента за датою складність дорівнює O(n) — тобто скільки елементів, стільки перевірок потрібно зробити в найгіршому випадку, щоб знайти заданий (або сказати, що множина його не містить в собі).

Усім відомий алгоритм сортування бульбашкою. У ньому є два цикли:

  1. Зовнішній, де ми визначаємо, який елемент є поточним.
  2. Внутрішній, де ми йдемо по всіх елементах до кінця масиву і робимо перестановку, якщо знайдемо менший елемент за поточний.

Алгоритм сортування бульбашкою має алгоритмічну складність О(n2), оскільки для кожного елемента ми перевіряємо всі наступні елементи.

Що менше значення O, то ефективніший алгоритм. Наприклад, завдяки тому, що алгоритм сортування Quick Sort поділяє масив за певним принципом, він зменшує кількість необхідних порівнянь між елементами. Його складність O(n log(n)). Більше тут.

Повернемось до нашого алгоритму. Як було сказано, складність пошуку елемента за датою дорівнює O(n). Це не є високою складністю, якщо це окрема операція. Але в нас цей пошук відбувається в циклі:

 while (source.length > 0) {
    const item = source[0];
    const match = groupedByDate.find(itemToFind => itemToFind.date === item.date);
 
    // ...
    source.splice(0, 1); // remove the first element 
  }

Виходить, щоб погрупувати всі елементи з однаковою датою, ми використовуємо алгоритм зі складністю O(n2), а це вже висока складність.

Бінарний пошук (Binary Search)

Існує алгоритм, складність пошуку якого дорівнює O(log(n)). Він називається «бінарний пошук». Масив, у якому відбуваються пошук, має бути відсортований. Як він працює:

  1. Маємо відсортований масив.
  2. Якщо масив порожній, то елемента не знайдено.
  3. Беремо елемент посередині масиву:
    • якщо він рівний тому, який ми шукаємо, — пошук завершено;
    • якщо він більший від того, який ми шукаємо, — візьмемо лише ліву частину масиву і проводитимемо пошук тільки в ній. Виконаємо крок № 2 лише у цій частині;
    • якщо елемент посередині масиву менший, то візьмемо лише праву частину масиву і виконаємо у ній крок.

Завдяки тому, що на кожному кроці розмір масиву, в якому ми робимо пошук, зменшується вдвічі, отримуємо O(log(n)).

Бінарне дерево пошуку (Binary Search Tree — BSD)

Є структури даних, що призначені для швидкого пошуку. Розглянемо бінарне дерево пошуку.

Дерево складається з вершин і ребер між ними. Вершина має батьківську вершину і дві або одну дочірню. Вершина, з якої починається дерево, не має батьківської вершини та називається коренем дерева.

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

У найгіршому випадку нам потрібно O(h) кроків, щоб знайти заданий ключ, де h — висота дерева. Оскільки швидкість пошуку залежить від висоти дерева, потрібно добитися того, щоб у міру додавання нових елементів його висота зменшувалася максимально повільно. Якщо у кожної вершини дерева висота її лівого піддерева відрізняється від висоти правого піддерева на більше ніж на 1, то таке дерево називають збалансованим. Пошук у ньому найоптимальніший. У збалансованому дереві складність пошуку елемента дорівнює O(log(n)).

Якщо ми довільним чином додаватимемо елементи до дерева, то його баланс буде зміщуватися то в праву, то в ліву частину. Розбалансоване дерево є небажаним, оскільки пошук у ньому не є оптимальним. Існують такі бінарні дерева, які зберігають баланс після вставлення або видалення елементів. Оскільки за певним алгоритмом після цих дій вони проводять своє балансування, то називаються самозбалансованими.

Самозбалансовані бінарні дерева пошуку

Приклади самозбалансованих бінарних дерев пошуку:

АВЛ-дерево (AVL tree)

Червоно-чорне дерево (Red-black tree)

Б-дерево (B tree)

Б-дерево цікаве тим, що вершина може мати кілька значень і з неї виходять більше ніж дві дочірні вершини. Якщо вершина має кілька значень (a, b), то між ними буде піддерево, в якому кожен ключ xn кожної вершини буде a < xn < b. Якщо таке дерево міститиме багато даних, то порівняно з іншими типами бінарних дерев пошуку його висота буде малою. Це важливо тоді, коли робимо пошук по дереву, яке зберігають не в оперативній пам’яті, а в постійній (HDD, SSD). В постійній пам’яті час доступу до інформації на носії значно довший. Інформація на постійному носії збережена у вигляді неперервних блоків (секторів), розмір яких може становити 4 кБ (залежить від файлової системи та вибраного розміру сектора). Оскільки ми за раз читаємо весь сектор (де записана вершина з кількома ключами), можемо за значно меншу кількість зчитувань з носія зробити обхід по дереву і знайти потрібну вершину.

Б-дерева виступають основою для індексів SQL та NoSQL баз даних (більше читайте тут і тут). Розуміння того, як працюють Б-дерева, дає можливість оптимально будувати індекси та досягти високої продуктивності в роботі з базою даних.

Хеш-таблиця (HashMap)

Коли є масив і ми знаємо порядковий номер елемента, щоб отримати його значення, потрібно звернутися до нього за індексом:

const item = source[index];

Алгоритмічна складність такої операції дорівнює O(1).

Якщо є потреба часто звертатися до елемента певної множини за ID, іменем, датою чи іншим ключем, замість пошуку по масиву можемо використати структуру даних «хеш-таблиця».

const item = hashMap[`2020-01-01`];

Складність доступу до елемента хеш-таблиці дорівнює O(1), тобто така сама, як би ми отримували доступ до елемента за індексом.

Хеш-функція hash(a) = b призначена для перетворення деякого набору даних a у певний результат фіксованої довжини b. При цьому мають виконуватися дві умови:

  1. Будь-яка, навіть найменша зміна вхідного набору даних a має повністю змінювати результат функції b.
  2. Знаючи лише результат функції b, має бути складно вирахувати оригінальний набір вхідних даних a.

Можливі випадки, коли хеш-функція для різних значень a дає однакові значення b. Такі ситуації називаються колізіями. Що краща функція hash, то менше колізій вона буде створювати.

В основі хеш-таблиці лежить масив. Коли ми робимо вставлення в хеш-таблицю, беремо hash від нашого ключа і зіставляємо результат з позицією у масиві hash(key) = index. Хеш-функція має працювати таким чином, щоб генерувати hash, значення якого буде менше за довжину масиву, і викликати найменше число колізій.

Оскільки будуть з’являтися колізії, нам потрібен механізм, щоб з ними боротися. Таких механізмів є кілька. Розглянемо два з них.

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

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

Алгоритм з використанням хеш-таблиці

Повернемось до нашого сервісу з обчислення середньої температури за день. Ми брали кожен елемент з масиву source і шукали інші елементи за датою в масиві groupedByDate. Як уже з’ясували, такий алгоритм має складність пошуку O(n2):

 
const groupedByDate: { date: string, array: IWeatherItem[] }[] = [];
 
    while (source.length > 0) {
      const item = source[0];
 
      // check if we already have found items with date of the current element
      const match = groupedByDate.find(itemToFind => itemToFind.date === item.date);

Тепер масив groupedByDate замінимо хеш-таблицею. Це дасть змогу замість операції пошуку, складність якої O(n), використати операцію доступу до елемента хеш-таблиці за ключем.

 const groupedByDate: { [date: string]: IWeatherItem[] } = {};
 
    while (source.length > 0) {
      const item = source[0];
 
      const match = groupedByDate[item.date];

Складність такої операції O(1).

    
// was: const groupedByDate: { date: string, array: IWearerItem[] }[] = [];
    // hashmap instead of list
    const groupedByDate: { [date: string]: IWeatherItem[] } = {};
 
    while (source.length > 0) {
      const item = source[0];
 
      // was:
      // const match = groupedByDate.find(itemToFind => itemToFind.date === item.date);
      // search O(1) instead of O(n)
      const match = groupedByDate[item.date];
 
      if (match) {
        match.push(item);
      } else {
        // was:
        // groupedByDate.push({
        //  date: item.date,
        //  array: [item]
        // })
        groupedByDate[item.date] = [item];
      }
 
      source.splice(0, 1); // remove the first element 
    }
 
    // get all dates
    const dates = Object.keys(groupedByDate);
    const meanTemperaturesByDate: { date: string, meanTemperature: number }[] =
      // for every date get mean temperature
      dates.map(date => {
        const temperaturesInOneDay = groupedByDate[date];
        return {
          date,
          meanTemperature:
            _.sumBy(temperaturesInOneDay, item => item.temperature) / temperaturesInOneDay.length
        }
      })
 
    return new Result(data.length, meanTemperaturesByDate, start);
  }

GitHub-репозиторій

Результат виконання

localhost:3000/v3

{
  "count": 8784,
  "memoryUsed": "18.69Mb",
  "processingTime": "11ms",
  "pid": 7440,
  "meanTemperaturesByDate": [
    {
      "date": "2019-01-01",
      "meanTemperature": 8.441666666666663
    },
    {
      "date": "2019-01-02",
      "meanTemperature": 5.054166666666666
    },
    {
      "date": "2019-01-03",
      "meanTemperature": 4.724999999999999
    },

Як бачимо, середній час виконання одного запиту скоротився з 26 до 11 мілісекунд.


v1v2v3v4v5v6 pm2
Response time (single request) ms1742611


Load test


v1v2v3v4v5v6 pm2
Requests completed (10 000 total)5652,3803,960


Mean response/sec15.9348.792.76


Після запуску навантажувального тесту видно, що кількість виконаних запитів зросла з 2380 до 3960. Це все одно тільки 39% успішних запитів зі 10 000. Кількість опрацьованих запитів за секунду зросла з 48.7 до 92.76. Наша ціль — понад 1000 за секунду, — все ще дуже далека, тому будемо продовжувати оптимізацію.

Четвертий алгоритм. Як працюють зв’язаний список (linked list), масив (array) та список (list)

Зв’язаний список (linked list)

Зв’язаний список — колекція у вигляді ланцюжка, де кожен елемент містить певний об’єкт і має вказівник на наступний елемент (next). Перший елемент списку називають його головою (head), а останній — хвостом (tail).

У зв’язаному списку ми не можемо одразу прямо отримати елемент за індексом (index), оскільки елементи не розміщені послідовно в пам’яті, а розкидані в різних її частинах. Починаючи з head, ми послідовно переміщаємося з одного елемента на інший, використовуючи next. Нам потрібно зробити стільки кроків, скільки рівне значення index. Тобто якщо в масиві у нас складність доступу за індексом рівна O(1), то у зв’язаного списку аж O(n).

Додавання нового елемента працює так:

  1. Якщо додаємо новий елемент на початку списку, то next нового елемента задаємо рівному тому елементу, який зараз head, а після цього робимо новий елемент head.
  2. Якщо додаємо вкінці, то next елемента, який зараз tail, задаємо рівним новому елементу, а тоді новий елемент робимо tail.
  3. Якщо ми додаємо елемент в довільну позицію index, то нам треба зупинитися на елементі (index — 1) — previous, прочитати його поле next і записати це значення в next нового елемента, а тоді в поле next елемента previous записати новий елемент.

Видалення відбувається аналогічним чином.

Характеристики зв’язаного списку:

  • пам’ять наперед не виділяється;
  • довжину можна змінити: додавання або видалення нового елемента на початку або в кінці списку O(1) чи додавання або видалення елемента в довільному місці списку O(n);
  • елемент зв’язаного списку можна отримати через index кроків, проходячи список від голови до потрібного елемента O(n).

Масив (array)

Масивом називають множину даних фіксованої довжини, які розміщені послідовно в пам’яті.

Основні характеристики:

  • пам’ять виділяється наперед;
  • довжину масиву змінити не можна;
  • елемент масиву можна отримати за його індексом одразу O(1).

Те, що JavaScript називають масивом (array), насправді є списком (list), оскільки його довжина може змінюватися.

Список (list)

В основі списку лежить масив. Але довжина списку може змінюватися.

Як це працює:

  1. Створюється масив. У нього є дві властивості: довжина (length) і місткість (capacity). Довжина показує, скільки елементів уже заповнили виділений простір пам’яті під масив. Місткість — скільки ще може вміститися елементів до того моменту, як масив доведеться збільшувати.
  2. Якщо додаємо новий елемент і length > capacity, то тоді створюємо більший масив, копіюємо у нього дані з попереднього масиву і додаємо новий елемент. У різних імплементаціях новий масив має різну місткість. Він може бути більший на половину від своєї попередньої capacity, а може і подвоїти її. Ось чому корисно наперед задавати capacity, якщо вона точно відома. Розширення списку є дорогою операцією.
  3. Якщо ми видаляємо багато елементів зі списку, то немає змісту тримати виділеною велику ділянку пам’яті, яка не використовується. Тому якщо length < 0.75 capacity (або 0,5 залежно від імплементації), то створюється менший масив і у нього копіюються елементи з попереднього.
  4. Після копіювання попередній масив видаляється відразу (C, C++) або під час Garbage Collection.

Характеристики списку:

  1. Пам’ять виділяється наперед.
  2. Довжина списку може змінюватися:
    • якщо новий елемент додається в кінець списку (append, push), то амортизаційна складність алгоритму буде О(1). Амортизаційна, бо в найгіршому випадку, коли список збільшуватиметься, складність буде O(n). Оскільки це дуже песимістична оцінка (ця операція відбуватиметься досить рідко), то беруть той випадок, який буде відбуватися майже весь час, а саме запис елемента у незайняте місце масиву, тобто зі складністю O(1);
    • якщо новий елемент видаляється з кінця списку (pop), то амортизаційна складність дорівнює O(1);
    • якщо новий елемент додається на позицію index, то складність буде O(n). Така складність зумовлена тим, що всі елементи, в яких позиція більша за позицію index, треба перенести на одну позицію далі в кінець списку. Також якщо вільного місця немає, потрібно створити новий масив і зробити копіювання;
    • якщо новий елемент видаляється з позиції index, то складність буде O(n), оскільки всі елементи з позицією більшою за index треба посунути на початок масиву або скопіювати в новий масив, якщо length < 0.75 capacity.
  3. Елемент списку можна отримати за його індексом відразу O(1).

Оптимізований алгоритм

Отже, видалення елемента зі списку є дорогою операцією. Ми її виконуємо, коли проходимось по колекції source:

  
while (source.length > 0) {
      const item = source[0];
	...
      source.splice(0, 1); // remove the first element 
    }

Щоб кожного разу не видаляти перший елемент, будемо проходити по кожному елементу колекції source, не змінюючи її.

  // was: while (source.length > 0) {
    source.forEach(item => {
      const match = groupedByDate[item.date];
 
      if (match) {
        match.push(item);
      } else {
        groupedByDate[item.date] = [item];
      }
 
      // was: source.splice(0, 1); remove the first element 
      // remove element from the list is an expensive operation
    });

GitHub-репозиторій

Результат виконання

localhost:3000/v4

{
  "count": 8784,
  "memoryUsed": "24.05Mb",
  "processingTime": "5ms",
  "pid": 19488,
  "meanTemperaturesByDate": [
    {
      "date": "2019-01-01",
      "meanTemperature": 8.441666666666663
    },
    {
      "date": "2019-01-02",
      "meanTemperature": 5.054166666666666
    },
    {
      "date": "2019-01-03",
      "meanTemperature": 4.724999999999999
    },

Попередня версія алгоритму опрацьовувала запит 11 мілісекунд, нова версія робить це за 5.


v1v2v3v4v5v6 pm2
Response time (single request) ms17426115

Load test


v1v2v3v4v5v6 pm2
Requests completed (10 000 total)565238039604940

Mean response/sec15.9348.792.76213.07

Як видно за результатами навантажувального тесту, ми успішно опрацювали майже половину запитів. За секунду нова версія алгоритму опрацьовує 213 запитів, порівняйте з 92 запитами попередньої версії.

Алгоритм п’ятий. Позбуваємося зайвих циклів і виділення пам’яті

Шукаємо зайві операції

У попередній версії алгоритму ми позбулися видалення елементів з колекції source. Оскільки тепер source ми не змінюємо, а колекція data відрізняється від source лише тим, що в її елементів немає поля date, можемо обійтися без source. Будемо проходити по data, обчислювати дату, використовуючи поле time кожного елемента. І маючи ці дані, групувати елементи в хеш-таблиці groupedByDate.

   
  // was:
    // const source = data.map(item => ({
    //  ...item,
    //  date: item.time.substring(0, 10)
    // }));
 
    const groupedByDate: { [date: string]: IWeatherItem[] } = {};
    
    // was: source.forEach(item => {
    data.forEach(item => {
      const date = item.time.substring(0, 10);
 
      // was:
      // const match = groupedByDate[item.date];
 
      // if (match) {
      //  match.push(item);
      // } else {
      //   groupedByDate[item.date] = [item];
      // }
 
      // less code
      // if groupedByDate[date] is not undefined, set self, otherwise set an empty list
      groupedByDate[date] = groupedByDate[date] || []; 
      groupedByDate[date].push(item);
    })

GitHub-репозиторій

Результат виконання

localhost:3000/v5

{
  "count": 8784,
  "memoryUsed": "14.21Mb",
  "processingTime": "2ms",
  "pid": 7992,
  "meanTemperaturesByDate": [
    {
      "date": "2019-01-01",
      "meanTemperature": 8.441666666666663
    },
    {
      "date": "2019-01-02",
      "meanTemperature": 5.054166666666666
    },
    {
      "date": "2019-01-03",
      "meanTemperature": 4.724999999999999
    },

Оскільки вдалося обійтися без створення додаткової колекції source, ми заощадили процесорний час на виділенні великого об’єму пам’яті та додаванні елементів. Це позитивно відбилося на продуктивності програми. Якщо порівнювати з попередньою версією, час виконання одного запиту скоротився з п’яти мілісекунд до двох.


v1v2v3v4v5v6 pm2
Response time (single request) ms174261152

Load test


v1v2v3v4v5v6 pm2
Requests completed (10 000 total)5652380396049407860
Mean response/sec15.9348.792.76213.07594.55

Результати навантажувального тестування показують, що ми успішно опрацювати 78% запитів. За секунду опрацьовуємо 594 запити.

Алгоритм шостий. Зведення до загального рішення. Паралельне виконання

Загальні рішення

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

Коли розбиваємо на простіші задачі, пам’ятайте, що різні задачі будуть мати рішення різної алгоритмічної складності. Треба комбінувати так, щоб у кінцевому результаті складність алгоритму була найнижча. Не варто забувати і про пам’ять:

  • Уникайте того, щоб проміжні результати залишалися після того, як алгоритм закінчив роботу. Це призводить до memory leaks (витоків пам’яті). Вони з часом забирають увесь вільний простір пам’яті, і програма аварійно припиняє роботу.
  • Якщо в пам’яті є важкі об’єкти (малюнки, фрагменти відео, великі масиви даних), то намагайтеся їх передавати з методу в метод, не створюючи копій.
  • Робіть сервіси так, щоб вони були stateless: не тримали в пам’яті дані про сесію між запитами.

У цьому прикладі я використав бібліотеку lodash. Вона містить методи groupBy та meanBy. Застосуймо їх і спростімо код алгоритму.

    
// was:
    // const groupedByDate: { [date: string]: IWeatherItem[] } = {};
    
    // data.forEach(item => {
    //   const date = item.time.substring(0, 10);
 
    //   groupedByDate[date] = groupedByDate[date] || []; 
    //   groupedByDate[date].push(item);
    // })
 
    const groupedByDate: { [day: string]: IWeatherItem[] } =
      _.groupBy(data, item => item.time.substring(0, 10));
 
    const dates = Object.keys(groupedByDate);
 
    const meanTemperaturesByDate: { date: string, meanTemperature: number }[] =
      dates.map(date => {
        const temperaturesInOneDay = groupedByDate[date];
        return {
          date,
          // was:
          // _.sumBy(temperaturesInOneDay, item => item.temperature) / temperaturesInOneDay.length
          meanTemperature: _.meanBy(temperaturesInOneDay, item => item.temperature)
        }
      })

GitHub-репозиторій

Якщо зараз знову запустити програму, то результати її виконання будуть такі самі, як у попередній версії, але код став лаконічніший і простіший для сприйняття.

Розпаралелення задач

Крім того, що можемо ділити складну задачу на простіші, можемо виділяти в алгоритмі незалежні процеси та виконувати їх паралельно. Найпростіший приклад: наш сервіс отримує дані з сервісів А та Б. Дані ніяк не залежать одні від одних. Замість того, щоб спочатку зробити запит на сервіс А, дочекатися відповіді та зробити запит на сервіс Б, краще виконати два запити одночасно і дочекатися, коли відповідь прийде від обох.

Так само варто розбивати великі об’єми даних на менші частини й паралельно проводити над ними обчислення. Далі всі часткові результати об’єднуємо в один.

Є таке поняття, як утилізація процесорного часу. Вона показує, наскільки процесор завантажений під час роботи. Наприклад, у нас вже є добре оптимізована програма. Ми її запускаємо і бачимо, що 12-ядерний (24-поточний) процесор використовує для виконання програми лише один потік. Це нормально, якщо навантаження на систему невелике і процесор встигає швидко обробляти всі запити, які до нього надходять. Але зі збільшенням навантаження починає створюватися черга запитів. Деякі з них настільки довго очікують обробки, що починають відхилятися. Зараз це добре видно, оскільки з 10 000 запитів у найкращому разі вдалось опрацювати лише 78%. Водночас, якщо відкриємо диспетчер задач, то побачимо, що тільки одне ядро завантажене на 100%. Це говорить про те, що ми недостатньо утилізуємо ресурси процесора.

Node.js асинхронно опрацьовує запити в одному потоці. Ми не можемо створити ще один потік, але можемо запустити ще один Node.js-процес, який паралельно буде обробляти запити.

Найпростіше це реалізувати через менеджер процесів. Він створюватиме декілька Node.js-процесів для обробки запитів, а також слугуватиме як load balancer, розподіляючи запити між цими процесами. У цьому прикладі я використав PM2, за допомогою якого запустив два паралельних Node.js-процеси.

Результат виконання з PM2 (два паралельних процеси)

{
  "count": 8784,
  "memoryUsed": "17.03Mb",
  "processingTime": "2ms",
  "pid": 21840,
  "meanTemperaturesByDate": [
    {
      "date": "2019-01-01",
      "meanTemperature": 8.441666666666663
    },
    {
      "date": "2019-01-02",
      "meanTemperature": 5.054166666666666
    },
    {
      "date": "2019-01-03",
      "meanTemperature": 4.724999999999999
    },

Коли ми робимо один запит, то отримуємо ті самі дві мілісекунди, що й у попередній версії.


v1v2v3v4v5v6 pm2
Response time (single request) ms1742611522

Load test


v1v2v3v4v5v6 pm2
Requests completed (10 000 total)565238039604940786010 000
Mean response/sec15.9348.792.76213.07594.551189.06

Зараз у нас запущено два паралельних Node.js-процеси, навантаження між ними однаково розподіляється. Це дало змогу виконати всі 10 000 запитів, які згенерував load test. За секунду ми обробляємо понад 1 100 запитів. Ціль досягнута.

Підсумки

Як бачимо, основи алгоритмів — це не така уже й складна річ. Їхнє розуміння допоможе бачити ширше коло рішень для задач, прогнозувати споживання процесорного часу та пам’яті програмами, розробляти системи, які краще та ефективніше використовують обчислювальні ресурси. Більш глибоке розуміння алгоритмів вимагає деяких інвестицій ваших зусиль і часу. Ресурси, які я можу порекомендувати:

LinkedIn

Лучшие комментарии пропустить

Дані потрібно готувати. Показники температури приходять раз на ... годину (припустимо). Шедулер вкладає до ДБ підраховані температури (за 170 мсек) , які нода тупо читає. Тоді — хоч мільон запитів

127 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Хороша стаття. Особливо сподобалось використання профайлера для пошуку вузького місця. Багато інженерів навіть сьогодні забувають про профілювання і оптимізують те, що суб’єктивно вважають вузьким місцем.

Додав декілька версій. Є Docker container з MySQL та Redis. Під час запуску Docker генеруються рандомні дані для 1000 міст і записуються в MySQL і Redis. Load test для кожного із 1000 користувачів робить запит на різне місто.
/v9 — обрахунки в SQL запиті, без індексів
/v10 — обрахунки в SQL запиті, з індексами
/v11 — обрахунки у веб-сервісі, але дані беруться з Redis
/v12 — обрахунки у веб-сервісі, дані перший раз беруться з Redis, а тоді кешуються в пам’яті процесу. Кешуються саме початкові дані, а не ті, для яких вже пораховані середні температури.

Я Вам отправил два pull requests: один на точность измерения времени ответа на запросы и v8 — версия алгоритма вообще без lodash.
Оцените, пожалуйста. Благодарю.

process.hrtime() - не знав про цей метод. Виглядає класно! Змерджив. Після мерджу другий PR вже був з конфіктами.

Насчет moment(item.time) — если всё-таки необходимо работать с moment в цикле, и дата представлена в формате ISO 8601, можно немного сэкономить, если сделать так:

moment(new Date(item.time))

Спасибо, поучительные примеры.

Як бачимо, непомірно велику кількість процесорного часу займає виклик:
moment(item.time).format(’YYYY-MM-DD’)
У ньому виокремлюємо дату 2019-01-01 з поля time 2019-01-01 00:10:00.

Дата-время в формате строки? Ну дальше можно не читать )

Node.js коли десереалізує JSON, автоматично не приводить стрічку з датою до Date об’єкту. Цьому є логічне пояснення — десереалізація дати займає додатковий час. Конкретно для 8000 елементів у цій статті — це в середньому 4 мілісекунди. В той час, як остання версія алгоритму у цій статті, займає 2.

    data.forEach(item => {
        new Date(item.time)
    });
   // 4 ms

Вам далеко не завжди потрібно працювати з датою. Десеріалізувати її в Date, а потім серіалізувати її у стрічку назад, щоб відправити відповідь в браузер — ну трохи зайве.

Серіазувати можна не тільки в текст, але і в binary. Тут вже пробем з довгою серіалізацією/десеріалізацією не повинно виникати, але виникають інші.

Ну і взагалі серіалізація/десеріалізація — часом складна тема. На деяких проектах навіть пишуть кастумні серіалізатори/десеріалізатори, які точно знають розмір даних, та їх позиції, і можуть оптималініше здійснювати операції. А ще часто оптимізують сам JSON, скорочуючи назви полів та констант до одного символа.

  • У вас все примеры до пятого не прошли бы code review, а написать такое можно только будучи низкоквалифицированным специалистом и/или большой спешке и потом не читать. Поэтому, это скорее обучение как нужно писать код в целом, а не про оптимизацию алгоритма.
  • Ипользовании сторонней библиотеки, где нативная конструкция занимает столько же места это антипатерн. В последнем примере у вас лишняя операция (создание массива с ключами) — по ключам объекта можно итерировать и пушить в массив уже агрегированные данные.
  • Зачем нужна оптимизация если основная задача веб-сервера — IO, в реальных системах, первый шаг при создании/оптимизации будет выделение CPU bound операций в отдельный сервис, иначе, получается выполнение различного рода задач в рамках одного процесса и этот процесс будет заведомо хуже масштабируем.
  • Выбор данных очень неудачный, мало того что небольшой по объему, так еще и обновляется раз в час. Это уже ETL процесс, можно написать скрипт на любом языке и в статике хранить результат.
  • Как связаны деревья поиска с данной задачей?
  • Горизонтальное масштабирование сервера == оптимизация CPU bound алгоритма?
не прошли бы code review,
будучи низкоквалифицированным специалистом и/или большой спешке и потом не читать

Дуже суб’єктивні твердження. Дайте об’єктивні метрики, щоб можна було почати діалог.

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

Конкретніше

В последнем примере у вас лишняя операция (создание массива с ключами

Затегайте код, напишіть, як має виглядати за вашою версією, покажіть різницю продуктивності. Бо зараз поки суб’єктивна оцінка.

Зачем нужна оптимизация если основная задача веб-сервера — IO, в реальных системах, первый шаг при создании/оптимизации будет выделение CPU bound операций в отдельный сервис

Не завжди. Вам потрібні важкі обчислення, щоб мотивувати створення окремого сервісу. Окремий сервіс — це дорожче. Віртуалки не безплатні. Ганяти дані по мережі — це додаткова latency. Сереалізація/десереалізація також не безкоштовні і забирають процесорний час. Якщо у вас обчислення на API займають мілісекунди, то вам буде важко добитися хоч якогось позитивного ефекту, делегувавши обчислення іншому сервісу. Простіше понизити рівень складності обчислення оптимальнішими алгоритмами, або використовувати кеші різного рівня

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

Невдалий для чого? Для контексту моєї задачі і прикладів, які я описую — в самий раз, адже можна легко помітити різницю в часі виконання між різними версіями алгоритму. «небольшой по объему» — почитайте коментар Roman Pavlyuk про 1000 елементів та кубічну складність.

Как связаны деревья поиска с данной задачей?

В однїй з версій алгоритму я роблю пошук по масиву і далі в статті розказую, як можна робити швидкий пошук. BST є частиною цієї розповіді.

Горизонтальное масштабирование сервера == оптимизация CPU bound алгоритма?

— ні. Це дуже різні речі. Крім горизонтального, існує ще й верикальне маштабування. А ще, якщо говорити про мікросервіси, існує Z-маштабування. Про маштабування ви можете прочитати на вікіпедії en.wikipedia.org/wiki/Scalability. Ну і ще б я вам дуже порекомендував прочитати Patterns of Enterprise Application Architecture. У цій книзі Фаулер пояснює про властивості розподілених систем, і як іх варто проектувати, щоб не погіршити загальну продуктивність системи.

Дуже суб’єктивні твердження. Дайте об’єктивні метрики, щоб можна було почати діалог.

Тобто ви вважаєте, що такий спосіб ітерації по масиву це нормально?

while (source.length > 0) { source.splice(0, 1); }

Ваша перша оптимізація заключалася в виклученні бібліотекі та заміну її на нативний код, чому вас дивує ствердження:

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

Далі ви використовуєте lodash для простих операцій, котрі теж можно замінити на нативний код.

В последнем примере у вас лишняя операция (создание массива с ключами
Затегайте код, напишіть, як має виглядати за вашою версією, покажіть різницю продуктивності.
const dates = Object.keys(groupedByDate);
const meanTemperaturesByDate: { date: string, meanTemperature: number }[] =
dates.map(date => {
const temperaturesInOneDay = groupedByDate[date];
return {
date,
meanTemperature: _.meanBy(temperaturesInOneDay, item => item.temperature)
}
})

Можно замінити на:

const meanTemperaturesByDate = [];
for (const date in groupedByDate) {

const meanTemperature = groupedByDate[date].reduce((a,b) => a + b) / groupedByDate[date].length

meanTemperaturesByDate.push({ date, meanTemperature })
}

Але все це не оптимізація, а написання логічного кода з використанням структур данних та інструментів які є в цій мові програмування.

Ви намалювали «сферичного коня в вакуумі» для сладной сістемі спростивши її у зручний вам спосіб, тому всі ці запитання й з’явилися. Чому ви вичитуєте у пам’ять вихідний JSON, хоча серелізація цього об’єкту є самою затратною операцією і JSON.parse блокує Event Loop? Чому на останьому етапі підіймаєте ще один сервіс, коли даже с першим варіантом кода та кешем можно було б збільшити показники відповіді в рази по відношенню з останнім кодом? Чому ви взяли js код як приклад оптимізації, коли вся оптимізація трапляеться в ньому under the hood і метрики продуктивності дуже залежать від системи та способа вимірювання?

Тобто ви вважаєте, що такий спосіб ітерації по масиву це нормально?

while (source.length > 0) { source.splice(0, 1); }

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

Можно замінити на:

Та можна, але переважна більшість людей, які не працюють з JS, не зловить сходу, що через reduce шукаємо суму. Я б все ж хотів, щоб стаття принесла користь якомога більшому колу читачів.

Ви намалювали «сферичного коня в вакуумі» для сладной сістемі спростивши її у зручний вам спосіб, тому всі ці запитання й з’явилися.

Так в цьому ж і суть: коли ви робите тестову площадку, ви ізолюєте її від всіх сторонніх впливів і досліджуєте тільки ті характеристити, які вам цікаві. Якщо я хочу показати, що видалення ементів зі спистку забирає час, то навіщо мені робити запити у базу даних, або включати час парсання JSON? Мій фокус — список.

Чому на останьому етапі підіймаєте ще один сервіс, коли даже с першим варіантом кода та кешем можно було б збільшити показники відповіді в рази по відношенню з останнім кодом?

Кеш не допоможе, якщо всі запити будуть різні. Я думав спочатку додати від 100 до 1000 різних JSON для різних міст, але вирішив, що буде очевидно, що раз нова версія працює скоріше з одним однаковим файлом, то вона буде працювати так само і для 1000 різних файлів.

Добре, припустимо, що задача побудувати сервис, який би отимував данні зі сторонього ресурсу для 1000 міст раз на годину та робив по ним агрегацію. Доречі, для работи з большою кількостью за об’ємом та трафиком данних, що требо бистро серелізувати/десерелізувати, Nodejs не дуже підійде, бо це CPU bound EventLoop блокуючий процесс.

Якщо грубо підрахувати:
Розмір файла приблизно 3.3мб у запакованому вигляді приблизно 200кб(цифри отримав з браузеру). Загрузка одного файлу з ресурсу якщо встановлювати з’єднання то > 800 мс у Firefox. Для простоти вважаемо що разпаковка файла 0 мс, далі йде парсинг JSON.parse > 100 мс (прогнав пару раз на локальной машині с данними) далі логіка 2-176 мс (сюди вже включено JSON.stringify < 1 мс)(зі статті).

При прочих сталих в найгиршому випадку маємо: (800 + 100 + 176) * 1000 / (1000 * 60) ≈ 18 хвилин, а для найкращого: (800 + 100 + 2) * 1000 / (1000 * 60) ≈ 15 хвилин.
Це все в разрахунку для синхронного коду.

З цифр випливае наступна оптимізація по порядку:
1) Тримати відкрите підключення, чи пул підключень до сервера
2) Змінити формат данних, щоб уникнути парсинга великого за об’ємом JSON (наприклад стрімити чанки JSON/CSV)
3) Оптимизувати алгоритм, якщо це стало bottleneck
4) Замінити Nodejs на більш «продуктивний» сервер чи змінити подхід до агрегації данних (наприклад використовувати спеціалізовані БД)

Но зі статті випливає, що єдиною оптимізацією є алгорітм.
Вся «оптимізація» в таких випадках, це ефективно використання особливості JS, що основною структурою буде завжди хеш таблиця (не має значення чи то об’єкт чи його похідна — массив).

О, коли вже якісь цифри і формули, то вже можна предментно поговорити.
Але давайте я спрочатку покажу деякі результати, того, що було відбулося на практиці.
Я створив Azure сторе і залив туди JSON 3.3 мб.
Тоді додав CDN, він цей файлик зжимає через gzip і маємо 200кб. Відповідь приходить за 300 мілісекунд, тому я в коді ще додатково, що чекаю, щоб було 800 як у формулі.

  async v7(): Promise<Result> {
    const start = new Date();
    const response = await axios.get('https://weather-dou.azureedge.net/weather/hourly.json', {
      headers: {
        'Accept-Encoding': 'gzip'
      }
    });

    const responseTime = new Date().getTime() - start.getTime();
    await this.timeout(responseTime < 800 ? 800 - responseTime : 0);

    const groupedByDate: { [day: string]: IWeatherItem[] } =
      _.groupBy(response.data.data, item => item.time.substring(0, 10));

    const dates = Object.keys(groupedByDate);

    const meanTemperaturesByDate: { date: string, meanTemperature: number }[] =
      dates.map(date => {
        const temperaturesInOneDay = groupedByDate[date];
        return {
          date,
          meanTemperature: _.meanBy(temperaturesInOneDay, item => item.temperature)
        }
      })

    return new Result(response.data.data.length, meanTemperaturesByDate, start);
  }

  private timeout(milliseconds: number) {
    return new Promise(resolve => {
      setTimeout(resolve, milliseconds);
    });
  }

Коли запускаю один запит, у мене ось таке результати:

{
"count": 8784,
"memoryUsed": "25.26Mb",
"processingTime": "806ms",
"pid": 79264,
"meanTemperaturesByDate": [
{
"date": "2019-01-01",
"meanTemperature": 8.441666666666663
},
{
"date": "2019-01-02",
"meanTemperature": 5.054166666666666
},

Тепер я запускаю навантажувальний тест, в якому кожної секунди приходять 100 користувачів і розблять один запит. Користувачі приходять на протязі 10 секунд, тобто у нас буде 1000 запитів. Нагадаю, що в коментарі вище ми будемо очікувати, що запити будуть виконуватися близько 15 хвилин.

Запускаємо тест, дивимось, що практиці.

Started phase 0, duration: 10s @ 11:11:42(+0300) 2020-07-28
...
Report @ 11:12:24(+0300) 2020-07-28
Elapsed time: 43 seconds
  Scenarios launched:  0
  Scenarios completed: 2
  Requests completed:  2
  Mean response/sec: NaN
  Response time (msec):
    min: 39672.2
    max: 40115.8
    median: 39894
    p95: 40115.8
    p99: 40115.8
  Codes:
    200: 2

All virtual users finished
Summary report @ 11:12:24(+0300) 2020-07-28
  Scenarios launched:  1000
  Scenarios completed: 1000
  Requests completed:  1000
  Mean response/sec: 23.47
  Response time (msec):
    min: 803.4
    max: 40115.8
    median: 9270.9
    p95: 19747.3
    p99: 26210.4
  Scenario counts:
    0: 1000 (100%)
  Codes:
    200: 999
    500: 1

44 секунди. Не 15 хв, а 44 секунди.
Я можу погодитись, що якби у версії 7, я б використовував першу весію алгоритму, то це б зайняло на 3 хвилини довше, тобто майже 4.

Висновок, навіть коли ми підлючаємо мережу, програма під навантаженням для оптимального алгоритму виконується майже в 4 рази скоріше.

Чому так, а не 15 хвилин, як було припущено у попередньому коментарі. Нода виконує операції Event Loop в одному потоці. Але це не означає, що I/O операції також повинні виконуватися в одному потоці. Нода використовує багатопоточність, але вона схована від розробника.

На 43 секудні у нас 2 закінчених запити, а вже на 44 всі запити закінченні. Це тому, що решта 988 запитів були в процесі виконання. Вони разом качали майже 200мб JSON.

(800 + 100 + 2) * 1000 / (1000 * 60) ≈ 15 хвилин.
Це все в разрахунку для синхронного коду.
З цифр випливае наступна оптимізація по порядку:
1) Тримати відкрите підключення, чи пул підключень до сервера
2) Змінити формат данних, щоб уникнути парсинга великого за об’ємом JSON (наприклад стрімити чанки JSON/CSV)
3) Оптимизувати алгоритм, якщо це стало bottleneck
4) Замінити Nodejs на більш «продуктивний» сервер чи змінити подхід до агрегації данних (наприклад використовувати спеціалізовані БД)

Цікавий висновок. Спочатку показати, що в нас 800 — це найбільший таймаут (сторонній API + мережа), а потім сказати, «4) Замінити Nodejs на більш „продуктивний“ сервер».

далі йде парсинг JSON.parse > 100 мс (прогнав пару раз на локальной машині с данними)

Ну я теж поміряв

    const start = new Date();
    const obj = JSON.parse(jsonStr);
    console.log(`${new Date().getTime() - start.getTime()}ms`, jsonStr.length);

11ms 3756752
10ms 3756752
13ms 3756752
10ms 3756752
11ms 3756752
12ms 3756752
13ms 3756752
10ms 3756752

Може ви з диску читали файл, або десь з мережі качали?

Но зі статті випливає, що єдиною оптимізацією є алгорітм.

Стаття про алгоритми. У статті я розповідаю, як підняти продуктивність алгоритмічно. Стаття не про бази даних, кеші, мережу і так далі. Я не розповідаю про бази, кеші і мережу, а розповідаю про алгоритми, бо про це стаття, то з цього аж ніяк не випливає

Но зі статті випливає, що єдиною оптимізацією є алгорітм.

Версія 7 на гітхабі. Хто бажає, можете спробувати у себе самі.

const start = new Date();
const obj = JSON.parse(jsonStr);
console.log(`${new Date().getTime() - start.getTime()}ms`, jsonStr.length);

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

Відповідь приходить за 300 мілісекунд

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

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

файла приблизно 3.3мб у запакованому вигляді приблизно 200кб
Тоді додав CDN, він цей файлик зжимає через gzip і маємо 200кб.

Насчет моих расчетов:

(800 + 100 + 2) * 1000 / (1000 * 60) ≈ 15 хвилин.
Це все в разрахунку для синхронного коду.

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

З цифр випливае наступна оптимізація по порядку:
1) Тримати відкрите підключення, чи пул підключень до сервера
2) Змінити формат данних, щоб уникнути парсинга великого за об’ємом JSON (наприклад стрімити чанки JSON/CSV)
3) Оптимизувати алгоритм, якщо це стало bottleneck
4) Замінити Nodejs на більш «продуктивний» сервер чи змінити подхід до агрегації данних (наприклад використовувати спеціалізовані БД)
Цікавий висновок. Спочатку показати, що в нас 800 — це найбільший таймаут (сторонній API + мережа), а потім сказати, «4) Замінити Nodejs на більш „продуктивний“ сервер».

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

Нода виконує операції Event Loop в одному потоці. Але це не означає, що I/O операції також повинні виконуватися в одному потоці. Нода використовує багатопоточність, але вона схована від розробника.

Все же мне кажется, что основное преимущество Nodejs — это асинхронность, а не многопоточнось.

Можете мне ответить на одни вопрос. Нужно ли столько «оптимизировать» если изначально оталкиваться в написании кода на Nodejs от неких парадигм, например:
1.

основною структурою буде завжди хеш таблиця (не має значення чи то об’єкт чи його похідна — массив).

2. Не блокируй EventLoop.
2.

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

3. Избегать вложенных циклов, где это возможо (Плоское лучше, чем вложенное — The Zen of Python, by Tim Peters).

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

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

Я і не намагався вам нічого заперечувати. Просто сказав, що я відтворив теж саме, про що ви говорили, 1 в 1.

оталкиваться в написании кода на Nodejs от неких парадигм, например:

1.

основною структурою буде завжди хеш таблиця (не має значення чи то об’єкт чи його похідна — массив).

.
— ні. у випадку об’єкта — це буде хеш таблиця. у випадку Array — буде List. ryanpeden.com/...​rays-work-under-the-hood.
2. +
2.5 про антипатерн. ну +/-. якщо вже є підключений лодаш, і хтось напише _.sumBy замість нативної reduce, ну мені важко сказати, що це погано. з одного боку користуватися нативними функціями — це добре, з іншого sumBy явно каже, що ти робиш. не готовий відповісти, +/-
3. + до вкладених циклів. +/- «Плоское лучше, чем вложенное» — ну а якщо є дерево, чи хеш табилця має вкладені масиви, чи навіть матриця — це все певного роду вкладення.

Нужно ли столько «оптимизировать» если изначально оталкиваться в написании кода на Nodejs от неких парадигм, например:

Хтось казав, не пригадаю хто, що немає поганих алгоритмів — є неоптимізовані. Слідувати певним парадигмам — це необхідка ознака оптимального алгоритму, але не достатня. «Нужно ли столько „оптимизировать“» «столько» залежить від початкових requirements, від середовища, де буде виконуватися програма, від навантаження і так далі. «столько» — це можуть бути супер оптимізовані алгоритми для людини, яка їх пише сходу, бо добре володіє ними. Не завжди оптимальні алгоритми вимагають надзусиль. Якщо ви володієте базовими речами, то ви будете писати оптимальні алгоритми не докладаючи до цього особиливих чусиль, але це не буде тому, що ви слідуєте парадигмам, а тому, що ви розумієте, що робите, а не робити здогадки про це.

Bottom line — парадигми потрібні, але їх не завжди достатньо

основною структурою буде завжди хеш таблиця (не має значення чи то об’єкт чи його похідна — массив).

.
— ні. у випадку об’єкта — це буде хеш таблиця. у випадку Array — буде List. ryanpeden.com/...​rays-work-under-the-hood.

Да верно, забыл об этом:
PACKED_SMI_ELEMENTS — a packed integer array
PACKED_DOUBLE_ELEMENTS — a packed double array
PACKED_ELEMENTS — a packed object array
HOLEY_SMI_ELEMENTS — a sparse integer array
HOLEY_DOUBLE_ELEMENTS — a sparse double array
HOLEY_ELEMENTS — a sparse object array
DICTIONARY_ELEMENTS — a very sparse array that is backed by a dictionary

И собственно еще одно правил:
4) По возможности, данные в JS массиве должы быть однородны

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

Представим себе, что задача оживить проект после того, как там порезвилась толпа обезьян любой национальности. Будет иметь значение подобная критика «попередників»?

первый шаг при создании/оптимизации будет выделение CPU bound операций в отдельный сервис

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

Автор в мене є декілька запитань до вас з приводу статті, чи не могли б ви залишити свою пошту чи додати мене в linkedin

Сервіс буде запущений на Node.js. Всі запити будуть опрацьовуватися в Event Loop

Ось тут помилка в ДНК.

Поясніть, що мається на увазі, будь ласка.

Очевидні (бувають і не очевидні, якто розбір JSON та валідація вхідних даних) розрахунки в Event loop свідчать про помилку в ДНК розробника або архітектора.

А, ось що малось на увазі. Node.js не для CPU intensive операцій, а для I/O intensive. Якщо написаний неоптимальний алгоритм, то він якраз і спричиняє ці CPU intensive операції, та призводить до блокування обробки наступних запитів. На початку статті якраз і описаний такий CPU intensive алгоритм, який займає на виконання одного запиту 174 мілісекунди. В кінці ж статті час виконання запиту лише 2 мілісекунди.

розрахунки в Event loop свідчать про помилку

Вони свідчать про милку, якщо вони CPU intensive. Якщо ваш API робить прості перетворення, або певну агрегацію даних — це також розрахунки. І це повністю ок, якщо він робить їх швидко. Не всі розрахунки однакові.

Как поможет ДНК разработчика/архитектора, ориентированного на много-поточность при выполнении задачи с временем выполнения в 1 сек?

Яка різниця 1 сек чи п’ять годин? Все в чергу.

Да вы правы — особо нет никакой разницы между многопоточным сервером и циклично-событийным на CPU с 1 core.

Вообще сервера с циклично-событийной моделью более эффективно используют ресурсы на железе со современными CPU, чем сервера с многопоточной моделью. Как минимум тратится значительно меньше времени на переключение между контекстами потоков и код чаще читает данные из кэша памяти CPU. Я не сильно силен в nodejs, но можно запустить несколько процессов nodejs, которые будут работать на указанных ядрах. На других платформах это решается в виде запуска нескольких циклов в разных потоках.Переход на событийно-цикличную модель может сэкономить десятки процентов производительности. Конечно, это не имеет смысла делать для слабо нагруженных серверов — до 100 одновременно работающих пользователей. Экономия будет мизерной, а затраты на создание и поддержку будут значительными. А если одновременно работающих пользователей будет пару сот тысяч, то экономия может выливаться в сотни тысяч, миллионы $.

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

Усі формули у теорії масового обслуговування (вона ж Queue theory). Та сама помилка в ДНК не дозволить прочитати теорію.

Помилка в ДНК в того, хто застосовує теорію, не розуміючи методи застосування теорії до практики. Нічого крім швидкости сферічних коней він не отримує.

Разве в js есть настоящий массив?

Есть еще interpolation search, его сложность в лучшем случае O(log(log(N)), для вашей задачи должен подойти. Но мне кажется что массив в js это хорошо спрятанный хешмап, поэтому не уверен что там есть смысл в таких алгоритмах.

Так, ви праві — в JS справжнього масиву немає.

Те, що JavaScript називають масивом (array), насправді є списком (list), оскільки його довжина може змінюватися.

А HashMap — це звичайний об’єкт, або Map. Map оптимізованіший для частих вставок та видалень. А ще, в Map ключами можуть бути не тільки стрічки.

Есть еще interpolation search, его сложность в лучшем случае O(log(log(N)),

Не чув про нього, обов’язково пререгляну. Дякую!

А можно лінк де написано, що масив у JS це не об’єкт.

Ви такого лінка не знайдете. Масив в JS — це об’єкт. Думаю в С масив не можна назвати об’єктом.

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

Зато струтктуры есть :)

Хеш-функція має працювати таким чином, щоб генерувати hash, значення якого буде менше за довжину масиву

Ничего подобного, позиция в массиве это «hash(key) % length» где длинна массива как правило простое число. При определенном количестве добавленых в хеш элементов происходит перестройка этого массива в новый с большим размером.

Знаючи лише результат функції b, має бути складно вирахувати оригінальний набір вхідних даних a

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

Ничего подобного, позиция в массиве это «hash(key) % length» где длинна массива как правило простое число. При определенном количестве добавленых в хеш элементов происходит перестройка этого массива в новый с большим размером.

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

www.cs.princeton.edu/...​lectures/34HashTables.pdf
Designing a hash function
Required properties. [for correctness]
・Deterministic.
・Each key hashes to a table index between 0 and m — 1.

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

Для хеш-колекції — так, зайве. Тим не менше, це важлива ознака хеш-функцій, тому варто про неї згадати. Багато хто знає, що паролі в базі даних хешуються. І як ви вже згадали, тут ця властивість — важлива.

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

Так в цьому була і суть статті: розказати, як вони всередині працюють )).

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

Я понял, у нас тут два разных понятия что такое хеш-функция. В академическом понятии — да, значение хеша должно ложиться в интервал нашего массива. А беря во внимание обычный коддинг в ООП когда код хеш-коллекции и обьектов лежаших в коллекции разделен, то для «override getHashCode» нет никакого ограничения на диапазон значений, так как тут мы не имеем никакого представления о длине массива (по ваше ссылке пример на 12 стр такой хеш-функции). А позиция в массиве хеша равна key.getHashCode()%length.

Ничего подобного, позиция в массиве это «hash(key) % length» где длинна массива как правило простое число.

Во-первых, вы придираетесь к излишне, может быть, вольной в общем случае, но вполне пригодной формулировке. Да, хэш-функция объекта обычно сконструирована для генерации числа в очень больших пределах (32 или 64 бита), а уже для конкретной мапы она урезается. Но если понимать как уже урезанную, то для данной статьи более чем достаточно.
Во-вторых, «втискивание» через остаток от деления — не единственный вариант — бывает, например, что берут набор битов не с самого младшего.
В-третьих, про «позицию в массиве» справедливо только для closed addressing, который хоть и самый распространённый вариант, но не единственный и не лучший — почему-то самые эффективные реализации обычно оказываются на open addressing, несмотря на то, что теоретически они значительно сложнее обосновываются, и реализации сильно капризнее к деталям. Стандартная closed-addressing на остатке от деления на простое число, и с полной перестройкой за одну операцию, в мире хэш-таблиц это как сделанная одним топором табуретка среди всех видов мебели — надёжно, но слишком неказисто. А есть ещё и варианты с деревом таблиц...

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

Нет, не лишнее. Почитайте про атаки на переполнение конкретных корзин хэш-таблиц и почему, например, в Python введён такой параметр, как PYTHONHASHSEED.

Если придираетесь к теории, то постарайтесь вначале сами узнать в объёме больше одноминутного чтения.

По поводу изучения алгоритмов, посоветовали бы лучше книгу от Роберта Седжвика — фундаментальные алгоритмы на C или Java.

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

Если уж начали холивар на тему литературы, то советую «Абстракция данных и решение задач на С++», реально классная книга

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

Во время собеседования вы подробно рассказываете о предметной области и об используемых алгоритмов в веб-сервисе?

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

Это похоже на поведенческое интервью, как вы поймете технические навыки кандидата.

Це насправді значно більше каже про кандидата, ніж коли задаєш точкові питання. Наприклад, мене цікавить CAP теорема і які наслідки з неї випливають. Нехай ми спілкуємось в контексті онлайн магазину. Замість того, щоб прямо запитати про CAP теорему, я скажу щось таке «а якщо тепер бізнес розширюється і вам потрібно розподілити вашу систему між декількома континентами на планеті, з якими проблемами ви зіткнетеся?» Якщо він сам задетектить, що потрібно буде пожертвувати або Availability, або Consistency, або шукати якийсь між ними баланс, то це в рази краще, ніж він просто дасть мені визначення теореми, чи розкаже наслідки. А ще, якщо він запитає, чи залишиться один склад, чи будуть окремі склади для кожного регіону, це взагалі круто, бо він скоріш за все розуміє, що таке Data Sharding. Це говорить про те, що такі речі він приймає до уваги, коли розробляє рішення, а не просто знає, що таке десь є. Або, наприклад, мене цікавлять SQL Isolation levels. Замість того, щоб попросити перерахувати рівні, я запитаю щось таке: «Якщо мені потрібно максимально швидко дізнатися, скільки приблизно кожного виду товарів залишилось, як це зробити?» Те, що він почує «приблизно і максимально швидко», і зробить висновок «ага, значить транзакції можна читати незакоміченими» скаже значно більше, ніж якщо він знає про рівні ізоляції, але навіть не припускає, що можна використовувати щось інше, ніж Read Commited. Я можу продовжити історію і запитати, а якщо мені такі дані потрібно дуже часто. І ми переключаємось на кеші. І так далі.

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

Тезис говорить про те, що кандитат принаймі розглядає можливість покращення продуктивності програми через використання інших алгоритмів. Це є дуже важливим, оскільки він піддає критиці програмкий код, а не каже відразу, що хочете більше продуктивності, ставте більше оперативки, або додавайте більше віртуалок.
Якщо бути точним, я використовую «оптимальніших», а не «оптимальних».

оптимальніших алгоритмів

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

Ну если предположить что алгоритмы в программе кодил не интерн, то их оптимизация как раз должна быть после оптимизации запросов к БД (индексы) и кеширования. Алгоритм оптимизировать, если программист специально не тренировался это делать (читай олимпиадник), займёт дольше по времени и усилиям чем другие способы. Иногда даже увеличение мощности сервера может быть «дешевле» (если речь не о проекте где сервера уже не одну сотню долларов в месяц обходятся)

Спочатку був DB First підхід. Всю логіку писали в сторед процедурах. Простий API, який тільки вмів викликати базу і віддавати результат на фроненд.
Потім прийшов Code First. Пишемо бекенд, а тоді вибираємо базу або навіть набір баз данних, які нам підходять. Фокус не на данних, а на тому, що з ними можна робити.
Зараз UI First. Проектуємо складні процеси на UI, потім робимо декілька бекендів (microservises, serverless), а тоді під бекенди вибираємо бази данних.
Я це пишу до того, що бекенд має диктувати базі, які там мають бути індекси. Добре оптимізуєте бекенд, а тоді вже оптимізуєте базу під його потреби. При чому під різні потреби можна зробити різні бази даних: одна на читання, а друга на запис — CQRS

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

чого це маштабування, кеші і т.д. стали засобами підвищення продуктивності? Як Ви взагалі визначаєте продуктивність? продуктивність по визначенняю це єфективне використання ресурсів. www.google.com/...​&sourceid=chrome&ie=UTF-8
А маштабування і т.д. просто додають додаткові ресурси а не дозволяють використати ефективніше вже існуючі

Продуктівність — це скільки одиниць система може обробити за певний проміжок часу. Це кількісна характеристита. Єфективність — це вже якісна, тобто на скільки ефективно в порівнянні з іншою системою вона використовує ресурси. Якщо є два автомобілі і вони можуть на одному баку проїхати 1000 кіломентів, то їх продуктивність однакова. Але якщо один з них потратить на 20% менше пального, то він ефективніший. Якщо одна система за хвилину може обробити 10,000 запитів, а інша тільки 9,000, то перша продуктивніша, ніж друга. Але якщо друга система потребує один сервер, щоб обробити 9,000 запитів, а перша 2 таких самих серверів, щоб обробити 10,000, то друга ефективніша.

Є productivity and performance and efficiency. І наведене визначення

Продуктівність — це скільки одиниць система може обробити за певний проміжок часу.

 це визначення performance а не productivity

Ну але я і не хотів сказати Productivity. Я хотів сказати Performance. Гугл як і я прекладає Performance як Продуктивність. translate.google.com.ua/...​k&text=system performance

Гугл транслейт тут не еталон. Він productivity and performance перекладає однаково. А ось значення різні.Введіть обидва слова і результат буде дивним для українського і російського перекладу translate.google.com/...​ductivity and performance

я —

Продуктивність — це скільки одиниць система може обробити за певний проміжок часу.

ви —

це визначення performance

ви —

чого це маштабування, кеші і т.д. стали засобами підвищення продуктивност

тому що вони дозволяють обробляти більше запитів за певний проміжок часу. Я весь час говорив про performance, український переклад — продуктивність.

А я вам весь час намагаюся пояснити що ці 2 різних поняття перекладаються одним словом і що заголовок статті в вам саме про ефективність і productivity а в передмові це вже вкупі з загальним performance системи іде. Якби то було написано англійської то питань не виникло б. А так вийшло не дуже

Як прискорити код з 15 до 1000 запитів за секунду
Продуктивність — це скільки одиниць система може обробити за певний проміжок часу.

Було 15 за одиницю часу, а стало 1000. Код став продуктивніший. Так він став ефективніший, бо використовує менше процесорних ресурсів для обробки одного запиту, але «було 15 стало 1000» говорить прямо про продуктивність і непрямо про ефективність. Саме про продуктивність прямо сказано у заголовку цієї статті.

продуктивність по визначенняю це єфективне використання ресурсів. www.google.com/...​&sourceid=chrome&ie=UTF-8
А маштабування і т.д. просто додають додаткові ресурси а не дозволяють використати ефективніше вже існуючі

Ні, це визначення є не вірним. Не можна ототожнювати «продуктивний» і «той, що ефективно використовує ресурси». Продуктивність може бути досягнута і неефективним використанням ресурсів. Завод може підвищити свою продуктивність (випускати більше товарів в місяць) тим, що робітники будуть працювати у 2 зміни, а може роботизувати процес виробництва. Ви ж не скажете, що подвійна робоча зміна — це ефективно? Тим не менше, раз завод витустить в місяць більше товарів, він працював продуктивніше, ніж попередній місяць. Як я вже писав і ви з цим погодилися «продуктивність — кількісна характеристика, а ефективність — якісна».
Те ж саме з автоматизованими системами: мені потрібно більше запитів в секунду (більше продуктивності), я ставлю або більше віртуалок (не дуже ефективно), або покращую алгоритми (більш ефективно), якщо це можливо. І збільшення кількості віртуалок, і покращення алгоритмів впливають на продуктивність системи, але покращення алгоритмів не вимагає додаткових процесорних ресурсів, що є більш ефективно.
Переходимо по вашому ж посиланню (продуктивність визначення). Перші посилення реферат і вікіпедія — скіпаємо. Далі
bakertilly.ua/news/id46342 Продуктивність і ефективність: в чому різниця?
Вже ніби як наштовхує на думку, що ці поняття не тотожні.
«Хоча продуктивність і ефективність іноді сприймаються як синоніми, насправді мають два різні значення. Ці поняття переплетені, але між ними є важлива відмінність, яка значно впливає на те, як виконується робота.»
«Словникове визначення продуктивності таке: ефективність продуктивних зусиль, особливо в промисловості, вимірюється в одиницях продуктивності. Іншими словами, якщо ви видали 1 000 одиниць за тиждень і 1 100 одиниць на наступному, то другий тиждень був продуктивнішим.»
«Ефективність же полягає в тому, щоб працювати розумніше, а не старанніше. Якщо ви працюватимете більш організовано і компетентно, то зможете виконати завдання швидше, ніж зазвичай. Наприклад, якщо можете написати пост на 600 слів за 30 хвилин замість 40, ви підвищите свою ефективність.»
Отже, продуктивність — фіксований час, але кількість вироблених одиниць за цей час різна. Ефективнісь — кількість вироблених одиниць фіксована, а час різний.
Повертаємось до заголовку «15 за секунду і 1000 за секунду» — що з цього фіксоване, одна секунда, чи 15 і 1000? Про що стаття: про продуктивність (фіксований час, одна секунда), чи ефективнісь? Якби ця стаття була про ефективність, то загаловок був би «Як прискорити код опрацювання 1000 запитів з 10 хвилин до 1 секунди».
Ну і твердження «Performance і Productivity перекладаються однаково на українську, як Продуктивність». Тобто вигадати нове слово в українській мові, яке буде означати Performance, але не буде означати Productivity? Я б розумів, якщо стаття була на англійській і ви б сказали, що я замість Productivity, я вживаю Performance. Але в українській мові є одне слово — Продуктивнісь. Якби було ще якесь, то ви б його назвали, а не говорили відповідники з англійської.

От бачите скільки тексту іде в вас на пояснення що малося на увазі? А я лише вказав на неоднозначність одного визначення. А потім на співбесіду оцінюєте

відповідь є правильною, але неповною

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

А потім на співбесіду оцінюєте

відповідь є правильною, але неповною

Тобто, якщо людина каже правильну відповідь, але можливо не каже якусь деталь, то ви таку відповідь зараховуєте, як неправильну? Ви не задаєте уточнюючі питання? Людина банально може просто забути про якусь деталь згадарти, а ви вже ставите їй мінус, замість того, щоб уточнити.

Мені звичайно дуже імпоную підхід в пошуку «визначення продуктивності»

Перші посилення реферат і вікіпедія — скіпаємо.

а потім пошуком того що підтверджує вашу думку. Але.. давайте всеж таки повернемося до вікіпедіі. Наприклад подивіться як перекладена стання про «якість ПЗ» uk.wikipedia.org/...​_програмного_забезпечення

Продуктивність (efficiency) або ефективність. Здатність ПЗ при заданих умовах забезпечувати необхідну працездатність стосовно виділюваного для цього ресурсам. Можна визначити її і як відношення одержуваних за допомогою ПЗ результатів до затрачуваних на це ресурсів усіх типів.
Часова ефективність (time behaviour). Здатність ПЗ видавати очікувані результати, а також забезпечувати передачу необхідного об’єму даних за відведений час.

Не будемо сперечатися про коректнісь всього того і т.д. Але коли ви спількуєтеся з іншими людьми термінологія має розумітися однаково. Тут є факти що вона різна і не однозначна. А ви з самого початку підходите з позиціі «є моє і є непривильне». Ви використали терміни які звучать солідно, але створюють неоднозначність а потім пишите «відповідь правильна але не повна...». Можливо це не реальний випадок а літературний прийом, але це технічна стаття а не твір з літератури. От для чого писати «як можна підвищити продуктивність роботи вебсервісу?» якщо насправді ви питаєте про методи як збільшити «requests per seconds» цілоі системи

Ну, ну, вже підміни понять не достатньо, будете підміняти лінки? :) Оригінально ви скинили ось цю лінку www.google.com/...​&sourceid=chrome&ie=UTF-8.
У видачі:
Продуктивність та продуктивність праці: сутність та ... Реферат
Продуктивність — Вікіпедія
Продуктивність праці — Вікіпедія
Продуктивність і ефективність: в чому різниця? — Baker Tilly

Ви хотіли, щоб я не скіпнув реферат і вікіпедію і ми почали говорити про продуктиність праці?

Стаття, яку показуєте ви зараз:
Якість програмного забезпечення — Вікіпедія. Її у видачі не було, оскільки тоді ви гуглили «продуктивність визначення»

Продуктивність (efficiency) або ефективність

І знову ж ваші слова

Є productivity and performance and efficiency.

Або зараз вікіпедія не права, або ви тоді були не правий.

Російською можна відрізнити: производительность (performance) // продуктивность (productivity).
Може, для української теж знайдеться слово...

Як часто я чую «чому ви в своєму гуглі питаєте ці алгоритми, я сіньор, працюю в індустрії 10+ років і жодного разу їх не використовував». Насправді дійсно здивований цією статтею — такі речі зазвичай досить важко пояснювати і їх розуміє в основному тільки ті люди, які вже використовували алгоритмічні/DS оптимізації (або життя заставило або TL :)). Тому той факт що це питають вже показує нерозуміння і я зазвичай навіть не починаю пояснювати :)

Єдине що я б додав — це алгоритмічні оптимізації для p50, p95 — тут є деякі тонкощі які впливають на реальний результат (проблема з однорідністью load testing-а наприклад).

В 2008-му один з наших синьйорів написав алгоритм складності N в кубі.

Приїхала баржа на 1000 позицій — тести таких об’ємів не покривали (на проекті були зроблені майже всі з можливих організаційних помилок на початку, і потів він героїчно запустився в дедлайн. А дедлайн був проголосований парламентом, і за затримки були штрафні санкції).

Розмитнення баржі, яка прибула на благословенний острів Джерзі, стало затягуватися приблизно до другого пришестя. Дебагер (а ми з ПМом сиділи на об’єкті перші два тижні впровадження) через 30 хвилин відвалювався за таймаутом.

Вже не пам’ятаю, як ми це тоді обійшли, до чого там був дебагер (щось на льоту підправляли на сервері). Баржа поїхала, клієнт ніби досі щасливий, але моя довіра до людей з того часу не відновилася.

тести таких об’ємів не покривали

Как же так вышло? Если не автотесты, то хотя бы вручную тестировать на больших объёмах данных нужно

Суть алгоритмів в тому, що їх або використовують у проектах (і вони дійсно там потрібні), або ні. І для вакансій/обов’язків, за відомим принципом, вони будуть потрібні у 20% випадків щонайбільше (в реаліях і до 5% не дійдемо). Але дебілізм реалій у тому, що коли пишуть у вакансії «знання алгоритмів», і пишуть це не HR, а «круті» розробники компанії, і далі на співбесіді вони їх не запитують, і вже сам їх питаєшь «ну то що у вас з алгоритмами у роботі?» — тут починаються цікаві запливи: ну буває, ну кастомні, ну... ну... ну... Тож як варіант перевірки гнучкості мислення/знань, реальних потреб посади/компанії у цьому і т.д. — це ок, але за умов коли люди вміють, розуміють і знають що перевіряють. В той же час розробник теж має співставляти компанію і потреби вакансії, а не свій власний попередній досвід і знання, щоб виразити свої зауваження щодо того, що не працював з алгоритмами і не буде в них потреби в саме цій компанії

в реаліях і до 5% не дійдемо

Многие с 5+ лет стажем работы не в состоянии ответить на вопрос — какая будет длина коллекции set?

class Foo {
    public int value;
    
    public Foo(int value) {
        this.value = value;
    }
    
    @Override
    public boolean equals(Object o) {
        // ...
        Foo foo = (Foo) o;
        return value == foo.value;
    }
    
    @Override
    public int hashCode() {
        return value;
    }
    
    @Override
    public String toString() {
        return "Foo(" + value + ")";
    }
}


// ...
Foo foo1 = new Foo(10);
Foo foo2 = new Foo(20);

HashSet<Foo> set = new HashSet<>();
set.add(foo1);

foo1.value = 20;
set.add(foo2);

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

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

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

в тому то і річ, що все наведене у статті було більш характерне для 2000х, коли було все більш хардкорно і з мінімальними рівнями абстракцій (реальне залізо, немає фреймворків, немає віртуалок, хмар, лімітовані тулзи, ресурси і т.д.). І тому є таке нерозуміння в плані «навіщо стільки ітерацій з оптимізації і не у тому місті, якщо є БД та інші механізми». Розуміння, що є і які є базові структури даних та алгоритми, — цьому є місце, особливо, враховуючи ваш приклад, який по суті є частиної специфікації конкретної мови програмування.

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

взагалі, то вже був частково і коментар на коментар... ну то таке;)

Cloud-и кажете, анліміт ресурсів. Цілих 2-ва Gb пам’яті і віртуальний процесор з 2-ма ядрами на тактовій 2.2. Інші ноди
по кошторису виходять як політ до Марсу, і Amazon робить із сайту більше грошей ніж господар.

у тому то і біда, що треба розрізняти мух і котлети. Оптимізувати треба на будь якій платформі. Але якщо вам потрібно реалізувати підтримку «хайлоаду» у стислий проміжок часу, то це цікаво б було поглянути зараз яккоманди розробників бігають, купують залізо, строять мережі, наливають їх, розгортають свій чудо проект і викочують у паблік

Приведенный вами пример подходит разве что для более менее прокаченого уровня, так как для большинства внутреннюю имплементацию HashSet знать не обязательно: увы, по моему опыту как правило строчка в резюме что ты работал к примеру с Redis важнее знания алгоритмов. Для 99% сеньйоров правильный ответ будет: менять поля обьекта, от которого зависит getHachCode или equals — нельзя. Ну а если позанудствовать: 1 или 2. Если для 10 и 20 внутренний алгоритм определяет один и тот же bucket (ничножно маловероятно, но все же) — то 1, иначе 2.

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

Вобще говоря по hash-code определяют цепоцку в hash-таблице. И после изменения ключы таблица не консистентна(вставленый ключ в неправельном bucket-е). Далее если hash-ы 10 и 20 будут попадать в разные цепочки то размер будет два, если же число цепочек 10, то оба ключа попадут в один bucket и при проверке на equals второй ключ будет не добавлен, и размер будет 1. Значение capacity по-умолчанию зависит от реализации, но в open-jdk 16, то есть ответ будет 1. Вцелом пример очень исскуственный, сама хеш-мапа предполагает, значение hash-code не будет менятся после вставки(иначе поиск ключа находящегося в коллекции может быть неудачен). То есть здесь приведен пример как не надо использовать hash-set, сама концепция структуры данных не расчитана на это. Соответственно все упирается в конкретную реализацию, и не факт что в следующей версии ответ на этот вопрос не изменится.

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

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

Вот написал и задумался. В языках, где есть типажи, или интерфейсы в их роли, можно ли сделать подкласс с отменой принадлежности к конкретному типажу? Или только сделать, грубо говоря, throw «нафиг» в getHashValue()?

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

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

Почему же искусственный. Я нередко наблюдал реализацию сущности с переопределенными equal и hashCode по изменяемым полям.

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

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

И при этом этот сценарий использований коректный, эти не потенциальный баг, то что кто-то так пишет, не значит что это правильно.
И что вы ждете от кандидата? Услышать 1 ил 2, скорее всего два... Как он/она может правильно ответить если не понимает сути данной структуры данных.

И при этом этот сценарий использований коректный, эти не потенциальный баг, то что кто-то так пишет, не значит что это правильно.

Не совсем понимаю, что вы подразумеваете по сценарием использования. Если use case/user story, то, например, доменная сущность может использоваться в десятках сценариев. И разработчик должен спроектировать сущность так, чтобы от изменения ее состояния ни один из этих сценариев не ломался.

И что вы ждете от кандидата? Услышать 1 ил 2, скорее всего два...

Как минимум, что так делать нельзя с объяснением почему. Как максимум, что коллекция будет в невалидном состоянии и длина коллекции будет зависеть от реализации.

Как он/она может правильно ответить если не понимает сути данной структуры данных.

Может быть кандидат подзабыл устройство хэштаблицы, но понимает как правильно использовать эту коллекцию. Или не понимает :)

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

как можно подзабыть устройство хеш таблицы?

я понимаю можно не знать все методы решения конфликтов вроде open addressing или про механизмы перестройки таблицы но сам принцип как можно «подзабыть устройство»?

я встречал уже массу наиболее популярных вариантов люди просто не понимают что такое контейнер вообще как принцип что такое ключ и что такое значение и по которому их них производится на самом деле поиск и что у вектора (массива) всё точно так же ж есть ключ а вот у связанного списка например нет реально люди

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

просто реально не слишком хорошо

но понимает как правильно использовать эту коллекцию

причём это именно как принцип они вообще не понимают что про такое даже не задумывались что именно они не понимают

ЗЫ: вот например свежий пример решался вопрос сохраняется ли и соотв. отражается ли реальная последовательность json после десериализации его в js и знаете люди вот говорят «на там преобразуется в мапу ключ-значение» а вот сказать «б» и как-то сопоставить что у мапы своей последовательности уже нет этого они уже не могут ну просто потому как

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

бугога селяви ничего личного просто бизнес

ЗЫ: самый популярный ответ «ну там хеш функция...» ну ок хеш функция и что? и что дальше? ну да ну да «кандидат подзабыл» (к) (тм)

Ситуации и люди разные бывают. Как говорится — своя душа в потемках, а чужая — так и подавно.

что у вектора (массива) всё точно так же ж есть ключ

Мне не совсем понятно, что за ключ в векторе? На сколько помню — это в с++ стандартный контейнер изменяемого массива.

что за ключ в векторе?

именно! что за ключ в векторе? и как это связано с устройством хеш мап?

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

З.Ы. если посмотреть исходинки реализации вектора в gcc, то, мягко говоря, в глазах начинает рябить. Это одна из многих причин, почему мне не зашел с++.

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

А вот тут загвоздка в том, что это у хэшмапы вообще такой последовательности нет, а в JS она есть :)
все реализации (а с какого-то момента и стандарт) держат порядок, в котором ключи добавлялись. Это не только там (в CPython в 3.6, в PyPy начиная с очень ранних), и постепенно в подобных средствах становится отраслевой нормой.
Я уже однажды видел одного коллегу, который фигел от «а как это в Java итерируется не в порядке добавления???»
И такие могут просто не сооставлять теорию со своим опытом, в котором почему-то этот порядок всегда соблюдается.

И да, от open/closed addressing, bucket collision и пр. это не зависит.

А вот тут загвоздка в том, что это у хэшмапы вообще такой последовательности нет, а в JS она есть :)

это интересно спасибо за инфу и по питону тоже! видимо это выведет дискуссию по вопросу конкретно json на новый уровень ))

В Java есть и LinkedHasMap/Set которые соблюдают порядок. Только стоит учесть что это за это придется заплатить памятью. В питоне, руби и им подобных на это сразу забили, это скриптовые языки с принципом — быстро сделать сам скрипт и решить задачу, на перформанс забить т.к. не принципиально.

Так ведь 2, хеш код foo1 на момент добавления его в хеш таблицу был равен 10-ти. Пойду Блоха перечитаю на предмет immutable классов.

жодного разу їх не використовував

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

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

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

Я просто имел в виду что в случае 2 сеньйоров где один работает над проектом в производительность не критична. Соответственно там люди вряд ли будут запариваться над какими-то овер оптимизациями и алгоритмами, работает — не трогай :). И другой кейс, где, как упомянуто в статье, улучшение перфоманса хотя бы на 10% поможет сэкономить десятки тысяч долларов и следовательно это будет довольно приоритетной задачей

Соответственно там люди вряд ли будут запариваться над какими-то овер оптимизациями и алгоритмами

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

что в случае 2 сеньйоров где один работает

... другое дело кого считать таки «синьор один» а кого «другой» и кто из них кто ))

И один и другой человек формально сеньйор.

а мне интересно в этом месте формальные признаки формального синьора как определить?

задача кстати важная разве нет?

По мне так в зависимости от проекта будет разная шкала. Вот попытка создать универсальную шкалу — sijinjoseph.com/...​rammer-competency-matrix . Но собеседовать по матрицы можно оочень долго.

А нет никаких признаков. На какую лычку/зп сторгуешься, тем и будешь :)
+ В каждой компании свои требования и критерии

Условно будем считать, что если галера в вакансии написала, что ищет сеньйор специалиста и ты прошел к ним собеседование, то ты сеньйор

а вот з.п. вопрос подвезли и там пишут что разница синьор не синьор не +500 (к) (тм) но почти 2 кратная ))

Ничего не понял из твоего сообщения, могу лишь догадываться
Ну зп сеньйора тоже бывает разная :)
Я бы скорее на основе укро рынка классифицировал бы как
0-1500 — джун
1500-3000 — мидл
3000+ синьйор, ну и там дальше -> лид, архитект и тд
Вроде красиво
Так что да, в зависимости от того, какого мидла с каким сеньйором сравниваем разница может быть и в 2 раза по зп

Дані потрібно готувати. Показники температури приходять раз на ... годину (припустимо). Шедулер вкладає до ДБ підраховані температури (за 170 мсек) , які нода тупо читає. Тоді — хоч мільон запитів

У мене були думки використати якісь задачі, наближені до роботи в реальному часі. Наприклад фінансові біржі, онлайн ігри, computer vision. Там багато даних і вони кожного моменту змінюються. Але я зупинився на прикладі з погодою, бо його дуже легко зрозуміти і сам алгоритм також простий. Це не була стаття «Ось як треба опрацьовувати дані про погоду за рік», це стаття скоріше про «Давайте оптимізуємо алгоритм задачі, яка повторюється 1000 разів в секунди»

Приклад — чудовий, як для демонстрації можливостей оптимізації. Різнобічний.
Подібне завдання з білінгом (необхідність підрахунків під час масових запитів) нещодавно у знайомого зв‘явилося. Попередня калькуляція дуже допомогла

Популяризация алгоритмов — это замечательно.
К сожалению, итоговое решение не сможет в действительности работать с большими данными (как в вашем примере выше) и имеет ужасную сложность (имеется в виду BigO. Кстати, получится сходу определить итоговую сложность по времени и памяти?) Что, если есть тривиальный алгоритм который (не учитывая пустого UPDATE/SELECT запроса к базе данных) работает за O(1)? :)
Не подумайте, что я пытаюсь придраться. Таких статей бы больше, чтобы код в вашем первом примере существовал только в кошмарных снах, но решаемая задача (и алгоритм подсчета среднего значения) выбрана на мой взгляд не самая лучшая

Так, в BigData і стрімами було б інакше. Я б робив якось так: 2 singletone масиви (один для суми, інший для кількості) довжиною 366 елементів. Ідемо по стріму, вираховуємо номер дня у році (ну і позицію в масиві), сумуємо там значення. В іншому масиві робимо інкемент. Коли потрібно повертати результати — ділимо один масив на інший. Тут O(n) по часу і O(1) для пам’яті.
В тому алгоритмі, що у статті остання версія v6
Групування O(n) + Отримати дат по ключах HashMap O(n) + Обрахунок середньої температури O(n) — по часу і пам’яті

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

А ещё, а если нет БД? Например чисто фронт или мобильное приложение на RN.

А вот и нет. Речь шла о вычислениях на сервере. Так можно и чистый массив отдать на клиента — пусть считает хоть секунду свою температуру.

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

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

Чому не зберігати масив в БД і написати запит який порахує за вас?

Монга порахує. Ще той рахуватель. Це ж mern

Запит в БД також потрібно ефективно написати. Або зробити Stored Procedure, яка теж має бути ефективно написана. Це як закон збереження енергії, лоад сам по собі нікуди не дінеться, ви просто перенесете його з API на БД. В свою чергу ресурси БД також обмежені. Якщо ви маштабуєте stateless API, ви просто додаєте нові ноди після лоад балансера. БД вже не так легко маштабується, бо вам потрібно думати про цілісність даних.

По крайней мере это позволит на всю использовать кеш БД (до тех пор, пока исходные данные или запрос не поменяются) и получать результат запроса из кэша БД. А можно сторонним процессом это всё считать и готовый результат ложить в какой-нибудь memcache|redis и пересчитывать данные с заданной периодичностью. Я бы склонился ко второму варианту со сторонним процессом и раскидывал результаты по кэш-серверам. А тут хоть 1М запросов в секунду, лишь бы железо выдержало...

На рахунок 1М запитів: MS SQL Server стягне паралельно 30,000 запитів. Redis може стягнути 65 тисяч запитів, що рівне максимальній кількості відкритих TCP з’єднань. І вам треба дуже нехиле залізо, щоб буди близьким до таких цифр. Ну і не будемо забувати про fault tolerance, тобто вам потрібна надлишковість ресурсів, щоб коли щось завалиться, ваші користувачі цього не відчули. Тобто ви праві про кеші, але вони будуть не тільки в вигляді Redis Cluster, але і локальні в пам’яті. Словом — 1М ні разу не просто.
Остання версія алгоритму опрацьовує запит 2 мс, це дійсно варто додаткового процесу, щоб він підрахував додатково дані десь окремо?
Давайте уявимо, що у нас є додатковий процес, який підраховує дані для нас. Перша версія алгоритму опрацьовувала 16 запитів в секунди. Нахай ми отримуємо дані про 1000 міст. Тобто, щоб опрацювати всі дані, у нас піде більше 16 * 1000 / 60 / 60 = 4 годин. Якщо дані приходять раз в годину, то нам треба 4 такі процеси, щоб хоча б встигав в проміжок 1 година, але користувачі будуть чекати годину, щоб отримати актуальні дані.

Если упираемся в количество открытых tcp соединений, делаем финт ушами:
1. По возможности переносим все сервисы в первую тысячу портов, расширяем net.ipv4.ip_local_port_range под себя по максимуму;
2. Навешиваем дополнительные сетевые интерфейсы. Можно алиасами на единственный сетевой адаптер, можно физически добавить сетевух если бюджет позволяет.

Тут дуже цікава лекція з прискорення реальних систем (архітектурою, а не алгоритмами)
ithare.com/...​-threading-with-a-script
Взагалі, сайт хороший для high load

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

Є масив даних із 8 784 елементами

Ну от візьмемо коментар Roman Pavlyuk вище. Був собі сініор. Написав програму з кубічною складністю. Прийшли 1,000 елементів, які оброблялися за 1,000,000,000 кроків, і програма відвалилася за 30 хвилин. Хіба таке не може трапитися кожного дня?) Багато проектів пишуть код і не підозрюють про наслідки до першого, навіть не дуже великого, навантаження.

Кубическое — фигня. У меня на прошлой неделе чувак(типа сеньйор тоже, судя по профилю на апворке) написал запрос sql, в котором вместо 10 записей просматривается N^3 от всех, причем всех там около миллиона. И сидит ждет, пока база просчитает.
У каждого прохода естимейт в 150 тыс лет.
Так он крутой мужик, он его еще и по крону раз в 15 минут поставил.
С сертификатами, эксперт по базам данным, куда там мне скромному админу.
Сервер таки перегружали.... Я заметил через 4 часа, пока выяснили кто чего сделал — еще 8 прошло.

У каждого прохода естимейт в 150 тыс лет.

епічно ))))

Ну так получалося если сравнить время выполнения выборок на малых данных и explain. ±30%, все же иногда база делает неочевидные оптимизации. Но порядок где-то такой, да.
Просто когда оно фактически целый день работало, попросили узнать сколько еще будет работать.
А поскольку это все работает на EC2 с EBS, то там еще и нехило по i/o скорее всего счет прилетит в конце месяца.
А запускалося 8 проходов. больше не запускалося, походу по памяти не хватало.

Ага, дуже важливо прогнозувати кости наперед. Всі клауди дуже дешеві на старті. Потім коли починається лоад, вже все не так райдужно. Якщо лоад постійний, то AWS лямбди можуть стати золоті. Чув про стартапи, де лямбди були у 8 раз дорожчі, ніж аналогічні по лоаду EC2.

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