Как заказать обрезку (нумерацию страниц) большого массива?

Question

Класси c задача, мне нужно вернуть список, который можно разбить на страницы.

Вот элементы:

ecgdfahb

позволяет упорядочить его:

abcdefgh

и я хочу вернуть первую страницу с 2 элементами:

ab

или 2-й страницей:

cd

, поэтому в основном я просто добавляю исходные элементы, заказываю их и сделать простую операцию разбиения массива (данные не приходят из базы данных). Но этот список огромен. Слишком большой, и при этом я получаю переполнение памяти, когда пытаюсь добавить элементы 5.. Есть ли подход с сохранением памяти? Если бы не было страниц, то это было бы просто, потому что в списке были бы только не переполненные элементы.

Answer 1

Самое простое решение - использовать СУБД и написать запрос SQL, например:

SELECT x FROM table
ORDER by x
LIMIT window_size OFFSET window_offset

Убедитесь, что в поле table.x указан индекс B-дерева. Основной интерес B-деревьев заключается в том, что они требуют небольшого количества доступа к диску и сохраняют отсортированный список значений.

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

Подводя итог, можно сказать, что B-дерево похоже на двоичное дерево, но его узлы имеют много дочерних элементов, скажем, до m. Следовательно, эти деревья меньше бинарных деревьев. Узлы хранятся на диске (обычно каждый узел сохраняется на диске), что позволяет хранить упорядоченные списки значений, которые не помещаются в память. Если у вас есть не 1014 * ключи x1, ... xn в неконечных узлах, то у вас есть n+1 дочерние узлы, содержащие значения <= x1 значений между x1 и x2, .... Основная трудность заключается в том, чтобы вставить значения: когда число значений в узле превышает m, необходимо разделить этот узел.

Некоторые ссылки: https://en.wikipedia.org/wiki/B-tree#Algorithms и https://www.geeksforgeeks.org/introduction-of-b-tree-2/.

Чтобы вывести данное окно, используйте DFS , чтобы найти начальный индекс и продолжайте, пока не найдете последний индекс окна.