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

For algorithms, a little memory outweighs a lot of time

quantamagazine.org

Post reply on HN
Print view View original

81–90 of 144 posts

Re: For algorithms, a little memory outweighs a lot of time

#81

Post by ChrisMarshallNY »

Interesting. 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 wrote it in a few hours, and got pretty good performance, right out of the starting gate.

Pretty basic stuff. I doubt the pattern is unique, but it’s one that I’ve used for ages. It’s where I try to do as much “upfront” work as possible, and store “half-baked” results into memory.

Like I said, I always “just worked that way,” and never really thought about it. There’s been a lot of “rule of thumb” stuff in my work. Didn’t have an MIT professor to teach it, but it’s sort of gratifying to see that it wasn’t just “old wives” stuff.

There’s probably a ton of stuff that we do, every day, that we don’t think about. Some of it almost certainly originated from really smart folks like him, finding the best way (like the “winding number” algorithm, in that server[1]), and some of it also probably comes from “grug-brained programmers,” simply doing what makes sense.

[0] https://news.ycombinator.com/item?id=44046227

[1] https://github.com/LittleGreenViper/LGV_TZ_Lookup/blob/e247f...

Re: For algorithms, a little memory outweighs a lot of time

#83

Post by bmacho »

Almondsetat wrote: post #12
LPisGood wrote: post #9

Earlier quoted context omitted.

I’m not sure what you mean here. If you’re in the realm of “more space” than you’re not thinking of the time it takes. More precisely, I think it is intuitive that the class of problems that can be solved in any time given O(n) space is far larger than the class of problems that can be solved in any space given O(n) time.

If your program runs in O(n) time, it cannot use more than O(n) memory (upper bound on memory usage. If your program uses O(n) memory, it must run at least in O(n) time (lower bound on time).

In other words M <= T.

Re: For algorithms, a little memory outweighs a lot of time

#86

Post by IvanK_net »

cperciva wrote: post #26
IvanK_net wrote: post #24

I am confused. If a single-tape turing machine receives a digit N in binary, and is supposed to write N ones on the tape, on the right side of the digit N, it performs N steps. If you expect N ones at the output, how can this machine be simulated in the space smaller than N? This machine must decrement the digit N at the beginning of the tape, and move to the end of the tape to write "1", so it runs in time O(N^2), n…

Multitape Turing machines are far more powerful (in terms of how fast they can run, not computability) than single-tape machines. But to answer your question: "space" here refers to working space, excluding the input and output.

A single tape machine is still a multi tape machine, only with one tape.

Re: For algorithms, a little memory outweighs a lot of time

#87

Post by IvanK_net »

iNic wrote: post #74
IvanK_net wrote: post #24

I am confused. If a single-tape turing machine receives a digit N in binary, and is supposed to write N ones on the tape, on the right side of the digit N, it performs N steps. If you expect N ones at the output, how can this machine be simulated in the space smaller than N? This machine must decrement the digit N at the beginning of the tape, and move to the end of the tape to write "1", so it runs in time O(N^2), n…

This paper looks exclusively at decision problems, i.e. problems where the output is a single bit. EDIT: This makes sense because if you look at all problems with N outputs then that is just the same as "gluing together" N different decision problems (+ some epsilon of overhead)

Oh okay, that was my second guess.

Re: For algorithms, a little memory outweighs a lot of time

#88

Post by JohnKemeny »

amelius wrote: post #85

> Williams’ proof established a mathematical procedure for transforming any algorithm — no matter what it does — into a form that uses much less space. Ok, but space is cheap, and we usually want to trade processing time for space. I.e., the opposite.

Ryan made a dent (a tiny dent) in one of the most important open problems in mathematics.

He's not trying to please programmers.

Re: For algorithms, a little memory outweighs a lot of time

#89

Post by jodrellblank »

deadfoxygrandpa wrote: post #65
jodrellblank wrote: post #47

Earlier quoted context omitted.

Reminds me of when I imagined brute-forcing every possible small picture as simply 256 shades of gray for each pixel x (640 x 480 = 307200 pixels) = 78 million possible pictures. Actually I don't have any intuition for why that's wrong, except that if we catenate the rows into one long row then the picture can be considered as a number 307200 digits long in base 256, and then I see that it could represent 256^307200…

i think at some point you should have realized that there are obviously more than 78 million possible greyscale 640x480 pictures. theres a lot of intuitive examples but just think of this: https://images.lsnglobal.com/ZFSJiK61WTql9okXV1N5XyGtCEc=/fi... if there were only 78 million possible pictures, how could that portrait be so recongizably one specific person? wouldnt that mean that your entire picture space would…

"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 isn't 10x3.

> "if there were only 78 million possible pictures, how could that portrait be so recongizably one specific person? wouldnt that mean that your entire picture space wouldnt even be able to fit a single portrait of everyone in Germany?"

It's not intuitive that "a 640x480 computer picture must be able to fit a single portrait of everyone in Germany"; A human couldn't check it, a human couldn't remember 78 million distinct pictures, look through them, and see that they all look sufficiently distinct and at no point is it representing 50k people with one picture; human attention and memory isn't enough for that.

Re: For algorithms, a little memory outweighs a lot of time

#90

Post by Dban1 »

immibis wrote: post #75
xlii wrote: post #68

From the „Camel Book”, one of my favorite programming books (not because it was enlightening, but because it was entertaining); on the Perl philosophy: “If you’re running out of memory, you can buy more. But if you’re running out of time, you’re screwed.”

This can work both ways. If the program needs more memory than the computer has, it can't run until you buy more. But if it takes twice as long, at least it runs at all.

brain brain brain
Post reply on HN