Быстрая обратная сортировка в (SWI) Пролог

Question

Я ищу быстрый способ сортировки списка в обратном порядке в Прологе.Алгоритмически он должен работать так же быстро, как и стандартная сортировка, но варианты, которые я придумала, гораздо медленнее, по очевидным причинам.

Предикат rsort1/2 сортирует и затем переворачивает.

rsort1(L1, L2) :-
    sort(L1, Tmp),
    reverse(Tmp, L2).

Предикат rsort2/2 использует predsort/3 с пользовательским компаратором.

rsort2(L1, L2) :-
    predsort(reverse_compare, L1, L2).

reverse_compare(Delta, E1, E2) :-
    compare(Delta, E2, E1).

Чтобы проверить их производительность, я создал огромный случайный список, подобный этому:

?- Size = 1234567,
   findall(N, (between(1, Size, _), N is random(Size)), Ns),
   assert(test_list(Ns)).
Size = 1234567,
Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258|...].

Этовремя выполнения для стандартного sort:

?- test_list(Ns), time(sort(Ns, NsS)).
% 2 inferences, 7.550 CPU in 8.534 seconds (88% CPU, 0 Lips)
Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...],
NsS = [0, 1, 3, 5, 8, 10, 12, 14, 16|...].

... для rsort1:

?- test_list(Ns), time(rsort1(Ns, NsS)).
% 779,895 inferences, 8.310 CPU in 9.011 seconds (92% CPU, 93850 Lips)
Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...],
NsS = [1234564, 1234563, 1234562, 1234558, 1234557, 1234556, 1234555|...].

... и для rsort2:

?- test_list(Ns), time(rsort2(Ns, NsS)).
% 92,768,484 inferences, 67.990 CPU in 97.666 seconds (70% CPU, 1364443 Lips)
Ns = [183677, 351963, 737135, 246842, 22754, 1176800, 1036258, 625628|...],
NsS = [1234564, 1234563, 1234562, 1234558, 1234557, 1234556, 1234555|...].

Могу ли я сделать лучше, чем rsort1 и rsort2 по скорости?

Answer 1

Если вы после переносимой подпрограммы сортировки (то есть определенной с помощью PROLOG), вы, вероятно, не сможете реализовать что-либо быстрее (или так быстро, с необходимостью изменить порядок сортировки), чем те, которые предикаты, которые выполняют процедуры сортировки изначально в C / C ++, такие как sort/2 или msort/2.

Если скорость имеет первостепенное значение, вы, конечно, могли бы написать свой собственный непереносимый предикат с внешним определением, чтобы выполнить обратную сортировку. Например, SWI-PL интерфейс C ++ может использоваться (см. Примеры там) для написания определения C ++ для rsort/2, возможно, с использованием предикатов сравнения , также реализованных в C ++.

Аналогично, вы также можете написать rsort/2 на C, используя интерфейс SWI-PL C. src/pl-list.c в источнике SWI-PROLOG содержит реализации методов сортировки (а именно nat_sort()), которые используются для sort/2, msort/2 и keysort/2. Чтобы реализовать rsort/2, вам может потребоваться только следовать их реализации и настроить / изменить интерпретацию вызовов на compare(), которая описывает стандартный порядок терминов.

Answer 2

определить предикаты:
1. получить самый низкий номер в списке.
2. удаление элемента в списке.
3. объединение двух списков.
4. сортировка списка по
а) получение самого низкого
б) удаление самого низкого в списке
в) отсортировать новый список без наименьшего (рекурсия)
с базовым списком правил правил ([X], [X]).