Исследовательская группа

Лаборатория языковых инструментов

Сравнение структурированных данных

March 2

В этом докладе будет рассказано о сравнении структурированных данных. Применение простых алгоритмов хоть и обеспечивает хорошую скорость для простых случаев, но их применение оказывается недостаточно широким из-за циклических структур входных данных и необходимости хранения дополнительных указателей. Авторы статьи [1] разработали алгоритм сравнения деревьев на языке Scheme, который всегда завершается и при этом не сильно медленнее более простых и узких алгоритмов для отдельных случаев.


[1] Michael D. Adams, R. Kent Dybvig. Efficient nondestructive equality checking for trees and graphs. In ICFP '08: Proceedings of the 13th ACM SIGPLAN international conference on Functional programming, September 2008, pp. 179-188.

Материалы