251–260 of 328 posts
You can see hashing optimizations as well https://www.deepmind.com/blog/alphadev-discovers-faster-sort... , https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7d... I was one of the members who reviewed expertly what has been done both in sorting and hashing. Overall it's more about assembly, finding missed compiler optimizations and balancing between correctness and distribution (in hashing in particular). It…
sounds revolutionary
Earlier quoted context omitted.
This is correct history, but not the point TaupeRanger was trying to make (I believe). I think their assertion is that the release of AlphaGo has actually made human Go players worse at the game, contrasted with chess where most agree that the introduction of Superhuman chess engines has elevated the (human) state of play. But I don't think there is actually much evidence for that. I'm sure the introduction of AlphaG…
I don't think that AlphaGo has made players worse. My point is that there's no evidence that anything USEFUL or IMPORTANT has come from a system that has gotten so much hype (and cost ungodly amounts of money). If players aren't getting better (there's no evidence they are) or are quitting the game after playing, it's simply a net negative, along with DeepMind's other ventures.
Geez. We are talking about pebbles on a wooden plank. They are not even colourful!
Go is super cool game, but it is that. Just a game. We are not talking about curing cancer, or solving world hunger, or reversing climate change here. So by the very formulation a Go playing AI can be cool, or interesting, or promising. But could it really be useful/important with all-caps? It sounds like you have too high expectations here.
You can see hashing optimizations as well https://www.deepmind.com/blog/alphadev-discovers-faster-sort... , https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7d... I was one of the members who reviewed expertly what has been done both in sorting and hashing. Overall it's more about assembly, finding missed compiler optimizations and balancing between correctness and distribution (in hashing in particular). It…
Earlier quoted context omitted.
I think you are getting your information mixed up. Here is a comparison that shows quicksort running in 1/10th the time as heapsort. https://johnysswlab.com/why-is-quicksort-faster-than-heapsor...
Versions of quick sort differ in how the partitions are determined. A guess is that some of the versions are not worst case O(n log n) for sorting n keys. In that case, for sufficiently large n, on a normal computer, any version of heap sort will beat that version of quick sort in number of comparisons, time in seconds, Joules of energy to run the computer, etc. It is this point that has much of the academic computer…
It is this point that has much of the academic computer science community saying that no sorting algorithm based on comparing keys two at a time can beat heap sort.
I think you're the only one saying that. Where did you get this idea? I just showed you a quicksort being 10 times faster than a heapsort. You can try this for yourself.
Sure, we don't know how big n has to be. In practice, in an actual case, the n might have to be too big for current computers.
This is never going to be true. Quicksort and other sorts exploit locality much better. Partitioning an array gradually makes the sorting more local. That's going to work better relatively to a heap sort as data gets bigger, not worse.
Sure, in practice, for some value of n, on some list of n keys, some version of heap sort, and some version of quick sort, the quick sort might run 10 times faster in seconds of elapsed time than heap sort.
No, on any modern computer other sorts are going to beat a heapsort. It isn't exotic, it is how it works. Even if you have to scan every element first to get a distribution of your elements to choose your pivot, that is still going to be O(n log n) and it will still beat a heap sort.
Heap sorts are not the fastest way to sort. They can be consistent and they can split the time between inserting and extracting elements.
Earlier quoted context omitted.
I don't think that AlphaGo has made players worse. My point is that there's no evidence that anything USEFUL or IMPORTANT has come from a system that has gotten so much hype (and cost ungodly amounts of money). If players aren't getting better (there's no evidence they are) or are quitting the game after playing, it's simply a net negative, along with DeepMind's other ventures.
Sorry, but this is just incorrect. Go players have gotten stronger over time overall [0][1], and AI discovered many new ideas that all top pros have incorporated into their game-play (idk how to give a source for this, it's just very well known in the Go community that the style of play changed drastically in response to AlphaGo, and absolutely everyone trains with AI these days). [0]: "The sudden overall increase in…
Earlier quoted context omitted.
> > It is all about probabilistic guarantees > So are cryptographic hash functions. Cryptographic hash functions like MD5, SHA-2, BLAKE2, etc are deterministic functions, so it doesn't really make sense to talk about Pr[h(x)=h(y)]. Either the collide or not. It's muddied a bit by the fact that cryptographers also use universal hashing (or probabilistic hashing, or what I called algorithmic hashing) for stuff like UMA…
> Cryptographic hash functions like MD5, SHA-2, BLAKE2, etc are deterministic functions, so it doesn't really make sense to talk about Pr[h(x)=h(y)]. Either the collide or not. Eh, that's how I usually see collision resistance described. The probability is based on generating fresh inputs with any method you want/the most effective attack method available. But I wouldn't say the hash you linked is nondeterministic ju…
I'm curious if you can link to such an analysis. These functions are notoriously much harder to analyze than simple functions like "h(x) = ax+b mod p" which is all you need for the probabilistic guarantee.
But even if you could analyze this, you would just end up with a universal hash function that's way slower than you need, because you didn't pick the right tool for the job.
Earlier quoted context omitted.
It's made here in response to a claim that Go players are made worse by practicing with AlphaGo, which is also unsubstantiated.
Wrong. The claim was never made that players got worse, only that their ratings dropped, which is empirically true. After playing AlphaGo, for example, Ke Jie dropped in the rankings and was quickly taken out of 1st place overall. The overall point though, is that AlphaGo produced nothing of value for humans, since there's also no evidence that players have improved since AlphaGo's creation. Factoring in the immense…
Hear me out - what if we learned something about creating AI by creating a new AI?
Earlier quoted context omitted.
This sounds like a more intelligent version of superoptimization. The original Masselin SO, albeit for its time, also created surprising results which is similar to AlphaDev's incomprehensible for humans . You see the same thing in computer chess which Agadmator calls disgusting engine lines . https://courses.cs.washington.edu/courses/cse501/15sp/papers...
Stockfish actually use machine learning to pick the best magic numbers for their code.
https://en.m.wikipedia.org/wiki/Simultaneous_perturbation_st...
Earlier quoted context omitted.
The Gleason bound is n log(n) and says that no sorting algorithm based on comparing pairs of keys can be faster. Heap sort meets the Gleason bound so is the fastest possible in this context. Actually the usual versions of quick sort are slower. If the keys are not too long, radix sort is O(n) and faster. All this has been well known for decades. I explained a little more in another post in this thread.
Come on, guys: Early in my career, I had a really good career going. I paid a lot of attention to writing fast code. Some of that career was in a Navy lab, and some of the people there wrote fast code by going down to the assembly language and checking each instruction, load, store, etc. At times that career bumped into some math -- 0-1 integer linear programming, even ordinary linear programming, optimization, e.g.,…
Second, your "alternative speed" measures are a hallucination.
Sooo, broadly that's two quite different ways to look at how to write fast code.
No there isn't. The one that takes 1/10th the time of the other one is faster. You going off on tangents and making up terms to try to say that a heap sort is the fastest sort (of all the strange things to argue) is nonsense.
Earlier quoted context omitted.
70% better than O(N log N) is still O(N log N).
It's 70% better than O(1). The algorithms it found are for sort3, sort4, and sort5, which were poorly optimized in LLVM's libc++.