19 Nov 2004 brlewis   » (Journeyer)

In Coding Challenge: Increment a date/timestamp string, ncm challenges us to "consider the string as a pure 14-digit number, with digits that have very odd add-with-carry relationships." Then think of a fun-to-code way to write a function that could be "a lot faster than calling mktime etc."

Besides losing the libary-call overhead, there are other reasons such a function could be made very fast. Assuming a random distribution of tiemstamps,

  • Nine out of ten times this function would only be incrementing one character.

  • Fifty-nine times out of sixty this function would be incrementing one or two characters.

  • Since these times are GMT and we ignore leap seconds, only once in 24 * 60 * 60 times do we care how many days are in any given month.

Interestingly, nobody seems interested in writing the function this way. It seems much more fun for people to focus on conciseness rather than performance.

For what it's worth, I wrote a Scheme version that does not allocate new objects, is tail recursive, uses functions that are likely to be inlined, and does multiplication and modulo only with constant powers of two, allowing compiler optimization into bitwise operations.

It is longer than the other posted solutions, but all the way through it focuses on finding the most common case, doing it, and returning immediately.

(define (timestamp-increment! timestamp)
  (timestamp-position-increment! timestamp 13))

(define (timestamp-position-increment! timestamp pos) (let ((current-char (string-ref timestamp pos))) (case pos ((13 11 3 2 1 0) ; last digits of second, minute, all year digits (timestamp-position-increment-simple! timestamp pos current-char #\0 #\9)) ((12 10) ; first digits of second, minute (timestamp-position-increment-simple! timestamp pos current-char #\0 #\5)) ((9) ; last digit of hour (timestamp-position-increment-depending! timestamp pos current-char #\0 #\0 #\9 #\3 #\2)) ((8) ; first digit of hour (timestamp-position-increment-simple! timestamp pos current-char #\0 #\2)) ((7) ; last digit of day (timestamp-position-increment-day! timestamp pos current-char)) ((6) ; first digit of day (timestamp-position-increment-simple! timestamp pos current-char #\0 (if (february? timestamp) #\2 #\3))) ((5) ; last digit of month (timestamp-position-increment-depending! timestamp pos current-char #\0 #\1 #\9 #\2 #\1)) ((4) ; first digit of month (timestamp-position-increment-simple! timestamp pos current-char #\0 #\1)))))

(define (timestamp-position-increment-simple! timestamp pos current-char ch0 ch9) (if (char=? current-char ch9) (begin (string-set! timestamp pos ch0) (timestamp-position-increment! timestamp (- pos 1))) (string-set! timestamp pos (next-digit current-char))))

(define (next-digit ch) (integer->char (+ 1 (char->integer ch))))

(define (timestamp-position-increment-depending! timestamp pos current-char ch0 ch0-special ch9 ch9-special chprev-special) (if (and (char=? current-char ch9-special) (char=? (string-ref timestamp (- pos 1)) chprev-special)) (begin (string-set! timestamp pos ch0-special) (timestamp-position-increment! timestamp (- pos 1))) (timestamp-position-increment-simple! timestamp pos current-char ch0 ch9)))

(define (timestamp-position-increment-day! timestamp pos current-char) (let ((first-day-pos (string-ref timestamp (- pos 1)))) (case first-day-pos ((#\0 #\1) (timestamp-position-increment-simple! timestamp pos current-char #\0 #\9)) ((#\2) (if (char<? current-char #\8) (string-set! timestamp pos (next-digit current-char)) (if (february? timestamp) (timestamp-position-increment-simple! timestamp pos current-char #\1 (ly-day-char timestamp)) (timestamp-position-increment-simple! timestamp pos current-char #\0 #\9)))) ((#\3) (timestamp-position-increment-simple! timestamp pos current-char #\1 (case (string-ref timestamp (- pos 2)) ((#\2 #\3 #\5 #\7 #\8 #\0) #\1) ; 31 in December, March, etc. ((#\1) (if (char=? #\0 (string-ref timestamp (- pos 3))) #\1 ; 31 days in January, 30 in November #\0)) (else #\0)))))))

(define (ly-day-char timestamp) (if (positive? (mod4 (string-ref timestamp 2) (string-ref timestamp 3))) #\8 ; year not a multiple of 4 (if (or (char<? #\0 (string-ref timestamp 2)) (char<? #\0 (string-ref timestamp 3))) #\9 ; multiple of 4 but not on a century (if (positive? (mod4 (string-ref timestamp 0) (string-ref timestamp 1))) #\8 ; multiple of 4 century #\9)))) ; regular century

(define (mod4 ch1 ch2) (modulo (+ (* 2 (modulo (char->integer ch1) 2)) (modulo (char->integer ch2) 4)) 4))

(define (february? timestamp) (and (char=? #\2 (string-ref timestamp 5)) (char=? #\0 (string-ref timestamp 4))))

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!