🤓 Как используя enum из TS можно оптимизировать ваш код.
Обозначим проблему: есть такая абстрактная структура данных "ассоциативный массив". В общем то это как массив, но вместо числовых индексов у него каждому значению соответствует некоторый ключ. Реализовываться эта абстрактная структура данных может по-разному: compile-time структуры, сбалансированные деревья, хеш-таблицы и т.д.
В JS у нас есть сразу 2 реализации этой структуры данных: Object и Map. Причем JS не указывает как именно должны реализовываться эти структуры данных, но фактически делается это через хеш-таблицу. Да, хеш-таблицы тоже бывают разные и Object имеет отличную от Map семантику и реализацию. Но, концептуально, обе структуры используют подход хеш-таблицы.
И теперь посмотрим на такой код:
С виду все абсолютно просто и работает очень хорошо: при первом "касании" данные откладываются в словарик и дальше уже берутся из него. Операция работы с табличкой занимает какие-то жалкие микросекунды.
Но теперь переносимся на телефон: не супер старый, но и не новый. И предположим, что данная функция вызывается очень много раз подряд. В моем случае это было несколько сотен раз на старте. И в итоге, суммарное время работы функции, которая, фактически сводилась к работе с хеш-таблицей исчисляется уже сотней миллисекунд. Да-да, достаточно взять не самый свежий девайс и мы получаем такие проблемы.
Почему так происходит? Ведь время доступа к ключу в хеш-таблице - это O(1)? Ну, ребят, во-первых, это среднее амортизируемое время. А значит в некоторых случаях хеш-таблица может сильно и даже очень сильно деградировать. Во-вторых, сложность O(1) говорит, что у структуры данных нет зависимости от количества содержащихся в ней данных, но данные не могут "волшебно" записаться в память.
Хеш-таблица - это структура построенная поверх массива. У нас есть хеш-функция, которая преобразует значения ключа в некоторый индекс этого массива, а дальше данные уже записываются в массив. Хеш-функции могут быть разные. Например, хеш для строки скорее всего будет высчитываться на основе её символов и их позиции в строке, выходит, что сложно работы хеш-функции уже никак не O(1) для таких кейсов.
К тому же, любая хеш-функция может дать одинаковый индекс для разных ключей - это называется коллизией. Эти коллизии надо разрешать и тут тоже существую разные подходы, причем отличаются они как по скорости работы и памяти, так и устойчивости к деградации. А еще, внутренний массив хеш-таблицы может просто "переполнится" и нам придется выделить память большего размера и заново рассчитать хеш для всех значений...
К чему виду - хеш-таблица штука сложная и имеющая кучу нюансов. Другое дело простой массив: доступ к элементу по индексу - это простая арифметика над указателем на первый элемент; элементы лежат рядом в памяти, что хорошо для кеша процессора; и с расходом памяти дела обстоят лучше, чем в хеш-таблице. Можно-ли в данной ситуации использовать массив, вместо хеш-таблицы, но так, чтобы код выглядел читаемо?
Обозначим проблему: есть такая абстрактная структура данных "ассоциативный массив". В общем то это как массив, но вместо числовых индексов у него каждому значению соответствует некоторый ключ. Реализовываться эта абстрактная структура данных может по-разному: compile-time структуры, сбалансированные деревья, хеш-таблицы и т.д.
В JS у нас есть сразу 2 реализации этой структуры данных: Object и Map. Причем JS не указывает как именно должны реализовываться эти структуры данных, но фактически делается это через хеш-таблицу. Да, хеш-таблицы тоже бывают разные и Object имеет отличную от Map семантику и реализацию. Но, концептуально, обе структуры используют подход хеш-таблицы.
И теперь посмотрим на такой код:
const cache = {};
function exec(key: string) {
if (cache[key] != null) {
return cache[key];
}
/// ...
cache[key] = result;
}С виду все абсолютно просто и работает очень хорошо: при первом "касании" данные откладываются в словарик и дальше уже берутся из него. Операция работы с табличкой занимает какие-то жалкие микросекунды.
Но теперь переносимся на телефон: не супер старый, но и не новый. И предположим, что данная функция вызывается очень много раз подряд. В моем случае это было несколько сотен раз на старте. И в итоге, суммарное время работы функции, которая, фактически сводилась к работе с хеш-таблицей исчисляется уже сотней миллисекунд. Да-да, достаточно взять не самый свежий девайс и мы получаем такие проблемы.
Почему так происходит? Ведь время доступа к ключу в хеш-таблице - это O(1)? Ну, ребят, во-первых, это среднее амортизируемое время. А значит в некоторых случаях хеш-таблица может сильно и даже очень сильно деградировать. Во-вторых, сложность O(1) говорит, что у структуры данных нет зависимости от количества содержащихся в ней данных, но данные не могут "волшебно" записаться в память.
Хеш-таблица - это структура построенная поверх массива. У нас есть хеш-функция, которая преобразует значения ключа в некоторый индекс этого массива, а дальше данные уже записываются в массив. Хеш-функции могут быть разные. Например, хеш для строки скорее всего будет высчитываться на основе её символов и их позиции в строке, выходит, что сложно работы хеш-функции уже никак не O(1) для таких кейсов.
К тому же, любая хеш-функция может дать одинаковый индекс для разных ключей - это называется коллизией. Эти коллизии надо разрешать и тут тоже существую разные подходы, причем отличаются они как по скорости работы и памяти, так и устойчивости к деградации. А еще, внутренний массив хеш-таблицы может просто "переполнится" и нам придется выделить память большего размера и заново рассчитать хеш для всех значений...
К чему виду - хеш-таблица штука сложная и имеющая кучу нюансов. Другое дело простой массив: доступ к элементу по индексу - это простая арифметика над указателем на первый элемент; элементы лежат рядом в памяти, что хорошо для кеша процессора; и с расходом памяти дела обстоят лучше, чем в хеш-таблице. Можно-ли в данной ситуации использовать массив, вместо хеш-таблицы, но так, чтобы код выглядел читаемо?