Недостаточно памяти [алгоритм деления и завоевания]

Question

Итак, у меня есть таблица foo, которая огромна, и всякий раз, когда я пытаюсь прочитать все данные из этой таблицы, Node.JS дает мне ошибку в памяти! Тем не менее, вы можете получить chancks данных путем смещения и ограничения; но снова я не могу объединить все чанки и иметь их в памяти, потому что я снова сталкиваюсь с памятью! В моем алгоритме у меня много идентификаторов и нужно проверить, существует ли каждый идентификатор в таблице foo или нет; какое наилучшее решение (с точки зрения сложности алгоритма), когда я не могу иметь все данные в памяти, чтобы увидеть, существует ли id в таблице foo или нет?

PS: Наивное решение состоит в том, чтобы получить данные о чанках и посмотреть chunck на chunck для каждого id; но сложность n квадрата; должен быть лучший способ, который я считаю ...

Answer 1

В соответствии с указанными вами ограничениями вы можете создать хеш-таблицу, содержащую идентификаторы, которые вы ищете как ключи, со всеми значениями, инициализированными значением false.

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

После прохождения всех кусков ваша хеш-таблица будет содержать значения true для ID, найденных в таблице.

При условии, что поиск в хеш-таблице имеет фиксированную временную сложность, тогда этот алгоритм имеет временную сложность O (N).

Answer 2

Вы можете отсортировать свои идентификаторы и разбить их на куски. Затем вы можете хранить в памяти диапазон значений в каждом фрагменте - (lowId, maximumId) для этого фрагмента.

Вы можете быстро найти фрагмент (если есть), который может содержаться в использовании двоичного поиска в памяти, а затем загружать этот конкретный фрагмент в память и бинарный поиск на нем.

Сложность должна быть логина для обоих. В общем, читайте о бинарном алгоритме поиска.

Answer 3

«PS: Наивное решение получить chuncks данных и посмотреть chunck по chunck для каждого идентификатора, но сложность п квадрат, должно быть лучше, я верю ...»

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

Сказав это, на ум приходит хэш-стол. Допустим, что идентификаторы являются целыми числами, и они выбираются случайным образом. вы можете использовать идентификаторы, которые вам нужно проверить по двум последним цифрам (или первым двум в этом отношении). Тогда проверка предметов, которые у вас есть в вашей памяти, будет быстрее.