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

В какой-то момент стали поступать жалобы от пользователей на то, что приложение вылетает на андроид-устройствах. Сами устройства довольно старые: RFID-считыватели на Android 6 и Android 14. После диагностики поняли, что суть в том, что тупо кончается оперативная память и приложение падает. Сразу оговорюсь, что к падению приложения причастен был и ряд других проблем, но в рамках темы рассмотрим только алгоритм.

Суть: в приложении есть функционал выгрузки части базы данных на устройство для оффлайн работы. При выгрузке из БД (у нас couchdb 1.7.2 😢) тянется 130000 документов. Пару секунд приложение пыжится, потом ломается. Предлагаю рассмотреть изначальный код. Смотрим скрин 1. Как мы видим, внутри цикла forEach на каждой итерации вызывается filter, который проходит по тому же массиву. У нас квадратичная сложность вычисления O(n²).

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

А теперь представим, что проходя по одному элементу, мы вызываем еще один цикл, который проходится по тому же массиву (цикл в цикле). Сколько будет операций? На каждую операцию будет тоже O(n) вычислений. То есть, 1000 * 1000 = 1000000 операций. То есть, O(n * n) = O(n²).

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

В общем, решили мы это так. Смотрим скрин 2.

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

#javascript #algo #android