3
\$\begingroup\$

I'm writing a Genetic Algorithm, and need to write a function that crosses two gene sequences. Basically, I want it to work like this:

(running-cross [1 2 3 4 5 6 7 8 9] ; Gene sequence 1
               [11 22 33 44 55 66 77 88 99] ; Gene sequence 2
               [2 5]) ; The "cross points"
=> [1 2 33 44 55 6 7 8 9]

Note how it crosses over to the second sequence at index 2, and back to the first sequence at index 5. See the related PPCG challenge for more examples.

I have two main concerns with my implementation:

  • It's ugly. The reducing function is atrocious, but I don't know what can be improved. The short names don't help, but longer names would add significant bloat which wouldn't be great either.

  • It's inefficient. It requires iterating the entire gene sequence, even if there are few, or even no cross over points. Of course I could add a special case and check if the points are empty first, but that still doesn't help much. Say there's a single cross over point at the end of the genes. It will require a full iteration regardless. I can't tell if O(n) is the best I'm going to get, but I'd prefer n be the number of cross-over points, not the number of genes per sequence.


(defn running-cross [genes other-genes cross-points]
  (let [cp-set (set cross-points)]
    (->> (map vector (range) genes other-genes)

      (reduce (fn [[g1? acc] [i g1 g2]]
                (let [g1?' (if (cp-set i) (not g1?) g1?)]
                  [g1?' (conj acc (if g1?' g1 g2))]))
              [true []])

      (second))))
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

I tried writing it with a recursive loop. I personally find it a bit easier to read, but I guess it depends on how familiar you are with recursion.

(defn running-cross
    [genes other-genes cross-points]
    (loop [remaining-cross-points cross-points 
           last-cross 0
           take-from-g1? true
           result []]
        (let [next-gene (if take-from-g1? genes other-genes)
              next-cross (first remaining-cross-points)]
            (if next-cross
                (recur (rest remaining-cross-points)
                       next-cross
                       (not take-from-g1?)
                       (concat result (subvec next-gene last-cross next-cross)))
                (concat result (subvec next-gene last-cross))))))

As for efficiency, my algorithm is a lot faster; especially when there are few cross-points. I believe this is mainly because it iterates over the cross-points instead of the full length of the genes, and then uses subvec and concat which are quite efficient when used on vectors.

Here are some times:

;; 5 000 000 length genes, crossing over on every index
user=> (do (time (running-cross-mine (vec (range 5000000)) (vec (range 5000000)) (vec (range 5000000)))) nil)
"Elapsed time: 3298.197955 msecs"
nil
user=> (do (time (running-cross-yours (vec (range 5000000)) (vec (range 5000000)) (vec (range 5000000)))) nil)
"Elapsed time: 11672.627633 msecs"
nil

;; 5 000 000 length genes, crossing over once
user=> (do (time (running-cross-mine (vec (range 5000000)) (vec (range 5000000)) [2500000])) nil)
"Elapsed time: 287.335904 msecs"
nil
user=> (do (time (running-cross-yours (vec (range 5000000)) (vec (range 5000000)) [2500000])) nil)
"Elapsed time: 6160.856827 msecs"
nil
\$\endgroup\$
1
  • \$\begingroup\$ I actually prefer the look of mine, but I can't deny that efficiency increase. That will definitely help down the road. Thank you. \$\endgroup\$ Apr 3, 2018 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.