1. 12

  2. 6

    Should you need to do this in real life, notice that Python sets have an isdisjoint() method.

    1. 2

      Quadratic algorithms pop up everywhere, and they aren’t always obvious, especially in software with a great deal of abstraction. Sometimes you’re calling into a method which does far more work than you expect. In a system I’ve worked on, it caches certain structures to make the common case fast, but evicts the cache on mutation and forces a rebuild on next read (don’t ask me why it’s not maintained incrementally). If you’re doing a read-modify-read, now you’re quadratic. Yay.

      Worse, you don’t always have a good way to preempt it. On the JVM, threads are cooperatively scheduled. If a thread doesn’t yield, it keeps running. So those algorithms that occasionally take hours to run? Bad news, you just lost a thread from your executor (and probably a core, or at least part of one) for the next few hours. The request you just received probably timed out and retried, so you lose another thread. If you’re lucky, you have enough capacity to handle it, or notice early enough to kick some tasks while you rush a fix in.

      Running services is hard.

      1. 2

        Quadratic algorithms are fine as long as you strictly control the size of their inputs. E.g., quadratic sorting algorithms like insertion sort are generally used as the base case of optimized linearithmic algorithms like quicksort. As a rule of thumb, I start worrying about quadratic algorithms when N gets close to 10^4 or so (so N^2 is approaching a billion).