Does brute force have any chances here?

Does brute force have any chances here?

Hi,

I am wondering, if a brute force, even if veeery well optimized, would have any chances to succeed here. Correct me if I am wrong: the problem is quadratic, so a bit bigger input, a lot of computation more, and even 40 cores won't help : )

Do you think that there is any chance for brute-force (searching all possible rectangles), or only specialized algorithms (i.e. Kadane's, check Wiki references) can beat the problem?

7 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

I think this paper has an algorithm with O(mn) which is better than O(m2n)=O(n3)

Attachments: 

AttachmentSize
Downloadapplication/pdf 10.1.1.13.9917.pdf110.55 KB

hello

I won't answer to your question specifically, but in real life situations an highly optimized and vectorized brut force solution is sometimes a lot faster than an optimized algorithm implemented with tons of branches and divisions.

Regards, paul

Good real-life hint, thanks : )

What do you mean "vectorized"?

Hello

Most of the performance in modern cpus comes from vectorization.
http://software.intel.com/en-us/articles/vectorization-writing-cc-code-i...

But you don't have to code assembly, reading the compiler output and adapting your code to let the compiler do it is often enough.

That said, think parallel first, find a good algorithm, then worry about implementation and optimization.

Regards, paul

That said, think parallel first, find a good algorithm, then worry about implementation and optimization.

First make it work, then make it work faster (otherwise you will end up with a very fast bug : )

Leave a Comment

Please sign in to add a comment. Not a member? Join today