I say this as a professor myself, because we do that all the time in my team: we create some software system (also in NLP, by the way), we do experiments to show that it improves whatever metric we are interested in or that it teaches us something interesting, we publish a paper with it, make the code available and then move on to the next paper. That's what we are typically incentivized to do. The time spent into optimizing a system that we are not going to take to production anyway is time not spent doing more research. Which doesn't mean that we don't know how to optimize.
But, fyi, this tagger was not just a professor's demonstration, it was kind of ground-breaking and served as a foundation for other taggers. The professor went on to have a pretty awesome career at a few different big tech companies, far surpassing my own success. And yes, I agree, I am sure he could have made it faster himself had he dedicated the time to it.
- It serves as a form of documentation for what the optimized stuff is supposed to do. I find this most beneficial when the primitives being used in the optimized code don't map well to the overarching flow of ideas (like how _mm256_maddubs_epi16 is just a vectorized 8-bit unsigned multiply if some preconditions on the inputs hold). The unoptimized code will follow the broader brush strokes of the fast implementation.
- More importantly, you can drop it into your test suite as an oracle to check that the optimized code actually behaves like it's supposed to on a wide variety of test cases. The ability to test any (small enough) input opens a door in terms of robustness.
But a structured program will take you through these things, ensure that you understand them, be available to answer questions in a manner other than "bang your head on the problem for weeks" or "just give up", and provide a structure progression through to more advanced topics.
I think it's important to keep both sides of this in mind; the universities do not have a monopoly on the knowledge and arguably it's easier than ever to pick up yourself, but that doesn't mean the structured experience is useless either. I've worked with some very good self-taught people, but they all have also tended to have gaping holes in their education relative to a good computer science education. (I agree with those people that they are much better than some people who end up with bad computer science educations. Unfortunately, if one optimizes one's computer science education for "the easiest 4.0s", one can end up with very similar gaping holes in one's formal education!)
It also often seems missed that somebody who went through a formal degree in lieu of gaining real-world experience can also gain real-world experience at least as easily as somebody who got the equivalent of a formal degree through real-world experience.
Now, you can imagine smart algorithms, trees, hashes...
Nothing of that sort. The database was written as append only transactional log. To retrieve data, entire file was scanned for initial record and all its updates. No indexes. Some algorithms were plainly O(n^3).
Yeah, I got into many heated discussions with "computer scientists" in the team. Yet for all their might they were not able to improve upon the program because they forget that algorithmic complexity is only one factor of performance.
Because I used extremely simple algorithms (like linear search) the operations were very simple and progressed quite fast on a CPU that was good at prefetching from the storage.
The total amount of memory available was just 0,5MB meaning that the "super inefficient" scans still completed within perception threshold of the user.
While O(n^3) was used for some operations, the application state machine which limited number of actual number of steps. Most transactions follow same basic pattern of execution and so I don't care what happens when somebody does 500 updates to the transaction when I can figure out there will ever be 5 state changes at most.
There were other consideration for the program. For example, it had to use very little instructions (we were very short on space) and it had to work in constant memory (to be able to statically calculate stack space necessary, for example).
Obviously you chose this solution because it made the most sense given your constraints (time/money/knowledge/microcontroller limitations). But that doesn't mean it was an optimal solution nor that with slightly more time/money/knowledge a significantly better solution couldn't have been found.
Had a week long argument once about an (relatively) inefficient MySQL query because "it's not going to work for 1000 things" when a) we had barely 10 things currently running and b) the customer was >this far< from cancelling because stuff wasn't working (which this query would help with.) It was a frustrating time. I think there's a lot of developers who "know the price of everything and the value of nothing".
Frequency of run is also important - a batch job that takes 5 hours that only runs once a month? Is it worth optimising that?
But your story shows the gulf that exists between Computer Science and software development. You needed to actually use a piece of software constrained by business requirements (not spinning up 250 servers), and when it didn't do what you needed it to, you changed it. The fact that you failed a data structures class didn't prevent you from refactoring and improving the code. The fact that that professor wrote code that performs poorly on good hardware doesn't negate the fact that there was probably some novel CS implementation in there somewhere.
I know in the past I've gotten caught up on CS profs having terrible websites or programmers not understanding the intricacies of bubble sorting but I think it helps to keep in mind that they are two different disciplines that inform each other, and the gap is seeming to get wider over time.
I don't understand the reduction of all of math and CS to complaining about people who overindulge their notations. I've been reading this recently, and it just affirms how important and ubiquitous mathematical thinking is everywhere in life: https://www.gatesnotes.com/Books/How-Not-to-be-Wrong.
It's a good reminder to always try to understand your likely workloads as well as possible (know your "n"), and to get good measurements (what are K1 and K2 values) before prematurely optimizing these kinds of things.
"f(x) ∈ O(g(x)) as there exists c > 0 and x0 such that f(x) ≤ cg(x) whenever x ≥ x0"
Saying f(x) is O(g(x)) doesn't say anything about how those two functions compare below x0?
https://en.wikipedia.org/wiki/Big_O_notation
Edit: Not trying to be snarky - just trying to check whether my 30+ year old memory of education on such matters is even vaguely correct... :-)
Edit2: Added "memory of" - I'm pretty sure what I was taught was correct, just my memory of it that is all too fallible.
After all, the most efficient (in terms of big-O) known algorithm for multiplying two numbers uses a 1729-dimensional Fourier transform and only becomes more efficient once the numbers involved are significantly larger than the number of atoms in the universe[1].
[a] Key words are 100 items very rarely: if you’re sorting many times a second (for whatever reason) or (relatively) large datasets, using a quicker sorting algorithm than bubble or insertion would make sense.
1. Solve the problem.
2. Ensure correctness of that solution
3. The code is easy to reason about
4. The app is robust
5. "good enough" performance
6. Performance tuning
Which is of course the "correct answer", and of course in practice these all blend together I will emphasize any number of those at a given time (who doesn't love spending an occasional afternoon just chasing pointless benchmarks?). But I never come at it from a "big O mindset" even when that's what I'm doing in practice, I just call it "common sense" and heuristics: don't put slow things in tight loops, memoize when you can, and leverage concurrency.
In my line of work (CV), moving a slow blocking operation from serial to async will get you easy, bigger wins 90% of the time, vs seeking out something in polytime and refactoring to nlogn.
Know your data.
It's the equivalent philosophy to always buying the cheapest tool you can the first time around. When you break that tool, then you go out and buy the expensive one.
I set a breakpoint at the beginning of the main() method and it crashed before it even got to main().
That had me scratching my head for a minute, then I realized that the program was static initializing a 2^32 byte array. The prof had a 64-bit computer (probably DEC Alpha) which you could do that on, but it didn't work on my 32-bit x86 machine.
It turned out that the program never used the array that it allocated so deleting one line from the code got it to run.
Most CS profs never have to really finish the systems they work on so they lack many of the skills and attitudes of the professional programmer. Some of them are artisans with code, but mostly they making a living writing papers and teaching classes and the code is tertiary.
Fun fact: Just getting the job done works out well most of the time, technical debt is introduced but as in your example it served its purpose.
I find the opposite to be true, but it depends entirely on what problems you work with on a daily basis.
Data structures and algorithms are a toolbox and the more you know, the more options you have at your disposal to tackle a specific problem.
If you work in an area that doesn't benefit much from this specific set of tools, then yes, you only it during interviews; interviews done by people who don't have the faintest clue about what they're hiring you for (which is a big problem itself).
I suppose that's true, my perspective is as a client engineer where for the most part, someone's built the data structures for you. Yes you need to know their performance characteristics and when to use them, but otherwise if you're building them yourself you're doing something wrong. I'm sure that's not true in all roles.
> If you work in an area that doesn't benefit much from this specific set of tools, then yes, you only it during interviews; interviews done by people who don't have the faintest clue about what they're hiring you for (which is a big problem itself).
I'm actually really passionate about recruiting and improving the recruiting process anywhere I work, I'd love you to elaborate on this.
Unfortunately this is a really complex topic and I'm afraid I'm not nearly knowledgeable or experienced enough to give any meaningful advice in a concise way.
Say a candidate is to be hired for developing and maintaining a line of business app. In this case it's important for them to know the programming environment, frameworks and tools, as well as working with large programs or legacy code if applicable.
Start by asking a few "no brainers" sprinkled into a general conversation about their previous work experience and increase the "difficulty level" from there.
There will come a point at which the only honest answer will be "I don't know" or "I'd have to look that up", which is the perfect opportunity to just hand them a tablet (or laptop) and let them do so. This is an excellent way to learn how they look-up technical information (which sites do they use, how long does it take them, do they use meaningful keywords).
Another effective way of judging someone's skill is asking them to point out problems with a small piece of code or have them discuss required modifications to meet some constraint (e.g. sort a dataset by one of a user-selectable set of criteria, but you can only read each item once and the dataset doesn't fit into memory - a common problem with archival data stored on tape).
These are just some pointers, but they all have two things in common: they require the interviewer to know what the candidate is going to work on and they need more preparation work than just a checklist that reads "knows how to implement an AVL-tree in Python" or "can tell the arguments of all 6 overloads of std::transform_reduce() in C++17".
I did not study computer science in any substantial way, and I hardly consider myself a computer scientist, but I do have a nose for algorithms despite not really thinking about it in a structured way. I think lot of people get wrapped up in the notation without realizing they can approach the problem in a completely different way. Case in point, a professor at a University in the US created a parts-of-speech tagger and released the source in the early 2000's. I wanted to leverage this tagger to create a topic oriented search engine, but it was WAY too slow. It took about 10 seconds to tag a document (back in 2003 on decent hardware), and since I needed to tag hundreds of millions of documents, and despite having about 15 servers at my disposal, this was not going to work. So I dug into that algorithm and realized it was trying to test all of it's conditions all of the time to figure out which rule would apply. I redesigned it to index the rules and only apply them if it was possible for that rule to have some effect. Or something like that, the details are now fuzzy. The speedup was roughly 1000x, and made the tagger usable at scale.
Plot twist: I took a computer science class (as a Mech E major) taught by that same professor years earlier and failed it. That class was Data Structures.