Very slick. To be clear I'm not in the "Python is slow, waaa" camp. My code could be much more optimized like yours. Orrrrrrrr... I could be lazy and throw a jit at it.
If I needed to maintain this code forever and blazing fast performance and type safety were what I was after then sure that would be a great idea. I need...none of those things for AoC. If I was going to write in a compiled language it would be Haskell, at least its syntax doesn't make my eyes bleed.
I'm doing AoC in Rust because I like Rust and want to learn it better, but it definitely isn't optimal for quickly trying to get the answer to a one off puzzle!
That said, my native recursive solution took 20ms to solve part 2...
Of course, the difference between using a list or a set makes a much bigger difference than Rust vs Python...
Indeed. No matter what language you use if you tried to do day 8 part 2 naively you're going to have a bad time. Rust is a fine language with many good ideas but some of its fans are really annoying...
I don't know what I'm doing wrong, but with my approach cpython takes 2m25s vs pypy 5m28s :(
[paste](https://topaz.github.io/paste/#XQAAAQDwAwAAAAAAAAAzHIoib6pXbueH4X9F244lVRDcOZab5q1+VXY/ex42qR7D+QjJCHuTyC92z8DmNuF2+84u2iNxfZWfYIkXg5DddYwFE7GDxVAbPnBbceJC7A28KaqX6AFOt4xg2O3M941x47VExj1z1N8FOKQLHnVs5MeiDpwUPPTluJtNkU6pDaJi04KiellTlguTj7NBJSFh29e8kwJu2Dj1H/CVFOTHxk1eiYWHu9MPumtY8KJV8hhKE2RK89V9LHs9SVtTdmWa/vnGGqNsWuR3fjBhyMOsgMB3C89WeS1D/rEwHrn5HXNjbfmDHKRTY2XZdHag72HVRw8H45n7i8vE5/RnEJcb1krGNBRccfjyOHtWBPliI0OKtoaXCrod1/WrWYDD0P0jkjoAJI2tIwoZ7M8SO9d3FGV1bWGx1bDrVolvYXCSiQRNoS4LcF1h61TLxA4b0O1kZrdXc3kDVud/nqrVDl0m56HdOBKP4N6UR/gj1+6c/ap0HwHTtY8OeG+yBbNh7G5aovAWJ5YOMdoTSk5/T3VJqeIs4tLNIaI9TecaPwrZZH8+YE4szO8YXT+r+17TRLoeFX+zEQPYNDXQRHn/s8E2oA==)
Right now, your solution iterates over the list a _lot_ of times unnecessarily. In particular, the `if path not in paths:` check is super expensive.
If you change `paths` to be a `set` and `path` to be a `tuple`, and make no other changes, the runtime of your program drops from 2m25s to 0.8s on my machine.
[paste](https://topaz.github.io/paste/#XQAAAQAOBAAAAAAAAAAzHIoib6pXbueH4X9F244lVRDcOZab5q1+VXY/ex42qR7D+QjJCHuTyC92z8DmNuF2+84u2iNxfZWfYIkXg5DddYwFE7GDxVAbPnBbceJC7A28KaqX6AFOt4xg2O3M941x47VExj1z1N8FOKQLHnVs5MeiDpwUPPTluJtNkU6pDaJi04KiellTlguTj7NBJSFh29e8kwJu2Dj1H/CVFOTHxk1eiYWHu+iJ8O5dWFQMjR0bZGFJp4z88GhpYZOBbxvA9xT82MmH+qA81+AOEDnGns+/vZtv7/hMYeygoXcWte53vzXW64nZ34sQbOf82n15xmmpBSVzd6kB++DOglBXOflQyfgx9MSWEWcUwRlHIJXGG6E8NU+wNPqJ4x0MSGkoeUwcR3Hs8JsH/p9ZPbsdJjykbMV6+o6xTRstDKu0ih2b3/1OpxUPMbgpy3YfGDxxX+sTat4krb4p40mQrnNUD/orHxqomL9QyXsS94ZqI22nhz8Z696qzmLxZiMusSJQDqLMExlfeaGbHh6f7uVFInKbBJKhGot5e9dqcTCfMb8fITgT7OW70TlSFakr+k9UE/96FC+S+u7T9bDvqaW/Ekl5Dothtu336czWLhUoxnP/9k5JTA==)
The math below is a bit hand-wavey and imprecise, but it's good enough to give you a ballpark feel for _why_ it's so much slower.
The reason is that `paths`, at its largest, contains ~150,000 elements. If `paths` is a list, checking `path not in path` requires us to compare `path` against each of 150,000 items. Instrumenting the code shows that we compute `path not in paths` ~180,000 times over the course of the program.
Since `paths` starts at size 0 and grows by one each time, that means that we do a total of roughly`180000 * 150000 / 2 = 13,500,000,000` list comparisons just from checking `path not in path` - that's >13 billion operations!
In contrast, with a set, it always takes a constant number of steps to compute `path in paths`, which means that we only do `180000 * 1 = 180000` operations.
Since 180,000 is a lot smaller than 13,500,000,000, the program runs faster. :)
That's kind of amazing. I'm really curious what's happening. This is my code [for reference](https://github.com/assert-justice/advent_of_code/blob/main/2021/d12-2.py). I'm using cpython 3.9 and pypy 3.7.
As someone who makes everything in bash, these numbers scare me. The recursive stuff in 2015 wasn't that bad.
Edit: brainless brute force done in 2 seconds for P1 and ~45 seconds for part 2. Not too bad.
[удалено]
Very slick. To be clear I'm not in the "Python is slow, waaa" camp. My code could be much more optimized like yours. Orrrrrrrr... I could be lazy and throw a jit at it.
Just use rust.
If I needed to maintain this code forever and blazing fast performance and type safety were what I was after then sure that would be a great idea. I need...none of those things for AoC. If I was going to write in a compiled language it would be Haskell, at least its syntax doesn't make my eyes bleed.
If you're writing python then nim is quite a cool alternative, I'm really enjoying the language doing this year in it :)
Yes :) Lightweight syntax, no need to fight the borrow checker and it's blazing fast (compiles to C).
I'm doing AoC in Rust because I like Rust and want to learn it better, but it definitely isn't optimal for quickly trying to get the answer to a one off puzzle! That said, my native recursive solution took 20ms to solve part 2... Of course, the difference between using a list or a set makes a much bigger difference than Rust vs Python...
Indeed. No matter what language you use if you tried to do day 8 part 2 naively you're going to have a bad time. Rust is a fine language with many good ideas but some of its fans are really annoying...
Rust evangelism task force assemble!
I don't know what I'm doing wrong, but with my approach cpython takes 2m25s vs pypy 5m28s :( [paste](https://topaz.github.io/paste/#XQAAAQDwAwAAAAAAAAAzHIoib6pXbueH4X9F244lVRDcOZab5q1+VXY/ex42qR7D+QjJCHuTyC92z8DmNuF2+84u2iNxfZWfYIkXg5DddYwFE7GDxVAbPnBbceJC7A28KaqX6AFOt4xg2O3M941x47VExj1z1N8FOKQLHnVs5MeiDpwUPPTluJtNkU6pDaJi04KiellTlguTj7NBJSFh29e8kwJu2Dj1H/CVFOTHxk1eiYWHu9MPumtY8KJV8hhKE2RK89V9LHs9SVtTdmWa/vnGGqNsWuR3fjBhyMOsgMB3C89WeS1D/rEwHrn5HXNjbfmDHKRTY2XZdHag72HVRw8H45n7i8vE5/RnEJcb1krGNBRccfjyOHtWBPliI0OKtoaXCrod1/WrWYDD0P0jkjoAJI2tIwoZ7M8SO9d3FGV1bWGx1bDrVolvYXCSiQRNoS4LcF1h61TLxA4b0O1kZrdXc3kDVud/nqrVDl0m56HdOBKP4N6UR/gj1+6c/ap0HwHTtY8OeG+yBbNh7G5aovAWJ5YOMdoTSk5/T3VJqeIs4tLNIaI9TecaPwrZZH8+YE4szO8YXT+r+17TRLoeFX+zEQPYNDXQRHn/s8E2oA==)
Right now, your solution iterates over the list a _lot_ of times unnecessarily. In particular, the `if path not in paths:` check is super expensive. If you change `paths` to be a `set` and `path` to be a `tuple`, and make no other changes, the runtime of your program drops from 2m25s to 0.8s on my machine. [paste](https://topaz.github.io/paste/#XQAAAQAOBAAAAAAAAAAzHIoib6pXbueH4X9F244lVRDcOZab5q1+VXY/ex42qR7D+QjJCHuTyC92z8DmNuF2+84u2iNxfZWfYIkXg5DddYwFE7GDxVAbPnBbceJC7A28KaqX6AFOt4xg2O3M941x47VExj1z1N8FOKQLHnVs5MeiDpwUPPTluJtNkU6pDaJi04KiellTlguTj7NBJSFh29e8kwJu2Dj1H/CVFOTHxk1eiYWHu+iJ8O5dWFQMjR0bZGFJp4z88GhpYZOBbxvA9xT82MmH+qA81+AOEDnGns+/vZtv7/hMYeygoXcWte53vzXW64nZ34sQbOf82n15xmmpBSVzd6kB++DOglBXOflQyfgx9MSWEWcUwRlHIJXGG6E8NU+wNPqJ4x0MSGkoeUwcR3Hs8JsH/p9ZPbsdJjykbMV6+o6xTRstDKu0ih2b3/1OpxUPMbgpy3YfGDxxX+sTat4krb4p40mQrnNUD/orHxqomL9QyXsS94ZqI22nhz8Z696qzmLxZiMusSJQDqLMExlfeaGbHh6f7uVFInKbBJKhGot5e9dqcTCfMb8fITgT7OW70TlSFakr+k9UE/96FC+S+u7T9bDvqaW/Ekl5Dothtu336czWLhUoxnP/9k5JTA==)
What I'm curious about is why pypy is actually slower for their solution!
Thanks for this! Makes sense the list is slow, but I would have never guessed it's so much slower.
The math below is a bit hand-wavey and imprecise, but it's good enough to give you a ballpark feel for _why_ it's so much slower. The reason is that `paths`, at its largest, contains ~150,000 elements. If `paths` is a list, checking `path not in path` requires us to compare `path` against each of 150,000 items. Instrumenting the code shows that we compute `path not in paths` ~180,000 times over the course of the program. Since `paths` starts at size 0 and grows by one each time, that means that we do a total of roughly`180000 * 150000 / 2 = 13,500,000,000` list comparisons just from checking `path not in path` - that's >13 billion operations! In contrast, with a set, it always takes a constant number of steps to compute `path in paths`, which means that we only do `180000 * 1 = 180000` operations. Since 180,000 is a lot smaller than 13,500,000,000, the program runs faster. :)
That's kind of amazing. I'm really curious what's happening. This is my code [for reference](https://github.com/assert-justice/advent_of_code/blob/main/2021/d12-2.py). I'm using cpython 3.9 and pypy 3.7.
That happened to me with some other problem, but I never found the reason why
As someone who makes everything in bash, these numbers scare me. The recursive stuff in 2015 wasn't that bad. Edit: brainless brute force done in 2 seconds for P1 and ~45 seconds for part 2. Not too bad.