This seems like a refactoring issue primarily. So did the developer do a an O() analysis on the various algorithms used (I'll bet there were more than one algorithm involved) decided upon using others based on his O() analysis then implemented them? I'm going to guess that he/she started out by wondering where they could improve performance. Then they looked at the code and saw some obvious problems with the approach taken; made an assessment that if they implemented the code using different algorithms (probably well known and O() characterized) that it would improve performance substantially; made an assessment of the risk involved in changing the software; and came up with a plan to mitigate the risk and accomplish the task in an acceptable time and cost to management. I'm guessing the really important factor that made the project a success was the skill in developing a refactored solution and the ability to do O() analysis was of a lot less important, maybe they even used the cheat sheet link I posted.

I'd assume most developers dealing with non trivial algorithms in a setting where runtime matters will frequently do an O() analysis, especially when developing new algorithms. Of course you don't need to do it explicitly, but it's pretty essential to be able to make a decent guess at the O() of various implementation options without actually coding them first.

Not that far and not really able to relocate though I'm already in the midwest.

Have a Bach looking to go into a master's program for electrical or computer engineering. Self teaching some things right now and then going through the whole process of getting into schools.

I have a full time job now and am supporting my wife as she goes back to school so educating myself is as I have time right now which unfortunately is not as fast as I would like.

Thanks for the information though. It's still cool to know that kind of work is going on here in the Midwest where I could be a part of it.

Yeah, I don't think its a matter of consciously evaluating all of your code on an O() basis. A simple example might be knowing that you can put a search operation in a loop instead of using nested for loops because n log n is better than n^2.

Hi 2p2ers!

don't know if this is the right place to ask this but basically in my class we were given an assignment, where we are given a program and we are supposed to optimise it(both serially and parallelise it c/openmp). and the best performance gets a prize, me being me(i'm really ****ing competitive) and i really want to win, so my questions are:

how do i know if my code still needs to be further optimised?
if u are looking for optimal performance is there a checklist of some sort that i could go through? or maybe a really good book that i can read?

any advice is welcome =)

Academic projects like this are kind of a unique beast. In real life you optimize by profiling, finding bottlenecks, optimizing bottlenecks, and reaching some sort of acceptable (defined by the business) performance trade off with cost.

For your project, its slightly different. You can take the 'profile and optimize bottlenecks' approach, but that might reach a local optimal performance instead of a sort of overall optimal performance. Completely different approaches can probably be optimized to different 'optimal' amounts.

So if you really want to win you probably want to try a bunch of different high level approaches and then see how you do optimizing those.

But depending on the size of your class it still takes a lot of luck to win.

I've never seen a discussion of O() in db optimization articles or books.

I barrin6's story.

I think you may have been right. The DBA guy never graduated to college, so I doubt he knew O() analysis. But then again, he's the type of guy who would really keep up to date on tech and stuff.

Basically from what I understand, the previous DBA was writing really inefficient lookups(?). I didn't understand any of the database lingo back then, not that I would know more of it now. But it was great to see him shake his head when he would look at his previous predecessor's work.

Fortunately for him, he found a new job.

Just submitted my app to the apple store. According to http://appreviewtimes.com , the review time is 7 days. I have a bad feeling that Apple is going to reject my app. Hopefully whatever the reason, it will be easily fixable.

First define a non trivial algorithm. Remember almost all well know algorithms that I know of have already been characterized by O() analysis.

Since your post is basically dealing with the hypothetical I'll play along. What about if a developer knew that they had plenty of processing power to implement an algorithm and had two choices in which way to go. The first algorithm was inherently easier to code, easier to read code when implemented, easier to implement and easier to maintain than the second alternative algorithm. However, the first algorithm is an n**2 type while the second is an n log n algorithm and n could be a large number. Implementing the n**2 algorithm meets all the performance requirements that have been laid out even for a large value on n. Which algorithm do you choose?

Allow me to describe a situation where I believe being highly skilled in O() analysis would be very critical. I have posted about this situation in the past. I discussed a position with a network storage company a few years ago. They can support some incredible amount of mass storage and have performance criteria that they guarantee their customers. They had a project that was ramping up where they were going to increase the storage capacity they could support by an order of magnitude but maintain their current performance specs. In this situation my view was that some really original thinking, like phd level expertise was required and I would think that detailed O() analysis was required. A 10 fold increase in storage capacity while maintaining their current performance seemed like a monumental challenge.

Obviously depends on the details, but I'd have no problem going with the n^2 in this specific scenario.

To make this less hypothetical, the following is an actual problem i had to implement a few years back:
You have this as starting point and need a version that runs for n=20, e.g.:
stacks = payouts = {20, 19, 18,...,1}

I was alluding to this the other day when jmakin? I think was talking about the professor who had an unhealthy obsession with initializing loop variables prior to the loop. Programming used to be heavily about detail-oriented neckbeard stuff. There was no such thing as Stack Overflow and code completion in IDEs was nowhere near as good so you needed a good memory and an eye for detail. Performance optimization generally meant static code analysis, big O kind of stuff.

Nowadays a good programmer partly means one who can juggle a huge range of concerns - future-proofing, readability, maintainability, testing, performance, scalability, plus business concerns such as time to market and project delivery times. And "performance" in the majority of jobs more often means tuning settings on frameworks, profiling etc than it does doing big O analysis.

ChrisV - I generally agree.

But there's still fundamentals of performance that you need to understand. A typical example is doing something like a database query in a loop. Good programmers still need to have an inherent understanding of the basics of Big-O. That is that doing something N^2 times is significantly worse than doing something N times - and even with modern hardware that can have a huge difference in performance.

I'd also argue that there are still many jobs where performance matters (basic stuff, not neckbeard stuff). Lots of jobs are doing things at "Web Scale" or with "Big Data" where stupid performance choices can cost a company hundreds of thousands of dollars or more a year in extra costs.

I don't believe every programmer has to be a math person; to know when they're writing poor code, which isn't optimized and will run longer to accomplish a task compared to if it was written better.

I'm not a math person by any stretch, yet I can pull out the resources needed to understand most, if not all, topics of discussion that require a math background.
When you're in this field, you meet many people that do have a math backgrounds, get to listen to their knowledge and share code.

The biggest deception, I believe can happen is if someone wanted to become a programmer but convinced themselves, they wouldn't be able to because they're just not wanting to be a math person.
I've seen it happen to few people actually, that probably missed out in life because of it.

CTCI covers that issue really well. Like, most people can problem solve if they're not aware they're doing it. They'll come up with a system for doing a thing efficiently, but as soon as you add the word "algorithm" to the equation, their brains just seize up.

I should add that i'm not saying, you should dodge math if you become a programmer and dislike math specific code. There is just that option of avoiding math but to do the coolest things in programming; you have to dive into math a tiny bit (not hard) and luckily there are a lot of math wizards that are also programmers to help with that.

^^ sort of what needs to be told to everyone, to get more people into programming imo.

I'm guessing your average CRUD or SPA app doesn't require much math. I don't remember ever thinking I needed any math at all for a website.

For something like Kato Krazy is doing, I would suspect you need a very good sense of the math, data structures, and Big O.

For databases work, you need a strong sense of the "other" math, like classical logic, set theory, graph theory, data structures (esp. hash tables), a good sense of Big O, and program size issues. None of these are things that are easy to look up and understand without some upfront studying and manually working through it, I don't think.

For database work, don't you need some knowledge of relational algebra?

Stanford mooc recommends it

RA is nothing more than the symbolic representation of SQL select queries, or rather, SQL is nothing more than the English representation of RA.

I think RA is good to know about but not get obsessed over. It is no different than knowing symbolic logic, but using words instead if symbols. As long as you can compute the correct answer, you know how to do it.

I think the Stanford class only spent a week on RA then moved on, treating as a good to know of subject.

Speaking on n**2 vs log n algorithms, I know as a complete certainty that the original BASIC language interpreter that Microsoft wrote used an n**2 algorithm in implementing their garbage collection. I also know that they really wished they would have used a log n alogarithm. I'm pretty sure that one of the factors in deciding to use an n**2 algorithm was memory usage.

after discovering changing all my doubles to floats gave me an insane performance boost, i was wondering if i should change all my loop counters to unsigned short or something?

Started responding to this but then had to get on a plane.

Luckily for me it's mostly the opposite in terms of interviewing well in person. I consider in-person interviews (phone interviews maybe not as good) and first dates to be two of my top skills (no joke tho ). Similar skill sets, bonding with and selling yourself to one person over an extended conversation.

My resume is bad. The last few years I worked at a restaurant, before that years of poker, before that Finance. No CS degree or related experience, came out of a bootcamp (one of the biggest and "best" names but I don't think most companies distinguish much).

So my phone screen rate was quite low, 3-5%-ish. On some of those, the recruiter had probably just scanned the resume quickly or somebody else did it, and they were clearly disinterested when they realized my experience level and background.

I blew a couple of tech screens towards the beginning of the process where if I had been a bit stronger I would have gotten an offer in one case, an on-site or offer in the other case.

I had 5 "on sites" basically, but 1 was for this crap "office manager" hybrid position, 1 was mostly a formality with a guy I had met at a meetup for contract work in JavaScript (plus his partner), 2 were paid internships (1 explicitly "intern-to-hire"), and the last was with the big company that I landed at. Only 2 of these involved whiteboarding or much of anything technical. I got offers from all except the "office manager" thing, and thank God I didn't get that.

I'm probably not as competent or studious as I may appear but certainly got better as the interview process went on. That's how the bootcamp recommended we go about things. Just keep applying, and you'll get better as it goes along. Some people were good enough right away of course, and I did just miss out on one job to a fellow classmate.

Happy to answer more questions. It is definitely possible that I'm bad at phone screens. I found it difficult to tell a compelling story about my career narrative, and until I started doing cool work with new technologies at the contract job I had nothing terribly interesting to discuss when they asked about my personal projects etc. (I had them, it was just very standard Rails and Backbone stuff). Still though, my phone screen rate was quite low as I said anyway. I can try to dig up the conversion rate of phone screen to next step.

Did you ever do any practice phone screens or interviews with fellow students?

smoke a joint before the phone screen