Представьте, что вам нужно реализовать drag&drop список, в котором можно менять элементы местами. Элементы списка хранятся в БД, и мы можем добавить туда поле priority, по которому будет выполняться сортировка.
Можно решить задачу в лоб и просто пересчитывать все приоритеты при перемещении карточки — на небольших списках это даже будет работать нормально.
Но представим, что у вас сотни таких элементов, и вы двигаете последнюю карточку в начало списка. Тогда придётся сделать 100 записей в БД — звучит не очень оптимально 🤔
Как сделать лучше?
Можно заполнять поле priority не с шагом 1, а, например, с шагом 100.
🟢Тогда при перестановке элемента в середину списка нам будет достаточно взять средний приоритет между соседними значениями и обновить только один элемент в БД.
🟢Для крайних элементов тоже всё просто: либо вычитаем шаг приоритета, либо прибавляем.
🟢Но может случиться так, что после многих перестановок разница между элементами станет равной 1, только тогда придётся перезаписать все приоритеты.
Итого: в первом варианте у нас всегда была бы сложность O(N), а во втором, в большинстве случаев O(1), и только в худшем сценарии мы получим линейное время.
❓ А вы бы стали заморачиваться с оптимизацией? Или сделали бы простой вариант?
Представьте, что вам нужно реализовать drag&drop список, в котором можно менять элементы местами. Элементы списка хранятся в БД, и мы можем добавить туда поле priority, по которому будет выполняться сортировка.
Можно решить задачу в лоб и просто пересчитывать все приоритеты при перемещении карточки — на небольших списках это даже будет работать нормально.
Но представим, что у вас сотни таких элементов, и вы двигаете последнюю карточку в начало списка. Тогда придётся сделать 100 записей в БД — звучит не очень оптимально 🤔
Как сделать лучше?
Можно заполнять поле priority не с шагом 1, а, например, с шагом 100.
🟢Тогда при перестановке элемента в середину списка нам будет достаточно взять средний приоритет между соседними значениями и обновить только один элемент в БД.
🟢Для крайних элементов тоже всё просто: либо вычитаем шаг приоритета, либо прибавляем.
🟢Но может случиться так, что после многих перестановок разница между элементами станет равной 1, только тогда придётся перезаписать все приоритеты.
Итого: в первом варианте у нас всегда была бы сложность O(N), а во втором, в большинстве случаев O(1), и только в худшем сценарии мы получим линейное время.
❓ А вы бы стали заморачиваться с оптимизацией? Или сделали бы простой вариант?
Don’t publish new content at nighttime. Since not all users disable notifications for the night, you risk inadvertently disturbing them. Earlier, crypto enthusiasts had created a self-described “meme app” dubbed “gm” app wherein users would greet each other with “gm” or “good morning” messages. However, in September 2021, the gm app was down after a hacker reportedly gained access to the user data. Over 33,000 people sent out over 1,000 doxxing messages in the group. Although the administrators tried to delete all of the messages, the posting speed was far too much for them to keep up. Content is editable within two days of publishing How to create a business channel on Telegram? (Tutorial)
from us
