Also reading Feynman's Lectures on Physics [0]. He presents loads of topics in a way that I think captures a lot of the beauty and cleverness of physics while focusing more on building intuition and understanding than on specific math techniques that often come up in physics courses.
I think they're a good way to learn about physics without a ton of background. I also find they're nice to read when studying for my physics exams, just because of Feynman's unique approach to teaching.
By the same guys who gave the talk on how common most physical keys were? That one was a blast, too. Wouldn't you know that a key which opens one Kone elevator opens EVERY Kone elevator...
I think there was some good info in there but I also couldn’t help thinking ‘this guy is just lumping together all of the tech buzzwords of the last 2 years’.
Reminded me of college, when we had to write several pages of assembly code (that was 6 years ago). Fun exercise, not so much when your grade depends on it.
You really wish for a paranthesis counting pen when you have to write pages and pages of LISP (I think it was Common Lisp in our case) on paper for an exam.
This is a talk by Professor Fritz Henglein about how to sort general datasets in linear time. Most people in industry do not believe this is possible, but it's actually part of a family of well-researched techniques.
https://youtu.be/sz9ZlZIRDAg
It's been six years since the talk... Why hasn't someone drilled down through all the irrelevant typing goo, and shown how to sort integers in linear time? Where does the standard proof that optimal algorithms are Ω(n log n) break?
> Why hasn't someone drilled down through all the irrelevant typing goo, and shown how to sort integers in linear time?
I mean, if that's all you want Radix sort and American Flag sort are wikipedia fodder.
As for the "typing goo" is, uh, fairly important for how it's derived and what it does. A lot of advanced CS work uses it now, because it's quite powerful. A huge amount of pure-CS research is done in that world.
I guess we don't see this work in more contexts because it's just very very difficult to get it right. Edward Kmett, who is globally recognized for his talent in the field, did a haskell implementation which we all use and love, but it's pretty excruciating to implement it outside of a functional and generic language (and it is genuinely hard to do it in a language without general side effects, so you get difficulty from both sides).
I think a lot of folks in industry just don't think it matters. Certainly when I talk to my peers they suggest it doesn't matter to their work at all.
One particularly interesting work was computing specific types relational algebras producing products in linear time, which is pretty cool: https://dl.acm.org/citation.cfm?id=1706372 (btw, sorry, ACM is down tonight they're showing us their cloudflare).
This is not new stuff in the world of graduate CS, anymore than succinct data structures or wavelet trees. It's seldom applied in industry, but many of these techniques and sorts are taught as upper division courses in recent, algorithm-and-theory intensive CS programs. That stuff just doesn't make it out of academia very fast these days. Academics face a lot of pushback from industry now with disruptive findings. Look at how Emin Gun Sirer has been blackballed by the cryptocurrency community, for example. Look at how steadfastly folks have stood by JWT despite Lentczner's team's work on a better alternative in Macaroons.
Where is the Haskell implementation? Are there public benchmarks of its asymptotic performance?
I'm pretty sure a worst-case linear sorting algorithm would have multiple NYT articles about it.
EDIT: The edits to the parent since I made this comment make it look a bit silly. It made more sense in the context I was initially responding to.
EDIT 2: Thanks for linking the paper. From there:
> As Proposition 1.1 and the corresponding well-known combinatorial lower bound of Ω(n log n) (Knuth 1998, Section 5.3.1) for comparison-based sorting show, we cannot accomplish efficient generic partitioning and linear-time sorting by using black-box binary comparison functions as specifications of equivalence or ordering relations. Instead, we show how to construct efficient discriminators by structural recursion on specifications defined compositionally in an expressive domain-specific language for denoting equivalence and ordering relations.
Which sounds like the advantage I speculated on in the grandchild below. I understand, now, and it's a nice result. Thanks for pointing it out.
Which, by the way, contains boatloads of novel work. It uses internal parallel execution to work around some of the problems with discrimination passes between two groups. Cutting edge stuff.
It's haskell. People like you have chips on their shoulder about "typing goo." I'm sure one day someone will write a golang implementation then go to some inventor-centric conference and be hailed as a genius tho, as per usual.
But, did you not know about Radix sort or American Flag sort? Counting sort is a common stupid silicon valley interview question, and has been in the ruby code katas since like 2003. So as keen as I am to see this work widely distributed, it's not totally unprecedented the way you make it out to be.
Hey, want to know another surprising one? With a proper pre-encoding you can compress an (extremely long) binary value and answer questions about how many bits in a given range have occured (a popcount) in constant time. You can also, by extension, figure out the offset of the Nth hot bit appears, in O(1) time. Pretty surprising, huh? Especially when you realize that the entire space of 32 bit integers is only 512mb as a fully realized bitfield, 32x smaller than actually storing one instance of every integer.
No I'm afraid they don't. I confess I regret this conversation. I've gotten very little out of it other than a confrontstonal attitude from you and a bunch of confusingly worded challenges.
In general asymptotic analyses (including the well-known O(n log n) bound for comparison based sort) assume a model where operations like compare, swap, arithmetics, etc. are constant-time. So they only work for bounded integers, practically speaking.
If you want to know for the general case, you need to adapt your machine model and redo the analysis. Operations will likely be not constant-time but something like log(x) where x is the size of the integer at hand. But of course, that's up to you and what you want to do and how you build your machine.
I think this isolation is done to critique the algorithm in question in isolation of any underlying structure.
What's cool about Discrimination sort is that it does, in fact, can give these linearity guarantees for most kinds of data a computer can represent, including things like strings which have variable length or structs. There are some caveats there, but they're easy enough to work with that nearly every default structure in haskell as seen here: http://hackage.haskell.org/package/discrimination-0.3/docs/D...
Note particularly the instance for [a], and that you can extend it to something like Data.Text's codepoints (and this would work out of the box with something like ByteString's chunked form).
"typing goo". Generally complaining about the methods used by someone with a novel-peer reviewed result and demanding further and further reductive summarization on your terms, defining said terms with phrases like "typing goo" is bad form.
Further suggesting a lack of credibility by suggesting press coverage should be in place is confrontational.
I lost my temper after you did these things a few times. I apologize.
And yes, it can get O(n) performance with Arbitrary length integers. These analysis exclude underlying comparison times.
> suggesting a lack of credibility by suggesting press coverage should be in place is confrontational.
You edited out the context I was responding to, there. As I recall, you were originally explaining the "six years" in terms of it just being hard to get academic results into the mainstream. That seemed extremely unlikely for such a well-known result.
I'm not bothered by your invective or personal attacks, but editing your comments so that my responses are out of context is pretty disturbing.
I edited a cloned paragraph with a missing sentence that was accidentally added. I prepared that reply on mobile, and that can happen because you don't see scroll bars.
The literal and figurative content weren't changed. I just removed duplication and improve the flow of the post.
It's easy to see that you two weren't on the same page for quite a bit. I can't see a confrontational attitude. Please avoid belittling the other commenter - they never asked for a long-winded explanation (slightly bragging?) but were obviously only lacking a bit of essential knowledge (O(n log n) is for comparison based sorts).
Anyways, thanks for posting the links, although I'm not sure I will get anything out of it :-)
For that long time period you might want to watch "A Glorious Accident". Wim Kazyer sits down with Daniel Dennett, Freeman Dyson, Stephen Jay Gould, Oliver Sacks and Stephen Toulmin (and Rupert Sheldrake) to do one-on-one interviews. Then all of them sit down together for 3 1/2 hours at a round table and have a wide-ranging discussion. Wim Kazyer acts as a kind of moderator, Rupert Sheldrake, who has written books like "The Science Delusion" acts as a kind of antagonist.
I've started watching Raymond Hettinger's talks lately. He's a core dev on Python. I love them, the guy is charismatic, very smart and his Python knowledge constantly impresses me.
This is cool. I really love these type of posts where the people under discussion is not in the main stream but should have been popular in programming groups. John Carmack talks also is of that type. Very charismatic and delivers his speech standing at the same place with minimal movement for over an hour and talking from the fundamentals to the extreme details of the topics.
Netflix now lets you download many (most?) of their films, I always get some documentaries and fictional shows of my destination. For France I watched a documentary on the national soccer team and a comedy special by Jacky Bloom.
161 comments
[ 4.9 ms ] story [ 258 ms ] thread[0] - https://www.youtube.com/watch?v=j3mhkYbznBk&list=PLLzGzdSNup...
I think they're a good way to learn about physics without a ton of background. I also find they're nice to read when studying for my physics exams, just because of Feynman's unique approach to teaching.
[0] - http://www.feynmanlectures.caltech.edu/index.html
I recommend the full 2 hour version, with all the secrets: https://youtu.be/ZUvGfuLlZus
My second favourite talk: You spent all that money and your still got owned: https://youtu.be/tJsNu0VRKYY
I even watch these again and again.
http://digitalphotography.exposed/#schedule
Check my submission history. I keep trying to show people this work. Sadly, it never seems to take to a wide audience.
As a consequence, selective joins across 2 fields are also linear time.
I mean, if that's all you want Radix sort and American Flag sort are wikipedia fodder.
As for the "typing goo" is, uh, fairly important for how it's derived and what it does. A lot of advanced CS work uses it now, because it's quite powerful. A huge amount of pure-CS research is done in that world.
I guess we don't see this work in more contexts because it's just very very difficult to get it right. Edward Kmett, who is globally recognized for his talent in the field, did a haskell implementation which we all use and love, but it's pretty excruciating to implement it outside of a functional and generic language (and it is genuinely hard to do it in a language without general side effects, so you get difficulty from both sides).
I think a lot of folks in industry just don't think it matters. Certainly when I talk to my peers they suggest it doesn't matter to their work at all.
As for "6 years", they author has continued to push the work. It's also been used in a variety of applications. You can cite search the original paper. https://pdfs.semanticscholar.org/f425/7af9221ca7fe21dc84a049...
https://scholar.google.dk/scholar?oi=bibs&hl=en&cites=180821...
One particularly interesting work was computing specific types relational algebras producing products in linear time, which is pretty cool: https://dl.acm.org/citation.cfm?id=1706372 (btw, sorry, ACM is down tonight they're showing us their cloudflare).
This is not new stuff in the world of graduate CS, anymore than succinct data structures or wavelet trees. It's seldom applied in industry, but many of these techniques and sorts are taught as upper division courses in recent, algorithm-and-theory intensive CS programs. That stuff just doesn't make it out of academia very fast these days. Academics face a lot of pushback from industry now with disruptive findings. Look at how Emin Gun Sirer has been blackballed by the cryptocurrency community, for example. Look at how steadfastly folks have stood by JWT despite Lentczner's team's work on a better alternative in Macaroons.
I'm pretty sure a worst-case linear sorting algorithm would have multiple NYT articles about it.
EDIT: The edits to the parent since I made this comment make it look a bit silly. It made more sense in the context I was initially responding to.
EDIT 2: Thanks for linking the paper. From there:
> As Proposition 1.1 and the corresponding well-known combinatorial lower bound of Ω(n log n) (Knuth 1998, Section 5.3.1) for comparison-based sorting show, we cannot accomplish efficient generic partitioning and linear-time sorting by using black-box binary comparison functions as specifications of equivalence or ordering relations. Instead, we show how to construct efficient discriminators by structural recursion on specifications defined compositionally in an expressive domain-specific language for denoting equivalence and ordering relations.
Which sounds like the advantage I speculated on in the grandchild below. I understand, now, and it's a nice result. Thanks for pointing it out.
Which, by the way, contains boatloads of novel work. It uses internal parallel execution to work around some of the problems with discrimination passes between two groups. Cutting edge stuff.
It's haskell. People like you have chips on their shoulder about "typing goo." I'm sure one day someone will write a golang implementation then go to some inventor-centric conference and be hailed as a genius tho, as per usual.
But, did you not know about Radix sort or American Flag sort? Counting sort is a common stupid silicon valley interview question, and has been in the ruby code katas since like 2003. So as keen as I am to see this work widely distributed, it's not totally unprecedented the way you make it out to be.
Hey, want to know another surprising one? With a proper pre-encoding you can compress an (extremely long) binary value and answer questions about how many bits in a given range have occured (a popcount) in constant time. You can also, by extension, figure out the offset of the Nth hot bit appears, in O(1) time. Pretty surprising, huh? Especially when you realize that the entire space of 32 bit integers is only 512mb as a fully realized bitfield, 32x smaller than actually storing one instance of every integer.
See here: http://alexbowe.com/rrr/
Oh, is it that the types somehow mandate roughly evenly-sized ordered partitions at any sample size? If so, I get it, now. Thanks.
Can you get linear time even on Haskell's arbitrary-precision `Integer`s?
If you want to know for the general case, you need to adapt your machine model and redo the analysis. Operations will likely be not constant-time but something like log(x) where x is the size of the integer at hand. But of course, that's up to you and what you want to do and how you build your machine.
What's cool about Discrimination sort is that it does, in fact, can give these linearity guarantees for most kinds of data a computer can represent, including things like strings which have variable length or structs. There are some caveats there, but they're easy enough to work with that nearly every default structure in haskell as seen here: http://hackage.haskell.org/package/discrimination-0.3/docs/D...
Note particularly the instance for [a], and that you can extend it to something like Data.Text's codepoints (and this would work out of the box with something like ByteString's chunked form).
Further suggesting a lack of credibility by suggesting press coverage should be in place is confrontational.
I lost my temper after you did these things a few times. I apologize.
And yes, it can get O(n) performance with Arbitrary length integers. These analysis exclude underlying comparison times.
> suggesting a lack of credibility by suggesting press coverage should be in place is confrontational.
You edited out the context I was responding to, there. As I recall, you were originally explaining the "six years" in terms of it just being hard to get academic results into the mainstream. That seemed extremely unlikely for such a well-known result.
I'm not bothered by your invective or personal attacks, but editing your comments so that my responses are out of context is pretty disturbing.
The literal and figurative content weren't changed. I just removed duplication and improve the flow of the post.
Anyways, thanks for posting the links, although I'm not sure I will get anything out of it :-)
The title threw me off, but it's a very interesting and grounded talk about the different approaches to scaling fusion energy.
https://www.youtube.com/playlist?list=PLRVdut2KPAguz3xcd22i_...
My favourite: https://www.youtube.com/watch?v=9zinZmE3Ogk
https://youtu.be/cbu_bCQ2Lkg
https://youtu.be/_eC14GonZnU
The Ultimate Game Boy Talk https://media.ccc.de/v/33c3-8029-the_ultimate_game_boy_talk
The Ultimate Apollo Guidance Computer Talk https://media.ccc.de/v/34c3-9064-the_ultimate_apollo_guidanc...
The Ultimate Atari 2600 Talk https://media.ccc.de/v/28c3-4711-en-the_atari_2600_video_com...
More here:(Commodore 64, Amiga 500, etc.) https://media.ccc.de/search/?q=ultimate
It's in the genre of "two dudes talking" podcasts, but technology and futurology are some of the topics they touch on often.