4 ms·

I did AoC 2021 through Day 7 in Python, before switching to Go (for personal learning, can't remember if times listed below were with "go run" or from running a

by mroche 5y ago

I did AoC 2021 through Day 7 in Python, before switching to Go (for personal learning, can't remember if times listed below were with "go run" or from running after "go build"). D7 actually in both, to try and solve a problem I was having with my Python performance. But, it was actually a big learning moment for me when it came to structuring my logic. My Python code in Part 2 (some minor adjustments from Part 1) took about 40 seconds to run. Terrible, but usable to get a proper answer. I was able to bring it down to ~25 seconds with some optimization by adding a calculated lookup dictionary per loop. Now, the same exact logic in Go ran in about 0.8 seconds. However, I wasn't satisfied with this and realized that if I moved the dictionary to be global rather than per-loop, I would be able to realize significant gains in performance by completing eliminating redundant calculations. This change dropped the runtime from 25 seconds to 0.35 seconds (of course, applying the same logic in Go brought it down from 0.8s to 0.05s). Due to the nature of performance you can get out of the Python interpreter, it can actually lead you down paths of learning better optimization strategies that you may initially write off in other languages (depending on the use case) because they perform inherently better. It made me think a bit more about what I was doing and how I could improve it since (in this particular case), the impact of not doing so was pretty drastic.

matsemann 5y ago
I don't understand your solution to Day7. What kind of dictionary, and how come even a naive solution would be so slow? My Kotlin solution runs in about a second. And it was even so stupid that I didn't calculate the sum of the arithmetic series directly, but through a loop. Can't fathom something being slower. line.split(",").map { it.toInt() }.let { crabs -> (0..crabs.maxOf { it }).minOf { pos -> crabs.sumOf { (0..abs(it - pos)).sum() // slower than calculating arithmetic sum, but quicker to write } } } My proper Kotlin solution runs in less than a ms, though. I do think that "it's good that python is slow because it forces you to optimize" is a weird take, though.
- deleted 5y ago
  [deleted]
- mroche 5y ago
  > I do think that "it's good that python is slow because it forces you to optimize" is a weird take, though. My take wasn't that it forces you to, but that non-optimal code paths can be greatly exaggerated in comparison to other languages, particularly compiled ones. You can still ignore it (I mean, within reason), but it can give you that extra push to really look a bit deeper to understand what's going on. And of course, there's optimized libraries written in C/C++ that you can take advantage of for even better number crunching than standard CPython. > What kind of dictionary, and how come even a naive solution would be so slow? My naive solution was literally going through every single element for every loop and not storing any data besides the fuel buildup and the alignment number that generated it. The dictionary was added to act as a cache to store already computed fuel consumption values, initially per-loop then moved one level up to be global (because the summations wouldn't be different). I'm not saying my method (posted in a sibling comment) is the best solution, but it's the way my brain walked through the problem.
  - matsemann 5y ago
    Posted my optimized Kotlin solution in that sibling thread :) Cool of you to participate without being a developer! Lots of computer science topics makes it easier, so hard without knowing of them. For instance graph searching / Dijkstra has beem relevant this week.
    - mroche 5y ago
      Yeah, I was doing a CS minor in college but had to drop as it was consuming too much of my time from my other discipline in the non-intro courses. Big(O)/time complexity were my usual failings in the intro algorithms course I took. I'm not unfamiliar with programming, but I come from the sysadmin side of things. "Glue" work is usually where things are focused and the 'fun' nitty-gritty of algorithms can be a bit out-of-scope, though I'm not a sysadmin in my current role anymore so any dev-related work I do is purely personal now. I've had to take a break from AoC, only got up through Day 10, but didn't get P2 for 8 and 9. It's a fun way to keep the mind going and to slip back into the coding space to at least not lose skills, even if the solutions are simple/non-optimal.
malka 5y ago
The better optimization with Python is to not use python. Half joking. If you want awesome performances, transform your problem into a numerical one, and use Numpy. Numpy is awesome. I always miss it when using other languages than Python.
BiteCode_dev 5y ago
Day 6 and 7 are fantastic for that. It's a learning moment, where you can get the benefit of thinking about the problem for a few minutes instead of bruteforcing gives you a dramatic speed up. When I read the Day 7, I saw bruteforcing would lead to bad perfs. Then I remembered that in high school, I learned a formula to calculate the nth term of a sequence without having to process the entire sequence. I couldn't remember the formula, nor the name of the concept, so I google around until I found some tutorials, and relearned what I was taught as a child: arithmetic sums. The consumption for a crab can then be calculated in constant time: def crab_consumption(crab, target): n = abs(target - crab) - 1 return (n**2 + 3*n + 2) / 2 And the Python solution finishes instantly. Bottom line, I could keep using Python for all problems and benefit from the amazing productivity of it. I've been using python since 2.4 now, and it's not always fast enough. But it very, very often, is.
- mroche 5y ago
  Interesting, I'll have to look at that. Actual algorithms are a big weak point for me, I'm not a developer by day, so I don't spend a lot of time learning code practices or computer science/math topics. This was my solution to Day 7 Part 2 (positions = sorted int list of input data): def calculate_fuel(positions): fuel = None low_fuel_value = None calculated = dict() for value in range(positions[0], positions[-1]+1): consumed = 0 for position in positions: diff = abs(value - position) try: consumed += calculated[diff] except KeyError: if position != value: consumption = sum([x for x in range(1,diff+1)]) calculated[diff] = consumption consumed += consumption if fuel: if consumed < fuel: fuel = consumed low_fuel_value = value else: fuel = consumed low_fuel_value = value print(f"Aligning to: {low_fuel_value}") return fuel And Day 6 I fell for the bruteforce bait and had the thought "It can't be as easy as changing 80 to 256, right?". Then I realized the pain I had created for myself. BUT! My 6p2 code ran faster than my 6p1 by a good margin, which I was happy about.
- matsemann 5y ago

by mroche 5y ago

matsemann 5y ago

I don't understand your solution to Day7. What kind of dictionary, and how come even a naive solution would be so slow? My Kotlin solution runs in about a second. And it was even so stupid that I didn't calculate the sum of the arithmetic series directly, but through a loop. Can't fathom something being slower. line.split(",").map { it.toInt() }.let { crabs -> (0..crabs.maxOf { it }).minOf { pos -> crabs.sumOf { (0..abs(it - pos)).sum() // slower than calculating arithmetic sum, but quicker to write } } } My proper Kotlin solution runs in less than a ms, though. I do think that "it's good that python is slow because it forces you to optimize" is a weird take, though.

deleted 5y ago
[deleted]
mroche 5y ago
> I do think that "it's good that python is slow because it forces you to optimize" is a weird take, though. My take wasn't that it forces you to, but that non-optimal code paths can be greatly exaggerated in comparison to other languages, particularly compiled ones. You can still ignore it (I mean, within reason), but it can give you that extra push to really look a bit deeper to understand what's going on. And of course, there's optimized libraries written in C/C++ that you can take advantage of for even better number crunching than standard CPython. > What kind of dictionary, and how come even a naive solution would be so slow? My naive solution was literally going through every single element for every loop and not storing any data besides the fuel buildup and the alignment number that generated it. The dictionary was added to act as a cache to store already computed fuel consumption values, initially per-loop then moved one level up to be global (because the summations wouldn't be different). I'm not saying my method (posted in a sibling comment) is the best solution, but it's the way my brain walked through the problem.
- matsemann 5y ago
  Posted my optimized Kotlin solution in that sibling thread :) Cool of you to participate without being a developer! Lots of computer science topics makes it easier, so hard without knowing of them. For instance graph searching / Dijkstra has beem relevant this week.
  - mroche 5y ago
    Yeah, I was doing a CS minor in college but had to drop as it was consuming too much of my time from my other discipline in the non-intro courses. Big(O)/time complexity were my usual failings in the intro algorithms course I took. I'm not unfamiliar with programming, but I come from the sysadmin side of things. "Glue" work is usually where things are focused and the 'fun' nitty-gritty of algorithms can be a bit out-of-scope, though I'm not a sysadmin in my current role anymore so any dev-related work I do is purely personal now. I've had to take a break from AoC, only got up through Day 10, but didn't get P2 for 8 and 9. It's a fun way to keep the mind going and to slip back into the coding space to at least not lose skills, even if the solutions are simple/non-optimal.

malka 5y ago

The better optimization with Python is to not use python. Half joking. If you want awesome performances, transform your problem into a numerical one, and use Numpy. Numpy is awesome. I always miss it when using other languages than Python.

BiteCode_dev 5y ago

Day 6 and 7 are fantastic for that. It's a learning moment, where you can get the benefit of thinking about the problem for a few minutes instead of bruteforcing gives you a dramatic speed up. When I read the Day 7, I saw bruteforcing would lead to bad perfs. Then I remembered that in high school, I learned a formula to calculate the nth term of a sequence without having to process the entire sequence. I couldn't remember the formula, nor the name of the concept, so I google around until I found some tutorials, and relearned what I was taught as a child: arithmetic sums. The consumption for a crab can then be calculated in constant time: def crab_consumption(crab, target): n = abs(target - crab) - 1 return (n**2 + 3*n + 2) / 2 And the Python solution finishes instantly. Bottom line, I could keep using Python for all problems and benefit from the amazing productivity of it. I've been using python since 2.4 now, and it's not always fast enough. But it very, very often, is.

mroche 5y ago
Interesting, I'll have to look at that. Actual algorithms are a big weak point for me, I'm not a developer by day, so I don't spend a lot of time learning code practices or computer science/math topics. This was my solution to Day 7 Part 2 (positions = sorted int list of input data): def calculate_fuel(positions): fuel = None low_fuel_value = None calculated = dict() for value in range(positions[0], positions[-1]+1): consumed = 0 for position in positions: diff = abs(value - position) try: consumed += calculated[diff] except KeyError: if position != value: consumption = sum([x for x in range(1,diff+1)]) calculated[diff] = consumption consumed += consumption if fuel: if consumed < fuel: fuel = consumed low_fuel_value = value else: fuel = consumed low_fuel_value = value print(f"Aligning to: {low_fuel_value}") return fuel And Day 6 I fell for the bruteforce bait and had the thought "It can't be as easy as changing 80 to 256, right?". Then I realized the pain I had created for myself. BUT! My 6p2 code ran faster than my 6p1 by a good margin, which I was happy about.
matsemann 5y ago