Как быстро сравнить два массива?

Question

[Imp]

Есть два массива.
1. Пользователи
global.users = [111,333,444,666,777]
2. Пользователи которые были уже обработаны ранее.
global.blacklist = [111,222,333,555,888]

В этих массивах может быть сотни тысяч элементов. Они загружаются с текстового файла таким образом:

const users = Files.readFileSync('./users.txt', 'utf8').split(/\r?\n/);
const blacklist = Files.readFileSync('./blacklist.txt', 'utf8').split(/\r?\n/);

Мне нужно сравнить массивы и оставить только уникальные значения:

global.users = global.users.filter(user => !global.blacklist.find(b => user == b));

Дошло до того, что сравнивает эти массивы по минут 10.
Можно как-то ускорить? Может на стадии чтения двух этих файлов. Эти файлы загружаются и массивы сравниваются при запуске приложения.

Comments

[Roman]

Ускорить...

Есть два массива.

А если будет два дерева

Или использовать binarySearch

Answer 1

[coderisimo]

А может сравнивать их ДО, еще на сервере (генерировать один текстовый файл заранее)? Или использовать базу данных, сразу получая нужную выборку? Т.е в БД есть поле 'processed' , которое может быть 1 или не 1 :)))))))) .

ИМХО, "сотни тысяч элементов" хреново сочетаются с "загружаются с текстового файла" и "сравниваются при запуске приложения". Это как "нужно превысить скорость звука" и "используется самокат для ребенка 3 лет"

Comments

[Imp]

ну есть вариант использовать только блеклист в качестве бд, поскольку users динамическое. При каждом запуске пользователь приложения в текстовик вбивает новых юзеров, а блеклист лишь дополняется и проверяет, что бы не трогать юзеров которые уже когда-то были обработаны. Ну если так, можете посоветовать что-то максимально простое для таких задач? Ну конкретно бд.

[coderisimo]

Impu, не уверен, что понял, как у вас все устроено и никогда не работал с node.js (имел дело с mySQL и монгой), но наверняка, есть стандартные средства для хранения и доступа к данным для вашего стека. Та же Mongo. Вы сохраняете туда обработанных юзеров (не забудьте про индексы). Затем, когда есть список новых - ищите каждого в базе . Те кого там нет обрабатываются и добавляются в базу, чтобы исключит повторную обработку.

Answer 2

[Илья Серов]

https://developer.mozilla.org/ru/docs/Web/JavaScri...

Answer 3

[Алексей]

Ты уверен что время уходит именно на сравнение ? Я бы сделал ставку какраз таки на .split, потому что 100к+ строк засплитить как мне кажется операция подороже чем просто перебрать массив. Ну и заменить find на банальный indexOf

const blacklist = Files.readFileSync('./blacklist.txt', 'utf8').split(/\r?\n/);
const users = Files.readFileSync('./users.txt', 'utf8').split(/\r?\n/).filter((user) => {
	var idx = blacklist.indexOf(user);
	if (idx === -1) {
		return true;
	} else {
		blacklist.splice(idx, 1); // тут я не уверен в профите уменьшения блеклиста, потому что это надо будет перестраивать индексы, так что можно просто сделать return blacklist.indexOf(user) === -1;
		return false;
	};	
});

Answer 4

[longclaps]

Что-то вроде слияния. Пожалуй, этот способ будет побыстрее, чем с Set(), и менее жаден до памяти:

let users = [111, 333, 444, 666, 777], // важно, что массивы отсортированы
    blacklist = [111, 222, 333, 555, 888],
    intersection = [];
users.unshift(-1); // -1 заведомо меньше всех
blacklist.unshift(-1);
for (let u = users.pop(), b = blacklist.pop(); u > -1 || b > -1;) {
    if (u > b) u = users.pop();
    else if (u < b) b = blacklist.pop();
    else {
        intersection.push(u);
        u = users.pop();
        b = blacklist.pop();
    }
}
intersection.reverse(); // если это вообще надо
console.log(intersection);