Logs: freenode/#haskell
| 2020-11-19 17:42:44 | <merijn> | I say death to Big O analysis :p |
| 2020-11-19 17:43:11 | <merijn> | It's just a mathematical way of lying about performance :p |
| 2020-11-19 17:43:31 | hackage | cryptol 2.10.0 - Cryptol: The Language of Cryptography https://hackage.haskell.org/package/cryptol-2.10.0 (AaronTomb) |
| 2020-11-19 17:43:41 | <c_wraith> | People are very bad at it, and believe lies like "hash table insert and lookup are O(1)" with shocking credulity |
| 2020-11-19 17:44:09 | <merijn> | c_wraith: A reasonable number people know about *that* |
| 2020-11-19 17:44:24 | × | codeAlways quits (uid272474@gateway/web/irccloud.com/x-rnqcrwigssxuyxdw) (Quit: Connection closed for inactivity) |
| 2020-11-19 17:44:30 | × | raehik quits (~raehik@cpc95906-rdng25-2-0-cust156.15-3.cable.virginm.net) (Quit: WeeChat 2.8) |
| 2020-11-19 17:44:53 | → | avn joins (~avn@78-56-108-78.static.zebra.lt) |
| 2020-11-19 17:44:53 | → | raehik joins (~raehik@cpc95906-rdng25-2-0-cust156.15-3.cable.virginm.net) |
| 2020-11-19 17:45:15 | <merijn> | The people that realise "the fundamental base of assumption of Big O is just 100% lies" is dramatically less :p |
| 2020-11-19 17:46:39 | <boxscape> | which assumption is that? |
| 2020-11-19 17:46:51 | <maerwald> | it's one of those things that make you look smart in interviews |
| 2020-11-19 17:46:54 | <dminuoso> | boxscape: Stuff like constant random memory access. |
| 2020-11-19 17:46:59 | <merijn> | It only seems to work because people in general mostly only care about the happy path |
| 2020-11-19 17:47:04 | → | kav joins (~kari@dsl-hkibng42-56733f-225.dhcp.inet.fi) |
| 2020-11-19 17:47:14 | <koz_> | maerwald: Alternatively, if you inhabit certain academic spaces. |
| 2020-11-19 17:47:17 | <koz_> | (which was my fate) |
| 2020-11-19 17:47:22 | <dminuoso> | If that's your model of computation, fine, but the truth of the matter is memory access is not constant on a computer implemented within the laws of physics. |
| 2020-11-19 17:47:27 | <merijn> | boxscape: random memory access is constant time |
| 2020-11-19 17:47:40 | <c_wraith> | that's only an assumption if you make it one... |
| 2020-11-19 17:47:40 | <merijn> | maerwald: It has real world implications |
| 2020-11-19 17:47:44 | <boxscape> | is the problem there caching or something else? |
| 2020-11-19 17:47:48 | <merijn> | boxscape: Yeah |
| 2020-11-19 17:47:51 | <boxscape> | I see |
| 2020-11-19 17:47:57 | <koz_> | Yeah, the memory hierarchy is a thing. |
| 2020-11-19 17:47:58 | <dminuoso> | boxscape: blackhole thermodynamics and relativity, roughly |
| 2020-11-19 17:48:01 | <koz_> | For good reason. |
| 2020-11-19 17:48:12 | <merijn> | You can construct algorithms that are "worse" per big O complexity while being *much* faster in reality |
| 2020-11-19 17:48:36 | <koz_> | merijn: And that's before we get to abuses of the form 'simplex is exponential'. |
| 2020-11-19 17:48:55 | <merijn> | c_wraith: eh, that assumption is baked into classical big O analysis as taught in CS and parroted when talking data structure complexity |
| 2020-11-19 17:49:10 | → | wroathe joins (~wroathe@c-68-54-25-135.hsd1.mn.comcast.net) |
| 2020-11-19 17:49:24 | <c_wraith> | merijn: hmm. not in my courses/textbooks. They explicitly called out that they were working in the RAM model |
| 2020-11-19 17:49:24 | <dminuoso> | c_wraith: Well, the question is what conclusions you can draw from complexity analysis if the model doesn't fit reality well |
| 2020-11-19 17:50:22 | × | kav quits (~kari@dsl-hkibng42-56733f-225.dhcp.inet.fi) (Read error: Connection timed out) |
| 2020-11-19 17:50:25 | <merijn> | c_wraith: Well, *CLRS* assumes that throughout the book and even calls it out as a wildly unrealistic assumption in the first 1 or 2 chapters |
| 2020-11-19 17:50:35 | <merijn> | Anyway, dinner time |
| 2020-11-19 17:50:54 | <koz_> | merijn: Yeah, you get this a lot. 'This isn't realistic, but we're just goin' with it.' came up a bunch when I was learning a lot of algorithms-related things. |
| 2020-11-19 17:51:00 | <merijn> | c_wraith: What does "RAM model" mean? Did they include caches or not? |
| 2020-11-19 17:51:16 | <merijn> | (Actually, don't bother answering, 'cause dinner time :p) |
| 2020-11-19 17:51:25 | <koz_> | merijn: I assume Random Access Model. AKA 'all memory is flat, if you have an address, you have that memory in Theta(1)'. |
| 2020-11-19 17:51:26 | <c_wraith> | merijn: it's the standard name for the model in which all memory accesses have the same cost |
| 2020-11-19 17:52:05 | → | codeAlways joins (uid272474@gateway/web/irccloud.com/x-zbflumxjrtygmhzc) |
| 2020-11-19 17:52:08 | → | kav joins (~kari@dsl-hkibng42-56733f-225.dhcp.inet.fi) |
| 2020-11-19 17:52:20 | × | toxix quits (~DTZUZU@207.81.171.116) (Ping timeout: 256 seconds) |
| 2020-11-19 17:52:23 | <koz_> | I think monochrom (maybe?) mentioned that many presentations of Dijkstra's algorithm straight-up lie about their actual performance because they assume magical thinking in priority changes. |
| 2020-11-19 17:54:44 | <monochrom> | Rather, an important implementation question of decrease-priority is grossed over. |
| 2020-11-19 17:55:02 | <koz_> | I _love_ the expression 'to gross over'. |
| 2020-11-19 17:55:25 | → | wroathe_ joins (~wroathe@c-73-24-27-54.hsd1.mn.comcast.net) |
| 2020-11-19 17:56:02 | × | wroathe quits (~wroathe@c-68-54-25-135.hsd1.mn.comcast.net) (Ping timeout: 260 seconds) |
| 2020-11-19 17:56:04 | × | boxscape quits (54a35f37@gateway/web/cgi-irc/kiwiirc.com/ip.84.163.95.55) (Ping timeout: 272 seconds) |
| 2020-11-19 17:56:36 | <monochrom> | In practice, I think people just gave up. |
| 2020-11-19 17:56:48 | <koz_> | In general, the folks that taught me algorithm-related stuff in CS had an attitude to implementation that was roughly 'ehh, it can be done somehow, who cares, now do more analysis'. |
| 2020-11-19 17:57:05 | → | acowley joins (~acowley@c-68-83-22-43.hsd1.nj.comcast.net) |
| 2020-11-19 17:57:10 | <koz_> | (one was outright dismissive, the other just mentioned that these issues were resolvable but gave zero explanation how) |
| 2020-11-19 17:57:53 | <monochrom> | I have seen programming-contest-quality code libraries that don't use a log-time priority queue at all. Every extract-min and decrease-priority is linear brute-force search over an array. |
| 2020-11-19 17:57:58 | × | oerjan quits (~oerjan@195.206.169.184) (Remote host closed the connection) |
| 2020-11-19 17:58:03 | wroathe_ | is now known as wroathe |
| 2020-11-19 17:58:20 | <monochrom> | Dijkstra himself also said he did that for his first demo, it was fast enough for him. |
| 2020-11-19 17:58:53 | <koz_> | monochrom: So wait, their priority queue essentially amounts to Vector (Int, a) or so? |
| 2020-11-19 18:00:02 | <monochrom> | I gross over details too. But I make a judgment: If I think an average student can think up how to code it up, I can gross over it; if it would be new and clever to them, I have to spell it out. |
| 2020-11-19 18:00:10 | <monochrom> | Yeah! |
| 2020-11-19 18:01:00 | <koz_> | Somewhat ironically, this makes me feel better about a recent Real Haskell Job call I had to make. |
| 2020-11-19 18:01:03 | <geekosaur> | considering the kinds of things your average student comes up with, you must have to spell things out a lot |
| 2020-11-19 18:01:22 | <monochrom> | And this is U of bloody Waterloo world class for-ACM-ICPC has-been-world-champion code library they bring on paper to the contests. |
| 2020-11-19 18:01:48 | <monochrom> | Fortunately, it's in C, so it is still fast. >:) |
| 2020-11-19 18:02:58 | × | heatsink quits (~heatsink@107-136-5-69.lightspeed.sntcca.sbcglobal.net) (Remote host closed the connection) |
| 2020-11-19 18:02:59 | <monochrom> | Oh, to be sure, "average student" still depends on which school we're talking about. |
| 2020-11-19 18:03:36 | → | enoq joins (~textual@194-208-146-143.lampert.tv) |
| 2020-11-19 18:04:12 | <monochrom> | Suppose you pose the 1st-year-CS problem of "find the max of an array" for example. Actually, more honestly, a word problem that doesn't say outright "find max of array" but if you understand the wordy problem you see it's that. |
| 2020-11-19 18:04:42 | <monochrom> | In my school, the average students wouldn't have any difficulty. |
| 2020-11-19 18:04:56 | <monochrom> | In U of Waterloo, haha are you kidding, that's too easy. |
| 2020-11-19 18:06:18 | → | jneira joins (02896ac0@gateway/web/cgi-irc/kiwiirc.com/ip.2.137.106.192) |
| 2020-11-19 18:06:44 | <monochrom> | So, that kind of word problems is the usual kind of problems you see during the warm-up practice stage of an ACM-ICPC-style programming contest. The warm-up practice stage being the whole point being familiarizing yourself with the computing environment, so let's solve a trivial problem so you can focus on learning how to use vi and gcc, say. |
| 2020-11-19 18:06:48 | → | cosimone joins (~cosimone@2001:b07:ae5:db26:9217:95c7:973d:d0ad) |
| 2020-11-19 18:07:46 | <monochrom> | I overheard the conversation of a team from another school. <Coach> So, what do you think? <Contestant> No clue. |
| 2020-11-19 18:08:11 | <monochrom> | That's their contestant. So now imagine the average of that school. But compare to the average of Waterloo. |
| 2020-11-19 18:10:08 | <maerwald> | Man. Why not just get under the sun at the beach, instead of all this programming. |
| 2020-11-19 18:11:18 | → | foursaph joins (~foursaph@dynamic-077-000-101-034.77.0.pool.telefonica.de) |
| 2020-11-19 18:11:25 | ski | . o O ( "The Myth of RAM, part I" by Emil Ernerfeldt in 2014-04-21 at <https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html> ) |
| 2020-11-19 18:11:28 | <monochrom> | IKR? I saw a lot of people working hard for their 100-metre dash, or marathon, or something. |
| 2020-11-19 18:11:43 | <monochrom> | Why not just get a ride? |
| 2020-11-19 18:11:54 | <monochrom> | Why not just call uber? |
| 2020-11-19 18:11:58 | <koz_> | ski: Thanks! I was hoping someone did a teardown. |
| 2020-11-19 18:12:43 | × | jpds quits (~jpds@gateway/tor-sasl/jpds) (Ping timeout: 240 seconds) |
| 2020-11-19 18:13:22 | × | AWizzArd quits (~code@gehrels.uberspace.de) (Changing host) |
| 2020-11-19 18:13:22 | → | AWizzArd joins (~code@unaffiliated/awizzard) |
| 2020-11-19 18:13:34 | → | toxix joins (~DTZUZU@207.81.171.116) |
| 2020-11-19 18:14:12 | → | ph88^ joins (~ph88@2a02:8109:9e00:7e5c:f073:c081:c2ef:433b) |
| 2020-11-19 18:15:07 | → | jpds joins (~jpds@gateway/tor-sasl/jpds) |
| 2020-11-19 18:16:38 | × | jrm quits (~jrm@freebsd/developer/jrm) (Ping timeout: 256 seconds) |
| 2020-11-19 18:16:50 | × | Yumasi quits (~guillaume@2a01cb09b06b29ea0877e1bda345185b.ipv6.abo.wanadoo.fr) (Ping timeout: 264 seconds) |
| 2020-11-19 18:17:07 | <koz_> | @unmtl StateT s Maybe a |
| 2020-11-19 18:17:07 | <lambdabot> | s -> Maybe (a, s) |
| 2020-11-19 18:18:28 | → | Tracerneo1 joins (~Tracerneo@193.56.252.12) |
| 2020-11-19 18:18:51 | → | neiluj joins (~jco@91-167-203-101.subs.proxad.net) |
| 2020-11-19 18:18:51 | × | neiluj quits (~jco@91-167-203-101.subs.proxad.net) (Changing host) |
| 2020-11-19 18:18:51 | → | neiluj joins (~jco@unaffiliated/neiluj) |
| 2020-11-19 18:19:35 | × | chele quits (~chele@ip5b416ea2.dynamic.kabel-deutschland.de) (Remote host closed the connection) |
| 2020-11-19 18:20:16 | <koz_> | :t guard |
| 2020-11-19 18:20:17 | <lambdabot> | Alternative f => Bool -> f () |
All times are in UTC.