maksipes
@maksipes

Какова реальная сложность данного алгоритма?

Вопрос по сути теоретический, но практический смысл он тоже имеет.

Задам его сразу для двух языков, а пример приведу абстрактный.

Скажем, нам дан лист адишников:
const ids = List(['id1', 'id2', 'id3']);

и дан ассоциативный массив:
const data = Map({
  id1: someData,
  id2: someData,
   ...
  idN: someData
});


Просматривая один проект я встретил там массу таких решений:
function getNeedData() {
  return data.filter((item) => ids.includes(item.get("id")));
}


Мне показалось это странным. Вместо того чтобы прямо получать из массива data данные по их ключам, итерируя массив ids, здесь итерируется массив data, а в вызываемой функции еще раз происходит итерация (неявно) по ids.

Решил заглянуть в бэковую часть, вроде как там более трепетно относятся к производительности алгоритмов - а там тоже самое - только вместо includes - contains. Насколько я понимаю - суть таже.

Так тут у меня закралось сомнение - а может так и надо?

Как я понимаю - filter перебирает весь массив, а includes делает тоже самое и где-то под капотом там юзается итератор some, т.е. includes переберет массив в среднем до середины.

В среднем придется сделать data.size * (ids.size / 2) итераций, если юзать приведенный алгоритм. Тогда как того же результата можно достичь за ids.size итераций , если итерировать по ids. Я уже не говорю прото что includes подразумевает некое сравнение, которое общем случае может быть весьма затратным, тогда как получая из data по ключам и сравнивать ничего не надо.

Но может я что-то не так понимаю?

Какова реальная сложность данного алгоритма для JS и JAVA и правильный ли это паттерн?
  • Вопрос задан
  • 246 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru
Довольно частая ошибка. Лечится или переворачиванием логики, как вы заметили - проходиться по списку ids и смотреть, если такой в data.

Еще лучший вариант - вместо списка использовать какой-либо set в ids. Это будет работать совсем быстро, если ids длинный, а data короткий.
Ответ написан
Bavashi
@Bavashi
return data.filter((item) => ids.includes(item.get("id")));

У объекта Map нет метода filter, а у массивов нет метода get. Вам нужно уточнить код, который вам кажется неверным по временной сложности, иначе это пока что выглядит как сон собаки.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы