如何在Julia中使用生成器优化整数除数算法？

我正在用Julia编写一个优化的整数除数算法，最耗时的因式分解部分已经借助Primes.jl实现，目前算法速度尚可，但希望进一步优化。由于最终仅需遍历除数，我尝试用生成器减少内存分配，却遇到了Iterators.Flatten的类型不稳定问题——例如Iterators.Flatten(((0 for i in 1:5), (1 for i in 1:5)))会返回eltype为Any的结果。特此请教如何用生成器优化该函数。

现有实现代码 #

基础版本 #

using Primes

function divisors(n)
    d = Int64[1]
    for (p, e) in factor(n)
        r = 1
        l = length(d)
        for i in 1:e
            r *= p
            for j in 1:l
                push!(d, d[j]*r)
            end
        end
    end
    return sort(d) # 非必需步骤
end

预分配优化版本（提速25%） #

function divisors2(n)
    f = factor(n)
    m = prod(e + 1 for (p, e) in f)
    d = Vector{Int64}(undef, m)
    k = 1
    d[k] = 1
    for (p, e) in f
        r = 1
        l = k
        for i in 1:e
            r *= p
            for j in 1:l
                d[k+=1] = d[j]*r
            end
        end
    end
    return sort(d) # 非必需步骤
end

生成器优化方案 #

核心问题分析 #

Iterators.Flatten出现类型不稳定，通常是因为传入的子迭代器类型不一致或eltype无法被Julia的类型推断系统明确识别。要解决这个问题，需确保构建的所有子迭代器具有相同的明确元素类型，或改用类型推断更可靠的迭代器组合方式。

方案1：递归式生成器（类型稳定） #

基于质因数分解结果递归生成除数，借助Iterators.product确保类型推断准确：

using Primes

function divisors_gen(n)
    f = factor(n)
    isempty(f) && return (1,)
    
    # 拆分第一个质因数与剩余因数
    ((p, e), rest...) = f
    # 生成当前质因数的所有幂次：p⁰, p¹, ..., pᵉ
    powers = (p^k for k in 0:e)
    # 递归生成剩余质因数对应的除数
    rest_divisors = divisors_gen(prod((p^e for (p,e) in rest)))
    
    # 通过笛卡尔积展开，生成所有除数的乘积组合
    return (a * b for (a, b) in Iterators.product(powers, rest_divisors))
end

• 优势：完全按需生成除数，内存分配极低；Iterators.product的两个输入迭代器均为Int64类型，生成器的eltype可被准确推断为Int64，无类型不稳定问题。
• 注意：若需要有序除数，可将生成器转为数组后排序（如sort(collect(divisors_gen(n)))）；若仅需遍历处理，直接使用生成器更高效。

方案2：迭代式生成器（无递归） #

通过迭代合并每个质因数的幂次组合，同样保证类型稳定：

using Primes

function divisors_iter(n)
    f = factor(n)
    current = (1,)
    
    for (p, e) in f
        # 生成当前质因数的所有幂次
        powers = (p^k for k in 0:e)
        # 合并现有除数与当前幂次的所有乘积组合
        current = (a * b for (a, b) in Iterators.product(current, powers))
    end
    
    return current
end

• 逻辑：初始除数集合为(1,)，对每个质因数，将现有除数与该质因数的所有幂次做笛卡尔积，生成新的除数组合。
• 类型稳定性：由于current和powers的eltype均为Int64，生成器的元素类型可被准确推断。

方案3：类型稳定的Flatten用法 #

若坚持使用Iterators.Flatten，需确保所有子迭代器的eltype一致：

using Primes

function divisors_flatten(n)
    f = factor(n)
    current = (1,)
    
    for (p, e) in f
        # 为每个幂次生成类型明确的子生成器
        sub_gens = ((d * p^k for d in current) for k in 0:e)
        # 合并所有子生成器，此时Flatten可推断出eltype为Int64
        current = Iterators.flatten(sub_gens)
    end
    
    return current
end

• 关键：每个sub_gens中的生成器元素类型均为Int64，因此Iterators.flatten能准确推断出生成器的eltype，避免类型不稳定。

性能对比 #

• 生成器版本无需预先分配数组，适合仅需遍历除数的场景，内存开销远低于数组版本。
• 若需要频繁访问所有除数或排序，预分配数组的版本（divisors2）在速度上仍有优势；若仅需单次遍历处理，生成器版本更高效。

内容的提问来源于stack exchange，提问作者AboAmmar