Well, your solution works, and it's very readable. It would be easy for someone else to maintain.

Python is a slow language no matter what, so trying to be terse in order to save execution time is frequently silly. If you really want it to run fast, you should probably be in a different language to begin with.

There is something to be said about making use of python's lazy evaluation (iterators and itertools) to lessen that, but I am forced to concur.

On the positive side, 'Scripts running' is the new 'Code is compiling.'

Well, I don't think the list comprehension is functionally different from LiquidMantis' code so it isn't an issue of efficiency but whether you prefer a block of simple instructions or a single dense line.

I do think however programmers should still think about basic efficiency when writing code so that you understand what you're actually doing. For example I assume count() does a linear pass over the entire collection. If you do that for every element that's a quadratic algorithm. There are better ways to do this such as using a dictionary or the counter in the collections module.

Also no one mentioned the numerical way of summing all the digits in an integer?

LiquidMantis wrote:It's also good to see the "right" way to do it for those of us that might want to take Python, or programming in general, further and aren't familiar with good/idiomatic programming techniques and structures. My limited Pascal, C, C# background has me wanting to do things a bit more verbose than what is apparently considered "Pythonic".

Case and point (CheckiO Challenge #2 spoilers):

The challenge is to remove the unique integers from a list (e.g. [1,3,4,1,5,4] -> [1,4])My solution:

Spoiler:And the popular published solution:

Spoiler:I'm now at the point where I understand that solution, I just don't immediately think of it and it seems like Perl levels of terseness.

Don't both of those solutions return [1,4,1,4] not [1,4]?

Don't both of those solutions return [1,4,1,4] not [1,4]?

Yes.

Merely my mistake. [1,4,1,4] would be the correct answer for my example.

Oh, OK.

This takes O(n log n) time; both of Mantis's solutions take quadratic time.

This should be O(N). Once through the list to put it into a Counter, then once more to check the counts. Since Counter's a dict, lookups are O(1). So it's 2N total.

I've read a little of Big-O notation, but haven't yet grokked how to assess/calculate it. Is there a better primer than Wikipedia?

I've read a little of Big-O notation, but haven't yet grokked how to assess/calculate it. Is there a better primer than Wikipedia?

Not sure. College explained it in an overly-complex way. There's a good cheatsheet for most algorithms.

The ELI5 version:

Figure out how many times your algorithm is going to have to touch an element in a collection of N elements. A single trip through a loop will have to touch N items, so worst case, it's O(N). Technically, it's O(xN + c), where c is some constant number of operations (let's say you have to fiddle with something or send an email for every element). The 'x' part of it comes into play in my answer above. I'm going through the loop twice, but still, in the worst case, the runtime grows linearly as N gets bigger. So O(2N) ~ O(N), as long as N is >= 2.

If you have a loop within a loop, like:

For each iteration of the outer loop, you're touching N elements in the inner loop, or N*N, giving quadratic complexity, or O(N^{2}). Look at a graph of y = x^{2} vs. y = 2x to see how the runtime grows with quadratic algorithms vs. linear.

Let's say you have a list with 1000 elements. The O(2N) algorithm will have to do 2,000 operations, while the O(N^{2}) algorithm will have to do 1,000,000.

With 1,000,000 elements, it's the difference between 2,000,000 and 1,000,000,000,000 operations. If they're non-trivial operations (sending an email, calculating a password hash, etc...), that can be an enormous time difference.

Each nest of that loop adds to the exponent for N, so a third loop would make it O(N^{3}). Typically anything at that level or above runs the risk of getting you fired, unless you know your N is going to be pretty low.

There are even higher categories, though I don't remember them all. I remember reading about O(N!) (N-factorial), which is ultra-bad.

You can also go lower than N, depending on your algorithm/data structure. If your list of numbers is sorted, you can search for a number at the halfway point, then depending on whether it hit, or was higher or lower, you can repeat using the halfway point of the half-list to the left or right, recursively repeating until you find it or where it should be if it's not in the list. At each step, you're cutting your search space in half. I forget how to do the math, but it works out to around O(ln N). That means you could search a list of 65,536 elements in at most 16 operations (log_{2}(N)).

And finally, there's constant-time operations, or O(1), like the dictionary lookups I mentioned above. Behind the scenes, dicts are usually arrays, and looking up or inserting an object as a key into the array involves hashing the object to figure out where to put it. Looking up the object is just hashing it again, and checking that spot in the array, involving a single element access. All it costs is the time it takes to hash the object.

You can actually do even worse. I'm not sure what the notation would be, because I'm a little blurry on the O(N) system myself.

A simple example: an algorithm to determine all the possible rolls of a set of dice. One way to do that is to loop through all the possibilities for every die, add up all the digits, and increment a list with that value by one. (you know the lower and upper bounds of what's possible, so you just have to keep track of how many times each total result comes up.)

In other words, say you're rolling four regular dice. You know the range has to be 4 to 24, and to calculate the results using this algorithm, you can set up four nested loops, each iterating from 1 to 6. The amount of work involved ends up being being 6 (numbers per die) ^ 4 (dice) unique possible outcomes, or 1,296 possible rolls.

That's fast: it's almost instant. But what if you're rolling 6 dice? That's 6^6, or 46,656.... 36 times as much work. And what if you're rolling 10 20-sided dice? That has 10,240,000,000,000 possibilities.... we've suddenly gone from a thousand things to calculate to a little over ten trillion. The numbers get gigantic in very short order.

There are probably better algorithms for that, but this specific one is moderately influenced by the number of sides on the dice, and very strongly influenced by the number of dice. There must be an official notation for this: it might be O(^N). Hopefully, someone with more expertise can confirm or deny.

Hypatian to the Python thread... Hypatian to the Python thread.

I would call that O(S^D) where S is number of sides to a dice and D is number of dice.

You don't always have to reduce things to N, leave them as natural as possible.

I would call that O(S^D) where S is number of sides to a dice and D is number of dice.

You don't always have to reduce things to N, leave them as natural as possible.

Ohhhh, look at Mr. Fancy Letter Math.

boogle wrote:I would call that O(S^D) where S is number of sides to a dice and D is number of dice.

You don't always have to reduce things to N, leave them as natural as possible.Ohhhh, look at Mr. Fancy Letter Math.

When they start putting numbers with it again?

This thread is dropping off! So the MITx 6.00.1x class is starting up on the 19th on edX. XXX! I've done the Codecademy "course", I'm nearly done with the Udacity Intro to CS course, but I think I'm going to do this class. It seem to be less about teaching Python and more about teaching CS concepts: algorithm efficiency and design, etc. Anyone interested in going through it?

I may be, where is this?

Here you go: https://www.edx.org/course/mitx/mitx...

6.001 is taught in a Lisp isn't it? Or have they updated it?

EDIT: Oh... 6.001 != 6.00.1x

This thread is dropping off! So the MITx 6.00.1x class is starting up on the 19th on edX. XXX! I've done the Codecademy "course", I'm nearly done with the Udacity Intro to CS course, but I think I'm going to do this class. It seem to be less about teaching Python and more about teaching CS concepts: algorithm efficiency and design, etc. Anyone interested in going through it?

I just signed up for the paid version. I may have trouble though with the ID verification though, as my license still has a picture of 16 year old me.

6.001 is taught in a Lisp isn't it? Or have they updated it?

EDIT: Oh... 6.001 != 6.00.1x

Yeah, they recently broke 6.00x into two half-semester classes.

I just signed up for the paid version.

Yay!

How timely, a Python thread! I've been studying on my own for a few weeks, with no prior experience. I never thought I could learn how to code, it always felt like such an advanced and arcane topic, yet here I am. Can't code to save my life, but making some progress every day!

So far I've done about half of Codecademy, and have now switched to Learn Python the Hard Way. I found CA didn't explain much, which was fine at first and then got problematic when tackling more complex concepts. A lot of the exercises seem sloppily written and arbitrary, which is a problem when that's the meat of the course. I think it shows that it's made of tutorials written by a bunch of different people. I might go back to it, but I feel like I'm learning much more and in a much more structured way with LPTH. But oh, do I ever miss the badges! Google's Python course seems good too, might be handy as a repetition.

My next step was going to be to follow this tutorial on writing a roguelike with libtcod, but now I might hop onto Coursera instead. Is the time limit really sharply enforced? Do you have to be done with your assignment week to week to clear the course? And what happens at the end with all the study material and scripts you write?

I've already managed to fall behind on the course, having not made it all the way through lecture 1 yet. The little mini quizzes after each video are not all that impressive so far.

Week 1 is very much an intro. I think the problem sets are where the real meat is anyway.

Okay, I finished up the first set of week two's problem sets. The problem was to find the longest substring in alphabetical order in s. My code works, but it doesn't feel elegant. I'm not sure that there is a much better solution in the context of the material presented so far though.

Spoiler flagged for absurddoctor.

And done with the 2nd problem set. I feel better about this code. The problem was to use bisection search to find the exact payment to pay off a credit card in 12 months. The online automated tester provides values for balance and annualInterestRate.

That sounds very encouraging, those are my exact same worries! I have a tendency (like many other nerds I would guess) to want to be familiar with all the tools before I start working with something, especially when it comes to software. I'm not done with the basic Python courses yet, but I was already looking ahead and feeling intimidated by all the stuff I don't know. Just diving in head-first and embracing my ignorance is probably a wise choice

This is your first programming language, right? Did you just go straight from Codecademy to making a game? And also, when can we see the game?!

The Coursera course on Python based on making games starts up on the 24th.

## Pages