Lecture
The program on the PROLOGUE operates with a knowledge base consisting of facts. As a rule, the search for a solution is carried out through the enumeration of all possible facts. This can lead to significant time losses. Therefore, it is sometimes necessary to sort the facts so that the program starts viewing knowledge from the best option to speed up the search for a solution. An algorithm for sorting the facts of the PROLOG language is proposed here. The algorithm and its implementation on Visual Prolog 5.2 was made by me in 3 hours. I do not know what method it is, because I invented it myself. I heard that there is a method with some bubbles, perhaps this is his likeness. domains EntryName = string Record Number, Record Value = integer MyEnter = My_Event (EntryNumber, EntryName, ValueValid); is empty database - my_records mz (MoyaZapis) predicates show_my_mails record_value (MyAblog, RecordValue) record_select (MyZapis Z1, MyZapis Z2, MyZapis Paste, MyZapis Up Up) record_insert (my record) Sort (My Record Down, My Record Up) - (i, o) sorting rollback clauses rollback: -fail. % take the value of the record record_value (my_record (_, _, Value), Value): - !. % select which record to add and which one to send to the top record_to select (Record1, empty, empty, Record1): - !. record_to select (Record1, Record2, Record1, Record2): - record_value (Record1, Value1), record_value (Record2, Value2), Value1> Value2, ! Record_select (Record1, Record2, Record2, Record1): - ! % insert the fact back into the knowledge base write_insert (empty): - !. Record_Insert (Record): - asserta (mz (Record)), ! % sorting itself Sort (RecordDown, RecordOver): - % select a record from the knowledge base retract (mz (Record1)), % determine which of the records to pass down, % and what is possible to insert in this predicate record_to select (RecordDown, Record1, RecordDown1, RecordInsert1), % sort recursion down sorting (RecordDown1, Record2), % determine which record to insert back into knowledge % what transfer to top record_to select (RecordInsert1, Record2, RecordInsert, RecordTop), % selected entry for insertion - insert record_insert (RecordInsert), ! % end of facts - remember last Sort (Record, empty): - write_in (Write), ! show_my_mails: - mz (Record), nl, write, rollback. show my entries: - !. sorting:- sorting (empty, Record), write_in (Write), show_my_mails, ! The knowledge base “sample.txt” contains facts in the following form and order: mz (my_record (1, "I", 23)). mz (my_record (2, "you", 3)). mz (my_record (3, "he", 2)). mz (my_record (4, "she", 123)). mz (my_record (5, "they", 223)). mz (my_record (6, "you", 213)). mz (my_write (7, "who", 23)). mz (my_record (8, "what", 20)). mz (my_record (9, "where", 13)). mz (my_record (10, "when", 12)). mz (my_record (1, "I", 5)). mz (my_record (2, "you", 55)). mz (my_record (3, "he", 24)). mz (my_record (4, "she", 1)). mz (my_record (5, "they", 223)). mz (my_record (6, "you", 33)). mz (my_write (7, "who", 44)). mz (my_record (8, "what", 20)). mz (my_record (9, "where", 113)). mz (my_record (10, "when", 4)). First you need to load the facts into memory using the command: Goal consult ("trial.txt", my_records). After that, you can start sorting the facts: Goal sorting. % sort once It should be noted that sorting at a time does not arrange all the facts completely in ascending Facts of Fact: here the predicate “sorting” is just one iteration of sorting. However, in one iteration, several facts move at once to a rather long distance in the list of facts. After several executions of the “sorting” predicate, the facts will be completely sorted. The fact is that in order to evaluate the end of sorting, you need to make an additional predicate that would restart sorting in case of incomplete sorting of facts. Here are the results of sorting the input facts from the sample file: Iteration 1. my_record (4, "she", 1) my_record (2, "you", 3) my_record (3, "he", 2) my_record (1, "I", 23) my_record (4, "she", 123) my_record (6, "you", 213) my_record (7, who, 23) my_record (8, "what", 20) my_record (9, "where", 13) my_record (10, when, 12) my_record (1, "i", 5) my_record (2, "you", 55) my_record (3, "he", 24) my_record (10, when, 4) my_record (5, "they", 223) my_record (6, "you", 33) my_record (7, who, 44) my_record (8, "what", 20) my_record (9, "where", 113) my_record (5, "they", 223) Iteration 2. my_record (4, "she", 1) my_record (3, "he", 2) my_record (2, "you", 3) my_record (10, when, 4) my_record (1, "I", 23) my_record (4, "she", 123) my_record (7, who, 23) my_record (8, "what", 20) my_record (9, "where", 13) my_record (10, when, 12) my_record (1, "i", 5) my_record (2, "you", 55) my_record (3, "he", 24) my_record (8, "what", 20) my_record (6, "you", 213) my_record (6, "you", 33) my_record (7, who, 44) my_record (9, "where", 113) my_record (5, "they", 223) my_record (5, "they", 223) Iteration 3 my_record (4, "she", 1) my_record (3, "he", 2) my_record (2, "you", 3) my_record (10, when, 4) my_record (1, "i", 5) my_record (1, "I", 23) my_record (7, who, 23) my_record (8, "what", 20) my_record (9, "where", 13) my_record (10, when, 12) my_record (8, "what", 20) my_record (2, "you", 55) my_record (3, "he", 24) my_record (6, "you", 33) my_record (4, "she", 123) my_record (7, who, 44) my_record (9, "where", 113) my_record (6, "you", 213) my_record (5, "they", 223) my_record (5, "they", 223) Iteration 4 my_record (4, "she", 1) my_record (3, "he", 2) my_record (2, "you", 3) my_record (10, when, 4) my_record (1, "i", 5) my_record (10, when, 12) my_record (1, "I", 23) my_record (8, "what", 20) my_record (9, "where", 13) my_record (8, "what", 20) my_record (7, who, 23) my_record (3, "he", 24) my_record (6, "you", 33) my_record (7, who, 44) my_record (2, "you", 55) my_record (9, "where", 113) my_record (4, "she", 123) my_record (6, "you", 213) my_record (5, "they", 223) my_record (5, "they", 223) Iteration 5 my_record (4, "she", 1) my_record (3, "he", 2) my_record (2, "you", 3) my_record (10, when, 4) my_record (1, "i", 5) my_record (10, when, 12) my_record (9, "where", 13) my_record (8, "what", 20) my_record (8, "what", 20) my_record (1, "I", 23) my_record (7, who, 23) my_record (3, "he", 24) my_record (6, "you", 33) my_record (7, who, 44) my_record (2, "you", 55) my_record (9, "where", 113) my_record (4, "she", 123) my_record (6, "you", 213) my_record (5, "they", 223) my_record (5, "they", 223) As you can see, at the fifth iteration, all the facts are completely sorted. Although it would be possible to dwell on the third iteration, because the best facts were already at the beginning of the knowledge base, and the accuracy of their sorting is not so important in this task. The disadvantage of the algorithm is that if there are many records with the same values in the facts, then sorting each time will shift such facts one place up. But a more complex algorithm. Here the disadvantage described above is eliminated. And now the same records are sorted as one record: if the two records are equal, then they will form a list and then travel to sort together. If the next entry is still equal, then she will join the list. Thus, sorting is performed in several iterations, regardless of the number of identical facts. % bubbles light up and heavy ones sink % and the bubbles are the same - cling to each other domains EntryName = string Record Number, Record Value = integer MyEnter = My_Event (EntryNumber, EntryName, ValueValid); my_records; is empty My Records = My Record * database - my_records mz (MoyaZapis) predicates show_my_mails record_value (MyAblog, RecordValue) record_select (MyZapis Z1, MyZapis Z2, MyZapis Paste, MyZapis Up Up) record_insert (my record) Record_Insert (MyReports) Sort (My Record Down, My Record Up) - (i, o) sorting record_select_down (MoyaZapisi, MoyaZapisi, MoyaZapisi Down, MoyaZapisi) record_to select_up (MyZapis, MyZapis, MyZapis, MyZapis Up) records_Lead (MoyaZapisa, MoyaZapisi, MoyaZapisi) - (i, i, o) clauses % add two records with the same value Record_Leave (Record1, Record2, my_records ([Record1, Record2])): -!. % take the value of the record record_value (my_record (_, _, Value), Value): - !. record_value (my_ record ([Record | _]), Value): record_value (Record, Value),!. % select which record to add and which one to transmit further record_to select (Record1, Record2, Record1, Record2): - record_value (Record1, Value1), record_value (Record2, Value2), Value1Value2, ! record_select (Record1, Record2, Record2, Record1): - !. % if the entries are equal, then both of them need to be collected in the list and dragged down Record_Select_Down (Record1, Record2, RecordDown, empty): - record_value (Record1, Value1), record_value (Record2, Value2), Value1 = Value2, write_ (write 1, write 2, write down), ! % if not equal, then the usual comparison record_to select_down (empty, Record, Record, empty): - !. record_select_down (Record, empty, Record, empty): - !. Record_Select_Down (Record1, Record2, RecordDown, RecordUp): - record_select (Record1, Record2, RecordDown, RecordUp), ! % if the records are equal, then both of them need to be collected in the list and dragged up record_to select_up (Record1, Record2, empty, RecordUp): - record_value (Record1, Value1), record_value (Record2, Value2), Value1 = Value2, records_Lead (Record1, Record2, RecordUp), ! % if not equal, then the usual comparison record_to select_up (Record, empty, empty, Record): - !. record_to select_up (empty, Record, empty, Record): - !. Record_to select_up (Record1, Record2, RecordDown, RecordUp): - record_select (Record1, Record2, RecordDown, RecordUp), ! % insert a list of records records_insert ([Record | Records]): - write_in (Write), records_insert (Records) ! entries_insert ([]): - !. % insert record or list of records write_insert (empty): - !. record_insert (my_records (Records)): - records_insert (Records) ! Record_Insert (Record): - asserta (mz (Record)), ! % fact sorting itself Sort (RecordDown, RecordOver): - % pull the current fact from the database retract (mz (Record1)), % see what goes down further Record_Select_Down (RecordDown, Record1, RecordDown1, RecordInsert1), % cause sort recursion (continue further) sorting (RecordDown1, RecordBack1), % see what to return to the top, and what to put in the knowledge base record_to select_up (RecordInsert1, RecordBack1, RecordInsert, RecordBack), record_insert (RecordInsert), ! % end of facts - remember last Sort (Record, empty): - write_in (Write), ! % to display entries on the screen show_my_mails: - mz (Record1), nl, write (Record1), rollback. show my entries: - !. % call sorting sorting:- sorting (empty, Record), write_in (Write), show_my_mails, % repeat ! Here are the results of sorting: Iteration 1 My_record (4, "she", 1) my_record (2, "you", 3) my_record (3, "he", 2) my_record (1, "I", 23) my_record (4, "she", 123) my_record (6, "you", 213) my_record (7, who, 23) my_record (8, "what", 20) my_record (9, "where", 13) my_record (10, when, 12) my_record (1, "i", 5) my_record (2, "you", 55) my_record (3, "he", 24) my_record (10, when, 4) my_record (6, "you", 33) my_record (7, who, 44) my_record (8, "what", 20) my_record (9, "where", 113) my_record (5, "they", 223) my_record (5, "they", 223) Iteration 2 my_record (4, "she", 1) my_record (3, "he", 2) my_record (2, "you", 3) my_record (10, when, 4) my_record (1, "I", 23) my_record (4, "she", 123) my_record (7, who, 23) my_record (8, "what", 20) my_record (9, "where", 13) my_record (10, when, 12) my_record (1, "i", 5) my_record (2, "you", 55) my_record (3, "he", 24) my_record (8, "what", 20) my_record (6, "you", 33) my_record (7, who, 44) my_record (9, "where", 113) my_record (6, "you", 213) my_record (5, "they", 223) my_record (5, "they", 223) Iteration 3 my_record (4, "she", 1) my_record (3, "he", 2) my_record (2, "you", 3) my_record (10, when, 4) my_record (1, "i", 5) my_record (1, "I", 23) my_record (7, who, 23) my_record (8, "what", 20) my_record (9, "where", 13) my_record (10, when, 12) my_record (8, "what", 20) my_record (2, "you", 55) my_record (3, "he", 24) my_record (6, "you", 33) my_record (7, who, 44) my_record (9, "where", 113) my_record (4, "she", 123) my_record (6, "you", 213) my_record (5, "they", 223) my_record (5, "they", 223) Iteration 4 my_record (4, "she", 1) my_record (3, "he", 2) my_record (2, "you", 3) my_record (10, when, 4) my_record (1, "i", 5) my_record (10, when, 12) my_record (8, "what", 20) my_record (9, "where", 13) my_record (8, "what", 20) my_record (7, who, 23) my_record (1, "I", 23) my_record (3, "he", 24) my_record (6, "you", 33) my_record (7, who, 44) my_record (2, "you", 55) my_record (9, "where", 113) my_record (4, "she", 123) my_record (6, "you", 213) my_record (5, "they", 223) my_record (5, "they", 223) Iteration 5 my_record (4, "she", 1) my_record (3, "he", 2) my_record (2, "you", 3) my_record (10, when, 4) my_record (1, "i", 5) my_record (10, when, 12) my_record (9, "where", 13) my_record (8, "what", 20) my_record (8, "what", 20) my_record (1, "I", 23) my_record (7, who, 23) my_record (3, "he", 24) my_record (6, "you", 33) my_record (7, who, 44) my_record (2, "you", 55) my_record (9, "where", 113) my_record (4, "she", 123) my_record (6, "you", 213) my_record (5, "they", 223) my_record (5, "they", 223) % In general, there is a classical sorting using binary trees. Such sorting works faster than the method described above. But its disadvantage is that it performs a full sort before all the items in the list are completely ordered. And the sorting proposed by me is not fully done, only increasing the probability of the appearance of the necessary fact at the beginning of the PROLOGES fact base. I carried out a test evaluation of the classical sorting and proposed: So for the number of records 100 in the database, the classical sort makes 800 comparisons, and the proposed in the article (in two passes): 378. For 400 records, respectively: 11600 and 1500 (in two passes). However, if we consider that the time to perform one comparison in the proposed method takes longer and the number of passes increases as the number of records increases, the profitability of the classical method increases. Here is a classic example of sorting on PROLOGE: % sort using reference domains % That is when the value betrays as a link % example file is in ch11e04.pro to VIP5.5 % and shows how to use reference values % in classical sorting according to the binary tree method / * Program ch11e05.pro * / DOMAINS tree = reference t (val, tree, tree) val = integer list = integer * PREDICATES insert (integer, tree) instree (list, tree) nondeterm treemembers (integer, tree) sort (list, list) CLAUSES insert (Val, t (Val, _, _)): - !. insert (Val, t (Val1, Tree, _)): - Val & gtVal1, ! insert (Val, Tree). insert (Val, t (_, _, Tree)): - insert (Val, Tree). instree ([], _). instree ([H | T], Tree): - insert (H, Tree), instree (T, Tree). treemembers (_, T): - free (t) ! fail. treemembers (X, t (_, L, _)): - treemembers (x, l). treemembers (X, t (Refstr, _, _)): - X = Refstr. treemembers (X, t (_, _, R)): - treemembers (X, R). sort (L, L1): - % sorts the list items into a binary tree instree (L, Tree), % converts a binary tree back to the list findall (X, treemembers (X, Tree), L1). GOAL sort ([3,6,1,4,5], L), write ("L =", L), nl. % Here, reference values are used only in the home tree |
Comments
To leave a comment
Presentation and use of knowledge
Terms: Presentation and use of knowledge