Быстрый двумерный массив в прологе

Question

Каков наиболее эффективный способ представления двумерных массивов в прологе? Я думал об одном длинном списке или списке списков, но у них есть линейное время доступа, которое кажется слишком медленным для моей проблемы. Я не обязательно ищу готовое решение, а скорее представляю, как оно должно быть реализовано.

Answer 1

Вы можете получить логарифмический доступ по времени с деревьями AVL или красно-черными деревьями, см. Библиотеку (assoc) и библиотеку (rbtrees) в SWI и YAP. Для постоянного доступа создайте термин с N аргументами и используйте arg / 3 для эффективного доступа. Каждый из этих аргументов может снова быть термином с арностью N, поэтому у вас есть массив с эффективным доступом для чтения. Используя setarg / 3, вы можете даже деструктивно изменять элементы, теряя при этом хорошие логические свойства и гораздо более болезненные отладку и тестирование. Во многих случаях вы можете переформулировать свои алгоритмы, чтобы не требовать произвольного доступа, и работать со списками списков. Если это невозможно, AVL или другие сбалансированные деревья часто являются очень хорошим вариантом.