How Can I Increase the Speed of a Large Number of Date Conversions

[vdicarlo]

I am a programming amateur and a Python newbie who needs to convert
about 100,000,000 strings of the form "1999-12-30" into ordinal dates
for sorting, comparison, and calculations. Though my script does a ton
of heavy calculational lifting (for which numpy and psyco are a
blessing) besides converting dates, it still seems to like to linger
in the datetime and time libraries. (Maybe there's a hot module in
there with a cute little function and an impressive set of
attributes.)

Anyway, others in this group have said that the date and time
libraries are a little on the slow side but, even if that's true, I'm
thinking that the best code I could come up with to do the conversion
looks so clunky that I'm probably running around the block three times
just to go next door. Maybe someone can suggest a faster, and perhaps
simpler, way.

Here's my code, in which I've used a sample date string instead of its
variable name for the sake of clarity. Please don't laugh loud enough
for me to hear you in Davis, California.

dateTuple = time.strptime("2005-12-19", '%Y-%m-%d')
dateTuple = dateTuple[:3]
date = datetime.date(dateTuple[0], dateTuple[1],
dateTuple[2])
ratingDateOrd = date.toordinal()

P.S. Why is an amateur newbie trying to convert 100,000,000 date
strings into ordinal dates? To win try to win a million dollars, of
course! In case you haven't seen it, the contest is at www.netflixprize.com.
There are currently only about 23,648 contestants on 19,164 teams from
151 different countries competing, so I figure my chances are pretty
good. ;-)

[James T. Dennis]

Some Other Guy <bg****@microsoft.comwrote:

vdicarlo wrote:

>I am a programming amateur and a Python newbie who needs to convert
about 100,000,000 strings of the form "1999-12-30" into ordinal dates
for sorting, comparison, and calculations. Though my script does a ton
of heavy calculational lifting (for which numpy and psyco are a
blessing) besides converting dates, it still seems to like to linger
in the datetime and time libraries. (Maybe there's a hot module in
there with a cute little function and an impressive set of
attributes.)

...

>dateTuple = time.strptime("2005-12-19", '%Y-%m-%d')
dateTuple = dateTuple[:3]
date = datetime.date(dateTuple[0], dateTuple[1],
dateTuple[2])
ratingDateOrd = date.toordinal()

There's nothing terribly wrong with that, although strptime() is overkill
if you already know the date format. You could get the date like this:

date = apply(datetime.date, map(int, "2005-12-19".split('-')))

But, more importantly... 100,000,000 individual dates would cover 274000
years! Do you really need that much?? You could just precompute a
dictionary that maps a date string to the ordinal for the last 50 years
or so. That's only 18250 entries, and can be computed in less than a second.
Lookups after that will be near instantaneous:

For that matter why not memoize the results of each conversion
(toss it in a dictionary and precede each conversion with a
check like: if this_date in datecache: return datecache[this_date]
else: ret=convert(this_date); datecache[this_date]=ret; return ret)

(If you don't believe that will help, consider that a memo-ized
implementation of a recursive Fibonacci function runs about as quickly
as iterative approach).
--
Jim Dennis,
Starshine: Signed, Sealed, Delivered

[Larry Bates]

James T. Dennis wrote:

Some Other Guy <bg****@microsoft.comwrote:

>vdicarlo wrote:

>>I am a programming amateur and a Python newbie who needs to convert
about 100,000,000 strings of the form "1999-12-30" into ordinal dates
for sorting, comparison, and calculations. Though my script does a ton
of heavy calculational lifting (for which numpy and psyco are a
blessing) besides converting dates, it still seems to like to linger
in the datetime and time libraries. (Maybe there's a hot module in
there with a cute little function and an impressive set of
attributes.)

...

>>dateTuple = time.strptime("2005-12-19", '%Y-%m-%d')
dateTuple = dateTuple[:3]
date = datetime.date(dateTuple[0], dateTuple[1],
dateTuple[2])
ratingDateOrd = date.toordinal()

>There's nothing terribly wrong with that, although strptime() is overkill
if you already know the date format. You could get the date like this:

> date = apply(datetime.date, map(int, "2005-12-19".split('-')))

>But, more importantly... 100,000,000 individual dates would cover 274000
years! Do you really need that much?? You could just precompute a
dictionary that maps a date string to the ordinal for the last 50 years
or so. That's only 18250 entries, and can be computed in less than a second.
Lookups after that will be near instantaneous:

For that matter why not memoize the results of each conversion
(toss it in a dictionary and precede each conversion with a
check like: if this_date in datecache: return datecache[this_date]
else: ret=convert(this_date); datecache[this_date]=ret; return ret)

(If you don't believe that will help, consider that a memo-ized
implementation of a recursive Fibonacci function runs about as quickly
as iterative approach).

Even better do something like (not tested):

try: dateord=datedict[cdate]
except KeyError:
dateord=datetime.date(*[int(x) for x in "2005-12-19".split('-'))
datedict[cdate]=dateord
hat way you build the cache on the fly and there is no penalty if
lookup key is already in the cache.

[Josiah Carlson]

Some Other Guy wrote:

vdicarlo wrote:

>I am a programming amateur and a Python newbie who needs to convert
about 100,000,000 strings of the form "1999-12-30" into ordinal dates
for sorting, comparison, and calculations. Though my script does a ton
of heavy calculational lifting (for which numpy and psyco are a
blessing) besides converting dates, it still seems to like to linger
in the datetime and time libraries. (Maybe there's a hot module in
there with a cute little function and an impressive set of
attributes.)

...

>dateTuple = time.strptime("2005-12-19", '%Y-%m-%d')
dateTuple = dateTuple[:3]
date = datetime.date(dateTuple[0], dateTuple[1],
dateTuple[2])
ratingDateOrd = date.toordinal()

There's nothing terribly wrong with that, although strptime() is overkill
if you already know the date format. You could get the date like this:

date = apply(datetime.date, map(int, "2005-12-19".split('-')))

But, more importantly... 100,000,000 individual dates would cover 274000
years! Do you really need that much?? You could just precompute a
dictionary that maps a date string to the ordinal for the last 50 years
or so. That's only 18250 entries, and can be computed in less than a second.
Lookups after that will be near instantaneous:
import datetime

days = 365*50 # about 50 years worth
dateToOrd = {} # dict. of date string to ordinal

....

Then there's the argument of "why bother using real dates?" I mean, all
that is necessary is a mapping of date -number for sorting. Who needs
accuracy?

for date in inp:
y, m, d = map(int, date.split('-'))
ordinal = (y-1990)*372 + (m-1)*31 + d-1

Depending on the allowable range of years, one could perhaps adjust the
1990 up, and get the range of date ordinals down to about 12 bits (if
one packs netflix data properly, you can get everything in memory).
With a bit of psyco, the above is pretty speedy.

- Josiah

[Eddie Corns]

vdicarlo <vd******@gmail.comwrites:

>I am a programming amateur and a Python newbie who needs to convert
about 100,000,000 strings of the form "1999-12-30" into ordinal dates
for sorting, comparison, and calculations. Though my script does a ton
of heavy calculational lifting (for which numpy and psyco are a
blessing) besides converting dates, it still seems to like to linger
in the datetime and time libraries. (Maybe there's a hot module in
there with a cute little function and an impressive set of
attributes.)

>Anyway, others in this group have said that the date and time
libraries are a little on the slow side but, even if that's true, I'm
thinking that the best code I could come up with to do the conversion
looks so clunky that I'm probably running around the block three times
just to go next door. Maybe someone can suggest a faster, and perhaps
simpler, way.

>Here's my code, in which I've used a sample date string instead of its
variable name for the sake of clarity. Please don't laugh loud enough
for me to hear you in Davis, California.

>dateTuple = time.strptime("2005-12-19", '%Y-%m-%d')
dateTuple = dateTuple[:3]
date = datetime.date(dateTuple[0], dateTuple[1],
dateTuple[2])
ratingDateOrd = date.toordinal()

>P.S. Why is an amateur newbie trying to convert 100,000,000 date
strings into ordinal dates? To win try to win a million dollars, of
course! In case you haven't seen it, the contest is at www.netflixprize.com.
There are currently only about 23,648 contestants on 19,164 teams from
151 different countries competing, so I figure my chances are pretty
good. ;-)

I can't help noticing that dates in 'yyyy-mm-dd' format are already sortable
as strings.

>>'1999-12-30' '1999-12-29'

True

depending on the pattern of access the slightly slower compare speed _might_
compensate for the conversion speed. Worth a try.

Eddie

[vdicarlo]

Many thanks for the lucid and helpful suggestions. Since my date range
was only a few years, I used Some Other Guy's suggestion above, which
the forum is saying will be deleted in five days, to make a dictionary
of the whole range of dates when the script starts. It was so fast it
wasn't even worth saving in a file. Made the script a LOT faster. I
guess two thousand function calls must be faster than 200 million?
Like maybe a hundred thousand times faster?

I also benefitted from studying the other suggestons. I had actually
implemented an on the fly dictionary caching scheme for one of my
other calculations. I don't know why it didn't occur to me to do it
with the dates, except I think I must be assuming, as a newbie
Pythonista, that the less I do and the more I let the libraries do the
better off I will be.

Thanks for putting me straight. As someone I know said to me when I
told him I wanted to learn Python, "the power of Python is in the
dictionaries".

Funny how long it's taking me to learn that.

[Terry Reedy]

"vdicarlo" <vd******@gmail.comwrote in message
news:11********************@i38g2000prf.googlegrou ps.com...
| Many thanks for the lucid and helpful suggestions. Since my date range
| was only a few years, I used Some Other Guy's suggestion above, which
| the forum is saying will be deleted in five days, to make a dictionary
| of the whole range of dates when the script starts. It was so fast it
| wasn't even worth saving in a file. Made the script a LOT faster. I
| guess two thousand function calls must be faster than 200 million?
| Like maybe a hundred thousand times faster?

Any function called repeatedly with the same input is a candidate for a
lookup table. This is a fairly extreme example.

|| I also benefitted from studying the other suggestons. I had actually
| implemented an on the fly dictionary caching scheme for one of my
| other calculations. I don't know why it didn't occur to me to do it
| with the dates, except I think I must be assuming, as a newbie
| Pythonista, that the less I do and the more I let the libraries do the
| better off I will be.
|
| Thanks for putting me straight. As someone I know said to me when I
| told him I wanted to learn Python, "the power of Python is in the
| dictionaries".
|
| Funny how long it's taking me to learn that.

Well, look at how many of us also did not quite see the now obvious answer.

Even Python's list.sort() only fairly recently gained the optional 'key'
parameter, which implements the decorate-sort-undecorate pattern and which
often obsoletes the original compare-function parameter because it saves
time by calculating (and saving) the key only once per item instead of once
each comparison.

>>import this

The Zen of Python, by Tim Peters
[snip]
Namespaces are one honking great idea -- let's do more of those!

I include lookup dictionaries in this admonition.

tjr