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

The One Billion Row Challenge

morling.dev

Post reply on HN
Print view View original

301–310 of 366 posts

Re: The One Billion Row Challenge

#301

Post by toth »

londons_explore wrote: post #292
toth wrote: post #278

Earlier quoted context omitted.

I deleted two previous comments because I realized I misunderstood your proposal. I understand it better now, but I am still confused about something... Your state machine would need at least 2*160,000 states (you need an extra bit to flag whether you have reached a newline in the last word and need to increment a counter or not), correct? And you are assuming the input is 4 bytes, so won't your transition table need…

The states don't need to map 1:1 with cities or temperatures. They merely need to encode all information collected so far which is still relevant. They also don't need to represent all possible situations - anything that is super rare (eg. temperature of 95C) can simply be diverted to a special "invalid" state which triggers regular code to take over for those few entries.

Hmm, still doesn't seem feasible. Even if you only have 256 "relevant" states (which I think you'll agree is far less than what you need) then given a 32-bit input your state transition table is 2^32*256 = 1 Terabyte.

You could shrink your input size to 2 bytes but then you can't work on a word at a time, and for a realistic number of relevant states your transition table is still way bigger than you can fit in even L3 cache.

Unless I am missing something very basic, this doesn't seem like a viable approach.

Re: The One Billion Row Challenge

#302

Post by feoren »

CamperBob2 wrote: post #273
refulgentis wrote: post #251

Earlier quoted context omitted.

I don't have a CS background and when I eventually had to do interviews for Google, "Calculate mean/median/mode of temperatures" was the interview question I went with, intending to avoid BS leetcode* I always worried it was too easy, but I'm heartened by how many comments miss the insight I always looked for and you named: you don't need to store a single thing. I do wonder if it'll work here, at least as simply as…

Streaming calculation of the exact median with no storage at all is non-trivial at best in the general case, and I'm not aware of any way to calculate the mode at all. Any pointers to the methods you used in your interview answers? If you came up with them on the fly, then... well, sign here for your bonus. Can you start Monday?

> Streaming calculation of the exact median with no storage at all is non-trivial at best in the general case

It's not "non-trivial" it's impossible. I'm not sure why people think median can be approximated at all. You need to look at every data point and store a counter for the lesser of: (a) all possible values, or (b) all elements. Just consider a data set with 1 million ones and 999,999 zeroes. Throwing away (or failing to look at) one single number can give you an error of 50%, or 100% for two numbers. If you want to make it really nasty, throw in another million random 64-bit floats between [-0.1, 0) and a million between (1, 1.1]. Four million elements, two million of them unique, in the range [-0.1, 1.1], and failing to account for two elements can get your answer wrong by +/- 1.0.

Unless you start by sorting the list, but I wouldn't call that a "streaming" calculation.

Re: The One Billion Row Challenge

#303

Post by pclmulqdq »

charcircuit wrote: post #37
pclmulqdq wrote: post #27

Earlier quoted context omitted.

You wouldn't want to do this for a huge file. A very fast solution would use a small number of buffers and io_uring (or equivalent), keeping the page table and cache footprint small.

What is the downside of memory mapping in this scenario? Shouldn't the page table properly handle the case of doing a single sequential read over a range of pages? Accessing the contents of a file doesn't seem like something caching would matter for. Do you mean that reading of sequential pages will keep adding to the cache compared to reading from a single page? That seems like a similar thing as before where they w…

Caching and paging almost always matter, even on things like this. The core problem is that the filesystem won't prefetch for you, and you will be waiting to page fault several times over the length of the file. Another problem of the size of the working set is that you will be seeing several slow calls to (essentially) malloc in the kernel to hold all of that data, while using a small, preallocated structure will give you none of that trouble.

Re: The One Billion Row Challenge

#304

Post by CamperBob2 »

feoren wrote: post #302
CamperBob2 wrote: post #273

Earlier quoted context omitted.

Streaming calculation of the exact median with no storage at all is non-trivial at best in the general case, and I'm not aware of any way to calculate the mode at all. Any pointers to the methods you used in your interview answers? If you came up with them on the fly, then... well, sign here for your bonus. Can you start Monday?

> Streaming calculation of the exact median with no storage at all is non-trivial at best in the general case It's not "non-trivial" it's impossible . I'm not sure why people think median can be approximated at all. You need to look at every data point and store a counter for the lesser of: (a) all possible values, or (b) all elements. Just consider a data set with 1 million ones and 999,999 zeroes. Throwing away (or…

Yeah, that's why I hedged so heavily; AFAIK it's impossible to compute a streaming median (having spent some time trying).

If someone on HN knows how to do it, they will jump in and tell me exactly why it's "trivial," and I'll get some nice R&D work for free. Of course, it will probably involve mounting an FTP account, spinning up a CA and running rsync...

Re: The One Billion Row Challenge

#305

Post by hknmtt »

hknmtt wrote: post #214
sudodudeo wrote: post #169

Earlier quoted context omitted.

Wouldn't this end up reducing the weight of earlier records by repeatedly dividing them into smaller chunks? I.e. avg of {22.5, 23, 24} = 23.17... But: 1. 22.5 2. (22.5 + 23)/2 = 22.75 3. (22.75 + 24)/2 = 23.375

say you load 1 million records and you average them at 5.1. you then load another million and average them at 4.5. so you 5.1+4.5=9.6/2=4.8. rinse and repeat. as long as you keep the amount of records processed per each run about the same, your numbers will not be skewed. only the last chunk will most likely be smaller and it will introduce small rounding error, like if it has only 10k records instead of 1M. but stil…

essentially that is how integrals are calculated in mathematics if i remember correctly. you take a curve and divide it into columns, the thinner the column the smaller the deviation(because the curve has round edges so your bar will have inherent error) and you simply calculate each column and then total it and you get the body/volume of the function. same principle like radians with circle. you are merely splitting the work into smaller pieces that you can process.

Re: The One Billion Row Challenge

#306

Post by bmicraft »

vintermann wrote: post #176
londons_explore wrote: post #171

Earlier quoted context omitted.

All the data is only to one decimal place. You can shift the decimal place and do the whole thing with int's and get a 100% precise result.

You can, but will it be the same result? :) binary floating point can't represent 0.1 or 0.2 exactly. To be fair, with only additions, and only a billion of them, you're probably fine working in floating point and rounding to one decimal in the end.

Just x10 it and count in integers?

Re: The One Billion Row Challenge

#307

Post by winrid »

brrrrrm wrote: post #240
winrid wrote: post #97

Earlier quoted context omitted.

It looks like they mostly work in JS, so maybe it's the type definitions that look clunky. Java is explicit, yes. This is intentional :)

yea, I guess it's the lack of human-friendly default assumptions mixed with prescriptive design patterns. definitely an anachronistic design intent :(

have you worked with any compiled languages? It's not much different. It can get a lot worse ^_^. Java's one of the best languages to work in IMO.

Re: The One Billion Row Challenge

#308

Post by winrid »

brrrrrm wrote: post #299
promiseofbeans wrote: post #295

Earlier quoted context omitted.

Funny thing is, most js devs do typescript now, which is the same as java, of not worse because you need an extra colon for your static types

Weird to think typescript is similar to a language that requires a class definition for “hello world” lol. You can’t even fit it on a single 80 character line…

Putting everything in a class has some really nice benefits.

For example, for performance monitoring/debugging, it's really nice to see memory usage and thread creation by package/class. Whereas, I've seen teams spend weeks trying to find memory leaks in NodeJS applications, because you just get "here's general usage by object-shape". Would literally take me less than a minute with Java...

Re: The One Billion Row Challenge

#309

Post by vintermann »

bmicraft wrote: post #306
vintermann wrote: post #176

Earlier quoted context omitted.

You can, but will it be the same result? :) binary floating point can't represent 0.1 or 0.2 exactly. To be fair, with only additions, and only a billion of them, you're probably fine working in floating point and rounding to one decimal in the end.

Just x10 it and count in integers?

I said that works here. The point is that floating point may give a different answer.

Re: The One Billion Row Challenge

#310

Post by troupo »

kaba0 wrote: post #291
krzyk wrote: post #266

Earlier quoted context omitted.

They are trying to make gradle better, by implementing a "maven over it" - declarative build configuration. But for time being maven is way easier to configure and understand.

It has always been “an imperative code that outputs the declarative configuration that can be used for the build”. Which is a very reasonable thing to do, but unfortunately most people fail to understand that a println in the config file’s global scope is different than inside a closure for a task description.

> but unfortunately most people fail to understand that a println in the config file’s global scope is different than inside a closure for a task description.

Literally no one complaining about gradle being slow is doing that. Allmost all of gradle's problems come not from people using it, but from Gradle itself.

I mean, you said it yourself: in 15 years the state of their API docs is "okayish". But somehow people are still expected to make sense of this shit because apparently it's a plane? But planes famously have extensive documentation, and procedures, and decades of expertise available. Exactly unlike gradle.

Post reply on HN