07.03.244 История из жизни. Жертва закона Мура - justjune/AiSD2026 GitHub Wiki

Combinatorica (www.combinatorica.com) — библиотека алгоритмов для работы с графами, созданная автором для взаимодействия с системой компьютерной алгебры Mathematica.

Большой проблемой Mathematica является производительность: код на её языке выполняется от 1000 до 5000 раз медленнее кода на C из-за аппликативной модели вычислений и накладных расходов на интерпретацию. Кроме того, Mathematica занимает большой объём оперативной памяти (в 1990 году - 4 мегабайта), и любая попытка вычислений на больших структурах вызывала переполнение памяти.

Одним из проектных решений стало использование матриц смежности вместо списков смежности в качестве основной структуры данных. Хотя списки смежности обычно экономят память (требуют примерно n + 2m слов против n² для матрицы), для малых графов (n ≤ 100) и плотных графов матрица смежности остаётся управляемой. Для интерпретируемого языка важнее было минимизировать накладные расходы: Mathematica лучше работает со структурами постоянного размера, такими как матрицы смежности, чем со структурами непостоянного размера, такими как списки смежности.

Несмотря на проблемы с производительностью, библиотека оказалась хорошим инструментом для математических исследований. Однако со временем пользователи начали спрашивать, почему вычисления на графах небольшого размера занимают так много времени. Объяснение заключается в законе Мура: скорость работы компьютеров удваивается приблизительно каждые два года. Ожидания пользователей относительно производительности прикладных программ возрастают в соответствии с улучшениями аппаратного обеспечения. Combinatorica была рассчитана на работу со структурами данных квадратичного размера и недостаточно хорошо масштабировалась на разреженные графы.

Спустя десять лет после первоначального выпуска библиотеку полностью переписали, используя эффективную структуру данных в виде списка рёбер. Размер списков рёбер линейно зависит от размера графа. Это заметно улучшило производительность, особенно для алгоритмов с линейным или почти линейным временем исполнения. Теперь Combinatorica может обрабатывать графы, которые в 50-100 раз больше, чем те, с которыми могла работать старая версия. Разница в производительности становится заметной только для графов большего размера. Относительная разница во времени исполнения увеличивается с возрастанием n, так как разница между линейным и квадратичным ростом является асимптотической.

Повышение производительности, достигнутое благодаря использованию списков смежности, намного превышает любое улучшение, обусловленное применением кэша.

Литература

https://djvu.online/file/3wrno0HyEnchM?ysclid=mty1fzeln9926949060