Изменение представления структуры данных во время выполнения: поиск других примеров

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

Контекст: Структуры данных "определяют", как структуры реального мира структурируются и представлены в компьютерной памяти. Для разных видов вычислений для достижения приемлемой производительности//может использоваться другая структура данных (например, реализация связанных ссылок и массивов).

Самоадаптивные (например, самообновляющиеся) структуры данных представляют собой структуры данных, которые изменяют свое внутреннее состояние в соответствии с конкретным шаблоном использования (например, деревьями, которые балансируют самостоятельно). Эти изменения являются внутренними, то есть в зависимости от данных. Более того, эти изменения ожидаются по дизайну.

Другие алгоритмы могут выиграть от внешнего изменения представления. В Например, матричное умножение - это хорошо знакомый трюк производительности для переноса "второй матрицы" (такой, что кеши используются более эффективно). Это фактически изменяет представление матрицы от основного номера строки к главному порядку столбца. Поскольку "A" не совпадает с "Transposed (A)", вторая матрица снова переносится после умножения, чтобы сохранить программу семантически корректной.

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

Я ищу программистов, которые имеют аналогичный опыт с другими примерами программ, где внешнее изменение представления выполняется в их приложении, чтобы иметь лучшую производительность. Таким образом, когда представление (выбранная реализация) структуры данных изменяется во время выполнения как явная часть программы.

Ответы

Ответ 1

Образец преобразования входного представления для обеспечения более эффективного алгоритма возникает во многих ситуациях. Я хотел бы сказать, что это важный способ подумать о разработке эффективных алгоритмов в целом. Некоторые примеры, которые приходят на ум:

  • пирамидальной сортировки. Он работает, преобразуя исходный список входных данных в двоичную кучу (возможно, мини-кучу), а затем повторно называя функцию remove-min, чтобы получить элементы списка в отсортированном порядке. Асимптотически он привязан к самому быстрому алгоритму сортировки на основе сравнения.

  • Поиск дубликатов в списке. Без изменения списка входных данных это займет время O (n ^ 2). Но если вы можете отсортировать список или сохранить элементы в хэш-таблице или в фильтре Bloom, вы можете найти все дубликаты в O (n log n) или лучше.

  • Решение линейной программы. Линейная программа (LP) - это определенная проблема оптимизации со многими приложениями в экономике и в других местах. Одним из наиболее важных методов решения LP является двойственность, что означает преобразование вашего оригинального LP в так называемое "двойное", а затем решение двойственного. В зависимости от вашей ситуации решение двойной проблемы может быть намного проще, чем решение оригинальной ( "первичной" ) LP. Эта глава книги начинается с хорошего примера первичных/двойных пластин.

  • Умножение очень больших целых чисел или многочленов. Самый быстрый метод использует БПФ; см. здесь или здесь для некоторых приятных описаний. Суть идеи состоит в том, чтобы преобразовать из обычного представления вашего многочлена (список коэффициентов) в базу оценки (список оценок этого многочлена в некоторых тщательно выбранных точках). Основа оценки делает умножение тривиальным - вы можете просто умножать каждую пару оценок. Теперь у вас есть полином продукта в базе оценки, и вы интерполируете (напротив оценки), чтобы вернуть коэффициенты, как вы хотели. Быстрое преобразование Фурье (FFT) - очень эффективный способ выполнения шагов оценки и интерполяции, и все это может быть намного быстрее, чем напрямую работать с коэффициентами.

  • Самая длинная общая подстрока. Если вы хотите найти самую длинную подстроку, которая появляется в кучке текстовых документов, одним из самых быстрых способов является создание дерева суффиксов из каждого, затем объедините их вместе и найдите самый глубокий общий node.

  • Линейная алгебра. Различные вычисления матрицы выполняются наиболее эффективно, преобразуя исходную матрицу в каноническую форму, такую ​​как нормальная форма Эрмита или вычисление a QR-факторизация. Эти альтернативные представления матрицы делают стандартные вещи, такие как нахождение инверсного, детерминанта или собственных значений намного быстрее для вычисления.

Есть, конечно, много примеров, кроме них, но я пытался придумать какое-то разнообразие.