询问两类计算加速技术的专业术语：去重缩减输入、高重复数据特性利用

Let's break down your questions about optimizing computations for datasets with high duplicate values, using your Sample Entropy example as context:

1. Term for Reducing Input to Unique Elements #

The core process of extracting only unique elements from your dataset to eliminate redundant work is called deduplication. This is a form of data reduction where you strip out duplicate entries so you only compute results once per unique value, rather than repeating the same calculation hundreds of millions of times.

2. Term for Leveraging High-Duplicate Data for Speed #

Absolutely—this class of optimizations goes by a few related terms, depending on how you frame it:

• Frequency-weighted computation: You compute results for each unique element once, then multiply those results by the frequency (how often each unique element appears) to get the total for the full dataset.
• Group-based optimization: Group identical data points (like your substrings) and perform calculations at the group level instead of the individual level. This avoids redundant operations that would otherwise happen for every duplicate entry.
• Duplicate-aware algorithm design: A broader term for algorithms built explicitly to take advantage of high duplication, reducing time complexity by focusing on unique elements rather than the full dataset.

In your Sample Entropy case, you're combining deduplication with frequency-weighted matching. Instead of comparing every single substring pair (O(n²) time), you compare only unique substring pairs (O(k²) time, where k is the number of unique substrings) and scale the results by how often each substring occurs. That's why you saw such a huge speedup from 10+ minutes to something far faster.

Original vs. Optimized Code #

Here's your code formatted for clarity, with necessary imports added:

Original O(n²) Implementation

import numpy as np

def sampen(L, m, r):
    N = len(L)
    B = 0.0
    A = 0.0
    # 将时间序列拆分并保存所有长度为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)])
    # 保存所有匹配（排除自匹配），计算B
    B = np.sum([np.sum(np.abs(xmii - xmj).max(axis=1) <= r) - 1 for xmii in xmi])
    # 类似步骤计算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])
    # 返回Sample Entropy值
    return -np.log(A / B)

Optimized Deduplication + Frequency-Weighted Implementation

import numpy as np

def sampen2(L, m, r):
    N = L.shape[0]
    # 将时间序列拆分并保存所有长度为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)])
    # 找出唯一子序列及其出现次数
    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)
    # 保存所有匹配（排除自匹配），计算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)
    # 类似步骤计算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)

Why This Works #

Your optimized code cuts the time complexity drastically by:

1. Deduplicating substrings: Instead of processing 640 billion substrings, you only handle the 1331 unique ones.
2. Frequency weighting: For each pair of unique substrings, you calculate how many total matches exist by multiplying their occurrence counts (adjusting to exclude self-matches). This scales the result from the unique pair level to the full dataset without redundant comparisons.

This is a brilliant optimization for datasets with extremely low cardinality (few unique values relative to total size)—exactly the scenario you're dealing with.

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