将输入减少到仅不同元素以加速计算的术语是什么？

Question

是否有一个术语可以利用数据由一些多次重复的值组成的事实来加速计算？

作为一个例子，当我试图计算长离散序列的样本熵（长度=64.000.000.000，不同元素=11，子串长度=3）时，我发现运行时间太长（超过 10 分钟）。我意识到我应该能够利用相对较少的不同元素来加快计算速度，但无法找到与此相关的任何文献（我怀疑是因为我不知道该做什么 Google）。

样本熵的算法涉及计算在一定公差范围内的子串对。这是算法 O(n^2) 计算量大的方面。通过只取不同的子串（最多有 1331 个），我能够在公差范围内找到不同的子串对，然后我使用每个不同的子串的计数来找到（非不同的）对的总数) 在一定公差范围内的子字符串。这种方法大大加快了我的计算速度。

使用相对较少、重复次数较多的元素的属性的算法是否有特定的术语。

def sampen(L, m, r):
    N = len(L)
    B = 0.0
    A = 0.0

    # Split time series and save all templates of length m
    xmi = np.array([L[i : i + m] for i in range(N - m)])
    xmj = np.array([L[i : i + m] for i in range(N - m + 1)])

    # Save all matches minus the self-match, compute B
    B = np.sum([np.sum(np.abs(xmii - xmj).max(axis=1) <= r) - 1 for xmii in xmi])

    # Similar for computing A
    m += 1
    xm = np.array([L[i : i + m] for i in range(N - m + 1)])

    A = np.sum([np.sum(np.abs(xmi - xm).max(axis=1) <= r) - 1 for xmi in xm])

    # Return SampEn
    return -np.log(A / B)

def sampen2(L, m, r):
    N = L.shape[0]

    # Split time series and save all templates of length m
    xmi = np.array([L[i : i + m] for i in range(N - m)])
    xmj = np.array([L[i : i + m] for i in range(N - m + 1)])

    # Find the unique subsequences and their counts
    uni_xmi, uni_xmi_counts = np.unique(xmi, axis=0, return_counts = True)
    uni_xmj, uni_xmj_counts = np.unique(xmj, axis=0, return_counts = True)

    # Save all matches minus the self-match, compute B
    B = np.sum(np.array([np.sum((np.abs(unii - uni_xmi).max(axis=1) <= r)*uni_xmj_counts)-1 for unii in uni_xmi])*uni_xmi_counts)

    # Similar for computing A
    m +=1
    xm = np.array([L[i: i + m] for i in range(N - m + 1)])

    uni_xm, uni_xm_counts= np.unique(xm, axis=0, return_counts = True)
    A = np.sum(np.array([np.sum((np.abs(unii - uni_xm).max(axis=1) <= r)*uni_xm_counts)-1 for unii in uni_xm])*uni_xm_counts)

    return -np.log(A / B)

Answer 1

这是一个广义的概念，有几个相关术语。

一个常见的、密切相关的术语是 Memoization, wherein the results of computing a subproblem for different inputs are stored, and reused when a previously-seen input is re-encountered. That's slightly different from what you're doing here, since memoization is a form of lazy evaluation，其中值是随机识别的，而不是代码对将要处理的输入执行预先详尽的枚举。

Materialization也值得一提。它在数据库上下文中遇到，指的是查询结果（a.k.a。表格处理包括可能的过滤 and/or 减少）被存储以供重用。对物化的积极关注主要围绕动态更新等长期考虑，因此它不是运行-and-forget 算法的完美匹配。

说到'dynamic'，也可以也许将其描述为dynamic programming的一种形式，通过穷举和求解序列来解决问题的子问题。但是，在动态规划中，人们希望这些子问题具有更规则和归纳的形式，所以我认为这是一个延伸。

我将这里的精确策略描述为一种 "eager memoization"，以与记忆化通常固有的惰性评估假设形成对比。

将输入减少到仅不同元素以加速计算的术语是什么？

What is the terminology for reducing inputs to only distinct elements to speed computation?

algorithm

terminology

distinct-values