One of my favorite things about the Redis docs[1] is that they include the time complexity for every command type.
It Can Happen to You
131–140 of 419 posts
Re: It Can Happen to You
#132Loving 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.
And maybe, in a decade or so, the man page for these functions will list their algorithmic complexity! That was the most interesting takeaway from this article, for me at least. I have only seen a one or two libraries that actually list this in their documentation.
Listing time complexity up top is my favorite thing about the Redis docs.
Re: It Can Happen to You
#133Earlier quoted context omitted.
I think your code would be pretty much the same, sscanf, strlen and all. The main differences would be the standard library's implementations of strlen and whatever function you use to read the file into a string in the first place.
str_t json = loadfile(); size_t offset = random(); sscanf(“%d”, ?); With opaque str_t you can’t just json[offset]. Should sscanf take offset with every string (sscanf(fmt, s, off))? Should we copy a slice of json and parse it? Should str_t have zerocopy mirroring ability (s2 = strmirror(s, off, len))? How many of these three are just a snakeoil that changes nothing? It’s only pretty much the same until you try to wri…
C++'s std::string_view is essentially your struct. You can check the methods it provides.
Re: It Can Happen to You
#134Earlier quoted context omitted.
I think your code would be pretty much the same, sscanf, strlen and all. The main differences would be the standard library's implementations of strlen and whatever function you use to read the file into a string in the first place.
str_t json = loadfile(); size_t offset = random(); sscanf(“%d”, ?); With opaque str_t you can’t just json[offset]. Should sscanf take offset with every string (sscanf(fmt, s, off))? Should we copy a slice of json and parse it? Should str_t have zerocopy mirroring ability (s2 = strmirror(s, off, len))? How many of these three are just a snakeoil that changes nothing? It’s only pretty much the same until you try to wri…
Okay, I see what you're saying now. I haven't worked with C strings in a while. Python uses offset parameters or seek operations in various places, and C++ string streams have an inherent position too (C++ probably has a number of other ways to do it too...).
Re: It Can Happen to You
#135Based on Jonathon Blow's tweet it seems like he want to purge the web from existence.
Re: It Can Happen to You
#136Earlier quoted context omitted.
Shouldn’t we just come clean and admit to ourselves that there is no such thing as the C standard? There is a collection of loosely related languages that look similar and that collectively we call C, but really they’re all completely different and share almost no interoperability or common characteristics. And those standards that do exist provide almost no ability to reason about your code including things like ord…
No, that's complete nonsense. Here's the latest revision of the standard: https://www.iso.org/standard/74528.html C has had a well-defined memory model since C11, I believe (re: "ordering of statements").
> ISO-C11 specifies 203 circumstances that cause undefined behaviors.
203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used.
Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation, even if it is known to be standards conforming to C11.
[1] https://resources.tasking.com/p/undefined-behaviors-iso-c-th...
Re: It Can Happen to You
#137Earlier quoted context omitted.
It's easy to forget that the original C standards were largely codifying existing practice during an era when using gets() [1] was existing practice. The world wasn't quite ready for Ada, I guess. Best-laid plans of mice and men etc. etc.. Also, keep an eye out for "amortized" complexity. This does have a legitimately rigorous definition, but for latency-bound paths it can practically amount to "O(whatever), except f…
...I fully plan to use "O(whatever)". Not sure for what. But, yes. (naive) Quicksort's amortized complexity being O(nlogn), but its O(n^2) on already sorted data, is all I ever needed to learn to take away that lesson. When sorting already sorted data is worse than sorting randomized data, it's a quick realization that "amortized cost" = "read the fine print".
Quicksort as O(n log n) is not amortized complexity, but average runtime for random data.
Re: It Can Happen to You
#138Earlier quoted context omitted.
I think a better moral is "don't roll your own parser unless your core competency/product is the parser". Especially in a corporate situation.
Don't roll your own parser? How the hell would you get anything done? Unless you don't count regular expressions or something, I can't imagine somehow avoiding problems requiring parsers, especially on any unix-based system.
There are a lot of tasks that only need to work with existing, commonplace file formats with existing high-quality parsers (e.g., JSON, XML, sqlite, ...).
Re: It Can Happen to You
#139Earlier quoted context omitted.
str_t json = loadfile(); size_t offset = random(); sscanf(“%d”, ?); With opaque str_t you can’t just json[offset]. Should sscanf take offset with every string (sscanf(fmt, s, off))? Should we copy a slice of json and parse it? Should str_t have zerocopy mirroring ability (s2 = strmirror(s, off, len))? How many of these three are just a snakeoil that changes nothing? It’s only pretty much the same until you try to wri…
C++'s std::string_view is essentially your struct. You can check the methods it provides.
Yes, I’m aware of it. I’m just tired by these layman’s “oh that’s another reason to ditch C strings”, when it has nothing to do with it. Working with offsets requires handling offsets and lengths, be it explicit ‘off’ and ‘n’ or a string_view. All that is needed in this case in C is snscanf (note the ‘n’), so that it would know its limits apriori, like snprintf does. Sadly that ‘n’ never made it into the standard.
Re: It Can Happen to You
#140Earlier quoted context omitted.
Looped algorithms generally outperform recursive algorithms.
does that hold for languages/compilers with tail call optimisation?
This isn't really related to your question, but I don't think tail calls could help for Fibonacci since f(n) branches to two calls, f(n-1) and f(n-2). And each of those branches into 2. So it can't be done in a finite stack area with naive recursion.
The compiler would either have to memoize, or be extremely clever and start at the base case (0, 1) and then transform the code to use the 2x2 matrix exponentiation. I wouldn't have been suprised if GHC haskell was that clever, but even with -O2 "print $ fibb 10000" isn't terminating.