Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
premature optimization is the root of all evil
Author Message
coolgod

Posted: Wed Dec 21, 2011 11:57 pm   Post subject: premature optimization is the root of all evil

I think this is one of my biggest flaws during major contest, i tend to optimize alot as i write the code. It especially screws me up during DWITE. My teacher says it has screwed numerous other stars in our schools before.
Any any advise or suggestions to help me deal with it? An example was today for DWITE #4 i used a star and made a silly mistake somewhere, got 3/5 and wasted 1.5 hrs. Could have bfsed 5/5 it in like 20 mins.

A.J

Posted: Thu Dec 22, 2011 12:26 am   Post subject: RE:premature optimization is the root of all evil

Would you mind elaborating 'optimize a lot as I write code'? As in, you try to make it memory efficient?

Usually with contests, you want to be aware of the time constraints and the input specs of the problems. For example, on DWITE I never suggest implementing a breadth first search, as a depth first search could as easily solve the problem with the given constraints, and requires (well, most of the time) less code than a breadth first search.

In general though, I would suggest thinking in terms of:

1) The complexity required to solve the problem (by this I mean what is the slowest program that could pass given the constraints).

2) Problem genre. This comes from experience, basically trying to recognize what 'genre' the intended solution falls under

3) Determining an Algorithm. Arguably the most challenging part. Come up with an algorithm (or implement a known one) to solve your problem

4) Implement your Algorithm. This is the part you want to try saving some precious time on, though not at the expense of complexity

But I guess its always a learning curve. DWITE does help a lot with small things like this (so now in the future you'll know to implement a DFS/BFS for pathfinding problems as opposed to an A*, if appropriate).
coolgod

Posted: Thu Dec 22, 2011 12:31 am   Post subject: Re: premature optimization is the root of all evil

Implement your Algorithm. This is the part you want to try saving some precious time on, though not at the expense of complexity <-
The astar today wasn't the best example. I kindda wanted to push myself and see if I could code an a star on the spot.
I mean just in general, optimizing the little details in the code.
Tony

Posted: Thu Dec 22, 2011 12:40 am   Post subject: Re: premature optimization is the root of all evil

coolgod @ Thu Dec 22, 2011 12:31 am wrote:
optimizing the little details in the code.

It might help to realize that a good compiler is better at optimizing than you are. The little details don't matter*, next to high-level algorithm complexity.

* the exception being embedded software where cpu cycles, memory, and space are still at a premium.
Tony's programming blog. DWITE - a programming contest.
trishume

Posted: Thu Dec 22, 2011 8:05 am   Post subject: Re: premature optimization is the root of all evil

This is my favourite programming motto. I use it constantly whenever I am coding anything.

Profiling is the only way to really know what is slow and in contests there is not even time for that.

I still have much to learn though. As a ruby user I automatically dismiss brute force solutions (like many people used for q5.)
I was writing a fancy tree matching boolean algebra simplifier for q5 when another person on my team (ttm) said "That's only about 20,000 possible combinations. C++ could easily brute force that." So he sat down and quickly coded a working brute-force algorithm.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 5 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: