Newest at the top
| 2024-11-07 17:46:57 +0100 | <c_wraith> | The funniest counter-argument I heard to "hashing isn't O(1)" was "it is if you cache it." |
| 2024-11-07 17:46:21 +0100 | <Inst> | like, seq is more efficient than list asymptotically, but benchmarks show that in many practical case list pulls ahead |
| 2024-11-07 17:46:04 +0100 | <Inst> | tbh at O(ln n) and below, I suspect you can easily have performance dominated by constant factors? |
| 2024-11-07 17:45:50 +0100 | JamesMowery43 | (~JamesMowe@ip68-228-212-232.ph.ph.cox.net) JamesMowery |
| 2024-11-07 17:44:28 +0100 | <merijn> | Most people handwave/ignore the cost of computing a hash of the key, handwave the possibility of complexity degradation due to collisions |
| 2024-11-07 17:42:28 +0100 | <merijn> | Meanwhile hashmaps are O(1) (with sufficient handwaving) average case and O(n) worst case complexity. And you need a pretty decent amount of memory bloat to avoid hitting the O(n) case |
| 2024-11-07 17:41:35 +0100 | <merijn> | Inst: Haskell's immutable maps use storage linear in number of elements and are O(log n) average *AND* worst case complexity |
| 2024-11-07 17:41:02 +0100 | <merijn> | Inst: Bit late, but there's also the issue of 1) memory complexity and 2) avg case vs worst case complexity |
| 2024-11-07 17:40:05 +0100 | Digitteknohippie | Digit |
| 2024-11-07 17:39:51 +0100 | <merijn> | hashtables are the most overrated datastructure IMHO |
| 2024-11-07 17:38:16 +0100 | JamesMowery43 | (~JamesMowe@ip98-167-207-182.ph.ph.cox.net) (Ping timeout: 272 seconds) |
| 2024-11-07 17:38:15 +0100 | alexherbo2 | (~alexherbo@2a02-8440-3318-5646-f579-461f-1ad7-34d7.rev.sfr.net) (Remote host closed the connection) |
| 2024-11-07 17:37:05 +0100 | housemate | (~housemate@146.70.66.228) (Ping timeout: 248 seconds) |
| 2024-11-07 17:34:58 +0100 | housemate_ | (~housemate@146.70.66.228) housemate |
| 2024-11-07 17:24:33 +0100 | poscat | (~poscat@user/poscat) poscat |
| 2024-11-07 17:23:59 +0100 | poscat0x04 | (~poscat@user/poscat) (Ping timeout: 252 seconds) |
| 2024-11-07 17:20:32 +0100 | Digit | (~user@user/digit) (Ping timeout: 272 seconds) |
| 2024-11-07 17:19:43 +0100 | Digitteknohippie | (~user@user/digit) Digit |
| 2024-11-07 17:18:05 +0100 | housemate | (~housemate@146.70.66.228) housemate |
| 2024-11-07 17:17:59 +0100 | misterfish | (~misterfis@31-161-39-137.biz.kpn.net) (Ping timeout: 255 seconds) |
| 2024-11-07 17:17:28 +0100 | notzmv | (~daniel@user/notzmv) notzmv |
| 2024-11-07 17:16:36 +0100 | housemate_ | (~housemate@146.70.66.228) (Quit: "I saw it in a tiktok video and thought that it was the most smartest answer ever." ~ AnonOps Radio [some time some place] | I AM THE DERIVATIVE I AM GOING TANGENT TO THE CURVE!) |
| 2024-11-07 17:07:29 +0100 | son0p | (~ff@186.119.84.155) (Ping timeout: 252 seconds) |
| 2024-11-07 17:00:30 +0100 | euphores | (~SASL_euph@user/euphores) euphores |
| 2024-11-07 16:50:02 +0100 | longlongdouble | (~longlongd@2405:201:5c16:135:1989:242:cab1:419a) |
| 2024-11-07 16:48:54 +0100 | tromp | (~textual@92-110-219-57.cable.dynamic.v4.ziggo.nl) (Quit: My iMac has gone to sleep. ZZZzzz…) |
| 2024-11-07 16:48:06 +0100 | euphores | (~SASL_euph@user/euphores) (Quit: Leaving.) |
| 2024-11-07 16:45:15 +0100 | euleritian | (~euleritia@dynamic-176-006-128-136.176.6.pool.telefonica.de) |
| 2024-11-07 16:44:32 +0100 | longlongdouble | (~longlongd@2405:201:5c16:135:1989:242:cab1:419a) (Remote host closed the connection) |
| 2024-11-07 16:43:57 +0100 | euleritian | (~euleritia@dynamic-176-006-131-038.176.6.pool.telefonica.de) (Ping timeout: 252 seconds) |
| 2024-11-07 16:43:34 +0100 | skylord5816 | (~skylord58@user/skylord5816) skylord5816 |
| 2024-11-07 16:42:53 +0100 | housemate | (~housemate@146.70.66.228) (Ping timeout: 255 seconds) |
| 2024-11-07 16:42:33 +0100 | alp | (~alp@2001:861:e3d6:8f80:4549:4578:5f94:9afe) (Ping timeout: 252 seconds) |
| 2024-11-07 16:42:23 +0100 | <c_wraith> | hash tables have more assumptions going into those O(1) claims than most data structures. In fact, those assumptions add up to having a bounded key space, in which case you claim any lookup strategy is O(1) |
| 2024-11-07 16:41:44 +0100 | housemate_ | (~housemate@146.70.66.228) housemate |
| 2024-11-07 16:39:41 +0100 | euleritian | (~euleritia@dynamic-176-006-131-038.176.6.pool.telefonica.de) |
| 2024-11-07 16:39:29 +0100 | euleritian | (~euleritia@ip4d16fc38.dynamic.kabel-deutschland.de) (Ping timeout: 248 seconds) |
| 2024-11-07 16:37:32 +0100 | housemate | (~housemate@146.70.66.228) housemate |
| 2024-11-07 16:37:02 +0100 | housemate | (~housemate@146.70.66.228) (Max SendQ exceeded) |
| 2024-11-07 16:36:10 +0100 | housemate | (~housemate@146.70.66.228) housemate |
| 2024-11-07 16:31:27 +0100 | Sgeo | (~Sgeo@user/sgeo) Sgeo |
| 2024-11-07 16:31:04 +0100 | lortabac | (~lortabac@2a01:e0a:541:b8f0:55ab:e185:7f81:54a4) (Quit: WeeChat 4.4.2) |
| 2024-11-07 16:30:58 +0100 | ubert | (~Thunderbi@77.119.163.56.wireless.dyn.drei.com) (Ping timeout: 248 seconds) |
| 2024-11-07 16:28:11 +0100 | AlexZenon | (~alzenon@178.34.160.231) |
| 2024-11-07 16:26:59 +0100 | CoolMa7 | (~CoolMa7@95.91.137.87) (Client Quit) |
| 2024-11-07 16:26:02 +0100 | CoolMa7 | (~CoolMa7@95.91.137.87) CoolMa7 |
| 2024-11-07 16:23:34 +0100 | CoolMa7 | (~CoolMa7@128.90.175.3) (Ping timeout: 260 seconds) |
| 2024-11-07 16:23:00 +0100 | AlexNoo_ | AlexNoo |
| 2024-11-07 16:21:15 +0100 | housemate | (~housemate@146.70.66.228) (Remote host closed the connection) |
| 2024-11-07 16:20:20 +0100 | housemate | (~housemate@146.70.66.228) housemate |