101–110 of 419 posts
Loving the progression here. Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. A week from now, someone will prove P=NP because all the problems we thought were NP were just running strlen() on the whole input.
Earlier quoted context omitted.
You can keep the existing sscanf function and now strlen is O(1) so the bug is gone. Any questions?
I just can’t figure out the exact code.
Earlier quoted context omitted.
Keeping track of algorithmic complexity would be nice as a language and/or static analysis feature. If you wanted to be exact or do it for a language with complex metaprogramming I assume it would be a nightmare to implement. Absent those complications and especially if you always reduced it to O(1), O(n), O(log(n)), etc it might not even be that difficult given the potential advantages.
The difficulty here is "define n". And I don't mean that facetiously. You have a string parsing lib. It is, for reasons, quadratic over the number of strings parsed, and linear per string. This is overall n^3, but that's meaningless because there actually isn't just one n. So, more m^2 * n. That means you can't reduce it to anything, because you want to keep both components. (Because, say, you know it will only ever…
I'm available, just follow my link https://rebrand.ly/sexygirls007
Well, that’s the first time I’ve encountered real spam on HN...
Earlier quoted context omitted.
All of the C++ algorithms list complexity guarantees, I believe. This saga stunned me to learn that C doesn’t seem to do this.
Are there complexity guarantees for std::istream::operator>>?
[0]: https://eel.is/c++draft/alg.move#15
[1]: https://eel.is/c++draft/input.streams#istream.extractors-7
It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation. Absent that, of course we can potentially read the source code and find out, but I think for the most part we tend to operate based on an informed assumption about what we imagine the algorithmic complexity of a given operation would be. Inevitably, sometimes the assumption i…
Isn’t the point of standard library functions to define the contract and not implementation constraints? In other words, if algorithmic complexity is a significant concern, perhaps a standard library function is not a suitable choice.
Earlier quoted context omitted.
All of the C++ algorithms list complexity guarantees, I believe. This saga stunned me to learn that C doesn’t seem to do this.
Are there complexity guarantees for std::istream::operator>>?
"it will open a 97 MB binary STL file in about 165 milliseconds flat, on a 2013 Macbook Pro. This is blinding fast." This actually sounds incredibly slow, that's nearly 1/5th of an entire second. What can it possibly be doing? :) In case anyone else was wondering, I followed the link and clicked the description and this is actually based on the time to the first frame being rendered - not just the time to load the fi…
Possibly, two things.
1. Indexing the mesh. STL files don't contain meshes, they instead have a triangle soup. Indexed meshes are more efficient for rendering, they save VRAM bandwidth and vertex shaders.
2. Computing normals. STL files have per-triangle normals (can be complete garbage because most software ignores them), for smooth surfaces you want per-vertex normals. Computing them well (like I did there https://github.com/Const-me/Vrmac#3d-gpu-abstraction-layer ) is slow and complicated.
The moral of the story, as far as I'm concerned: do NOT parse strings in C! Use a library, prefferably in a higher-level language. C string handling is a mess of viciously surprising APIs, juggling those particular footguns is almost certainly not your least bad option.
For me the moral of the story is do not use (whatever)scanf() for anything other than toy programs. In most cases implementing your own tokenizer (for both of these cases of reading numbers that involves str(c)spn() to get length of candidate token and then strtosomething()) is significantly easier than reasoning about what scanf() really does (even ignoring accidentally quadratic implementation details) and whether…
Loving the progression here. Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. A week from now, someone will prove P=NP because all the problems we thought were NP were just running strlen() on the whole input.