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)
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.
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)
So, kind of a non sequitur, but I occasionally think about Qt's QList<T>. When introduced, it was odd for reserving space at the beginning as well as the end, so you had constant-time inserts/removals at the beginning. That and storing pointers for any T larger than a pointer also reduced the constant factor on insertion/deletions from the middle. Since it was always stored as a list of pointer-sized items, some code could be shared between implementations for different types, so your program's binary could be a bit smaller. I think they said at the initial release that they benchmarked a bunch of options in some real code and this won.
That was waaay at odds with the mindset of the STL, which seemed to me and I think a lot of folks like the state-of-the-art of containers at the time: with the STL if you prepend/insert much you need to use a deque/linked list, you decide pointer vs. value each time you declare a type, and if you want to know about the constant factor on an insert in the middle of the list you probably already lost.
(Qt has/had some other fun pragmatic things, like copy-on-write types in a lot of places. I didn't really do nearly enough with it to discover the pitfalls, but was fun to read.)
So I think about that, about how there are likely some trees out there that could just as well be sorted arrays, about adaptive structures that change their behavior based on dynamically observing how they're used (one recently discussed here: http://blog.erlang.org/the-new-scalable-ets-ordered_set/), even about tricks in in JS string implementations and VMs. I don't have answers, but I sometimes wonder if we should be thinking more in terms of tools that may not be perfect on all axes but soften or eliminate performance cliffs we take for granted. Not that the zero-overhead fine-tuned types are going away, just that they aren't the only imaginable approach.
I wonder if we'll see progress in those sort of imperfect-but-resilient tools over time. I think the long-run trend is towards some form of programming being accessible to more people more easily (like how, as you note, folks do real work in Python now). That certainly fits with trying to make your tools resilient to "misuse"--or, better, properly supporting more patterns so they're not even misuse. No conclusions, just hand-waving, but I do wonder if anyone working in software construction tools will eventually more usefully wave their hands in that direction :P
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.
This made me search around about unsorted B-tree-like collections. Turns out Clojure[1] and the im immutable-collections crates in Rust[2] use a structure called an RRB-tree, and searching 'blist' (because why not) turned up a Python module[3]. So, yes, a thing!
Tricky bit is trying to work well when used like a plain vector too. Clojure's RRB-tree special-cased repeated small appends to the end to help with this, and the Rust page mentions a clever chunking technique for append/prepend. And I imagine largeish leaf pages might help with average prepend/append/iteration overhead, at some cost when inserting in the middle?
Anyway, just neat that it's been taken further than I realized!
If you haven't already seen it, you'd probably really enjoy Chandler Carruth's "Efficiency with Algorithms, Performance with Data Structures" talk from CppCon 2014: https://youtu.be/fHNmRkzxHWs
Yeah--JS seems to allow enough weird stuff with arrays that fast paths for when things aren't weird seem inevitable. I admit when I clicked I still found V8 had more implementations than I expected, haha.
What they do with strings is kind of neat, because if you do a lot of concats in a row (potentially an O(n^2) series of operations done the naïve way), they defer actually concatenating all the data until you try to get a character out or such (the string is just a "ConsString" pointing to the source strings): https://gist.github.com/mraleph/3397008
It's also impressive how much dynamic instrumentation they can do. Beyond finding hot code and guessing types, they're even e.g. using it to guess which garbage will be long-lived (for "pretenuring" to avoid needing to copy it).
There's a limit to how much clever stuff you can do implicitly since you don't want to impose big costs for code that's doing everything right; something like QList isn't that adventurous but it's also clearly wrong when you want to compactly store a bunch of small structs in memory. And like the linked post on V8's thing notes, when you patch over a problem in one specific case the 'fix' can be fragile. Still, interesting area.
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.
Do any languages give you min/max at the same time with their standard library data structures?
(setting the key function with "key=lambda x: -x" is really easy and works just like changing a comparator function in other languages so I dunno why you guys are talking about it)
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.
> Mathematicians mostly care about value semantics but programmers need to care about how it's realized in hardware too.
Exactly! The thing is this book gives a method where you care about value semantics, keep the ideal representation, and then care later about how it's realized in the hardware!
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].
In math everything is persistent/immutable anyway, so persistent data structures are a given when working with purely mathematical abstractions.
There is a memory issue because of this, but this problem isn't exclusive to FP languages. Many languages solve this with something called garbage collection.
The very definition of pure FP (which is basically just programming founded on the principles of mathematics) rest foundationally on just a program that is immutable and has no side effects. Those are the only two requirements needed to do FP.
Immutability is therefore the axiomatic foundation of FP.
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.
> 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.
On the other hand: those billions of eyeballs now have three gajillion hours of youtube presented to them any second. I'm fairly certain that a few large newspapers a hundred years ago had a much, much better reach when it came to implementing ideas into the general public, because there was so little else.
It's like hearing somebody speak that stands 5m from you in an otherwise silent room vs hearing somebody shout at the other end of a football stadium. If all the fans in that stadium coordinate to amplify their message, you will hear it and it will vibrate the seat you're sitting on, but they barely get that coordinated unless it's very simple messages that are incredible light on information.
Rather than hanging their neighbors for witchcraft, instead they moan about conspiracy theories involving QAnon or Russia.
On balance, the free dissemination of ideas seems to have helped truth spread more easily. Lies didn't have any problem spreading before we had electricity. Unless you think that we should still be basing our entire culture around the worship of gods carved from stone and wood?
In many countries, the power of social media gives a platform for superstition and mystical thinking to expand.
In less developed nations, where religion and superstition are fundamental parts of the power structure, they travel even faster than facts, and those who argue for reason are silenced (Death of rationalists in India for example).
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 think in some situations if users see value in the opt-in then it can be ok. E.g. your phone asking you if you're happy to share your location with an app. I sure as hell want my mapping app to know where I am, but I also feel very comforted that I still get a say in the process. The thing about this tracking opt-in is that no user would ever want it because it's solely there to exploit them. So in this case I think you're 100% right.
Wouldn't the value in this situation be "you get to use Facebook"? If they didn't make money off their users, Facebook wouldn't exist.
Would you be ok if they did it that way? A warning that says "by using Facebook, you are agreeing to be tracked", at which point the user could either continue or uninstall the app?
This is a bullshit tradeoff. Facebook still knows a ton about you by your friends and activity on Facebook, and they can still show you a ton of ads on Facebook that are highly targeted to your demographic profile, and make a shit ton of money doing it. They could also make a ton of money showing you ads on a partner app if, for example, you logged in with FB to another app.
The only thing Apple is preventing them from doing is making an even larger shit ton of money by essentially knowing every app you ever use for anything that includes the Facebook SDK.
Note the same thing is true of Google. Google can (and did, and does) make shit tons of money by showing you targeted, relevant ads just based on your search keywords, or alternatively on a partner site by showing you ads just based on that site's content. But no, they need to make even more gargantuan shit tons of money by tracking your every move in Chrome and Android.
I think the new changes will hurt facebook competitors more. Everyone knows Facebook and it has a brand. They want to collect some info? Most people won't care - they just want to use the app like they always have. They might think twice with a new app that they don't know
I hope it might have the effect that those newer apps instead choose to innovate with their business models and pursue directions that don't require the user to sacrifice their privacy.
The change Apple is making keeps Facebook (and others) from using the advertising ID to track users between apps. Facebook's ability to notice that you have suddenly started posting a lot of baby pictures and choose to serve baby-related ads is unaffected.
Aren't they free to make their app not work at all without this setting? If so, then they must still find enough in letting you use facebook without it, even if less than they would like.
If you add an opt-in step to anything people don't want, it will kill that thing. If people were opting into getting an actual cookie rather than a tracker for advertisers to understand and target their behavior, you'd have 100% uptake.
That people won't opt into something that they didn't ask for and isn't primarily for their benefit is unsurprising.
I think it’s a stretch to call Apple’s solution opt-in. It is answering to a Yes/No question where your reply to allow tracking is no more obnoxious than to prevent it.
It will certainly kill anything users wouldn't normally want. If my business model depends on stuffing a shit sandwich into my user's pocket without them knowing, and then something changes so I now have to ask them "Would you like a shit sandwich?" my business model will be in big trouble.
I think that was the parent commenter's point. That is, "opt-in never works" is only true if the thing you want the user to opt in to is something someone would never want in the first place.
And I don't even think it has to be the primary feature. As someone else mentioned about maps, map apps are still plenty useful without location tracking (indeed, analog maps worked well for millennia without it), but I know if I opt in to location tracking while using a map app that I'm going to get a lot of additional useful features, so I do it.
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.
I guess that it's more likely that someone implement an algorithm in an innovative way for its program than it is for one to publish a paper. But yeah maybe there's no blog anterior to the paper which would be surprising but possible.
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!)
Thanks, I see what you two mean. It didn't occur to me that programming with tensors can be so challenging and I thought the authors just big it up a little to motivate the work - as one does :)
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:
And that single example with the suggestive naming should be enough for most people to understand what a shift matrix is for arbitrary size.
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 wonder whether the same effect could be achieved with a better designed programming language, though. If the problem is ambiguity- there's nothing stopping a programming language from accepting ambiguous statements, which of course it would then interpret unambigously, according to context. It's just that this takes a lot of work and it's really not the done thing in terms of programming languages as far as I can tell- for reasons of eficiency of parsing also, I think.
Anyway I guess I'm turnning into the typical stuffy academic who can't even begin to think of real-world applications, hah. Thanks for pointing out the practical uses of the work described in the article.
And the reason it's hard is because of how heavily tensorflow discourages flow control and reusable general purpose constructs for efficiency and differentiability reasons. Instead you have to use the list of blessed special purpose things.
