2013-07-30: SIQ: Kth Element from the End of a List
The source for this post is online at 2013-07-30-k-from-end.rkt.
One of my students brough this interview question to my attention:
What is the most efficient way to find the kth element from the end of a single linked list?
Let’s see how to do it a bunch of different ways in Racket.
-
First, let’s set up a testing infrastructure. We’ll have a very large list where each element is its offset from the end, so that (equal? (k-from-end k l) k).
(define l (for/list ([i (in-range N)]) (- N i 1))) (define (test k-from-end) (for ([k (in-range N)]) (check-equal? (k-from-end k l) k)))
However, since we’re interested in speed, as well as correctness, we should time when we test.
(define (time label k-from-end) (define start (current-inexact-milliseconds)) (test k-from-end) (define end (current-inexact-milliseconds)) (printf "~a: ~a\n" (real->decimal-string (- end start)) label))
Once this infrastructure is in place, we can try a variety of techniques.
1 Reverse and then Index
One simple way to get the answer is to reverse the list and then index into it:
We could try to make this faster by using an unsafe list-ref, as well:
(define (reverse&unsafe-list-ref k l) (unsafe-list-ref (reverse l) k))
And we could try to make an unsafe reverse:
(define (unsafe-reverse l) (let loop ([acc null] [l l]) (if (null? l) acc (loop (cons (unsafe-car l) acc) (unsafe-cdr l))))) (define (unsafe-reverse&unsafe-list-ref k l) (unsafe-list-ref (unsafe-reverse l) k))
2 Computed Index
Rather than reversing and indexing to k, we could directly go to the kth from the end:
And an unsafe version of this as well:
(define (length&unsafe-list-ref k l) (unsafe-list-ref l (- (length l) k 1)))
And we could try to make the call to length unsafe as well:
(define (unsafe-length l) (let loop ([acc 0] [l l]) (if (null? l) acc (loop (unsafe-fx+ 1 acc) (unsafe-cdr l))))) (define (unsafe-length&unsafe-list-ref k l) (unsafe-list-ref l (- (unsafe-length l) k 1)))
3 Double Walk
After we’ve exhausted the obvious solutions, we could try something a bit more clever. For instance, we could bump one pointer out by k and then walk two pointers at the same time. When the one k down hits the end, the close pointer should be at the correct element.
(define (double-walk k l) (let loop ([l l] [k-down (list-tail l (+ k 1))]) (if (empty? k-down) (first l) (loop (rest l) (rest k-down)))))
And an unsafe version:
(define (unsafe-double-walk k l) (let loop ([l l] [k-down (unsafe-list-tail l (unsafe-fx+ k 1))]) (if (null? k-down) (unsafe-car l) (loop (unsafe-cdr l) (unsafe-cdr k-down)))))
4 Fused length and index
Another idea is to take the computed index and realize that when trying to find the length, you have to traverse the whole list, but on the way back up the list, you’d know when you were k from the end.
(define (fused-length+list-ref k l) (let/ec esc (let loop ([l l]) (cond [(empty? l) 0] [else (define n (loop (rest l))) (if (= n k) (esc (first l)) (add1 n))]))))
And there’s a similar unsafe version:
(define (unsafe-fused-length+list-ref k l) (let/ec esc (let loop ([l l]) (cond [(null? l) 0] [else (define n (loop (unsafe-cdr l))) (if (unsafe-fx= n k) (esc (unsafe-car l)) (unsafe-fx+ n 1))]))))
5 Ring Buffer
Finally, another idea is to create a fixed-size vector of k elements and fill it in as you traverse the whole list and then quickly extract the appropriate element as you get to the end.
(define (ring-buffer k+ l) (define k (add1 k+)) (define rb (make-vector k #f)) (let loop ([l l] [next 0]) (cond [(empty? l) (vector-ref rb (modulo (- next k) k))] [else (vector-set! rb next (first l)) (loop (rest l) (modulo (add1 next) k))])))
And a similarly unsafe version:
(define (unsafe-ring-buffer k+ l) (define k (unsafe-fx+ k+ 1)) (define rb (make-vector k #f)) (let loop ([l l] [next 0]) (cond [(null? l) (unsafe-vector-ref rb (unsafe-fxmodulo (unsafe-fx- next k) k))] [else (unsafe-vector-set! rb next (unsafe-car l)) (loop (unsafe-cdr l) (unsafe-fxmodulo (unsafe-fx+ next 1) k))])))
6 Results
Now, given all these different versions, which one is the fastest? If we experiment N set to 1000, then the results are:
21.38: length&list-ref |
23.16: unsafe-length&unsafe-list-ref |
23.43: unsafe-double-walk |
26.12: unsafe-fused-length+list-ref |
26.81: reverse&unsafe-list-ref |
28.98: length&unsafe-list-ref |
29.67: double-walk |
30.07: reverse&list-ref |
30.92: unsafe-reverse&unsafe-list-ref |
34.69: fused-length+list-ref |
36.75: unsafe-ring-buffer |
50.45: ring-buffer |
My student told me that his interviewer expected him to create the double-walk version to successfully pass the test. Interestingly, the most obvious answer length&list-ref is the fastest in Racket and using unsafe operations rarely produces a significant speed up.
7 Yo! It’s almost time to go!
But first let’s remember what we learned today!
Write the program that is best to read and understand. Racket is fast enough without your help.
If you’d like to run this exact code at home, you should put it in this order:
(require rackunit racket/list racket/unsafe/ops) (define N 1000) <testing> <timing> (define-syntax-rule (time-it f) (begin (collect-garbage) (collect-garbage) (collect-garbage) (time 'f f))) <reverse&list-ref> (time-it reverse&list-ref) <reverse&unsafe-list-ref> (time-it reverse&unsafe-list-ref) <unsafe-reverse&unsafe-list-ref> (time-it unsafe-reverse&unsafe-list-ref) <length&list-ref> (time-it length&list-ref) <length&unsafe-list-ref> (time-it length&unsafe-list-ref) <unsafe-length&unsafe-list-ref> (time-it unsafe-length&unsafe-list-ref) <double-walk> (time-it double-walk) <unsafe-double-walk> (time-it unsafe-double-walk) <fused-length+list-ref> (time-it fused-length+list-ref) <unsafe-fused-length+list-ref> (time-it unsafe-fused-length+list-ref) <ring-buffer> (time-it ring-buffer) <unsafe-ring-buffer> (time-it unsafe-ring-buffer)