3

So I was recently given a coding assignment from a large financial firm, and I thought of two ways to solve the problem. One of the ways involved 1 outer for loop and 1 inner for loop. In this case, the code would be relatively easy to understand, and I saw this method as a more "obvious" solution.

However, I thought of another way that used 4 out for loops consecutively. I'm no expert in Big O, but my understanding is that, asymptotically speaking, 4 outer for loops is O(n) and 1 outer and 1 inner for loop is O(n^2). However, the 4 outer for loops method was definitely a bit harder to understand and less obvious.

I was wondering from a coding assignment question, which method is seen as better? And then in a broader perspective, which one is better? Since I'm still sort of new to the idea of professional coding (I did a lot of casual coding when I was younger) I know there's an idea of balance between readability and efficiency. I was wondering what the balance is in this case.

Thanks!

Tyler M
  • 89
  • 3
  • 9
    Nothing can be considered "better" unless you specify a metric which you try to optimize, and the limits. An introductory book for beginners has different requirements than a bit of embedded code where every cycle counts. A "dumb" algorithm can be more efficient by RAM / CPU than an asymptotically faster / more economical algorithm on small data sizes. Etc, etc. – 9000 Sep 17 '18 at 00:44
  • 2
    If you really want to get a feedback on pros and cons of each approach, you should state the problem and describe your two algorithms, or post the code on codereview.SE. The question above is IMHO not answerable literally, the best answer you can get is IMHO the one by @ArseniMourzenko. – Doc Brown Sep 17 '18 at 05:49
  • 1
    Possible duplicate of [Clean readable code vs fast hard to read code. When to cross the line?](https://softwareengineering.stackexchange.com/questions/89620/clean-readable-code-vs-fast-hard-to-read-code-when-to-cross-the-line) – gnat Sep 17 '18 at 07:31
  • In a coding assignment i assumte that they want to check how much experience you have and if you know the [premature optimisatinon antipattern](https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize) – k3b Sep 17 '18 at 09:32

6 Answers6

19

If this wasn't an assignment, you could relatively easily guess which one of the solutions is better here.

  • In most cases, it would be the first one.

  • In some rare cases (and the fact that you're talking about the financial sector means that you shouldn't ignore this possibility), performance would be key (either because the piece of code will be run hundreds of times per second on thousands of machines, or because saving milliseconds would mean that traders will have a competitive advantage). But:

Since this is an assignment, do both.

The goal of an assignment is to see how you will react faced to a given problem. You may:

  • Find the simple solution and miss the optimized one,

  • Find the optimized solution and miss the simple one,

  • Spot both solutions and understand the benefits and drawbacks of each, including how much your second alternative is faster than the first one, why is it more difficult to understand, what can potentially be done to make it easier to understand without sacrificing its performance and what are the drawbacks of the potential change.

You cannot guess (otherwise you wouldn't be asking this question in the first place). Therefore, to be safe, just show that you found both solutions and are ready to suggest the one or the other after you get more information about the actual needs in terms of performance vs. maintainability.

Arseni Mourzenko
  • 134,780
  • 31
  • 343
  • 513
  • 5
    Arseni, you are extremely gifted at sniffing out homework and answering in such a way that is helpful but doesn’t give away too much. Kudos. This is at least the 10th thread I’ve seen your amazing answers. – Adam B Sep 17 '18 at 04:01
  • 1
    There is also the added benefit of having something to test the optimized solution against. The simple solution you know is correct so you can test the optimized solution against that. – Bent Sep 18 '18 at 07:28
  • @Bent How do you `know` that the simple solution is correct? It could suffer from any number of problems from incorrect coding through to naivety that misses certain cases. – Peter M Sep 22 '18 at 11:29
3

It depends.

Sometimes a company has clear preferences for the one or the other; sometimes the development team has preferences.

If you are free to decide, think about the relevance of the performance in this area:

  • If this is a critical part, and performance issues would affect the user satisfaction or usability of the application overall, go for the faster and more complex solution (but document your thoughts and the algorithm in the code).
  • If this is not a critical part, use the easier to understand (and maintain) version (if it bothers you, add a comment that you could have done it faster, but didn't, for readability).

Either way, make sure that your prediction is real (=> measure!). Nothing is worse than a complicated solution that is slower.

Aganju
  • 1,453
  • 13
  • 15
3

From a classroom perspective, I'd agree (with the majority of answers/comments) that easier-to-understand is better. Most of the time, that'll probably be the correct answer to that classroom question. But many problems you eventually encounter doing (quoting your phrase) "professional coding" may have no such easy solution whatsoever. So what do you do then?

Ultimately, your easier-to-understand versus more-efficient is a false dichotomy. Good inline documentation is always the sine qua non that allows maintainers to come to grips with tens-of-thousands of lines of code they'd never seen before, and where the original developers of that code are long-since gone.

One aspect of good inline documentation is a large header comment block preceding each function, describing and discussing its purpose, calling sequence, side effects, algorithms, etc. For example, from my little lib of projection functions,

/* ==========================================================================
 * Function:    rotatetoz ( l, r, axis, nlines )
 * Purpose:     xlate, rotate l, returning r as though
 *              axis were along the z-axis with axis.pt1 at origin
 * --------------------------------------------------------------------------
 * Arguments:   l (I)           input LINE * to 3d-lines to be xlated, rotated
 *                              along with axis
 *              r (O)           output LINE * to xlated, rotated 3d-lines
 *              axis (I)        LINE specifying rotation axis,
 *                              with pt1 the tail, and pt2 the head,
 *                              such that pt1 ends up at (0,0,0), and
 *                              pt2 at (0,0,z=r) with r the length of axis
 *              nlines (I)      int containing #lines to be rotated
 * Returns:     (double)        r, the length of axis, or -1.0 for any error
 * --------------------------------------------------------------------------
 * Notes:     o axis is (obviously) not changed, with r xlated, rotated as
 *              though axis pt1 was at the origin, and pt2 was at (0,0,z=r)
 *            o to accomplish this, first xlate pt1 of axis to (0,0,0),
 *              and then...
 *                    z.             As per usual spherical polar coords,
 *                    |  .                 x = r*cos(phi)*cos(theta)
 *                    |    .               y = r*cos(phi)*sin(theta)
 *                    |      .             z = r*sin(phi), where
 *                    |        o(x,y,z)    r^2 = x^2 + y^2 + z^2
 *                    |90-phi. |for r-axis
 *                    |    .   |     Then, to rotate axis to positive z-axis,
 *                    |  .     |           o rotate about z-axis by -theta
 *                    |.       |             to bring axis to x,z-plane
 *                    +--------|---y       o rotate about y-axis by -(90-phi)
 *                   /   .     |  /          to bring axis coincident with z
 *                  /theta .   | /   Where we calculate
 *                 /         . |/          o sin(phi)   = z/r
 *                x------------+           o sin(theta) = y/(r*cos(phi)) or
 *                                           cos(theta) = x/(r*cos(phi))
 *
 * ======================================================================= */
/* --- entry point --- */
double  rotatetoz ( LINE *l, LINE *r, LINE axis, int nlines ) {
  /* ---
   * lots of code;
   * ---------------- */
  } /* --- end-of-function rotatetoz() --- */

And the code is itself extensively commented, frequently referring back to the above algorithm synopsis/explanation. That hopefully lets some future maintainers more easily figure out the decomposition of the somewhat-dense code into functional blocks. But there was never any "easier-to-read versus more-efficient" design choice possible. And there frequently never is.

John Forkosh
  • 821
  • 5
  • 11
1

The consensis is to go for readable code over optimized code, because for most code you are going to spend more time reading the code then the time it's actually being executed.

If you want to optimize, first see if it's needed: use a profiler to find the areas that need it and then optimize only the routines that need it.

However, having a good feel for big O complexity should be a thing any programmer should get. Because choosing the right algorithm will save you a lot of time in the future. There is this nice book: "Algorithms" and in my opinion every software developer should read it. It's a big difference I see between self taught and academically schooled programmers, this basic algorithm knowledge which self-taught programmers often lack.

So my question to you here: which algorithm are you using?

Pieter B
  • 12,867
  • 1
  • 40
  • 65
  • Given the choice between O(n^2) and O(n), it’s essential to figure out how large n could become. With n = 50,000 it could become a road block. – gnasher729 Sep 17 '18 at 07:00
  • @gnasher729 it's about scaling. hey: let's make a list...let's make a function that adds items to a list. Let's make a function that checks whether the item is already in the list. by going over the items already in the list....hey, let's use that function on every item when filling the list.........and suddenly you have made a list that gets sluggish to load once you go put more then 5000 items in it. If you know your "algorithms" you will in this case immediately see where the problem is. – Pieter B Sep 17 '18 at 07:05
0

Donald Knuth stated something like

Premature optimization is the root of all evil.

Go for the simplest most self evident techniques until things are working.

Then test and optimize the bottlenecks.

dkretz
  • 179
  • 2
  • 2
    And how can you state, from the dearth of information the OP passed on, that it's premature? – Deduplicator Sep 19 '18 at 00:26
  • It's a fairly well-known Knuthism. But it's pretty much any optimization that isn't suggested by integration testing, especially if it increases code complexity. Otherwise you spend time solving problems you don't know if you have, and increase the bulk of code someone needs to understand and maintain in the future. But you're right, we don't have enough to answer the question. Kinda my point. – dkretz Sep 19 '18 at 04:22
  • It sounds like new code, so it hasn't been tested yet. So simplicity is likely indicated for the first cut. – dkretz Sep 19 '18 at 04:30
0

If you take the design approach of Developing everything as an API, the approach I recommend is this (Written in C++/Qt):

  1. Identify the return value you require to generate from your algorithm. In my rather arbitrary example, we need the number of hashes at the beginning of a string.

  2. Create a member function for that return value. It might look something like:

    // A descriptive function name is preferred over comments
int MyClass::countFrontRecurringHashes() 
{
     /* Validate Parameters */
     if (m_MyString.isNull()) {
          /* Throw Error */
     }

     /* Algorithm */
     ... 
}

  3. All subsequent code should rely exclusively upon this function's return value. No member variables should be altered within this code, thus allowing you to change the algorithm without having to worry about how other code is interacted with.

  4. On the first pass, write the code for readability if it saves you time. Mark it for improvement if its obvious:

    int MyClass::countFrontRecurringHashes()
{
     /* Validate Parameters */
     if (m_MyString.isNull()) {
          /* Throw Error */
     }

     /* Algorithm */
     /// Todo: Performance
     return QRegularExpression("^[#]*").match(m_MyString).capturedLength();
}

  5. When your code is up and running, you will be able to identify if improving performance is a higher priority than further development elsewhere. If it is, you can then go in and put in a change like so:

    int MyClass::countFrontRecurringHashes()
{
     /* Validate Parameters */
     if (m_MyString.isNull()) {
          /* Throw Error */
     }

     /* Algorithm */
     int i, l = m_MyString.length();
     for(i = 0; i < l && m_MyString[i] == '#'; ++i);
     return i;
     // This code is more complex, abstract, and difficult to read, 
     // However, it is about 100 times more efficient.
}

  6. Alternatively, if you are working on a team, this is also a good place to stick a new member. Tell him to search for todo's and fixme's in the code, although caution is advised, as often times, a fixme or a todo eventually becomes a feature other code might rely upon. That is why proper encapsulation and an API development strategy is important.

Anon
  • 3,565
  • 3
  • 27
  • 45