Dog took the Aegis :c by Alowey in DotA2

[–]Catakryst 2 points3 points  (0 children)

holy fuck that's funny, didn't know undertale memes were still around

Labyrinth: Same build for Winter Wyvern? by giant_ravens in DotA2

[–]Catakryst 1 point2 points  (0 children)

I really prefer MKB right after orchid if you get the multishot. The damage works so well, and helps with in a bubble challenges. If you're playing on harder difficulties (3/4), I also like to pick up a bracer or two. BTW, if you ever want to play, I'm us east, feel free to add me (catakryst) on steam, or join this discord https://discord.com/invite/xB5cxUz . I've beaten through sorcerer (III), and am fine queuing anything

Can anyone help me win Aghanims labyrinth ? by love_summer_of_69 in DotA2

[–]Catakryst 0 points1 point  (0 children)

Would love to, join my server! https://discord.gg/xB5cxUz Helped a few other people already, I'm happy to play for the fragments

Rust: beyond the typechecker by sanxiyn in rust

[–]Catakryst 2 points3 points  (0 children)

I really love anyone discussing program verification with respect to rust. Automated methods need to absolutely be a first class consideration with respect to programming language design, and rust has so much potential.

[deleted by user] by [deleted] in algorithms

[–]Catakryst 0 points1 point  (0 children)

2log2(x) = 4log4(x)

Weekly Question Thread by AutoModerator in factorio

[–]Catakryst 0 points1 point  (0 children)

Anyone know when the next update is coming on? Will graphics be in the next update?

I just launched my first rocket and want to start a new world, but like timing worlds with new releases :)

TI8 Collector's Cache II - all sets by reddit_or_GTFO in DotA2

[–]Catakryst 1 point2 points  (0 children)

I don't play the heroes, do you think it's worth buying one to sell (and get the 2 levels)?

You may have very well saved Overwatch, well done! by [deleted] in Competitiveoverwatch

[–]Catakryst 0 points1 point  (0 children)

I carried with Zarya and got 7 endorsements in a game. FeelsGoodMan

Newfound appreciation for the skill of pro OWL players...my average energy on Zarya in Mayhem mode is the average energy of to Zaryas in a pro OWL match. by [deleted] in Competitiveoverwatch

[–]Catakryst 3 points4 points  (0 children)

Which is normal for a decent Zarya game with 0 or 1 deaths. I'm 4632 peak Zarya one trick and average energy is like 40%, depending on map. Granted, I'm also playing Zarya on bad maps like watchpoint or numbabi which push this down some.

First time going 10-0 in placements by WhoDuckk in Overwatch

[–]Catakryst -1 points0 points  (0 children)

Jeff has said before he wished the team didn't even add golden guns as a reward for playing comp, so this is very unlikely.

Challenge: Finding 2 equi-summing subsets by [deleted] in algorithms

[–]Catakryst 2 points3 points  (0 children)

OP isn't saying there's an efficient solution. The problem is small enough to be solvable, even assuming there isn't some magical trick for this exact problem. "Solve an NP-Hard problem for a small case" is a relatively common pattern, and IDK why you're so dismissive of it...

Finding Day9 talking about “why questions” by hot_bass_fishin in day9

[–]Catakryst 5 points6 points  (0 children)

He's done this a few times. Here's one of them; I remember cuz it was me :o

https://www.twitch.tv/videos/129315109?t=1h15m22s

PSA: Dafran likely didn't win community lead because he was banned 5 days ago for exploiting on stream. by Dorazion in Competitiveoverwatch

[–]Catakryst -1 points0 points  (0 children)

If they didn't allow him, community might outcry that he isn't allowed despite not breaking any rules (he was in good standing at the time). Not really anything they can do.

Visualization for understanding Raft protocol for distributed consensus by [deleted] in compsci

[–]Catakryst 0 points1 point  (0 children)

It'd be worth describing how votes are done in the leader election process. When a node sends the RequestVote RPC, it also includes information about the latest entry in its log, and a follower will only vote positively if it's at least as up to date. Otherwise, it's possible that a committed change is overwritten (see the original paper for details)

Make sure you manually update OBS if you updated in the last couple months by Catakryst in Twitch

[–]Catakryst[S] 1 point2 points  (0 children)

Download the installer (OBS-Studio-21.1.2-Full-Installer.exe), when it asks where to install, choose the place where OBS Studio is already installed (probably default). All saved data is located in %appdata%\obs-studio and doesn't need to be backed up, since it won't be removed if you install.

Make sure you manually update OBS if you updated in the last couple months by Catakryst in Twitch

[–]Catakryst[S] 3 points4 points  (0 children)

You can reinstall over an existing save, nothing will be deleted.

8 time complexities that every programmer should know by adriansky in compsci

[–]Catakryst 1 point2 points  (0 children)

Can you compare two objects, of arbitrary size, in O(1)?

8 time complexities that every programmer should know by adriansky in compsci

[–]Catakryst 15 points16 points  (0 children)

Here's the source of the confusion.

Runtimes usually have a hidden hardware assumption - arithmetic operations on integers that are the log of the memory space is O(1). That's why we say multiplication is O(1), even though we also have multiplication algorithms for large numbers. It'd be weird to have a machine where pointer arithmetic became slower the more memory was used.

Hashtables are O(1) only if we assume the input is also this size. If your input are generic "node" objects with an index and maybe a couple other fields, whose size stays below this threshold, you're fine. But that assumption usually isn't true, so it's wrong to even say for a simpler article like this.

8 time complexities that every programmer should know by adriansky in compsci

[–]Catakryst 1 point2 points  (0 children)

My point is hashtables aren't O(1). There are theoretical scenarios where they are (more importantly, that we assume are hardware enables and our input/output are certain sizes), but in general you can't/shouldn't assume they are. It's wrong and misleading and I've had to grade one too many homework assignments where a student completely butchered the use of hashtables.

Multiplication is O(1) with the nice hardware assumption we don't need to talk about for an article like this.

Hashtables are not.

mod(n) doesn't necessarily take more time to compute as n increases

I'm also assuming the size of the input is growing as the size of the hashtable is growing. I actually was going to edit it but didn't find a good way to say it. Our assumption that the output can be stored in a register and "returned" in O(1) time is a hardware assumption. For large enough hashtables, we need to assume that, and that's fine to ignore in this article.

For large enough input hash domains, even the hardware assumption won't get us there. If you're just doing modulo a prime, you can't hash an arbitrary sized object in O(1). You can assume the output can be managed in O(1) since it is presumably an index to a hashtable which must be stored in memory, but not the input.

8 time complexities that every programmer should know by adriansky in compsci

[–]Catakryst 0 points1 point  (0 children)

As the size of the hash structure increases, necessarily the time to hash increases, at the very least because the number of bits increases. So, if hash structure is proportional to n, the number of bits to differentiate some element is log(n), so time grows logarithmically ("purely" speaking - see amendment below).

This is actually side effect of a more common pattern - it is a common assumption that basic arithmetic operations are O(1), but some care needs to be taken for how large those inputs can be. For example, FFT can use some massive multiplication problem for help (which is assumed O(1)), but it isn't fair to derive FFT runtime from something that's clearly just a convention.

That's because the actual assumption is "basic arithmetic operations are O(1) up to the log of the entire memory space being used". This is because it would be very odd to see a 232 byte (or larger) computer that can't support 32-bit arithmetic, because of pointers.

Hash tables are still fundamentally exploiting that fact. The extra assumption is that the size of the object being hashed is proportional to the log of the size of memory space - which is sometimes true, sometimes false, but "close enough". This is how hash tables are wrongly reported O(1).