Newest at the top
| 2024-11-07 15:36:09 +0100 | CoolMa7_ | (~CoolMa7@128.90.145.4) (Ping timeout: 260 seconds) |
| 2024-11-07 15:34:58 +0100 | CoolMa7 | (~CoolMa7@128.90.170.13) CoolMa7 |
| 2024-11-07 15:33:59 +0100 | CoolMa7 | (~CoolMa7@95.91.137.87) (Ping timeout: 252 seconds) |
| 2024-11-07 15:31:06 +0100 | CoolMa7_ | (~CoolMa7@128.90.145.4) CoolMa7 |
| 2024-11-07 15:30:11 +0100 | kuribas | (~user@ip-188-118-57-242.reverse.destiny.be) (Remote host closed the connection) |
| 2024-11-07 15:28:56 +0100 | CoolMa7 | (~CoolMa7@95.91.137.87) CoolMa7 |
| 2024-11-07 15:22:44 +0100 | Square | (~Square4@user/square) Square |
| 2024-11-07 15:21:06 +0100 | longlongdouble | (~longlongd@2405:201:5c16:135:1989:242:cab1:419a) |
| 2024-11-07 15:19:54 +0100 | longlongdouble | (~longlongd@2405:201:5c16:135:1989:242:cab1:419a) (Read error: Connection reset by peer) |
| 2024-11-07 15:16:34 +0100 | housemate | (~housemate@146.70.66.228) housemate |
| 2024-11-07 15:14:24 +0100 | blover | (~blover@2804:7f0:6780:f864:2d9e:2c7d:cab0:69d2) blover |
| 2024-11-07 15:12:53 +0100 | housemate | (~housemate@146.70.66.228) (Ping timeout: 245 seconds) |
| 2024-11-07 15:09:19 +0100 | sam113101 | (~sam@modemcable220.199-203-24.mc.videotron.ca) (Ping timeout: 260 seconds) |
| 2024-11-07 15:07:56 +0100 | <[exa]> | whew cool, they actually did cuckoo hashing |
| 2024-11-07 15:07:28 +0100 | <geekosaur> | wasn't even in `containers`, that didn't exist yet |
| 2024-11-07 15:07:17 +0100 | <geekosaur> | https://downloads.haskell.org/~ghc/6.6.1/docs/html/libraries/base/Data-HashTable.html |
| 2024-11-07 15:06:33 +0100 | housemate | (~housemate@146.70.66.228) housemate |
| 2024-11-07 15:06:24 +0100 | notzmv | (~daniel@user/notzmv) (Ping timeout: 276 seconds) |
| 2024-11-07 15:05:59 +0100 | <geekosaur> | (this was long before `unordered-containers`) |
| 2024-11-07 15:05:22 +0100 | <geekosaur> | (historical note: `containers` used to include an `IO`-based hash table. it was removed because its performance was pretty bad. but someone resuscitated it and mostly fixed the performance issues, and now it's in the `hashtables` package IIRC) |
| 2024-11-07 15:02:56 +0100 | <[exa]> | usually doing most operations in O(log n). |
| 2024-11-07 15:02:54 +0100 | <[exa]> | Inst: anyway re mutability, each hashtable change requires changing a single element in a (potentially big) array. Normally with computers that's very efficient so people can reach the "amortized hashy O(1)" aka O(log/loglog). In haskell it's absolutely not easy unless you either unsafePerformIO or force the user to pull ST or IO through each operation. So people kinda fall back to trees which are |
| 2024-11-07 15:02:34 +0100 | tromp | (~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl) |
| 2024-11-07 14:57:36 +0100 | CoolMa7 | (~CoolMa7@ip5f5b8957.dynamic.kabel-deutschland.de) (Quit: My Mac has gone to sleep. ZZZzzz…) |
| 2024-11-07 14:55:31 +0100 | <[exa]> | +- the usual consideration of "sometimes it just rehashes in O(n)" |
| 2024-11-07 14:53:21 +0100 | <[exa]> | for all kinds of mutable hashmaps you usually end up at something like O(log n/loglog n) with an uncanny constant factor and absolutely no chance to get any benefit from the usual computers' caching layers |
| 2024-11-07 14:53:17 +0100 | longlongdouble | (~longlongd@2405:201:5c16:135:1989:242:cab1:419a) |
| 2024-11-07 14:52:49 +0100 | longlongdouble | (~longlongd@117.225.100.25) (Ping timeout: 248 seconds) |
| 2024-11-07 14:51:34 +0100 | <[exa]> | at which point everyone should just use an array and integer index |
| 2024-11-07 14:51:26 +0100 | <[exa]> | yes it only holds for a completely immutable container prepared with a perfect hash |
| 2024-11-07 14:51:05 +0100 | housemate | (~housemate@146.70.66.228) (Ping timeout: 252 seconds) |
| 2024-11-07 14:50:46 +0100 | <kuribas> | It's only if the number of buckets is large enough? |
| 2024-11-07 14:50:24 +0100 | <kuribas> | Isn't the O(1) for a hashtable also a lie? |
| 2024-11-07 14:49:41 +0100 | weary-traveler | (~user@user/user363627) user363627 |
| 2024-11-07 14:48:40 +0100 | ocra8 | (ocra8@user/ocra8) (Quit: WeeChat 4.3.4) |
| 2024-11-07 14:48:02 +0100 | <[exa]> | but don't, the O(1) for hashmaps is a lie |
| 2024-11-07 14:47:30 +0100 | <[exa]> | tbh there are efficient hashy sets and maps even in haskell in https://hackage.haskell.org/package/unordered-containers |
| 2024-11-07 14:45:12 +0100 | <kuribas> | binary trees, which is are usually used in pure datatypes, have log n operations. |
| 2024-11-07 14:43:38 +0100 | <kuribas> | hashtables use mutation to insert elements. |
| 2024-11-07 14:43:17 +0100 | <Inst> | how do you use mutability to get O(1) access? |
| 2024-11-07 14:42:53 +0100 | <kuribas> | most languages depend on mutability to get O(1). Which is itself a lie, since memory access in a CPU is not O(1). |
| 2024-11-07 14:42:20 +0100 | <kuribas> | Inst: in any case, it's what you get with immutable structures. |
| 2024-11-07 14:42:07 +0100 | <kuribas> | Inst: it mostly depends on constant factors. |
| 2024-11-07 14:42:02 +0100 | sudden | (~cat@user/sudden) sudden |
| 2024-11-07 14:41:58 +0100 | <kuribas> | Inst: O(ln n) is not much different from O(1). |
| 2024-11-07 14:41:43 +0100 | <Inst> | afaik in other languages you can O(1) access objects |
| 2024-11-07 14:41:27 +0100 | <Inst> | tbh what's the deal with O(ln n) for Haskell sets and maps? |
| 2024-11-07 14:39:13 +0100 | weary-traveler | (~user@user/user363627) (Remote host closed the connection) |
| 2024-11-07 14:38:50 +0100 | merijn | (~merijn@77.242.116.146) merijn |
| 2024-11-07 14:37:58 +0100 | longlongdouble | (~longlongd@117.225.100.25) |