diff options
author | Ekaitz Zarraga <ekaitz@elenq.tech> | 2024-01-09 16:40:27 +0100 |
---|---|---|
committer | Ekaitz Zarraga <ekaitz@elenq.tech> | 2024-01-09 17:18:41 +0100 |
commit | 967b888d8c4671930117a6351129bc3186a2bdff (patch) | |
tree | def51825ff20a1e300c787e741bae1f7284c79cc | |
parent | a67e75926dcbf7ccbdfe588d7ad86ca9761a8207 (diff) |
Reduce iterations in concatenate!
This commit should reduce the amount of iterations in concatenate to N
where N is the sum of the lengths of the input lists.
The previous implementation iterated from the beginning in each
concatenation because of `last-pair`.
This implementation is significantly faster in this extreme case:
(concatenate! `(,(iota 50000) ,@(map list (iota 500))))
>> Previous implementation:
real 0m0.671s
user 0m0.658s
sys 0m0.013s
>> This implementation:
real 0m0.175s
user 0m0.174s
sys 0m0.001s
The tests is done using `time`, which is not reliable at all, but using
`(trace last-pair)` shows accurately what happens with the iterations.
-rw-r--r-- | lib/srfi/1/misc.scm | 17 |
1 files changed, 10 insertions, 7 deletions
diff --git a/lib/srfi/1/misc.scm b/lib/srfi/1/misc.scm index 843ed19d..e5a7f59e 100644 --- a/lib/srfi/1/misc.scm +++ b/lib/srfi/1/misc.scm @@ -15,13 +15,16 @@ (define (concatenate! lists) (if (null? lists) '() - (fold (lambda (el acc) - (cond - ((null? acc) el) - ((null? el) acc) - (else (begin (set-cdr! (last-pair acc) el) acc)))) - (car lists) - (cdr lists)))) + (let loop ((acc '()) + (prev '()) + (rem lists)) + (cond + ((null? rem) acc) + ((null? acc) (let ((cur (car rem))) (loop cur cur (cdr rem)))) + ((null? (car rem)) (loop acc prev (cdr rem))) + (else (let ((cur (car rem))) + (set-cdr! (last-pair prev) cur) + (loop acc cur (cdr rem)))))))) (define (append-reverse rev tail) (if (null? rev) tail (append-reverse (cdr rev) (cons (car rev) tail)))) |