Реализация хеш-таблицы в SWI-Пролог - PullRequest
Новая
       26

Реализация хеш-таблицы в SWI-Пролог

1 голос
/ 23 апреля 2019

Итак, я должен реализовать ADT, в данном случае хеш-таблицу в SWI-Prolog.Мне нужна помощь, потому что я новичок в этом языке программирования и не знаю, с чего начать.

Это началось как реализация в python (3), где я определил класс и добавил функции для работы (добавить, is_empty ?, удалить, перефразировать, хэш и т. д.).Но теперь мне нужно сделать нечто подобное в прологе.

Я посетил некоторые другие вопросы, связанные с stackoverflow, но я все еще беспомощен.

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

Ответы [ 2 ]

3 голосов
/ 23 апреля 2019

Некоторые системы Prolog предоставляют встроенный хеш-термин или предикат библиотеки.Например, SWI-Prolog предоставляет встроенные предикаты term_hash/2 и term_hash/4.Эти предикаты часто сочетаются с индексацией первого аргумента.Простой пример: 

% dynamic predicate to hold hash table entries
% with the term hash used as first argument to
% take advantage of first-argument indexing
%
% hash_table(Hash, Term).
:- dynamic(hash_table/2).

add_hash_table_entry(Term) :-
    nonvar(Term),
    term_hash(Term, Hash),      % or term_hash/4
    assertz(hash_table(Hash, Term)).

del_hash_table_entry(Term) :-
    nonvar(Term),
    term_hash(Term, Hash),  % or term_hash/4
    retractall(hash_table(Hash, _)).

hash_table_entry(Term) :-
    (   var(Term) ->
        hash_table(_, Term) 
    ;   term_hash(Term, Hash),  % or term_hash/4
        hash_table(Hash, Term)
    ).
1 голос
/ 23 апреля 2019

Это звучит как ошибочная идея.Как будет использоваться эта «таблица хешей»?Какую алгоритмическую сложность вы ожидаете от различных операций?Почему вы хотите реализовать хеш-таблицу на языке, который не нуждается в хеш-таблицах, реализованных пользователями?

Единственный полуприличный способ сделать это будет использовать плоскуютермин для таблицы, один аргумент на ведро.Если у вас есть k блоков, то вы используете термин с этой арностью k, поэтому для 256 блоков вы получите hash_table/256. 

empty_hash_table(T) :-
    length(Buckets, 256),
    maplist(=(nil), Buckets),
    T =.. [hash_table|Buckets].

Теперь вы можете использовать arg/3, чтобы получитьведро в постоянное время.Вы можете использовать setarg/3, чтобы изменить их.

Но все это начинает звучать очень подозрительно.Вы должны объяснить свои причины лучше.Почему вы хотите реализовать хэш-таблицу в Прологе?Как это будет использоваться?

...