O (1) hạn tra

Question

Tôi muốn có thể tìm kiếm sự tồn tại của một thuật ngữ nhanh nhất có thể trong chương trình prolog hiện tại của mình, mà không có công cụ prolog đi qua tất cả các điều khoản cho đến khi nó đạt đến thuật ngữ hiện tại.

tôi đã không tìm thấy bất kỳ bằng chứng về nó .. nhưng tôi cho rằng cho

animal(lion). 
animal(zebra). 
... 
% thousands of other animals 
... 
animal(tiger). 

Động cơ SWI-Prolog sẽ phải đi qua hàng ngàn loài động vật cố gắng để thống nhất với hổ để xác nhận động vật (tiger) có trong cơ sở dữ liệu prolog của tôi.

Trong các ngôn ngữ khác, tôi tin rằng một HashSet sẽ giải quyết vấn đề này, cho phép tra cứu O (1) ... Tuy nhiên tôi dường như không tìm thấy bất kỳ hashsets hoặc hashtables nào trong tài liệu swi-prolog.

Có thư viện swi-prolog cho hashsets hay tôi có thể tự xây dựng nó bằng cách sử dụng term_hash \ 2?

thông tin thưởng, tôi sẽ hầu như phải làm nhìn lên trên một số dữ liệu tự động thêm vào, hoặc là thêm vào một HashSet cấu trúc dữ liệu hoặc sử dụng assertz

Answer 1

Tất cả các hệ thống Prolog nghiêm trọng thực hiện O này (1) tra cứu qua băm tự động và ẩn hoàn toàn cho bạn, vì vậy bạn không phải tự mình làm điều đó.

Được gọi là lập chỉ mục đối số và bạn thấy điều này được giải thích trong tất cả các sách Prolog tốt. Xem thêm "JIT (just-in-time) indexing" trong các phiên bản gần đây của nhiều hệ thống Prolog, bao gồm SWI. Lập chỉ mục cũng được áp dụng cho các mệnh đề được thêm động và là một trong những lý do khiến assertz/1 bị chậm lại và do đó không phải là lựa chọn tốt cho dữ liệu thay đổi thường xuyên hơn số liệu được đọc.

Bạn cũng có thể dễ dàng tự mình kiểm tra bằng cách tạo cơ sở dữ liệu với nhiều sự kiện hơn và thấy rằng thời gian tra cứu vẫn gần như không đổi khi lập chỉ mục đối số áp dụng.

Answer 2

Khi lập chỉ mục đối số đầu tiên được tích hợp là không đủ (lưu ý rằng một số hệ thống Prolog cũng cung cấp lập chỉ mục đa đối số), tùy thuộc vào hệ thống, bạn có thể xây dựng lược đồ lập chỉ mục của riêng mình bằng cách sử dụng thuật ngữ tích hợp hoặc thư viện. vị ngữ. Trong trường hợp của ECLiPSe, GNU Prolog, SICStus Prolog, SWI-Prolog và YAP, hãy xem tài liệu của thuộc tính term_hash/4.