3 ms·

The tool is awesome, but I wouldn't rely too much on the instruction bounds. For example, the greatest sums exercise (http://people.csail.mit.edu/pgbovine/pytho

by bp_ 15y ago

The tool is awesome, but I wouldn't rely too much on the instruction bounds. For example, the greatest sums exercise (http://people.csail.mit.edu/pgbovine/python/question.html?optimize-sum#mode=edit http://people.csail.mit.edu/pgbovine/python/question.html?op...) can be solved in six "steps" for all input lengths, while it's certainly no O(1) business. def maxPairSum(data): return sum(sorted(data)[-2:]) # one "step"

tobiasSoftware 15y ago
Actually, both your solution and theirs are not O(1). Theirs is n^2, while yours is n lg n due to the use of a sort function. The best way to do this would simply be to find the largest element, ignore that element and find the largest element again, which is O(n).
- cmurphycode 15y ago
  I do believe the GP's message was that the tutor told him his solution took one "step", which is not equivalent to O(1), because sorted() takes O(nlgn). In other words, he was pointing out the limitations of the tutor program's analysis.
- nhamann 15y ago
  Indeed, but it won't even accept the following O(n) solution. I get "(stopped after 20 steps to prevent possible infinite loop)" when submitting this: def maxPairSum(lst): if lst[0] > lst[1]: top, top2 = lst[:2] else: top2, top = lst[:2] for i in range(2, len(lst)): if lst[i] > top: top, top2 = lst[i], top elif lst[i] > top2: top2 = lst[i] return top+top2
- bp_ 15y ago
  I'm perfectly aware, but can you take that approach and execute it in 6 "steps" for all data sizes? Since the whole point of the exercise is "optimizing" maxPairSum so that it runs in 20 "steps" or less, I guess this slower solution is still more "optimized" - which was my whole point, after all. :) (Please note 6 steps is the bare minimum - one for the function definition, one for preparing input, one for calling the function, one for calling the function, one for assigning function arguments, one for the actual function and one for returning from the function. You can't go shorter than this.)
lambda 15y ago
In fact, that is the solution they give (if you click on the "hint" and "solution" links).

by bp_ 15y ago

tobiasSoftware 15y ago

Actually, both your solution and theirs are not O(1). Theirs is n^2, while yours is n lg n due to the use of a sort function. The best way to do this would simply be to find the largest element, ignore that element and find the largest element again, which is O(n).

cmurphycode 15y ago
I do believe the GP's message was that the tutor told him his solution took one "step", which is not equivalent to O(1), because sorted() takes O(nlgn). In other words, he was pointing out the limitations of the tutor program's analysis.
nhamann 15y ago
Indeed, but it won't even accept the following O(n) solution. I get "(stopped after 20 steps to prevent possible infinite loop)" when submitting this: def maxPairSum(lst): if lst[0] > lst[1]: top, top2 = lst[:2] else: top2, top = lst[:2] for i in range(2, len(lst)): if lst[i] > top: top, top2 = lst[i], top elif lst[i] > top2: top2 = lst[i] return top+top2
bp_ 15y ago
I'm perfectly aware, but can you take that approach and execute it in 6 "steps" for all data sizes? Since the whole point of the exercise is "optimizing" maxPairSum so that it runs in 20 "steps" or less, I guess this slower solution is still more "optimized" - which was my whole point, after all. :) (Please note 6 steps is the bare minimum - one for the function definition, one for preparing input, one for calling the function, one for calling the function, one for assigning function arguments, one for the actual function and one for returning from the function. You can't go shorter than this.)

lambda 15y ago

In fact, that is the solution they give (if you click on the "hint" and "solution" links).