Logic programming

Logic programming has an interesting promise to solve problems: say what you want, instead of how to solve it.

As you'll see in my implementation below, the "say what you want" part is taken close to literal in logic programming. How it does so is an interesting question but I think there is a much more important question than that : how efficient is it?

Or a more practical question: is it fast?

So in this series, I'll benchmark logic programming against the traditional way of solving by programming problems.

Two sum

The problem: Given an array of integers nums and an integer target, find all pairs of integers in nums that has sum equal target.

Logic programming

(require '[clojure.core.logic :as cl]     ; logic programming library
         '[clojure.core.logic.fd :as cfd]
         '[criterium.core :as criterium]) ; for benchmarking

(defn two-sum-logic
  [target nums]
  (cl/run* [q]
    (cl/fresh [n1 n2]      ; define 2 vars correspond to 2 numbers we need to find
      (cl/membero n1 nums) ; n1 and n2 must be a member of nums
      (cl/membero n2 nums)
      (cfd/<= n1 n2)       ; constraint for n1 must be smaller than n2 to filter out duplicate results
      (cfd/+ n1 n2 target) ; n1 + n2 = target
      (cl/== q [n1 n2])))) ; q is a vector that contains n1 and n2

(two-sum-logic 10 (vec (range 10)))
;; => ([1 9] [2 8] [3 7] [4 6])

As I commented in the code above, it shows that when using logic programming, you really "say what you want" instead of saying how to solve it.

Lazy sequence

Most of the functions in Clojure operate on lazy-sequence, which means the sequence is not created until it is needed.

In this implementation we first create a lazy sequence of all possible combinations of two numbers, then apply a filter to find the combination that has a sum equal to our target

(defn two-sum-lazy-filter
  [target nums]
  (filter #(= (reduce + %) target)
          (for [i (range (count nums))
                j (range (count nums))
                :when (< i j)]
            (vector (nums i) (nums j)))))

(two-sum-lazy-filter 10 (vec (range 10)))
;; => ([1 9] [2 8] [3 7] [4 6])

Memorize

This implementation is the idiomatic way of solving the two-sum problem by using a set as a cache to store all the pairs

(defn two-sum-cache
  [target nums]
  (loop [remainings-set #{}
         res []
         i 0]
    (if (>= i (count nums))
      res
      (let [remaining (- target (nums i))]
        (if (contains? remainings-set (nums i))
          (recur remainings-set
                 (cons [(nums i) remaining] res)
                 (inc i))
          (recur (conj remainings-set remaining)
                 res
                 (inc i)))))))

(two-sum-cache 10 (vec (range 10)))
;; => ([9 1] [8 2] [7 3] [6 4])

Benchmark

Let's try to benchmark these 3 implementations to find all possible pairs that has sum = 1000 given an array with numbers from 0-1000.

(def nums (vec (range 1000)))

(def target 1000)

(criterium/bench (last (two-sum-logic target nums)))
Evaluation count : 60 in 60 samples of 1 calls.
      Execution time sample mean : 52.204231 sec
             Execution time mean : 52.213782 sec
Execution time sample std-deviation : 3.465209 sec
    Execution time std-deviation : 3.543990 sec
   Execution time lower quantile : 49.782616 sec ( 2.5%)
   Execution time upper quantile : 1.055121 min (97.5%)
                   Overhead used : 11.275750 ns

(criterium/bench (last (two-sum-lazy-filter target nums)))
Evaluation count : 1380 in 60 samples of 23 calls.
      Execution time sample mean : 44.480498 ms
             Execution time mean : 44.493556 ms
Execution time sample std-deviation : 961.141593 µs
    Execution time std-deviation : 989.203098 µs
   Execution time lower quantile : 43.941393 ms ( 2.5%)
   Execution time upper quantile : 47.852755 ms (97.5%)
                   Overhead used : 11.275750 ns

(criterium/bench (last (two-sum-cache target nums)))
      Execution time sample mean : 228.166515 µs
             Execution time mean : 228.247622 µs
Execution time sample std-deviation : 4.765209 µs
    Execution time std-deviation : 5.305996 µs
   Execution time lower quantile : 225.032231 µs ( 2.5%)
   Execution time upper quantile : 239.361348 µs (97.5%)
                   Overhead used : 11.275750 ns

Here is a couple of notes from this benchmark:

• The logic programming version is much more slower than cache version (about 200,000x times slower)
• The lazy-sequence version is slower than two-cache in this case (about 200x times slower)

Of course, this is not a fair benchmark but it has an interesting result.

Next time we'll look into how efficient it is to solve the 8-queen problem.