brlewis is currently certified at Journeyer level.

Name: Bruce Lewis
Member since: 2000-08-29 15:54:31
Last Login: N/A

FOAF RDF Share This

Homepage: http://web.mit.edu/brlewis/www/

Notes:

Author of cgiemail, BRL

Projects

  • Lead Developer on BRL
  • Contributor on GNU

Articles Posted by brlewis

Recent blog entries by brlewis

Syndication: RSS 2.0

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

I'm having fun with ncm's programming challenge. Here's a Scheme test harness for it, assuming you call the test function timestamp-increment!

(define test-values
  '(("19991231235959" . "20000101000000")
    ("20000228235959" . "20000229000000")
    ("20000229235959" . "20000301000000")
    ("20040228235959" . "20040229000000")
    ("21000228235959" . "21000301000000")
    ("19000228235959" . "19000301000000")
    ("16000228235959" . "16000229000000")))

(define (test-answer q-a-pair) (let ((a (string-copy (car q-a-pair)))) (timestamp-increment! a) (if (string=? a (cdr q-a-pair)) 'ok (cons a q-a-pair))))

(define test-results (map test-answer test-values))

remle: Pretending you've received QUIT does not imply you must pretend you've received CRLF.CRLF.

I've made a lot of progress on my BRL tutorial. Now anybody with Tomcat or similar servlet engine can unpack learnbrl.war and get right into it. Instant web/database app development!

It's great when management is supportive. I got approval for us to pay the author of Kawa Scheme for work that will improve BRL debugging. Two coworkers got their first Scheme lesson yesterday.

4 older entries...

 

brlewis certified others as follows:

  • brlewis certified brlewis as Journeyer
  • brlewis certified karimlakhani as Apprentice
  • brlewis certified remle as Journeyer

Others have certified brlewis as follows:

  • brlewis certified brlewis as Journeyer
  • sh certified brlewis as Journeyer
  • cmm certified brlewis as Journeyer
  • mbp certified brlewis as Journeyer
  • olandgren certified brlewis as Journeyer
  • davidw certified brlewis as Journeyer
  • fufie certified brlewis as Journeyer
  • fxn certified brlewis as Journeyer
  • xach certified brlewis as Journeyer
  • remle certified brlewis as Journeyer

[ Certification disabled because you're not logged in. ]

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!

X
Share this page