Yes, the deduplication can also be performed using retractAll:
Code: Select all
class facts
exampleFact : (string).
class predicates
dedupExampleFactDb : ().
clauses
dedupExampleFactDb() :-
foreach exampleFact(S) do
retractAll(exampleFact(S)),
assertA(exampleFact(S))
end foreach.
The advantage over the no-list-solution, I proposed before, is, that it does not eat up stack in recursion. Disadvantage is however, that it is in the worst case even more inefficient than my no-list-solution:
Let us count each try to match a fact with a value as 1 step (matches with unbound variables shall not count). The worst case is, that the database consists of n facts having n distinct values (i.e. that there are no duplicates).
In my before proposed no-list-solution the line
if not(exampleFact(Strg)) then is executed n times, whereby first time doing 0 steps, second time doing 1 step, etc. until n'th time doing n-1 steps. In total that are 0 + 1 + ... + n-1 = 0.5*n^2 - 0.5*n steps.
In the
retractAll-solution (in above code box) line
retractAll(exampleFact(S)) is executed n times and does each time n steps (Thomas may correct me, if retractAll is implemented differently). So, in total that are n^2 steps.
In contrast the
list::removeDuplicates predicate is implemented using a red-black tree (per package
setM_redBlack) to keep track of the already seen values. Let's count now comparison of two values as 1 step. Lookup and insert in a red-black tree having m nodes is running in O(log m) steps. Hence the removeDuplicates predicate runs on a list with n elements in O(log 1 + log 2 + ... + log n) = O(n log n) steps. The transfer of the values from database to list and back runs in O(n) and thus does not increase the cost in terms of big O. So the fact-deduplication using
list::removeDuplicates runs in only O(n log n) steps, while the both solutions without lists take O(n^2) steps.
Regards
Martin