Javascript: более умный способ фильтрации тысяч строк по тысячам значений

Question

У меня есть строки с 2 столбцами: SKU продукта и идентификаторы категории Мне нужно только вернуть SKU продукта и их cat_ids, которые соответствуют списку cat_ids в SQL это будет:

SELECT SKU,cat_id FROM myTable where cat_id IN(my_huge cat_ids_list)

но мне нужно сделать это в Javascript с вкладки возврата данных.

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

если у меня 30000 SKU, для сравнения с 1000 cat_ids, которые в худшем случае будут 30M тестами.

так есть ли более умный алгоритмический подход, который бы фильтровал это более глобально, без необходимости в большом количестве тестов?

Большое спасибо

Answer 1

Вам не нужны вложенные циклы. Используйте Set, который является поиском с постоянным временем. Вам нужно создать набор из массива категорий, а затем использовать set.has() для фильтрации:

let rows = [
    {sku: 1, cat_id:100},
    {sku: 11, cat_id:10},
    {sku: 12, cat_id:10},
    {sku: 13, cat_id:20},
    {sku: 14, cat_id:10},
    {sku: 15, cat_id:20},
    {sku: 16, cat_id:100}
]
//original array of ids to match
let matchCats = [10, 20]

// make a set from it
let matchSet = new Set(matchCats)

// filter with has()
let filtered = rows.filter(item => matchSet.has(item.cat_id))
console.log(filtered)

Это даст вам линейную фильтрацию времени.

Редактировать на основе комментария
Если вы не можете использовать ES6, вы все равно можете воспользоваться тем фактом, что обычные объекты JavaScript могут использоваться как хеши с постоянным поиском ключа. Это не так красиво, но все равно должно работать за линейное время:

let rows = [
    {sku: 1, cat_id:100},
    {sku: 11, cat_id:10},
    {sku: 12, cat_id:10},
    {sku: 13, cat_id:20},
    {sku: 14, cat_id:10},
    {sku: 15, cat_id:20},
    {sku: 16, cat_id:100}
]

let matchCats = [10, 20]

// make an object of key/null-value pairs
let matchObj = matchCats.reduce((obj, item) => (obj[item] = null, obj), {})
let filtered = rows.filter(item => item.cat_id in matchObj)
console.log(filtered)

Answer 2

Используйте хэш-набор для вашего списка cat_ids, который дает вам проверки на постоянное время.Не слишком знаком с javascript, но я считаю, что тип Set должен помочь.

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set