You get a bonus - 1 coin for daily activity. Now you have 1 coin

Sort Facts

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 
created: 2014-09-23
updated: 2021-03-13
132438



Rating 9 of 10. count vote: 2
Are you satisfied?:



Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Presentation and use of knowledge

Terms: Presentation and use of knowledge