10 ms·
Unusual to have no occurrence of the word "stream" anywhere in the article... given that's the usual term for algorithms which require a constant or almost-cons
by userbinator 7y ago
Unusual to have no occurrence of the word "stream" anywhere in the article... given that's the usual term for algorithms which require a constant or almost-constant space regardless of the amount of data they process.
A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space.
- itamarst 7y agoChunking is the term I used because that's more relevant to the data science domain I'm focusing on here (e.g. Pandas has "chunksize", Zarr has "chunks"). Streaming has some implication of an ongoing stream of data to me... but I ought to clarify some of the assumptions about a fixed size of data, yes.
- denhaus 7y agoDitto. Python multiprocessing also uses “chunks” with a specified chunksize.
- roter 7y agonetCDF, used for storing e.g. large multidimensional climate datasets, is also "chunked" through its HDF[0] backbone. The hard part for me is the "transpose" or "striding" problem. i.e. when the data is stored in a series of (x, y, z) files for a given hour, day, or month and I need a time series at a point. [0] https://en.wikipedia.org/wiki/Hierarchical_Data_Format https://en.wikipedia.org/wiki/Hierarchical_Data_Format
- dmurray 7y agoChunking and streaming are different things to me. Chunking means you get to process multiple rows of data at the same time, usually useful to take advantage of SIMD. Streaming means that the data is accessed in a single pass: once you compute the effect of a given row on your statistics, you never have to rewind to see it again. Many modern performant solutions will use both, but they're not the same thing.
- nine_k 7y agoOne important application of chunking is efficient I/O. Mass storage is most efficient when doing large sequential reads and writes, so you normally feed your constant-space streaming algorithms from buffers with a large number of input records. Sometimes you can just tell the OS do efficient chunking prefetch for you.
- pythonwutang 7y ago> Chunking is the term I used because that's more relevant to the data science If your intended audience are data scientists then why didn’t you mention Dask?
- mytailorisrich 7y ago> A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. In term of RAM this can be done an arbitrarily small buffer in the sense that this can be done by reading the file byte by byte. I.e. O(1). Edit: For all practical purposes the line counter is also constant space.
- rongenre 7y agoYeah log(n) would be the space to hold the digits of the counter. Presumably (unless things got super-silly), this would be dominated by the buffer size for the line being read.
- dfox 7y agoThe point there is that you don’t need a buffer for whole line, you only have to find the line terminators. Something like: printf(“0: “); ln = 1; while ((ch = getch()) != EOF) { putch(ch); if (ch == EOL) { printf(“%d: “, ln); ln++; } } And I believe that original unix implementation of nl is mostly this, although with the stdio functions replaced with raw read/write.
- johnc1231 7y agoYeah, I think the above poster said O(logn) space because that's the size of the line count in bits
- jeremysalwen 7y agoThe usual computation model includes "log n sized words", so it really is O (1). You usually are implicitly using that model, otherwise any algorithm that used pointers would have an extra log n tacked on, e.g. linked lists append would be log n not constant.
- gwbas1c 7y ago> Unusual to have no occurrence of the word "stream" anywhere in the article... Or "database"
- nautilus12 7y agoBoth indicators (along with python) that this is an article written by a yet another data scientist that thinks engineering is unecessary. Data science is a field that is plagued by individuals having very specific narrow experiences that are often easy to engineer making them think they are experts in data engineering. Vertical scalability has a hard bound, if your algorithm changes complexity it could become literally impossible to move forward. Horizontal scalability gives you options, this is why we like it, not just because we like to overengineer systems, but because we don't like embracing hard limitations on the systems we engineer, especially when we often don't know yet what problem we are solving. Engineers often don't get the liberty of solving extremely specific instances of problems like data scientists do.
- realusername 7y ago> Data science is a field that is plagued by individuals having very specific narrow experiences that are often easy to engineer making them think they are experts in data engineering. That's on point, some of the worst and most inefficient code I had to maintain was written by data scientists. They are for sure leagues above any of my data science knowledge in their respective field but the average engineering knowledge and best practices seems pretty low.
- deleted 7y ago[deleted]
- kyllo 7y agoMost of the time it's not that data scientists think engineering is "unnecessary," it's that they're expected to deliver analyses and models without the help of engineers, because the engineers are on another team, behind a massive backlog. So they make do with the tools they have.
- rhinoceraptor 7y ago> write a program that numbers the lines in a text file Ah, simple :) cat file | wc -l
- dyanaraps 7y agoUseless use of `cat`. :) wc -l file To hide filename: wc -l < file
- scarejunba 7y agoI'm actually pretty much against UUoC. The cat example is much more resilient to modification. For instance, there are usually natural modifications considering filtering etc. Anyway, since he said number we probably want `nl` not `wc`. Separating pipe-setup from processing is sound engineering to me and makes things much easier. For instance as I iterate, I will have cat piped to head piped to filter but eventually I'll take the head out and run the whole thing. That's a trivial ^W versus moving around arguments and worrying about arg order, etc.
- navaati 7y agoThat's right regarding directly giving the filename for the program (here wc) to open itself. However using the input redirect is fine, especially if you format it that way (which is exactly the same thing): <file wc -l Then, adding another step is as natural as with cat: <file grep meh |wc -l
- thestoicattack 7y agoUseless use of `wc` :) <file grep -c meh
- deleted 7y ago[deleted]
- herpderperator 7y ago
- diabeetusman 7y agoSorry, isn't there quite a bit of a difference between O(1) and O(log N) space? My first inclination would be to have a counter at zero, read in a line, write out the counter then write out the line, then increment the counter. The space complexity here is O(1), is it not?
- yifanl 7y agoStoring the number n takes log n bits, if we're being super pedantic :)
- thfuran 7y agoIn practice, I'd say it takes exactly 64 bits for any file.
- MiroF 7y agoAsymptotic notation isn't about what's "in practice." We have very good asymptotic complexity for multiplication, but don't use the ones that scale the closest to linear because the time constant is enormous.
- dfox 7y agoWith the O() notation the units are some arbitrary computation step or arbitrary unit of memory, which could even mean matrix multiplication of two 1024x1024 matrices of doubles. The whole point of big-O notation is that you don’t care about how fast/expensive it is, but how it scales.
- MiroF 7y agoYes and the memory to store a number scales with the log of the number
- darkmighty 7y agoThere are different models of computation. You can have a model in which integers can be arbitrarily large yet still count as constant memory (for analyzing practical-size algorithms on 64-bit machines, for example); I'm not sure how common those are. I know for example arithmetic is often assumed to be constant time (it indeed varies by input size, even x=y+1, which is clearly O(log(y))). Also relevant here is the RAM machine model that is often employed, where you can have essentially unlimited memory that can be randomly accessed at fixed time. This again is roughly in line with real practical machines running algorithms that use, and fit within RAM. In reality if you wanted a more physically consistent model eventually your access times must differentiate and increase for increasing memory -- data occupies physical space and must be fetched at increasingly long distances, limited by the speed of light. In principle this means m bits of memory at best can be accessed in O(m^(1/3)) time [1]. Of course, this realism isn't always practically relevant (maybe for datacenter-scale problems, perhaps even larger) and complicates the analysis of algorithms. [1]: Just for fun, if you want to get really physically accurate, this isn't quite right either I suspect -- that's because with enough data (physical bits) occupying a volume at constant density it will eventually collapse into a black hole, which kinda destroys your computer :). So for planetary-scale computers you eventually need to spread your data across a disk, like a small galaxy (or Discworld, if you prefer :)), so it won't collapse, giving it O(sqrt(m)) access time. Surprise, very large worlds must be flat. This is related to the BH entropy formula, and the so called Holographic principle, I guess -- the entropy and hence information content of a volume is surprisingly bounded by its area, since a Black Hole's area is proportional to its mass. The weird thing of course is how the universe itself perhaps should collapse to a black hole since it has a lot of stuff in any sufficiently large volume, being young and dynamic it hasn't happened yet. It's alsogiven by its fractal scale, but I guess this digression has grown large enough already :) (do tell if you want to learn more)
- tehsauce 7y agoO(log n) is not constant
- mark-r 7y agoI think the point in this case is that log n has a reasonable upper bound, and can be considered constant for any real world problem.
- WanderPanda 7y agoO(log n) is so precise it ain't even informative :P
- bogomipz 7y ago>The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space" Can you elaborate on the O(1) solution?
- xondono 7y agoNot an expert, but after reading around OP is saying you only need a constant sized buffer (that could be as little as a character deep) to read the whole file looking for line breaks. This roughly takes O(1) space (A lot of commenters are confusing time vs space requirements) but there's a little nitpick to be found, in extremely big files the line counter itself would be O(log(n)) and would dominate.
- bogomipz 7y agoI see, yes that makes sense. The conflation with time instead of space was confusing me. Thanks.
- tmh88j 7y ago>A semi-common beginning programmer's exercise is to write a program that numbers the lines in a text file. The naive solution will use O(n) space, while a bit more thought reveals that this can be done in constant (to be really precise, O(log n) where n is the number of lines in the file) space. I guess I'm misinterpreting the task, because I'm having trouble seeing how it's possible to access each line in a file without it being O(n) at a minimum. I understand O(log n) to mean that not every data point is "accessed" due to the way the data structure is organized, lines of a file in this case, but to me it appears that not every line would be prepended with a number. My instinct is that there's a lot going on with new lines/line breaks in files that I'm not aware of, so I'd really appreciate any reading material on the subject to help me better understand this. Thanks!
- unlivingthing 7y agoI think you've got confused with O(n) time; that is the amount of memory that is needed and not the time required to access a particular line.
- tmh88j 7y agoGood point, I was thinking in terms of time complexity rather than space, but the title clearly is in reference to memory. I guess that explains my confusion!
- profmonocle 7y agoI made the same mistake at first, had to reread the post. I'm so used to seeing Big O notation used for time that I guess my eyes just passed over the word "space". (My mistake obviously, the OP was very clear.)
- 3xblah 7y agosed = 1.txt Use small buffer. No need to fit all the data into memory.
- kashif 7y agoI was also surprised by the lack of streaming. In Python specifically for really large JSON datasets I wrote this streamer that many have found useful - https://github.com/kashifrazzaqui/json-streamer https://github.com/kashifrazzaqui/json-streamer
- deleted 7y ago[deleted]