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

Question

[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 и правильный ли это паттерн?

Comments

[Сергей Горностаев]

Java тут причём?

[maksipes]

Сергей Горностаев, на java тоже такое вижу , точно также схема, только там contains вместо includes, а так код один в один.

Answer 1

[Wataru]

Довольно частая ошибка. Лечится или переворачиванием логики, как вы заметили - проходиться по списку ids и смотреть, если такой в data.

Еще лучший вариант - вместо списка использовать какой-либо set в ids. Это будет работать совсем быстро, если ids длинный, а data короткий.

Comments

[maksipes]

так от длинны data вообще не должно зависеть, это же ассоциативный массив. Или не так?

[Wataru]

maksipes, Развернутое решение, да - не зависит от длины data и работает за O(len(ids)).

Второй вариант, которое используте ассоциативный массив вместо списка для ids работает за O(len(data)) - ведь оно по нему проходится.

Стоит выбрать одно из двух в зависимости, чего у вас сильно больше обычно.

[maksipes]

а, ну в данном случае - data общий массив записей откуда выбирают по id некоторые из них - в предельном случае все. т.е. ids всегда меньше data