basic implementation of skiplist

skiplist.clj

(ns skiplist.core)

(defn probability [& {:keys [p] :or {p 1/2}}]
  (> p (rand)))

(defn remove-duplicate [s]
  (distinct s))

(def c (atom 0))

(defn make-list [s & {:keys [p] :or {p 1/2}}]
  (loop [s s
         bottoms (list s)]
    (if-not (seq s)
      (remove-duplicate bottoms)
      (let [up (filter (fn [_] (probability :p p)) s)]
        (recur up (conj bottoms s))))))

(defn search [s n]
  (letfn [(search-fn [s n]
            (loop [s s]
              (when (seq s)
                (let [v (first s)]
                  (cond
                   (> v n) false
                   (== v n) n
                   (< v n) (recur (rest s)))))))]
    (map search-fn s (repeat n))))

(defn search-n-count [s n]
  (letfn [(search-fn [s n]
            (reset! c 0)
            (loop [s s]
              (swap! c inc)
              (when (seq s)
                (let [v (first s)]
                  (cond
                   (> v n) false
                   (== v n) n
                   (< v n) (recur (rest s)))))))]
    [(take 1 (drop-while #(or (false? %1) (nil? %1)) (map search-fn s (repeat n)))) @c ]))

user> (let [n (rand-int 100)
                 list (make-list (range 100))]
        (println list)
        (search-n-count list n))
((59) (58 59) (14 58 59 80) (8 14 41 58 59 78 80 94) (8 9 14 15 24 41 43 58 59 78 80 82 83 94 97) (1 5 6 8 9 14 15 24 30 33 38 41 43 47 48 52 53 54 58 59 65 74 75 78 80 82 83 94 97 98 99) (0 1 2 5 6 8 9 10 11 14 15 17 20 23 24 25 28 30 33 34 36 38 39 40 41 43 44 47 48 50 52 53 54 57 58 59 64 65 70 74 75 78 79 80 81 82 83 84 89 91 94 97 98 99) (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99))
[(93) 18]
user> (let [n (rand-int 100)
                 list (make-list (range 100))]
        (println list)
        (search-n-count list n))
((82) (37 82) (0 37 82) (0 12 37 63 82) (0 12 37 52 63 82) (0 12 37 45 51 52 63 82 85 93 98) (0 3 6 12 15 20 22 23 24 26 30 35 37 45 51 52 63 67 69 71 77 82 84 85 87 93 97 98) (0 1 3 6 7 8 12 15 18 19 20 21 22 23 24 26 30 35 37 38 43 45 46 51 52 53 58 60 61 63 66 67 68 69 71 72 75 77 78 79 80 81 82 84 85 87 88 89 93 94 97 98 99) (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99))
[(91) 94]
user> (let [n (rand-int 100)
                 list (make-list (range 100))]
        (println list)
        (search-n-count list n))
((56) (56 82) (24 56 80 82) (24 25 26 56 69 80 82 91) (16 24 25 26 38 55 56 57 69 77 80 82 89 91 93) (16 22 24 25 26 36 38 55 56 57 69 71 73 77 80 82 89 91 93 95 98) (0 9 12 16 17 18 21 22 24 25 26 29 34 35 36 37 38 41 52 54 55 56 57 58 59 62 64 69 71 73 75 77 78 80 82 85 87 89 91 93 94 95 96 97 98 99) (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99))
[(77) 92]

user> (for [_ (range 10)]
           (let [n (rand-int 100)
                 list (make-list (range 100))]
             (search-n-count list n)))
([(83) 10] [(62) 10] [(97) 10] [(66) 10] [(55) 10] [(53) 10] [(29) 10] [(54) 10] [(60) 10] [(86) 10])