CODEWITHSUNDEEP
listalgorithmmemory
John Smith
John Smith

Reputation: 6207

Ordering a triming (pagination) a big array, how?

a classic task, I need to return a list which can be paginated.

Here is the elements:

ecgdfahb

lets order it:

abcdefgh

and I want to return the first page, with 2 items:

ab

or the 2nd page:

cd

so basically I just add source items, order them and make a simple array-split operation (data dont come from database). But this list is huge. Way too huge, and with doing this, I get memory overflow when I try to add the 5. elements. Is there a memory-sparing approach of it? If there would no be pages, then it would be simple, because only the non-crowded out elements would be in list.

Upvotes: 0

Views: 59

Answers (1)

jferard
jferard

Reputation: 8180

The easiest solution is to use a RDBMS and to write a SQL query like:

SELECT x FROM table
ORDER by x
LIMIT window_size OFFSET window_offset

Be sure to have a B-tree index on the field table.x. The main interest of B-trees is that they require a small amount of disk access and keep the list of values sorted.

If you don't want to use a RDBMS, you'll have implement the B-tree yourself. See the wikipedia page on B-trees for general information. There is also a good chapter in Introduction to Algorithms.

To summarize, a B-tree is a like a binary tree, but its nodes have a lot of children, let's say up to m. Hence, those trees are shallower than binary trees. Nodes are stored on disk (typically, each node is saved on a disk block), allowing you to store ordered lists of values that don't fit into memory. If you have n keys x1, ... xn in a non-leaf node, then you have n+1 children nodes, containing values <= x1 values between x1 and x2, .... The main difficulty is to insert values: when the number of values in a node exceeds m, you have to split that node.

Some references: https://en.wikipedia.org/wiki/B-tree#Algorithms and https://www.geeksforgeeks.org/introduction-of-b-tree-2/.

To ouput a given window, use a DFS to find the start index and continue until you found the last index of the window.

Upvotes: 1

Related Questions