There are several well-known space and time efficient data-structures that answer membership/connectivity queries.
The main drawback has typically been that whilst they can be made to be incremental (e.g. the addition of vertices or edges) quite easily, they don't retain enough information to be made fully dynamic (addition AND removal of vertices and edges) without prohibitively increasing the space complexity required.
This data-structure, however, has particularly good time/space properties that make it interesting to anyone working on large-scale graph-analytical problems with a temporal component.
Our TypeScript project is ~20K SLOC. It compiles in roughly (I haven't measured exactly) the same amount of time it takes to compile 100 SLOC.
Since the Typescript compiler itself is > 2MB of minified js, it doesn't surprise me that compiling any TS has at least a second overhead.
What's more important to me is that:
- The compiler performance scales as the codebase increases in size.
- Incremental builds are fast. (ie the -watch option).
So far I have found both to be true. Incremental builds take < .5 sec on my laptop. That means I get a cute red-squiggly in Visual Studio in a convenient amount of time. Ultimately, that's half the reason for using TS in the first place; if it didn't improve our productivity, we wouldn't be using it.
It is more about the approach that keeps them there. i quote-
"Part of what makes Google such an amazing engine of innovation is their internal technology stack: a set of powerful proprietary technologies that makes it easy for Google developers to generate and process enormous quantities of data. According to a senior Microsoft developer who moved to Google, Googlers work and think at a higher level of abstraction than do developers at many other companies, including Microsoft: “Google uses Bayesian filtering the way Microsoft uses the if statement”
(Chrome devotee here). I spend an hour recently with FF-22 trying to debug a regression in FF by using the built-in dev tools; it seems to lack the ONLY feature that I actually want (and to be honest I feel so bemused that it's not there that I think I'm being dumb and missed it): I can't execute a JS statement in the context of the current stack frame. I'm sure the scratchpad must be able to do this, because otherwise it seems like its the most useless debugging console I've seen in some time.
That feature means you can set a breakpoint in any javascript and while you are paused on a frame you can execute JS in the web console. The code you type executes in the stackframe you have selected in the debugger.
The main drawback has typically been that whilst they can be made to be incremental (e.g. the addition of vertices or edges) quite easily, they don't retain enough information to be made fully dynamic (addition AND removal of vertices and edges) without prohibitively increasing the space complexity required.
This data-structure, however, has particularly good time/space properties that make it interesting to anyone working on large-scale graph-analytical problems with a temporal component.