存储一组序列的所有子序列时减少内存使用

Question

我有一组输入序列（表示为列表），对于每个输入序列，我都会生成一组其所有子序列（也包括列表）。这些子序列作为键存储在EQUAL哈希表中，并且永远不会进行垃圾回收或修改（但是，相关联的值会被修改）。

我的问题是，我目前用于实现此目的的方法使用的堆空间比我想要的要多得多。

为了弄清楚我在说什么，假设我们有一个序列：

#1=(A B C D)

子序列为：

#2=()
#3=(A)
#4=(A B)
#5=(A B C)
#6=(A B C D)
#7=(B)
#8=(B C)
#9=(B C D)
#10=(C)
#11=(C D)
#12=(D)

以下代码（我承认不是很好）会生成此集合（除了我实际上并不关心的空子序列）：

(defun subseqs-of-length (length sequence)
  (if (< (length sequence) length)
      nil
      (loop for start from 0 to (- (length sequence) length)
           collect (subseq sequence start (+ start length)))))

(defun subseqs-of-length-< (length sequence)
  (loop for len from 1 to (1- length)
     append (subseqs-of-length len sequence)))

(defun all-subseqs (sequence)
    (subseqs-of-length-< (1+ (length sequence)) sequence))

可以想象，在很多输入序列中，这会消耗大量的堆。

我可以想到的最明显的节省内存的方法是共享一堆列表结构。例如，您可以构建11的(cons 'c '#12#)列表，9的(cons 'b '#11#)列表，8的列表(cons 'b '#10#等等。如果多个调用的输出all-subseqs可以共享结构，那就更好了。但是我想不出一种优雅的写法。

我的问题有两个：

1. 是否有一种优雅的书写方式，all-subseqs以便其结果能以这种方式共享结构？
2. 在我看来，天真地生成子序列并编写函数来压缩结果并定期运行它可能会更容易。这不是一个愚蠢的主意吗？
3. 有没有一种更有效的内存存储方式来存储这些子序列并访问/更新与它们相关的值？也许使用数组的东西，或者使用其他数据结构而不是哈希表？

Answer 1

重建子序列所需的最少信息量是多少？

序列、起始索引和结束索引怎么样？将开始/结束索引存储在二维哈希表（哈希表的哈希表）或二维数组中。然后编写函数来处理该数据结构（根据给定的序列、开始索引和结束索引等重建子序列）。

另一个想法：如果你真的想在数据结构中存储子序列，你可以使用N维哈希表（哈希表的哈希表的哈希表......），其中N是序列的长度。您得到的不是元素的链接列表，而是哈希表的链接树。每个哈希表中都有一个特殊的键，存储键控序列一直到该点的实际值（也就是说，该键控序列是否确实有值）。每个哈希表中的其他链接都指向树中更下方的分支。

如果列表中的每个元素都是一个符号，那么一个列表中的 'a 将与另一个列表中的 'a eq （共享相同的内存位置）。我认为这意味着您可以通过添加数据结构的链接来获得 O(N) 存储增长 + 任何增量增长。