Timeline for Count the number of arithmetic progressions within a sequence
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 29, 2021 at 20:14 | comment | added | Toby Speight | Shouldn't be that surprising - I just fixed the obvious bugs and maintainability problems. Choosing a more efficient algorithm is left as an exercise. ;-) | |
| Apr 29, 2021 at 17:33 | comment | added | amdlaihfgan | Guess that I need to somehow come up with another algorithm that is less than quadratic in time. | |
| Apr 29, 2021 at 17:24 | comment | added | amdlaihfgan | Surprisingly your code doesn't beat my code's time. imgur.com/a/rSA672d | |
| Apr 29, 2021 at 16:03 | comment | added | JDługosz | There are presentations on signed vs unsigned speed in the major conference videos; I don't recall exactly where. The big deal is that unsigned requires two's complement behavior in wrapping, while going out of range for signed values is UB. This means that the optimizer can make assumptions about signed arithmetic, and the code generator must accommodate wrapping of unsigned values. The presentations give generated code with major optimization differences. Surprising? It's been well-known in the community for a few years. | |
| Apr 29, 2021 at 15:59 | history | edited | Toby Speight | CC BY-SA 4.0 |
Added the comment I removed
|
| Apr 29, 2021 at 15:57 | comment | added | Toby Speight | I never knew that signed arithmetic is faster than unsigned, and it seems very surprising. Would you be kind enough to share the evidence for that? | |
| Apr 29, 2021 at 15:56 | comment | added | Toby Speight |
I accidentally removed a comment saying that vector<char> might perform better (depending a lot on the effect of the larger storage on memory locality). I'll reinstate that.
|
|
| Apr 29, 2021 at 15:42 | comment | added | JDługosz |
Your use of vector<bool> is slowing it down, since this is a special case in the standard.
|
|
| Apr 29, 2021 at 15:41 | comment | added | JDługosz |
signed is faster than unsigned, sometimes significantly so. I disagree that "unsigned is more appropriate"; if you don't need a size_t you should prefer signed. Even then, there is a movement to migrate to signed size where possible.
|
|
| Apr 29, 2021 at 14:02 | history | edited | Toby Speight | CC BY-SA 4.0 |
More observations, and final modified code
|
| Apr 29, 2021 at 13:44 | history | edited | Toby Speight | CC BY-SA 4.0 |
Add some more observations
|
| Apr 29, 2021 at 12:42 | history | answered | Toby Speight | CC BY-SA 4.0 |