The poetic style of Quanta makes it impossible to understand what does this mean. Can someone familiar with the topic explain is this applicable to real world computers or just a theoretical scenario? Does this mean we need more memory in computers even if they need to run at a lower clock speed?
For algorithms, a little memory outweighs a lot of time
121–130 of 144 posts
Re: For algorithms, a little memory outweighs a lot of time
#122Earlier quoted context omitted.
Be generous - it saves a lot of time. Once you say "polynomial" readers will think, "like, ANY polynomial, even like n^100?!" and you'll have to explain, yes, but that's STILL better than exponential, etc. They avoided all of that
Quanta targets people who are above average. So I don't think it is too much for them to give a sentence or two stating that. Or even a little graphic could do wonders. I don't think it would take much time or effort to make a graphic like the one on wikipedia[0] and just throw in some equations within the ring. You can easily simplify too, by removing NL and merging EXP. Hell, look at the graphics here[1]. That's mu…
I suppose my point is that the readers who will wonder about this are a) very likely to know about complexity classes already, or b)capable of learning about it themselves. Perhaps a simple link to something like https://complexityzoo.net/Petting_Zoo would have been a nice middle-ground.
Edit: Aaronson even mentions the n^100 problem in the section about P!
Re: For algorithms, a little memory outweighs a lot of time
#123Earlier quoted context omitted.
Oh right, so the height is practically a constant. Square root for sure then.
All algorithms are O(1) in this case
You pick what things are constant and what's variable. If you're scaling a supercomputer to fit a problem, the height is going to max out quickly and can be treated as constant, while the other dimensions are variable.
Re: For algorithms, a little memory outweighs a lot of time
#124Interesting. It's one of those things that I’ve always “just assumed,” without thinking about it. I did a lot of raster graphics programming, in my career, and graphics work makes heavy use of lookup tables. Yesterday, I posted a rather simple tool I wrote[0]: a server that “frontloads” a set of polygons into a database, and then uses them, at query time. It’s fairly fast (but I’m sure it could be a lot faster). I wr…
I'm in the depths of optimization on a game right now, and it's interesting how the gains I'm making currently all seem to be a matter of scaling the concept of lookup tables, and using the right tool for the job. What I mean is that traditionally I think peoples' ideas of lookup tables are things like statically baked arrays setup at compile time, or even first thing at runtime, and they never change. But if you loo…
To some extent it is required that all serious work by a computer be the kind of repititious thing that can be at least partially addressed by a lookup table.
If you take the example of a game, drawing sprites say. Drawing a single preloaded sprite of reasonable size is always cheap, so a slow frame must have an excessive number. It's very hard to construct a practical scenario of a large number of truly distinct sprites though. A level has a finite tile palette, a finite cast of characters, abilities, etc. It's hard to logistically get them all into a scene together, and even then it won't be that many. So the only scenario left where sprite drawing will be slow is drawing the same handful of sprites over and over again. By contrast that's super common: just spam a persistent projectile, tap the analog stick to generate dust particles, etc.
Re: For algorithms, a little memory outweighs a lot of time
#125Earlier quoted context omitted.
"At some point" I do realise it. What I don't have is an intuitive feel for why a number can be three digits 000 to 999 and each place has ten choices, but it's not 10 x 3 possibles. I tried to ask ChatGPT to give me an intuition for it, but all it does is go into an explanation of combinations. I know it's 10 x 10 x 10 meaning 10^3 I don't need that explanation again, what I'm looking for is an intuition for why it…
Try starting with a 2x2, then 3x3, etc. image and manually list all the possibilities.
That's focusing on the wrong thing; as I said, "I know it's 10 x 10 x 10 meaning 10^3 I don't need that explanation [for the correct combinations], what I'm looking for is an intuition for why it isn't 10x3".
Re: For algorithms, a little memory outweighs a lot of time
#126Earlier quoted context omitted.
Can use cryptographic hashing.
How does that get around the pigeonhole principle? I think you'd have to compare the data value before purging, and you can only do the deduplication (purge) if the block is actually the same, otherwise you have to keep the block (you can't replace it with the hash because the hash link in the pool points to different data)
The hash collision chance is extremely low.
Re: For algorithms, a little memory outweighs a lot of time
#127Earlier quoted context omitted.
How does that get around the pigeonhole principle? I think you'd have to compare the data value before purging, and you can only do the deduplication (purge) if the block is actually the same, otherwise you have to keep the block (you can't replace it with the hash because the hash link in the pool points to different data)
The hash collision chance is extremely low.
For small amounts of data yeah. With growing data, the chance of a collision grows more than proportional. So in the context of working on storage systems (like s3 or so) that won't work unless customers actually accept the risk of a collission as okay. So for example, when storing media data (movies, photos), I could imagine that, but not for data in general.
Re: For algorithms, a little memory outweighs a lot of time
#128Earlier quoted context omitted.
Quanta targets people who are above average. So I don't think it is too much for them to give a sentence or two stating that. Or even a little graphic could do wonders. I don't think it would take much time or effort to make a graphic like the one on wikipedia[0] and just throw in some equations within the ring. You can easily simplify too, by removing NL and merging EXP. Hell, look at the graphics here[1]. That's mu…
I suppose my point is that the readers who will wonder about this are a) very likely to know about complexity classes already, or b)capable of learning about it themselves. Perhaps a simple link to something like https://complexityzoo.net/Petting_Zoo would have been a nice middle-ground. Edit: Aaronson even mentions the n^100 problem in the section about P!
I disagree and even think that this is besides the point. It is hard to wonder about what you don't know to wonder about. It is the job of the communicator to prime that and provide any critical information that the reader is not expected to know about. Without some basic explanation here then these terms might as well be black boxes to readers.
The point is that a single line[0] and a minimal graphic could substantially improve the reader's comprehension while simultaneously providing them the necessary nomenclature to find relevant material to further increase their understanding.
Look at this line:
| One of the most important classes goes by the humble name “P.”
| Roughly speaking, it encompasses all problems that can be solved in a reasonable amount of time. An analogous complexity class for space is dubbed “PSPACE.”
The whole work is about bridging these two concepts! How can we understand that if we don't know what we're building a bridge between? It's like reporting on a bridge being built connecting England and France but just calling it a bridge. Is it important? Sounds like it by the way they talk, but how can you even know the impact of such a thing when not given such critical context? You get tremendous amounts of additional context with the addition of so few words.
Re: For algorithms, a little memory outweighs a lot of time
#129Earlier quoted context omitted.
The hash collision chance is extremely low.
For small amounts of data yeah. With growing data, the chance of a collision grows more than proportional. So in the context of working on storage systems (like s3 or so) that won't work unless customers actually accept the risk of a collission as okay. So for example, when storing media data (movies, photos), I could imagine that, but not for data in general.
Cryptographic hashing collisions are very very small, like end of universe in numerous times small. They're smaller than AWS being burnt down and all backups were lost leading to data loss.
Re: For algorithms, a little memory outweighs a lot of time
#130Earlier quoted context omitted.
For small amounts of data yeah. With growing data, the chance of a collision grows more than proportional. So in the context of working on storage systems (like s3 or so) that won't work unless customers actually accept the risk of a collission as okay. So for example, when storing media data (movies, photos), I could imagine that, but not for data in general.
Cryptographic hashing collisions are very very small, like end of universe in numerous times small. They're smaller than AWS being burnt down and all backups were lost leading to data loss.
You have a point.
When using MD5 (128bit) then when AWS S3 would apply this technique, it would only get a handful of collisions. Using 256bit would drive that down to a level where any collision is very unlikely.
This would be worth it if a 4kb block is, on average, duplicated with a chance of at least 6.25%. (not considering overhead of data-structures etc.)