Блог

Существует Immutable.js со структурными данными в виде коллекций. Давайте возьмем карту. Также существуют методы для работы:

• включает
• Фильтр

Давайте рассмотрим эти данные:

 const data = Map({
  id1: Map({id: 'id1'}),
  id2: Map({id: 'id2'}),
  id100: Map({id: 'id100'}),
});

const ids = List(['id1', 'id100']);
  

И два подхода к итерации этой карты:

 function selectData() {
  return data.filter((item) => ids.includes(item.get("id")));
}
  

 function selectData() {
  let selected = Map();

  ids.forEach((id) => {
    selected = selected.set(id, data.get(id));
  });

  return selected;
}
  

Итак, вопрос в том, эквивалентны ли эти два подхода и имеют одинаковую временную сложность в

• Общая информация
• это особый случай с данными на карте выше

Из моего POV они не эквивалентны, но временная сложность должна быть одинаковой.

Обновление: эквивалент — сделайте то же самое, предоставьте тот же результат.

Как вы указали, семантика немного отличается. В примере они оба обеспечивают пересечение идентификаторов, поэтому

 
> JSON.stringify(s1())
'{"id1":{"id":"id1"},"id100":{"id":"id100"}}'
> JSON.stringify(s2())
'{"id1":{"id":"id1"},"id100":{"id":"id100"}}'
  

Однако существуют крайние случаи со структурой данных, которые не приводят к аналогичным результатам, таким как пример, который вы привели в комментарии:

 const data = Map({
  id1: Map({id: 'id1'}),
  id2: Map({id: 'id1'}),
  id100: Map({id: 'id100'}),
});

const ids = List(['id1', 'id100']);

...

> JSON.stringify(s1())
'{"id1":{"id":"id1"},"id2":{"id":"id1"},"id100":{"id":"id100"}}'
> JSON.stringify(s2())
'{"id1":{"id":"id1"},"id100":{"id":"id100"}}'
  

Примечание. Приведенный выше случай выглядит как ошибка, поскольку идентификатор в карте (значение) не совпадает с идентификатором ключа; но кто знает?

В общем

• подход 1 создает 1 элемент для каждого элемента в map ( data ) верхнего уровня, значение которого имеет id элемент, содержащийся в списке.
• подход 2 создает 1 элемент для каждого значения в списке, который имеет запись в карте верхнего уровня ( data )

Поскольку два подхода различаются с точки зрения поиска в amp ( data ) — один идет по ключу, другой по значению id в карте значений — если в этих двух значениях есть несоответствие, согласно второму примеру, вы получите разницу.

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

Поиск в списке будет O (N), тогда как поиск на карте документируется как O(log32 N) (так что какая-то реализация с широким деревом). Таким образом, для карты M и списка L стоимость приблизительно 1 будет O(L * log32 M) равна, тогда как стоимость второго подхода будет O(M * L) , если M == L (или близко), то, конечно, подход 1 выигрывает на бумаге.

Почти всегда лучше профилировать эти вещи, а не беспокоиться о теоретической временной сложности.

Практически, может быть другой хороший подход, который опирается на уже отсортированную природу карты. Если вы сначала отсортируете список, ( O(L log L) ) , то вы можете просто использовать скользящее окно по элементам обоих, чтобы найти пересечение…