RE: [Haskell-cafe] the case of the 100-fold program speedup
Don't knock it! Using a functional language helped you to think about the problem in a new way, and throw together a prototype that worked in a short enough time that you actually did it. A merit of fp is, I think, that you can explore the algorithm design space much more quickly -- and algorithms are the dominant factor in the performance equation. Simon | -Original Message- | From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Seth | Gordon | Sent: 15 November 2006 20:49 | To: haskell-cafe@haskell.org | Subject: Re: [Haskell-cafe] the case of the 100-fold program speedup | | As Lily Tomlin would say, neVERmind. | | Simon P-J asked me, in email, whether the deforestation was the thing | that actually made the program faster or whether it was just the thing | that made me think about how to solve the problem. I realized that my | fast program had *another* difference from the earlier, slower program: | it was based on an algorithm that was specifically designed to clip | polygons to rectangles, whereas OGR just had a function to compute the | intersection between two arbitrary polygons. | | So I threw together a version that accumulated all the vertices of the | clipped polygon in a list and then iterated through the list to compute | the centroid--i.e., preserving everything from my fast program except | the deforestation--and it ran at almost exactly the same speed as the | deforested program. (Actually, it ran 2% faster, but that could be just | random variation from things like the load on the database server.) | | "The tragedy of science: a beautiful theory slain by an ugly fact." | | "T. H. Huxley said it first." | ___ | Haskell-Cafe mailing list | Haskell-Cafe@haskell.org | http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] the case of the 100-fold program speedup
As Lily Tomlin would say, neVERmind. Simon P-J asked me, in email, whether the deforestation was the thing that actually made the program faster or whether it was just the thing that made me think about how to solve the problem. I realized that my fast program had *another* difference from the earlier, slower program: it was based on an algorithm that was specifically designed to clip polygons to rectangles, whereas OGR just had a function to compute the intersection between two arbitrary polygons. So I threw together a version that accumulated all the vertices of the clipped polygon in a list and then iterated through the list to compute the centroid--i.e., preserving everything from my fast program except the deforestation--and it ran at almost exactly the same speed as the deforested program. (Actually, it ran 2% faster, but that could be just random variation from things like the load on the database server.) "The tragedy of science: a beautiful theory slain by an ugly fact." "T. H. Huxley said it first." ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] the case of the 100-fold program speedup
Henning Thielemann wrote:
> On Tue, 14 Nov 2006, Seth Gordon wrote:
>
>
>>It took me a week to figure out the right algorithm for combining these
>>two procedures and write some almost-working code that implemented it.
>>It took a co-worker of mine another few days to find the bugs that had
>>eluded me.
>
>
> Were these bugs of the kind that would have been found by a static type
> checker, say the one of Haskell?
The most significant bug that my co-worker caught was in the math, not
the implementation--when translating the centroid formula from big-sigma
notation to a recurrence, I accidentally wrote (x_i x_{i+1}) when I
should have written (x_i + x_{i+1}). My stupidity surpasses the
stupidity-catching power of the type checker.
There were less significant bugs that probably would have been caught by
static type checking, but in this case I think the unit tests caught
them just as quickly.
The "producer" part of the clip-and-centroid algorithm generates 0, 1,
or 2 vertices for every vertex of the original polygon, which are then
fed into the "consumer" part to compute the centroid. It did cross my
mind as I was writing the Python code that this sort of thing could be
handled much more concisely with the List monad, but doing the whole
thing in Haskell would have required (a) writing Haskell glue code to
either interface with the OGR library or parse WKT strings, and (b)
convincing my co-workers that Haskell was *so* incredibly useful that it
was worth adding another language as a build-time dependency.
(I'm laying the groundwork for (b) in my Copious Free Time)
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] the case of the 100-fold program speedup
On Tue, 14 Nov 2006, Seth Gordon wrote: > It took me a week to figure out the right algorithm for combining these > two procedures and write some almost-working code that implemented it. > It took a co-worker of mine another few days to find the bugs that had > eluded me. Were these bugs of the kind that would have been found by a static type checker, say the one of Haskell? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
