时间戳

首页 > 解决方案 > 订购一个修剪（分页）一个大数组，如何？

list - 订购一个修剪（分页）一个大数组，如何？

问题描述

一个经典的任务，我需要返回一个可以分页的列表。

这里是元素：

ecgdfahb

让我们订购：

abcdefgh

我想返回第一页，有 2 项：

ab

或第二页：

cd

所以基本上我只是添加源项目，对它们进行排序并进行简单的数组拆分操作（数据不来自数据库）。但是这个列表是巨大的。太大了，这样做，当我尝试添加 5. 元素时会出现内存溢出。有没有节省内存的方法？如果没有页面，那就很简单了，因为只有非拥挤的元素会在列表中。

标签： listalgorithmmemory

解决方案

最简单的解决方案是使用 RDBMS 并编写如下 SQL 查询：

SELECT x FROM table
ORDER by x
LIMIT window_size OFFSET window_offset

确保在 field 上有一个 B-tree 索引table.x。B 树的主要兴趣在于它们需要少量的磁盘访问并保持值列表的排序。

如果您不想使用 RDBMS，您将自己实现 B 树。有关一般信息，请参阅B 树上的维基百科页面。Introduction to Algorithms也有一个很好的章节。

总而言之，B-tree 就像一棵二叉树，但它的节点有很多子节点，比如说m. 因此，这些树比二叉树更浅。节点存储在磁盘上（通常，每个节点都保存在一个磁盘块上），允许您存储不适合内存的有序值列表。如果您在非叶节点中有n键，那么您有子节点，包含介于和之间的值，...。主要困难是插入值：当节点中的值数量超过时，您必须拆分它节点。x1, ... xnn+1<= x1x1x2m

一些参考资料：https ://en.wikipedia.org/wiki/B-tree#Algorithms和https://www.geeksforgeeks.org/introduction-of-b-tree-2/。

要输出给定窗口，请使用DFS查找开始索引并继续，直到找到窗口的最后一个索引。

推荐阅读