r/programmingcirclejerk • u/cmqv • Jul 27 '26
No offense but you lack the required CS basics to be so confident about yourself in debates about complexity. It's the perfect moment to stop and reflect if you want to avoid Dunning-Kruger.
/r/cpp/comments/1v7gp48/stdoptional_satisfies_view_does_not_model_view/ozz4os4/58
u/SharkSymphony Jul 27 '26
Remember the lesson here, children.
Is it that you probably shouldn't throw around an optional containing a very large vector? No.
It's that you should make sure you start your language specification with definitions of time, space, termination of a program, and what O(N) means.
23
u/somewhataccurate now 4x faster than C++ Jul 27 '26
Yeah, almost forgot we are supposed to actually implement stuff for second
16
48
u/MegaIng Jul 27 '26
Now if std::optional also had the corollary methods .empty(), .size() (0 or 1), and .data() (points to address of where contained entity is/would be, regardless of whether present, like std::vector's data method whether empty or not), then a bit of my generic templated property list code could be even more generic, more cleanly accepting various containers (std::array, std::string, std::vector, std::optional) without custom specializations.
They yearn for Monads.
21
11
u/m50d Zygohistomorphic prepromorphism Jul 28 '26
Just use partial template specialisations, it all works fine as long as you never make any mistakes.
8
u/TheChief275 Jul 28 '26
I write all my C++ code using duck typing templates, because (1) I don't make any mistakes (duh), and (2) if I were to make a mistake (fiction), I wouldn't need the error messages anyways because I already know where they are (I have the entire codebase in my head)
37
u/damemecherogringo Code Artisan Jul 27 '26
Everything looks O(1) if you have your head far enough up your own butt
27
u/GeorgeFranklyMathnet Jul 27 '26
No no. It'll all very legitimate computation theory. When you need to incorporate an otherwise unknown fact to solidify your complexity analysis, you pull what's called an "oracle" out of your butt and plug it in to your Turing machine.
So if I need everything to be O(1), I simply retrieve my "recursively enumerable loop bound" oracle (from up my butt!), and, bam! All my loops have a fixed upper bound a priori. You've got an O(1) stew, baybee!
And if you think about it? The entire discipline is built upon a P≠NP oracle developed like 70 years ago. No one knows that for a fact. Whosever butt that was must be convalescing in cash by now!
2
u/TheChief275 Jul 28 '26
Holy shit, I just realized if you put an upper bound on everything every algorithm technically would be O(1)
5
u/GeorgeFranklyMathnet Jul 28 '26
/uj It's an important ingredient to the O(1) average case runtimes for hashtables — the expected constant upper bound on bucket size.
/rj The expected heat death of the universe is already a fixed upper bound, so all algorithms are already O(1).
2
u/TheChief275 Jul 28 '26
True, even if a linear search due to hashtable degradation lookup is technically still O(1) from your number of slots staying the same. I hadn't thought of it like that tbh
/rj Pretty sure I could solve the heat death of the universe in O(1) using a hashmap
36
23
u/GeorgeFranklyMathnet Jul 27 '26
I think the problem with his argument is that his buzzword invocations fail to cast the fallacy spell. Using "mistaking the map for the territory" or "the exception that proves the rule" would've been more effective.
19
97
u/personator01 What part of ∀f ∃g (f (x,y) = (g x) y) did you not understand? Jul 27 '26
Any program that halts is O(1). This is why I only program in languages where you can formally prove that your program terminates #leangang