Отсортированная карта в ACL2

Question

Я должен использовать отсортированную структуру карты / индекса в ACL2. В настоящее время у меня есть следующее:

( (key1 . (val1 val2)) (key2 . (val3)) (key3 . (val4 val5 val6)) )

Есть ли другой способ сделать это более эффективно?

Answer 1

Из вашего примера мне не ясно, что вы пытаетесь сделать.

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

• ваш get функция будет выглядеть как Acons
• ваш put Функция должна искать "правильное" место для размещения элемента.

Но это не особенно эффективно. Обе операции будут O(n). Кроме того, в качестве практического put операция потребует O(n) conses, что особенно дорого, так как cons выделяет память.

Обычно лучше просто использовать обычные списки ассоциаций, т.е. acons а также assoc, Основным преимуществом является то, что, поскольку он просто помещает новую пару ключ / значение в начало списка, acons равен O(1), поэтому построение ваших отображений обычно намного дешевле. Вы всегда можете отсортировать ключи alist, если вам нужно, например, используя set::mergesort или некоторую пользовательскую функцию сортировки.

Доступ к спискам по-прежнему O(n). Однако быстрые списки доступны в ACL2(h) и, по сути, предоставляют способ получения списков со скоростями хеш-таблиц. Смотрите также документацию для std / alists.