Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

nature.com

Post reply on HN
Print view View original

291–300 of 328 posts

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#291

Post by CyberDildonics »

graycat wrote: post #290
CyberDildonics wrote: post #284

Earlier quoted context omitted.

Also Gleason, Knuth, and much of the academic computer science community. Prove it, show me who is saying 'nothing can beat a heapsort'. says next to nothing about the big-O expression. Why do you think heap sort is the only n log n sort? Link something that proves what you say. settled on big-O as the way to compare algorithms and code Time determines speed, that's what this thread is about. I already linked you a b…

All your issues have been responded to thoroughly. Here you are embarrassing yourself.

I guess this is the "I already told you" part of the conversation, but you didn't link a single thing.

All you did was repeat your claim over and over. No benchmarks, no link to 'gleason bound' and nothing but hallucinating hypothetical scenarios and declaring that somehow they would back up your claims that go against literally all benchmarks and computer science knowledge. If I'm wrong, show me some links.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#292

Post by CyberDildonics »

graycat wrote: post #288
CyberDildonics wrote: post #191

Earlier quoted context omitted.

Who is talking about that? They said 'faster' not less algorithmic complexity. 1/10th the time is much faster.

> 1/10th the time is much faster. No, absolutely no, it's not in any meaningful or useful sense "faster" as in which algorithm is "faster". You utterly fail to get this point.

If something runs in less time, it's faster. If something runs in 1/10th the time as something else it is multiple orders of magnitude faster. I don't think I've ever seen someone try to redefine 'faster' before.

You keep trying to equate naive algorithmic complexity and speed, but you haven't even linked anything that shows heapsort is better than other sorts like quicksort at that. You haven't actually linked anything to back up any of what you're saying, even the irrelevant offtopic claims.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#293

Post by CyberDildonics »

graycat wrote: post #287
CyberDildonics wrote: post #281

Earlier quoted context omitted.

The Gleason bound? Instead of repeating yourself, can you link to some actual information? still will win no matter how measure speed Speed is measured with time. You can keep saying algorithmic complexity is speed, but that will never make it reality. If you want to argue against heap sort, then you need to argue That's not how it works. Other sorts take a fraction of the time. I showed you this already. I'll let so…

> You are trying to argue something that isn't real to make a point that no one cares about and has nothing to do with this thread. In a word, you are wrong. I've been very, very, very clear again, over again, once again, yet again, and you just fail to get it, a simple lesson often just in the first week of an easy, first college course in computer science. > Other sorts take a fraction of the time. I showed you thi…

In a word, you are wrong.

Prove it, show me something.

Your evidence is meaningless.

I showed you benchmarks with source code. You showed me nothing.

Heck, even bubble sort could beat heap sort or quick sort under some circumstances.

It isn't going to beat them on 32 million floats, which was what that benchmark showed. And are you now mixing up actual execution time with your other bizarre claims where 'speed' and 'faster' for some reason don't mean less time?

Okay, there are some ties. I never said there are no ties.

You did actually, now you're back peddling hard. Also these don't tie, they are faster because of locality.

Third, I gave the reference, D. Knuth's famous book.

Link something then, link any trace of what you are saying.

The Gleason bound is one of the nicer, most powerful, most useful, most important pieces of work in all of computer science,

Then why is there no evidence that it exists? Link me literally anything you can.

You have some problems, some blocks in understanding.

No, I have evidence and links that back up what I'm saying. You keep repeating the same things with no evidence. Link me literally anything you can find that reinforces your claims.

For your emotional problems, nothing in computing, computer science, or my writing can help you.

This is pure projection.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#294

Post by shrimp_emoji »

graycat wrote: post #287
CyberDildonics wrote: post #281

Earlier quoted context omitted.

The Gleason bound? Instead of repeating yourself, can you link to some actual information? still will win no matter how measure speed Speed is measured with time. You can keep saying algorithmic complexity is speed, but that will never make it reality. If you want to argue against heap sort, then you need to argue That's not how it works. Other sorts take a fraction of the time. I showed you this already. I'll let so…

> You are trying to argue something that isn't real to make a point that no one cares about and has nothing to do with this thread. In a word, you are wrong. I've been very, very, very clear again, over again, once again, yet again, and you just fail to get it, a simple lesson often just in the first week of an easy, first college course in computer science. > Other sorts take a fraction of the time. I showed you thi…

> Instead of repeating yourself, can you link to some actual information?

> I gave the reference, D. Knuth's famous book.

I just Ctrl+F'd "Gleason" in The Art of Computer Programming Vol 1, Vol 2, Vol 3, Vol 4A, and Vol 4B, with no hits in any of the 5 books.

I even looked in the glossaries. There's lots of last names -- Glaisher, Glassey, Gnedenko -- and no "Gleason".

I'm tempted to side with this iteration of CyberD's brutal takedowns on this one. :D

---- EDIT ----

WAIT: I found it in the glossary of Vol 3!

"Gleason, Andrew Mattei, 193, 648."

For this one, case sensitivity got me when I searched "gleason"!

The most relevant bit here seems to be page 193, discussing ways to minimize the average number of comparisons:

```

The minimum possible average number of comparisons, obtained by dividing by N, is never less than lg N and never more than lg N + 0.0861. [This result was first obtained by A. Gleason in an internal IBM memorandum (1956).]

```

"Gleason" is only mentioned in Vol 3.

"Gleason bound" is not used in Vol 3, which must be why it doesn't pop up on Google.

CyberD: now on the backfoot

graycat's startup: in talks for VC funding

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#295

Post by CyberDildonics »

shrimp_emoji wrote: post #294
graycat wrote: post #287

Earlier quoted context omitted.

> You are trying to argue something that isn't real to make a point that no one cares about and has nothing to do with this thread. In a word, you are wrong. I've been very, very, very clear again, over again, once again, yet again, and you just fail to get it, a simple lesson often just in the first week of an easy, first college course in computer science. > Other sorts take a fraction of the time. I showed you thi…

> Instead of repeating yourself, can you link to some actual information? > I gave the reference, D. Knuth's famous book. I just Ctrl+F'd "Gleason" in The Art of Computer Programming Vol 1, Vol 2, Vol 3, Vol 4A, and Vol 4B, with no hits in any of the 5 books. I even looked in the glossaries. There's lots of last names -- Glaisher, Glassey, Gnedenko -- and no "Gleason". I'm tempted to side with this iteration of Cyber…

That's great that you found actual information, but that doesn't seem to back up this person's bizarre claims that 'nothing beats heapsort'.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#296

Post by aldousd666 »

blazespin wrote: post #115
orlp wrote: post #91

> AlphaDev uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements. As someone that knows a thing or two about sorting... bullshit. No new algorithms were uncovered, and the work here did not lead to the claimed improvements. They found a sequence of assembly that saves.…

Yeah, this type of grifting is very proforma for Researchers. I used to stress about it, but realize it just sort of goes with the territory. It's also worth noting that the paper is blindingly obvious and everyone started doing this a long time ago but didn't want to tip their cards. And that's the real contribution here - Google is tipping their cards. We now have a rough baseline to compare our results against.

Well. I feel grifted too because being a developer, yet not into the state of the art in algorithms (at that level,) i was inclined to buy their BS

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#297

Post by hugopenmir »

Nimitz14 wrote: post #262
malux85 wrote: post #166

Earlier quoted context omitted.

I run atomictessellator.com and have been working on many different implementations of density functional theory for the last 10 years, as well as working closely with professors at Stanford university and Oxford university of using advanced, non-static geometry data structure for density functional theory for multiple years, this is a subject I know a LOT about, so I’m glad you brought it up. Deep minds work on Dens…

Love that you know enough to call him out haha

Right! Finally, thanks!

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#298

Post by hugopenmir »

TaupeRanger wrote: post #246
gusennan wrote: post #220

Earlier quoted context omitted.

They solved an open challenge problem, Protein Structure Prediction, with AlphaFold, which has been nothing short of revolutionary in the structural biology and biochemistry fields. I do scientific research in these fields and the capabilities AlphaFold provides are used now everywhere.

Yes, many research papers have been written, and many CVs have added lines which include the word "AlphaFold". But has the human condition been improved one iota from the "discovery"? Has anything real actually happened? Not at all. Only "maybes" and "possibilities" after more than 5 years of work. "Revolutionary" at padding researcher CVs indeed.

Man, with al respect why your “hate” with the good guys working at DeepMind? Everybody loves and respect Demis Hassabis, he is truly a genius. He really wants the best for the world/humanity and that takes a ton of time, so let’s wait and see.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#299

Post by hugopenmir »

tlringer wrote: post #208
orlp wrote: post #91

> AlphaDev uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements. As someone that knows a thing or two about sorting... bullshit. No new algorithms were uncovered, and the work here did not lead to the claimed improvements. They found a sequence of assembly that saves.…

Every DeepMind press release is like this.

You know people at Google, tell Demis about this.

Re: Deepmind Alphadev: Faster sorting algorithms discovered using deep RL

#300

Post by mgaunard »

Articles were making bold claims, but it's just optimizing libc++ and abseil's implementations. There are already known implementations faster than either of these in the right scenarios.

As always, speed depends on the use case. What's optimal for a sorting algorithm depends on the size of the data, its distribution, and also how it fits into the rest of the program and how that program fits into what else the machine is doing.

For example, you can make things faster by using more hardware resources, but that would penalize the rest of your program that doesn't have access to them anymore. I've frequently seen cases where a function was made faster in a microbenchmark by using all of the registers available, but then real programs ended up slower because the rest of the code had to spill to call it.

Post reply on HN