Самый эффективный способ поиска карты массивов в JavaScript

Question

У меня есть карта массивов чисел в JavaScript. Моя цель - получить ключ от значения, содержащего определенное число. Я также открыт для другой структуры данных, которая может быть более эффективной.

let bookCategory = { 
    "fantasy": [10064, 10066, 10071], 
    "scifi": [10060, 10037, 10061], 
    "history": [10001, 10003, 10004, 10005], 
    "biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031], 
    "educational": [10025] 
}; 

Каждое число будет только когда появляется один раз, но каждый массив может содержать около сотни номеров, и это может существенно расти оттуда. Массивы могут быть неизменными, поскольку мои данные являются статическими.

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

let category; 
let keys = _.keys(categories); 
let theNumber = 10032; 

for(let j = 0; j < keys.length; j++) { 
    if(_.includes(categories[keys[j]], theNumber)) { 
     category = keys[j]; 
     break; 
    } 
} 

Answer 1

lodash В библиотеке много полезных функций. С его помощью у вас есть следующие варианты:

1. Двоичный поиск

Создать новую структуру с отсортированный массив чисел. При поиске номера примените двоичный поиск.
Метод _.sortedIndexOf() использует двоичный поиск в массиве.

var bookCategory = { 
"fantasy": [10064, 10066, 10071], 
"scifi": [10060, 10037, 10061], 
"history": [10001, 10003, 10004, 10005], 
"biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031], 
"educational": [10025] 
}; 

var binaryMap = _.mapValues(bookCategory, function(category) { 
    return category.sort(function(num1, num2) { 
    return num1 - num2; 
    }); 
}); 

//then search using binary algorithm  
var number = 10032; 
var keyForNumber = _.findKey(binaryMap, function(numbers) { 
    return _.sortedIndexOf(numbers, number) !== -1; 
}); 

keyForNumber // prints "biography" 

Проверьте работоспособность demo.

2. Создайте объект карты

Поскольку цифры будут появляться только один раз, это легко создать большой хеш-объект, где ключ число и значение является категорией. Для этого требуется немного больше памяти, поскольку копирует строку категорий, но работает довольно быстро.
Это решение не требует lodash.

var bookCategory = { 
"fantasy": [10064, 10066, 10071], 
"scifi": [10060, 10037, 10061], 
"history": [10001, 10003, 10004, 10005], 
"biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031], 
"educational": [10025] 
}; 

var map = _.reduce(bookCategory, function(result, numbers, key) { 
    _.each(numbers, function(number) { 
    result[number] = key; 
    }); 
    return result; 
}, {}); 

// or alternative without lodash 
var mapAlternative = Object.keys(bookCategory).reduce(function(result, key) { 
    bookCategory[key].forEach(function(number) { 
    result[number] = key; 
    }); 
    return result; 
}, {}); 


var number = 10003; 
map[number]; // prints "history" 

Проверьте работоспособность demo.

Answer 2

Есть слишком много what-ifs, чтобы ответить на этот вопрос, самый большой один существо: Как часто данные собираются быть updated против read.

Если это будет read гораздо чаще, то сначала выполните итерацию через bookCategory и создайте разреженный массив/объект, который связывает числа с категорией.

(я пойду на объект здесь):

// Generate this programatticly, of course. 
bookCategoryLinkback = { 
    10064: "fantasy", 
    10066: "fantasy", 
    10071: "fantasy" 
}; 

Answer 3

сортировать массив и использовать бинарный поиск. Вы можете использовать lodash lib, чтобы сделать это легко.

Answer 4

Предлагаю использовать хеш-таблицу для чисел.

var bookCategory = { 
 
     "fantasy": [10064, 10066, 10071], 
 
     "scifi": [10060, 10037, 10061], 
 
     "history": [10001, 10003, 10004, 10005], 
 
     "biography": [10032, 10006, 10002, 10028, 10009, 10030, 100031], 
 
     "educational": [10025] 
 
    }, 
 
    numbers = function (data) { 
 
     var r = Object.create(null); 
 
     Object.keys(data).forEach(k => data[k].forEach(a => r[a] = k)); 
 
     return r; 
 
    }(bookCategory) 
 

 
document.write('<pre>' + JSON.stringify(numbers, 0, 4) + '</pre>');