java - 列表实现是多个子列表的 View ？

Question

我正在开发一款软件，它经常需要返回一个列表，该列表由许多其他列表的前(最多)N 个元素组成。返回未被其客户修改——它是只读的。

目前，我正在按照以下方式做一些事情(为便于阅读而简化代码):

List ret = new ArrayList<String>();
for (List aList : lists) {
    // add the first N elements, if they exist
    ret.addAll(aList.subList(0, Math.min(aList.size(), MAXMATCHESPERLIST)));
    if (ret.size() >= MAXMATCHESTOTAL) {
        break;
    }
}
return ret;

我想避免创建新列表和使用 addAll()，因为我不需要返回新列表，而且我每秒要处理数千个元素。这种方法是我的应用程序的主要瓶颈。

我正在寻找的是一个 List 的实现，它只包含每个包含列表的 subList() 结果(那些是廉价 View ，而不是实际副本)。

我查看了常见的可疑对象，包括 java.util、Commons Collections、Commons Lang 等，但终究找不到任何此类实现。不过，我很确定它必须在某个时候实现，希望我错过了一些明显的东西。

Stack Overflow，我想问问你——有人知道这样的实现吗？我可以自己写一个，但如果轮子就在那里，我讨厌重新发明轮子。

非常欢迎提出更有效的替代方法的建议!

可选的背景详细信息(可能与我的问题不相关，但以防万一它可以帮助您理解我正在尝试做的事情):这是一个填字游戏风格的程序带有围绕主题的单词的网格。每个主题可能有任意数量的候选词列表，按照主题相关性的降序排列。例如，“电影”主题可能以电影名称列表开始，然后是 Actor 列表，然后是可能与电影相关或可能不相关的地点的通用列表，然后是英文单词的通用列表。每个列表都存储在一个通配符的 trie 结构中，以允许满足网格约束的快速查找(例如，“CAT”将存储在针对键“CAT”、“CA?”、“C??”的 trie 列表中， "?AT", ... "???"等)列表从几个单词到几万个单词不等。

对于任何给定的查询，例如“C??”，我想返回一个包含最多 N(比如 50)个匹配词的列表，按照与源列表相同的顺序排列。因此，如果列表 1 包含“C??”的 3 个匹配项，列表 2 包含 7 个，列表 3 包含 100 个，我需要一个返回列表，其中首先包含列表 1 中的 3 个匹配项，然后是列表 2 中的 7 个匹配项，然后是 40 个列表 3 中的匹配项。我希望返回的“联合 ListView ”操作比必须以与 subList() 的实现类似的方式连续调用 addAll() 更有效。

由于内存限制，缓存返回的列表不是一个选项——我的 trie 已经消耗了我的(32 位)最大堆的绝大部分。

PS 这不是家庭作业，它是针对真实项目的。非常感谢任何帮助!

Answer 1

您是否需要随机访问结果列表？或者您的客户端代码只迭代结果？

如果你只需要遍历结果。创建一个自定义列表实现，它将原始列表的列表 :) 作为实例字段。返回自定义迭代器，它将从每个列表中逐一获取项目，并在任何基础列表中没有更多项目或您已经返回 MAXMATCHESTOTAL 项目时停止。

通过一些想法，您可以对随机访问做同样的事情。