При разработке бизнес-логики приложений нужно продумать действия с множествами – с пересечением, разностью массивов или двойной разностью. Недостатки в этом алгоритме могут привести к рискам. Например, если вам нужно в реальном времени обработать объем данных, превышающий определенную границу, система может «тормозить» – до минуты и даже больше. Такие ситуации требуют лишнего расхода ресурсов, отталкивают пользователей и вызывают другие проблемы.
Рассмотрим один из способов, которым мы пользуемся в работе для устранения подобных негативных эффектов. Статья будет полезна как разработчикам с опытом, которые ищут новые способы оптимизации своих продуктов, так и новичкам, которые только погружаются в тему оптимизации.
Например, вам нужно определить права пользователя на просмотр странички. Есть массив ролей, которым разрешён доступ (authorities) и массив прав конкретного пользователя (userRights). Требуется определить факт того, что этому пользователю разрешён доступ к страничке.
Что мы сделаем в этом случае? Конечно же, будем брать каждое право из массива userRights и пробегать по всем ролям в authorities:
const hasRight = userRights.filter(item => authorities.includes(item))
На первый взгляд, всё отработано красиво, читабельно и корректно. Но какие проблемы есть в вышеприведенном алгоритме?
Если это массив с небольшим количеством входящих данных, то особых проблем не возникает, несмотря на то, что у данного алгоритма O(n^2).
Однако, как только n достигает достаточно больших значений, время отработки алгоритма уже не будет нас устраивать.
Ниже в таблице приведена динамика деградации скорости выполнения алгоритмов разной сложности от размера входных данных.
Источник: «Алгоритмы: разработка и применение» (Клейнберг Дж., Тардос Е.)
В подобных задачах помогает алгоритм с O(n*log
)
- зелёный – разность
- красный – пересечение
- зелёный + синий – двойная разность
Разность можно получить следующим образом:
const dif = function(arr1, arr2) {
const temp = new Set([...arr1, ...arr2])
arr2.map(item => (temp.has(item) && temp.delete(item)))
return arr1.filter(item => !temp.has(item))
}
Пересечение:
const cross = function(arr1, arr2) {
const temp = new Set(arr2)
return arr1.filter(item => temp.has(item))
}
Двойное пересечение, например, можно получить так:
dif(arr1, arr2) + dif(arr2, arr1)
Сложность всех алгоритмов: O(n*log)
Однако, при n достаточно малых эти алгоритмы проиграют по скорости и памяти алгоритму filter(item => arr.includes(item)). Поэтому, примем что n <= 100 – нас устраивает для алгоритма O(n^2)
В результате получим следующий алгоритм:
if(n <= 100) {
filter(item => arr.includes(item))
} else {
diff или cross
}
Спасибо за внимание! Надеемся, что этот материал был вам полезен.
habr.com
Рассмотрим один из способов, которым мы пользуемся в работе для устранения подобных негативных эффектов. Статья будет полезна как разработчикам с опытом, которые ищут новые способы оптимизации своих продуктов, так и новичкам, которые только погружаются в тему оптимизации.
Например, вам нужно определить права пользователя на просмотр странички. Есть массив ролей, которым разрешён доступ (authorities) и массив прав конкретного пользователя (userRights). Требуется определить факт того, что этому пользователю разрешён доступ к страничке.
Что мы сделаем в этом случае? Конечно же, будем брать каждое право из массива userRights и пробегать по всем ролям в authorities:
const hasRight = userRights.filter(item => authorities.includes(item))
На первый взгляд, всё отработано красиво, читабельно и корректно. Но какие проблемы есть в вышеприведенном алгоритме?
Если это массив с небольшим количеством входящих данных, то особых проблем не возникает, несмотря на то, что у данного алгоритма O(n^2).
Однако, как только n достигает достаточно больших значений, время отработки алгоритма уже не будет нас устраивать.
Ниже в таблице приведена динамика деградации скорости выполнения алгоритмов разной сложности от размера входных данных.
В подобных задачах помогает алгоритм с O(n*log
)
- зелёный – разность
- красный – пересечение
- зелёный + синий – двойная разность
Разность можно получить следующим образом:
const dif = function(arr1, arr2) {
const temp = new Set([...arr1, ...arr2])
arr2.map(item => (temp.has(item) && temp.delete(item)))
return arr1.filter(item => !temp.has(item))
}
Пересечение:
const cross = function(arr1, arr2) {
const temp = new Set(arr2)
return arr1.filter(item => temp.has(item))
}
Двойное пересечение, например, можно получить так:
dif(arr1, arr2) + dif(arr2, arr1)
Сложность всех алгоритмов: O(n*log
)Однако, при n достаточно малых эти алгоритмы проиграют по скорости и памяти алгоритму filter(item => arr.includes(item)). Поэтому, примем что n <= 100 – нас устраивает для алгоритма O(n^2)
В результате получим следующий алгоритм:
if(n <= 100) {
filter(item => arr.includes(item))
} else {
diff или cross
}
Заключение
Правильно подобранный алгоритм в рамках вашей задачи может значительно улучшить производительность приложения. Если обработка данных в приложении занимает много времени, обратите внимание на возможные способы ее оптимизации, в частности, на предложенный в статье пример. Мы рекомендуем улучшать алгоритмы как можно раньше, не доводя систему до такого состояния, когда ожидание тех или иных операций действительно становится невыносимым для пользователя.Спасибо за внимание! Надеемся, что этот материал был вам полезен.
Выбираем алгоритм, или Когда ждать уже невыносимо
При разработке бизнес-логики приложений нужно продумать действия с множествами – с пересечением, разностью массивов или двойной разностью. Недостатки в этом алгоритме могут привести к рискам....
habr.com