5 years ago Neal Gafter wrote about reified generics...

Many people are unsatisfied with the restrictions caused by the way generics are implemented in Java. Specifically, they are unhappy that generic type parameters are not reified: they are not available at runtime. Generics are implemented using erasure, in which generic type parameters are simply removed at runtime. That doesn't render generics useless, because you get typechecking at compile-time based on the generic type parameters, and also because the compiler inserts casts in the code (so that you don't have to) based on the type parameters.

sorting to extract a range

So, we have 100500 records; we need to take, say, the second 100, as if we ordered the whole set and then got those 100.

Sure we don't need to sort everything. The (recursive) solution is this:

1. take a pivot value x
2. partition the records around the pivot, so there are k below x and N-k above x.
3. find where our required range (a..b) lies: if it is inside the whole partition, fine; repeat
4. otherwise, take some from the tail of the left partition and some from the head of the right partition.

That's it, right?

Complexity: average still O(n log(n)), but the worst case is O(n*(b-a)).

Right?

bad puzzle

What's this sequence about? What's next?
1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 1993 1997 1999 2003 2011

Цукербергу в укор

(10x thesz)