没有大内存如何存储和排序曾经出现过的数字？

Question

该程序给了我很多范围从 0 到大约 2^n_qubits 的整数，并且具有相同的汉明权重。下面的代码只是给出一个简单的例子，我无法控制随机数生成器，而且它也不是均匀随机采样。在我的例子中，我只得到随机生成的数字，并且需要给出一个包含所有出现过的数字的结果集。

我说一下我代码中的变量，n_e可能会在range(1, n_q)中变化，n_q可以是30或更多。实际上，我想要能够处理更大的 n_qubits 和 n_e = n_q//2 的算法，这是我的研究。 未出现的整数数量少于出现的整数数量，因为它不是均匀采样的，与我的示例代码不同。 如果元素从未出现过，我需要频繁地将元素插入到数据结构中，因此数据结构应该能够高效地执行插入运算符。

有没有时间效率和内存效率都好的算法？ 之前，如代码所示，我存储所有整数，然后对其进行排序并组合重复的相邻整数，但它需要大量内存。在某些情况下，排序后的结果数组的长度可能仅为所有整数数组的1%。 我也对哈希和二叉树有了一些了解，但不知道性能如何，需要帮助。 （我担心哈希函数的开销） 还有有好的算法推荐吗？ 预先感谢您！

下面是朱莉娅代码。

function get_basis(N_e, n_qubits::Int64) # get set of numbers of same hamming weight N_e in n_qubits bits
    basis_num::Int64 = factorial(big(n_qubits))/factorial(big(N_e))/factorial(big(n_qubits-N_e))
    basis_set = Array{Int64, 1}(undef, basis_num)
    count::Int64 = 0
    for i in 0:(2^n_qubits-1)
        if count_ones(i) == N_e
            count += 1
            basis_set[count] = i
        end
    end
    return basis_set
end

n_e = 4
n_q = 10
basis_set = get_basis(n_e, n_q)
set_len = length(basis_set)

res_len = set_len * 4
res_set = Array{Int64, 1}(undef, res_len)
for i in 1:res_len
    res_set[i] = basis_set[rand(1:set_len)]
end

sort!(res_set)

function combine!(my_set::Vector{Int64})
    r::Int64 = 1
    l::Int64 = 1       # length of processed part
    i::Int64 = my_set[r]    # row-index of current element
    tot_num::Int64 = length(my_set)
    # main loop
    while r < tot_num
        r += 1
        i2 = my_set[r]
        if i2 != i  # advance l, and move r-th to l-th
            l += 1
            i = i2
            if l < r
                my_set[l] = i
            end
        end
    end
    if l < tot_num
        resize!(my_set, l)
    end
end

combine!(res_set)
println(res_set) # res_set is what I want get

我也给出了python代码

import math
import random

def get_basis(N_e, n_qubits):
    basis_num = math.comb(n_qubits, N_e)
    basis_set = []

    val = 2**N_e - 1
    basis_set.append(val)
    for i in range(basis_num - 1):
        c = val & -val
        r = val + c
        val = (((r^val) >> 2) // c) | r
        basis_set.append(val)
    
    return basis_set

n_e = 4
n_q = 10
basis_set = get_basis(n_e, n_q)
set_len = len(basis_set)

res_len = set_len * 4
res_set = []
for i in range(res_len):
    res_set.append(basis_set[random.randint(0, set_len-1)])


res_set.sort()

def combine(my_set):
    r = 0
    l = 0      # length of processed part
    i = my_set[r]   # row-index of current element
    tot_num = len(my_set)
    # main loop
    while r < tot_num-1:
        r += 1
        i2 = my_set[r]
        if i2 != i:  # advance l, and move r-th to l-th
            l += 1
            i = i2
            if l < r:
                my_set[l] = i
    
    return my_set[:l+1]

res_set = combine(res_set)
print(res_set) # res_set is what I want get

Answer 1

强文字所以，无论如何，您都需要所有数字。最好的内存解决方案只有在您控制随机生成器的情况下：在您的算法是存储的情况下，您可以使用它来检索序列中的下一个数字。但你没有。

因此，您可以从红黑树图开始，其中键作为要存储的数字，值作为其计数。因此，如果您有重复项，它们只会增加价值。对结果进行排序也有利于您：只需本地遍历树，即可给出所有

key

value

次。性能会非常好：插入平均值为 O(log(N))，搜索给定数字是否存在于映射中为 O(log(N))，遍历结果映射以获取排序数组为 O(N)，因此 O(N* log(N)) 为整个解决方案。

当然，这不是最好的解决方案。高级方法可以使用有关您的分布的信息来组成：使二叉搜索树不是按值排列，而是按其出现的概率排列，以使加法更快（以最大速度插入更可能的值，受到惩罚的可能性较小。但这在很大程度上取决于在您的发行版上，可能会帮助或使事情变得更糟。

如果您能够以相对较低的成本将散列与分布对齐（也许可以使用良好的多项式近似），则可以通过散列来实现类似的方法。动机是让 O(1) 插入更有可能获得更可能的结果，并让它在细尾上滞后。如果分布的尾部很胖，你就有麻烦了。

还可以想象更复杂的方法来进行棘手的归档。