Какова терминология для сокращения входных данных до отдельных элементов для ускорения вычислений?

Question

Есть ли термин для использования того факта, что данные состоят из нескольких часто повторяющихся значений для ускорения вычислений?

В качестве примера при попытке вычислить выборочную энтропию для длинной дискретной последовательности (длина = 64,000 .000.000, Distinct elements = 11, Length of substring = 3) Мне показалось, что время выполнения слишком велико (более 10 минут). Я понял, что смогу использовать относительно небольшое количество отдельных элементов для ускорения вычислений, но не смог найти никакой литературы, относящейся к этому (подозреваю, потому что не знаю, что делать в Google).

Алгоритм Sample Entropy включает подсчет пар подстрок, которые находятся в пределах определенного допуска. Это был вычислительно дорогостоящий аспект алгоритма O (n ^ 2) . Взяв только отдельные подстроки (которых было не более 1331), я смог найти пары разных подстрок в пределах допуска, затем я использовал счетчики каждой отдельной подстроки, чтобы найти общее количество пар (неотличимых ) подстроки, которые находятся в пределах определенного допуска. Этот метод существенно ускорил мои вычисления.

Есть ли у алгоритмов, использующих свойство относительно небольшого числа часто повторяющихся элементов, особую c терминологию.

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

Это широкое понятие, включающее несколько связанных терминов.

Общий, тесно связанный термин - Мемоизация , в котором результаты вычисления подзадачи для разных входных данных сохраняются и повторно используются, когда ранее увиденный ввод встречается повторно. Это немного отличается от того, что вы делаете здесь, поскольку мемоизация - это форма ленивого вычисления , когда значения распознаются оппортунистически, а не код, выполняющий предварительное исчерпывающее перечисление входных данных, которые будут обрабатываться *. 1007 *

Материализация также стоит упомянуть. Он встречается в контексте баз данных и относится к результатам запроса (также известного как табличная обработка, включая возможную фильтрацию и / или сокращение), сохраняемых для повторного использования. Активные проблемы с материализацией в основном связаны с долгосрочными соображениями, такими как обновления динамического c, поэтому он не идеально подходит для алгоритма «запустил и забыл».

Говоря о 'Dynami c', один может также может быть описать это как форму динамического c программирования , с проблемой, решаемой путем исчерпывающего перечисления и решения последовательности подзадач. В динамическом c программировании, однако, ожидается, что эти подзадачи будут иметь более регулярную и индуктивную форму, поэтому я думаю, что это натяжка.

Я бы описал здесь точную стратегию как своего рода «нетерпеливую память» ", в отличие от предположения о ленивых вычислениях, обычно присущего мемоизации.