trjhtr

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))))

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