The Artima Developer Community
Articles | News | Weblogs | Books | Forums
Artima Forums | Articles | Weblogs | Java Answers | News
Sponsored Link •

Articles Forum
The Lazy Builder’s Complexity Lesson

9 replies on 1 page. Most recent reply: Jan 4, 2007 12:31 PM by Thomas Guest

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 9 replies on 1 page
Bill Venners

Posts: 2284
Nickname: bv
Registered: Jan, 2002

The Lazy Builder’s Complexity Lesson Posted: Oct 9, 2006 12:10 PM
Reply to this message Reply
Advertisement
This article investigates the complexity guarantees made by the C++ Standard Library. By analyzing and measuring the performance of alternative solutions to the same problem it shows how this library allows us to write code that is both simple and efficient.

http://www.artima.com/cppsource/lazy_builder.html

To what extent do you consider algorithmic complexity in your day to day coding tasks?


Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: The Lazy Builder’s Complexity Lesson Posted: Oct 10, 2006 4:14 AM
Reply to this message Reply
I am confused. The article says:

we wouldn’t be using C++ if we didn’t care about performance.

But then there are many who insist that other languages (Java, Haskell, Eiffel etc) are on par with C++.

So what gives? is C++ better performance-wise or not?

My opinion is that C++ is better performance-wise, provided that you know what you are doing.

Nemanja Trifunovic

Posts: 172
Nickname: ntrif
Registered: Jun, 2004

Re: The Lazy Builder’s Complexity Lesson Posted: Oct 10, 2006 6:25 AM
Reply to this message Reply
>other languages (Java, Haskell, Eiffel etc) are on par with C++.

Haskell??? Even on the Haskell advocacy page http://www.haskell.org/complex/why_does_haskell_matter.html they say: "As a general rule C++ should be faster than Haskell, there's no point claiming anything else."

Maybe you mean OCaml?

Thomas Guest

Posts: 236
Nickname: tag
Registered: Nov, 2004

Re: The Lazy Builder’s Complexity Lesson Posted: Oct 11, 2006 12:33 AM
Reply to this message Reply
> I am confused. The article says:
>
> we wouldn’t be using C++ if we didn’t care about
> performance.
>

What I meant was that for many jobs I prefer to use a high-level language; but in situations where processor cycles -- and other low-level resources -- need careful monitoring, then C++ is an excellent choice.

> But then there are many who insist that other languages
> (Java, Haskell, Eiffel etc) are on par with C++.
>
> So what gives? is C++ better performance-wise or not?

On paper, for example, an NlogN algorithm in Python will always beat an N^2 algorithm in C++, as N gets large. All things being equal, though, C++ will get more from the machine.

I'm not sure if C++ is best placed to exploit multi-processor architectures though.

> My opinion is that C++ is better performance-wise,
> provided that you know what you are doing.

Agreed.

Achilleas Margaritis

Posts: 674
Nickname: achilleas
Registered: Feb, 2005

Re: The Lazy Builder’s Complexity Lesson Posted: Oct 12, 2006 5:46 AM
Reply to this message Reply
> >other languages (Java, Haskell, Eiffel etc) are on par
> with C++.
>
> Haskell??? Even on the Haskell advocacy page
> http://www.haskell.org/complex/why_does_haskell_matter.html
> they say: "As a general rule C++ should be faster than
> Haskell, there's no point claiming anything else."
>
> Maybe you mean OCaml?

But they also say that For the vast majority of applications the speed difference will be negligible, however (copy-paste from the site you posted).

I do not buy 'negligible'. I haven't seen Haskell sorting equal to C/C++...I can not imagine how one could sort, let's say, thousands of records with functional languages...and sorting is a fairly common task.

m limber

Posts: 3
Nickname: mlimber
Registered: Nov, 2006

Re: The Lazy Builder’s Complexity Lesson Posted: Nov 2, 2006 12:42 PM
Reply to this message Reply
I think it's funny how he says, "The rule of thumb—to use std::vector unless there’s good reason not to—applies here." But then in the very next section, he uses a raw array instead of a vector with no apparent good reason:

unsigned job_widget_counts[widget::max_value];
std::fill(job_widget_counts,
job_widget_counts + widget::max_value, 0);

Cheers! --M

Thomas Guest

Posts: 236
Nickname: tag
Registered: Nov, 2004

Re: The Lazy Builder’s Complexity Lesson Posted: Nov 3, 2006 12:39 AM
Reply to this message Reply
> I think it's funny how he says, "The rule of thumb—to use
> std::vector unless there’s good reason not to—applies
> here." But then in the very next section, he uses a raw
> array instead of a vector with no apparent good reason:

Good point. My reason here was the usual one: the storage space required is known at compile time, so we can avoid dynamic allocation by using an array. An std::tr1::array would also do the job. And, as you say, so would a vector.

bug not

Posts: 41
Nickname: bugmenot
Registered: Jul, 2004

Re: The Lazy Builder’s Complexity Lesson Posted: Nov 11, 2006 12:15 PM
Reply to this message Reply
I dislike the benchmarks:

> perhaps the random widget generator gave significantly different inputs.
> Clearly, the algorithm runs so fast that our test results are subject to timing jitter.

Well, if you know that, why don't you run them for sensible times/input sizes?

Thomas Guest

Posts: 236
Nickname: tag
Registered: Nov, 2004

Re: The Lazy Builder’s Complexity Lesson Posted: Nov 12, 2006 8:41 AM
Reply to this message Reply
> I dislike the benchmarks:

And I like them. I think they yield some interesting points.

> > perhaps the random widget generator gave significantly
> different inputs.
> > Clearly, the algorithm runs so fast that our test
> results are subject to timing jitter.
>
> Well, if you know that, why don't you run them for
> sensible times/input sizes?

I didn't know that before I ran the benchmarks! My timing tests ran the same inputs the same number of times through the variant algorithms. But you're right, given this initial result, I could have run more tests.

Thomas Guest

Posts: 236
Nickname: tag
Registered: Nov, 2004

Re: The Lazy Builder’s Complexity Lesson Posted: Jan 4, 2007 12:31 PM
Reply to this message Reply
In an email from Christopher Vogt I got an interesting correction to this article. It turns out that my analysis of the complexity of the first (and worst) brute force algorithm wasn't correct. I wanted it to be O(N*N), but in fact in the worst case it performs O(N*N*log(N)).

This worst case occurs when both the job and the toolback contain N instances of a single widget. The "used" set will also grow to size N, and repeatedly searching through this set is what causes the additional log(N) factor.

More details can be found at: http://www.wordaligned.org/lazy_builder/index.html

Thanks again to Christopher for his help.

Flat View: This topic has 9 replies on 1 page
Topic: Spring Clustering with Terracotta Previous Topic   Next Topic Topic: Why PUT and DELETE?
Sponsored Links


Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use