В процессе тестирования алгоритма бинарного поиска мне стало любопытно как будет работать алгоритм на массиве чисел размером 4 миллиарда. Ожидаемо, при попытке создать такой массив, nodejs говорит нам, что места в куче больше нет:

<--- Last few GCs --->

[133294:0x5da3760]     1203 ms: Scavenge 1148.2 (1181.1) -> 1148.2 (1181.1) MB, 42.9 / 0.0 ms  (average mu = 1.000, current mu = 1.000) allocation failure
[133294:0x5da3760]     2175 ms: Mark-sweep 1722.0 (1755.0) -> 1709.7 (1743.0) MB, 479.6 / 0.0 ms  (+ 37.7 ms in 11 steps since start of marking, biggest step 4.7 ms, walltime since start of marking 2099 ms) (average mu = 1.000, current mu = 1.000) allocat

<--- JS stacktrace --->

FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory
1: 0xa295e0 node::Abort() [node]
2: 0x9782df node::FatalError(char const*, char const*) [node]
3: 0xb99c2e v8::Utils::ReportOOMFailure(v8::internal::Isolate*, char const*, bool) [node]
4: 0xb99fa7 v8::internal::V8::FatalProcessOutOfMemory(v8::internal::Isolate*, char const*, bool) [node]
5: 0xd3a3b5  [node]
6: 0xd1fe8d  [node]
7: 0xe7fc9e  [node]
8: 0xe837fa  [node]
9: 0x10243a3 v8::internal::Runtime_GrowArrayElements(int, unsigned long*, v8::internal::Isolate*) [node]
10: 0x13a5a99  [node]
[4]    133294 abort (core dumped)  node --heap-prof binarySearch.js


Возникает два вопроса:
1) В Javascript тип Number занимает 64 бита (альтернатив поменьше я не нашел). Соответственно, массив с 4 миллиардами таких элементов будет занимать 4 000 000 000 * 64 = 256000000000 бит или 32 гигабайта. Верно ли мое рассуждение?
2) Можно ли как-то решить данную проблему? Или только увеличение размера памяти и кучи поможет?

В принципе, думаю ответы на вопрос найду в видео

первый вопрос в том, правильны ли расчёты? ну да, правильны
на второй вопрос можно предложить не использовать ноду

у человека 4 млрд чисел, которые он хочет как-то обработать
думаю всё-таки есть инструменты, которые лучше подходят для задачи

@murzilka17 не принципиально использовать ноду, просто она мне сподручнее. Посмотрел на typedArray, для моих целей подойдет uInt32 (вмещает 4 млрд), но все равно много памяти потребуется, если помнить про то, что там еще дополнительно сколько-то байт навешивается (вроде как 8 байт). 4e9 * (4 + 8) = 48000000000 бит = 6 гигов. В принципе, уже лучше, но все равно очень много. Видимо, нужно распиливать данные, 4 млрд слишком много, чтобы с ними вот так просто работать, независимо от языка

вот не сильно красивый пример, но идею можно уловить https://nodejs.org/api/stream.html#stream_event_drain

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

не увидел, что речь про сортировку. тогда стримы не подойдут.
тогда нужно смотреть в сторону https://en.wikipedia.org/wiki/External_sorting

нет, речь о https://en.wikipedia.org/wiki/Binary_search_algorithm

Для этого, конечно, нет никакого смысла держать все данные в памяти, если они изначально не в ней

Нужно поднять книгу Д. Кнута и найти там алгоритмы внешней сортировки

У него уже всё отсортировано

Да, уже отсортированный массив на входе

не самый простой способ решить задачу)

Ну кому простой - в нпм возьсмите, а кто хочет понимать - вот вам Кнут

а пряник?
они по классике только в паре работают :)