That's crazy high isn't it? That's 1 out of 250 people!
634 karma · joined May 28, 2020
Either way thank you for all the amazing free content you've already put out and good luck on the new endeavor!
Seems like they don't believe that it solved the 3200 rated problem (https://codeforces.com/contest/1810/problem/G) w/o data leakage
For context, there are only around 20 humans above 3200 rating in the world. During the contest, there were only 21 successful submissions from 25k participants for that problem.
DEF CON 25 - John Sotos - Genetic Diseases to Guide Digital Hacks of the Human Genome (2017): https://www.youtube.com/watch?v=HKQDSgBHPfY
PyPy is pretty well stress-tested by the competitive programming community.
https://codeforces.com/contests has around 20-30k participants per contest, with contests happening roughly twice a week. I would say around 10% of them use python, with the vast majority choosing pypy over cpython.
I would guesstimate at least 100k lines of pypy is written per week just from these contests. This covers virtually every textbook algorithm you can think of and were automatically graded for correctness/speed/memory. Note that there's no special time multiplier for choosing a slower language, so if you're not within 2x the speed of the equivalent C++, your solution won't pass! (hence the popularity of pypy over cpython)
The sheer volume of advanced algorithms executed in pypy gives me huge amount of confidence in it. There was only one instance where I remember a contestant running into a bug with the jit, but it was fixed within a few days after being reported: https://codeforces.com/blog/entry/82329?#comment-693711 https://foss.heptapod.net/pypy/pypy/-/issues/3297.
New edit from that previous comment: there's now a Legendary Grandmaster (ELO rating > 3000, ranking 33 out of hundreds of thousands) who almost exclusively use pypy: https://codeforces.com/submissions/conqueror_of_tourist
There's no reason to build the repeats up by doubling since the string concatenation of two same string is still linear time.
For example, using CPython, if you try to make an array of a million ints, you won't get `int[1000000]` in your memory layout. Each int would actually be an object, which is huge and inefficient to reference (they are something like 24+ bytes each).
PyPy on the other hand, works as expected.
I think the more important point is that PyPy when written like C code, can actually get within 2x of the performance of C code. If it's any slower, python won't be a viable language in competitive programming at all.
(CPython is sometimes still used on other platforms like atcoder.jp, but only because they allow third party libraries like numba and numpy which can fill the same role pypy does)
https://codeforces.com/contests has around 20-30k participants per contest, with contests happening roughly twice a week. I would say around 10% of them use python, with the vast majority choosing pypy over cpython.
I would guesstimate at least 100k lines of pypy is written per week just from these contests. This covers virtually every textbook algorithm you can think of and were automatically graded for correctness/speed/memory. Note that there's no special time multiplier for choosing a slower language, so if you're not within 2x the speed of the equivalent C++, your solution won't pass! (hence the popularity of pypy over cpython)
The sheer volume of advanced algorithms executed in pypy gives me huge amount of confidence in it. There was only one instance where I remember a contestant running into a bug with the jit, but it was fixed within a few days after being reported: https://codeforces.com/blog/entry/82329?#comment-693711 https://foss.heptapod.net/pypy/pypy/-/issues/3297.
I think it's still a relatively low effort way (just need to write a scraper) to create a benchmark on a diverse set of algorithmic tasks that have clearcut criteria on AC/TLE/WA. PyPy is often 10x faster than cpython on these problems (and just 2x slower than equivalent C++ solution) so it will be a much nicer headline too if you can achieve similar performances!
Though I can also see how it can be completely irrelevant for server workloads. Pypy's unicode is so slow, some people on codeforces still use pypy2 over pypy3 just to avoid it. And c extensions is so bad on pypy, you can often get better performance on cpython if you need to use numpy.
I wonder if he would be interested in optimizing for purely algorithmic tasks?
There are a lot active and successful CPython and PyPy users on https://atcoder.jp/. For example:
https://atcoder.jp/contests/practice2/submissions?f.Task=&f.... (the user "maspy" is rated at 2750 using only cpython!!!)
https://atcoder.jp/contests/practice2/submissions?f.Task=&f.... (though pypy is more practical)
I am linking to atcoder because their testing data is public so you can rerun contestants solutions using both pyston/cpython/pypy for benchmarking purposes: https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGi...
Right now, other than a handful of people who figured out how to make numba's jit work, only pypy is viable for competitive programming. I wonder if you can do better than pypy?
There are also a few red coders on codeforces.com who mostly use pypy (cpython is completely unviable there because numpy and numba is not installed)
https://codeforces.com/submissions/pajenegod
https://codeforces.com/submissions/conqueror_of_tourist
But codeforces' test cases aren't public anyway so it's not as relevant.
But yea, not while you're trying to ship.
For typing hinting, I've been annotating with @overload which is just god awful ugly. And you still need to switch based on instance type for the actual implementation.
I will try this way instead!
[1] https://www.python.org/dev/peps/pep-0484/#function-method-ov...
BST supports log(n) min/max/inserts/removes (among other stuff).
It supports O(1) push_front/pop_front/push_back/pop_back/operator[]/at (like you would expect from a deque) but also O(sqrt(N)) insert and remove from middle!!!
The paper was from 1999 and 2001 but I only learned about it from a recent HN post[3] where some guy rediscovered it (20 years too late). I still wonder why this design lost to the std::deque we have in STL today.
[1] http://www.cphstl.dk/Report/Deque-first-attempt/cphstl-repor...
The real problem is if you need min/max at the same time. Then you not only need a min heap and max heap, you also need to track what was already popped from either heap! This is because in python you can't delete an element if it's not at the root. So tracking "tombstones" will let you pop from one heap, then know to ignore it the next time it comes up in the other heap.
This is of course super complicated to maintain and I get it wrong all the time. Luckily only shows up in algo interview problems.
So in that case I would use this data structure even if it weren't faster. I can't count the number of times I have had to mess with inserting negative priorities into a min heap to create a max heap! We should just have one data structure that does both.
(though taking this idea to the logical extreme means we should just use Order Statistic Tree for everything since it not only gives you log(n) min/max, but also log(n) find kth and get rank of x)
For example in mathematics if you write "C = A + B" and then you ask what A is, it's still always going to be the same.
To make this work in programming you basically have to make all your data structures persistent[1]. AFAIK you would need a store the list as a finger tree or something if you need fast concatenation and that will still only be O(log(n)) [2].
[1] https://en.wikipedia.org/wiki/Persistent_data_structure
[2] http://hackage.haskell.org/package/fingertree-0.1.4.2/docs/D...
[3] https://stackoverflow.com/questions/28406512/why-does-concat...
For example, sure, you can think of a list as a "monoid" where the add operator is concatenation of two list. But adding two lists is not a fast operation even using specialized functional data structures. So making concatenation a primitive for equational reasoning just results in really slow code.
In the past, every idea had to go through a filtering process in order to spread. I am not talking about some truth filter, but that the idea needs to meet some virality threshold since the medium of communication is very low bandwidth and slow. (Ex: scholars writing to letters to each other, or housewives gossiping about the latest folk remedy)
The greatest change that happened in the 21st century is that ideas spread at the speed of light, and any bullshit can be broadcast to billions of eyeballs very quickly.
Rather than a couple housewives laughing off how the neighbor tried the squeezing lemon juice into eyeball trick last week and found that it didn't work, you have some X% of people trying it immediately after seeing it on twitter.
My implementation: https://pastebin.com/48mMTTdK
I am surprised to see that the paper was only published in 2010. I would expect something this simple to have been discovered earlier. I guess it's easy only after someone tells you constant time is possible.
When communicating in mathematics you often assume the reader can understand precisely which mathematical object you're talking by extrapolating from ellipses "...". For example "the naturals are 1,2,3,4,..." or "the evens are 2,4,6,8,..."
Or I might tell you a shift matrix is something that looks like:
[0 1 0 0 0]
[0 0 1 0 0]
[0 0 0 1 0]
[0 0 0 0 1]
[0 0 0 0 0]
But if you want to explain what a shift matrix is to a computer, you must use a formal definition (and to do it idiomatically you need to know esoteric details like that numpy.diagonal takes in an offset parameter so you can do something like https://stackoverflow.com/a/30230801).
It would be nice if we can talk math with a computer in the same intuitive language we use with humans, just give it a few examples and it will generate the the rest and let you double check the formula is correct.
So I see stuff like tf-coder as a great step, not for synthesizing programs we don't know how to solve, but for language translation: between math notation and programming notation.
Say I know math but don't know tf api. I already know how to matrix multiply with `@` but don't know the function for matrix power.
Then in theory it should be fairly quick for me to create a random matrix and feed it `mat @ mat`, `mat @ mat @ mat`, `mat @ mat @ mat @ mat`, etc until it spits out the correct tf function I should call for matrix_power.
This is even better than googling since it guarantees that the function it found is correct for your example (googling returns tf.pow tf.exp tf.expm, none of which are actually what you want!)
# A dict mapping input variable names to input tensors.
inputs = {
'matrix': [[1, 1], [1, 0]],
'vector': [[1], [0]],
}
# The corresponding output tensor.
output = [[13],
[8]]
# A list of relevant scalar constants, if any.
constants = [6]
# An English description of the tensor manipulation.
description = 'Whatever the equivalent of numpy.linalg.matrix_power is in tf. Calculates fibonacci.'
matrix @ matrix @ matrix @ matrix @ matrix @ matrix @ vector
It seemed like this is a career summary from his time at Google Fiber (which was killed by google).
It sucks when your baby gets killed for reasons outside of your control. You want those years of your life to mean something, for the work to live on in some form (hence the "Please, please, steal these ideas").
He probably realized after publishing that the post wasn't enough to give him closure so he started a company to keep working on it instead.
(I don't know why I am psychoanalyzing a random blog. I am probably projecting really hard.)