ghj

That's crazy high isn't it? That's 1 out of 250 people!

Will you still be working on educational content on the side? (e.g. updating fast.ai and/or making one off lectures like https://www.youtube.com/watch?v=jkrNMKz9pWU)

Either way thank you for all the amazing free content you've already put out and good luck on the new endeavor!

AdamantChicken2 (aka AlphaCode2) replied to the thread! https://codeforces.com/blog/entry/123035?#comment-1091379

Some people on codeforces (the competitive programming platform that this was tested on) are discussing the model: https://codeforces.com/blog/entry/123035

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.

I remember deciding that I never want to ever have my DNA in any database after watching this talk:

DEF CON 25 - John Sotos - Genetic Diseases to Guide Digital Hacks of the Human Genome (2017): https://www.youtube.com/watch?v=HKQDSgBHPfY

I didn't realize who this was by the title, but this is betaveros, the guy who won 1st place in Advent of Code every single year since 2019: https://clist.by/account/32289/resource/adventofcode.com/

Copying from an older comment of mine shilling Pypy https://news.ycombinator.com/item?id=25595590

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

I've commented about this before, but their supposedly optimized implementation is still garbage: https://news.ycombinator.com/item?id=24125312

There's no reason to build the repeats up by doubling since the string concatenation of two same string is still linear time.

PyPy is easily 10x faster than CPython at numeric stuff, which is 99% of these contest problems.

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)

If you want more examples of real world use cases, PyPy is pretty stress-tested by the competitive programming community already.

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.

Isn't this use case the scientific computing use case? That's a fairly large part of the ecosystem to give up on!

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 stalked the author's linkedin and notice he has competitive programming experience: https://www.topcoder.com/members/kmod/details/?track=DATA_SC... (and top 15 putnam, ICPC world finals, etc)

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.

Soap film is also used to solve the steiner problem: https://www.youtube.com/watch?v=dAyDi1aa40E

GPT-3 can probably be ran deterministically given some a fixed random seed (even if you might need to "reroll" the seed a few times to cherry pick outputs). Then you can just attach the seed as proof of work. Anyone who wants to verify the output can just rerun with the same seeds.

Not a good example because being discontent with c++ for loops is how we got https://en.cppreference.com/w/cpp/ranges (which imo is a good addition to the standard library)

But yea, not while you're trying to ship.

I didn't know about functools.singledispatch/singledispatchmethod, it looks really nice!

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...

Yes actually. Both c++ and java have red black trees. In c++ it's std::set, in java it's TreeSet.

BST supports log(n) min/max/inserts/removes (among other stuff).

You would probably enjoy reading about an alternative implementation for STL's std::deque, called a tier vector[1][2].

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...

[2] https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf

[3] https://news.ycombinator.com/item?id=20872696

Dan Luu has a nice curated list: https://danluu.com/hn-comments/

Not in python! But I guess using negatives is the same as using different key (which is what python uses instead of comparators).

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.

In certain domains, the trend has been to give up constant factors in order to increase programmer productivity (e.g., python pays a 10x slowdown but is batteries included).

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)

You're probably thinking of storing it as some linked list but that doesn't work with mathematical abstractions (which is my point).

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...

Mathematical abstractions are often at the wrong level of abstraction. Mathematicians mostly care about value semantics but programmers need to care about how it's realized in hardware too.

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.

We live in very different times.

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.

To be fair if you add an opt-in step to anything, it will kill that thing. No moral judgement, just human laziness. If it doesn't kill it, it still becomes something everyone loathes (e.g., how you need an extra click to accept cookies on every site you use).

I've implemented this for leetcode without realizing it's paper worthy: https://leetcode.com/problems/lfu-cache/

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.

It's more that programming with math is hard.

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.

I can give another example use case.

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!)

I tried giving it a problem that required matrix power and it couldn't solve it. (this was a somewhat real task where I couldn't google how to raise a matrix to a power in tf).

    # 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

He wrote the post on 2019-02-16 and didn't put in the edit until 2019-04-26 so the causality probably happened the other way around.

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.)