Home liberachat/#haskell: Logs Calendar

Logs: liberachat/#haskell

←Prev  Next→
Page 1 .. 561 562 563 564 565 566 567 568 569 570 571 .. 18008
— 1,800,730 events total
2021-06-21 07:50:47 → gehmehgeh joins (~user@user/gehmehgeh)
2021-06-21 07:51:01 <Unhammer> I've got lots of experience with taking performant data structures and making them go slowly
2021-06-21 07:51:27 × berberman quits (~berberman@user/berberman) (Ping timeout: 244 seconds)
2021-06-21 07:52:11 → berberman joins (~berberman@user/berberman)
2021-06-21 07:52:31 × tzh_ quits (~tzh@c-24-21-73-154.hsd1.or.comcast.net) (Quit: zzz)
2021-06-21 07:52:49 × Lycurgus quits (~juan@cpe-45-46-140-49.buffalo.res.rr.com) (Quit: Exeunt)
2021-06-21 07:53:49 × hmmmas quits (~chenqisu1@183.217.200.246) (Quit: Leaving.)
2021-06-21 07:57:53 × fm quits (~fm@user/fm) (Quit: fm)
2021-06-21 08:00:54 × octeep quits (~octeep@n219077212239.netvigator.com) (Ping timeout: 264 seconds)
2021-06-21 08:01:16 × acid quits (~acid@user/acid) (Ping timeout: 244 seconds)
2021-06-21 08:02:20 → acid joins (~acid@user/acid)
2021-06-21 08:03:40 × Guest8323 quits (~pera@154.red-79-155-45.dynamicip.rima-tde.net) (Quit: leaving)
2021-06-21 08:03:54 × jneira quits (~jneira@212.8.115.226) (Quit: Client closed)
2021-06-21 08:03:56 → octeep joins (~octeep@42-2-220-152.static.netvigator.com)
2021-06-21 08:04:30 → jneira joins (~jneira@212.8.115.226)
2021-06-21 08:06:16 → kayprish joins (~kayprish@46.240.143.86)
2021-06-21 08:06:22 → elf_fortrez joins (~elf_fortr@adsl-64-237-239-58.prtc.net)
2021-06-21 08:06:40 → hendursa1 joins (~weechat@user/hendursaga)
2021-06-21 08:08:04 × Guest9 quits (~Guest9@43.250.158.40) (Ping timeout: 265 seconds)
2021-06-21 08:08:52 × jneira quits (~jneira@212.8.115.226) (Client Quit)
2021-06-21 08:09:10 → jneira joins (~jneira@212.8.115.226)
2021-06-21 08:09:20 <int-e> Unhammer: but if you do the natural thing, which is to look at the current node in the fingertree and its parts (each of which has a known length), and skip over all the parts that are shorter than your target length... you'll almost automatically end up with that complexity.
2021-06-21 08:09:30 × hendursaga quits (~weechat@user/hendursaga) (Ping timeout: 244 seconds)
2021-06-21 08:09:57 × lemmih quits (~lemmih@2406:3003:2072:44:925e:d7ab:50d2:4457) (Remote host closed the connection)
2021-06-21 08:10:15 → lemmih joins (~lemmih@2406:3003:2072:44:9bcd:6adc:313d:18f9)
2021-06-21 08:10:24 <int-e> And that was my point: you get that complexity even if you don't try to look at the finger tree from the "shorter" end.
2021-06-21 08:13:30 → hegstal joins (~hegstal@2a02:c7f:7604:8a00:7fb:5bd8:2599:2fdb)
2021-06-21 08:17:32 → allbery_b joins (~geekosaur@xmonad/geekosaur)
2021-06-21 08:17:32 × geekosaur quits (~geekosaur@xmonad/geekosaur) (Killed (NickServ (GHOST command used by allbery_b)))
2021-06-21 08:17:44 → jumper149 joins (~jumper149@80.240.31.34)
2021-06-21 08:18:23 × Sgeo_ quits (~Sgeo@ool-18b9875e.dyn.optonline.net) (Read error: Connection reset by peer)
2021-06-21 08:18:49 → maroloccio joins (~marolocci@186.210.216.126)
2021-06-21 08:19:13 × hegstal quits (~hegstal@2a02:c7f:7604:8a00:7fb:5bd8:2599:2fdb) (Remote host closed the connection)
2021-06-21 08:19:56 → hegstal joins (~hegstal@2a02:c7f:7604:8a00:2a76:42b9:78db:d162)
2021-06-21 08:20:24 → fizbin joins (~fizbin@c-73-33-197-160.hsd1.nj.comcast.net)
2021-06-21 08:22:38 × jneira quits (~jneira@212.8.115.226) (Quit: Client closed)
2021-06-21 08:23:00 → jneira joins (~jneira@212.8.115.226)
2021-06-21 08:24:08 → fendor joins (~fendor@178.115.131.43.wireless.dyn.drei.com)
2021-06-21 08:25:02 × jneira quits (~jneira@212.8.115.226) (Client Quit)
2021-06-21 08:25:05 × fizbin quits (~fizbin@c-73-33-197-160.hsd1.nj.comcast.net) (Ping timeout: 258 seconds)
2021-06-21 08:25:18 → jneira joins (~jneira@212.8.115.226)
2021-06-21 08:26:51 → maroloccio1 joins (~marolocci@189.15.9.54)
2021-06-21 08:29:22 × maroloccio quits (~marolocci@186.210.216.126) (Ping timeout: 246 seconds)
2021-06-21 08:31:04 × eggplant_ quits (~Eggplanta@2600:1700:bef1:5e10:945c:cf17:8af9:9d4a) (Remote host closed the connection)
2021-06-21 08:31:48 <merijn> Unhammer: Don't we all? ;)
2021-06-21 08:31:59 → Scotty_Trees joins (~Scotty_Tr@162-234-179-169.lightspeed.brhmal.sbcglobal.net)
2021-06-21 08:33:48 → kuribas joins (~user@ptr-25vy0i7yslxo8ej7h6j.18120a2.ip6.access.telenet.be)
2021-06-21 08:35:29 <siraben> finger trees <3
2021-06-21 08:36:10 <siraben> are there structures that can be used to replace mutable graphs in imperative languages? problems involving mutable graphs are usually quite difficult in Haskell
2021-06-21 08:37:22 <merijn> The answer is always arrays :p
2021-06-21 08:37:25 × qrpnxz quits (abc4f95c31@user/qrpnxz) (Quit: Gateway shutdown)
2021-06-21 08:37:41 → qrpnxz joins (~qrpnxz@user/qrpnxz)
2021-06-21 08:37:47 <merijn> If there is one lesson I have taken away from HPC it's that arrays are the universal HPC data structure :p
2021-06-21 08:37:54 <tomsmeding> re:finger trees: just want to post this very nice explanation of them for those who haven't seen it yet https://www.cs.tufts.edu/~nr/cs257/archive/koen-claessen/finger-trees.pdf
2021-06-21 08:38:14 <merijn> And if you're not using arrays...well, better figure out a way to start :p
2021-06-21 08:38:45 <EvanR> "everything is arrays", this is where conal comes to knock some sense into us
2021-06-21 08:39:34 <merijn> EvanR: Naah, that's APL talking
2021-06-21 08:39:48 <merijn> HPC isn't "everything is arrays", but "everything *should be* arrays" :p
2021-06-21 08:39:49 → involans joins (~alex@cpc92718-cmbg20-2-0-cust157.5-4.cable.virginm.net)
2021-06-21 08:40:49 <EvanR> is this because architecture is built to cache, prefetch, stream, and SIMD operate on arrays
2021-06-21 08:41:22 <merijn> Like that one time I had a perfectly optimal, single pass O(n log n) algorithm and I made it 7x faster, by adding a double pass on top of it and replacing heaps with a single massive array :p
2021-06-21 08:41:26 <merijn> EvanR: Pretty much
2021-06-21 08:41:51 × jneira quits (~jneira@212.8.115.226) (Quit: Client closed)
2021-06-21 08:42:19 → jneira joins (~jneira@212.8.115.226)
2021-06-21 08:42:28 <merijn> EvanR: O(n) where you are basically linearly going over a massive array will almost always beat some fancy optimal data structure where you have dynamic allocations, pointer chasing, etc.
2021-06-21 08:42:37 <int-e> merijn: it's embarrasing how often the stupidest approach is the fastest because CPUs coevolve with stupid algorithms (if you want to be cynical about it ;-) )
2021-06-21 08:42:51 <siraben> merijn: Data.Array is enough or should I use Data.Vector?
2021-06-21 08:42:57 <siraben> Hm, always arrays? aaaa
2021-06-21 08:43:11 <merijn> siraben: tbh, either are a massive improvement overy lists
2021-06-21 08:43:17 <int-e> siraben: yes, arrays, especially if you get sequential access to them
2021-06-21 08:43:24 <merijn> siraben: Personally I prefer Vector for 1D
2021-06-21 08:43:32 <int-e> or the arrays are small enough to (mostly) fit into the cache
2021-06-21 08:43:38 <merijn> siraben: Array is more flexible (as it allows custom indexing schemes)
2021-06-21 08:43:45 <shachaf> int-e: Do you think CPUs could do much better?
2021-06-21 08:43:48 <siraben> Yeah I already avoid lists whenever doing random access, but arrays are awkward enough that sometimes I just resort to Map (Int,Int) a
2021-06-21 08:43:58 <merijn> siraben: tbh, Map is surprisingly performant
2021-06-21 08:44:01 <siraben> multidimensional arrays, that is
2021-06-21 08:44:18 <merijn> siraben: Like, I've had Map with millions of elements doing lookups in tight loops and it performs pretty well
2021-06-21 08:44:53 <siraben> I see
2021-06-21 08:44:57 <merijn> Of course, there's also the matter of "does performance matter here?"
2021-06-21 08:45:19 × kayprish quits (~kayprish@46.240.143.86) (Read error: Connection reset by peer)
2021-06-21 08:45:22 <merijn> Like, if your code is doing disk/network IO there's basically no point in optimising compute to be faster than the time you're waiting for IO anyway
2021-06-21 08:45:44 <merijn> (well, there's some if the machine is shared or whatever, but you get what I mean)
2021-06-21 08:46:03 <EvanR> it's like drive faster so we can get to the red light sooner
2021-06-21 08:46:22 <merijn> EvanR: Now I'm imagining "green waves" for compute xD
2021-06-21 08:46:39 <int-e> shachaf: I don't know. Maybe RAM is not the right abstraction for advanced algorithms :P
2021-06-21 08:47:00 × jneira quits (~jneira@212.8.115.226) (Client Quit)
2021-06-21 08:47:01 <kuribas> merijn: wouldn't it be better to combine arrays with other structures (like trees or lists)?
2021-06-21 08:47:19 × moet quits (~moet@172.58.38.233) (Ping timeout: 258 seconds)
2021-06-21 08:47:20 → jneira joins (~jneira@212.8.115.226)
2021-06-21 08:47:21 <merijn> kuribas: In what scenario?
2021-06-21 08:47:22 <siraben> merijn: yeah, this is in solving algorithmic type problems
2021-06-21 08:47:22 <EvanR> array mapped trie
2021-06-21 08:47:24 <kuribas> merijn: for example, chunked lists for time series.
2021-06-21 08:47:28 <siraben> e.g. AOC, Codeforces, etc.
2021-06-21 08:47:31 <siraben> Google Code Jam
2021-06-21 08:47:56 <siraben> I have a conservative template for these types of problems
2021-06-21 08:47:57 <siraben> https://github.com/siraben/haoc-2020/blob/master/template.hs
2021-06-21 08:48:15 <merijn> kuribas: Why would a chunked list be better than just an array?
2021-06-21 08:48:20 <siraben> but in particular I should avoid other libraries whenever possible, even Data.Vector isn't always on the autograder
←Prev  Next→
Page 1 .. 561 562 563 564 565 566 567 568 569 570 571 .. 18008

All times are in UTC.