215 reputation
128
bio website
location
age
visits member for 1 year, 9 months
seen Feb 5 at 4:36

Jan
2
comment Why don't compilers support non-English keywords?
I'd remove implicit as an example replacement for var in C#, since implicit is also a C# keyword which means something completely different.
Dec
11
comment Unit testing to prove balanced tree
Well, as long as you can prove the tree is balanced at any given point, you know that any basic operations will operate in log time. So a solution which analyzes the current state of the tree and proves it's balanced should be good enough, and doesn't needlessly add time or space complexity when it's not being used for testing. (And is in fact what I've already done - this was a month ago.)
Dec
10
comment Unit testing to prove balanced tree
And also add complexity to every step of the operation. If it were just being used to test (and compare to something unbalanced, say), that might be okay, but you'd have to then disable that code before putting into production.
Nov
11
comment Unit testing to prove balanced tree
@JanHudec I think then by that token you could guarantee that the furthest leaf from the root is no more than twice as deep as the closest leaf - one could be black nodes all the way down, while another could alternate red and black, meaning twice the distance but no further. That seems easy enough to test for.
Nov
11
accepted Unit testing to prove balanced tree
Nov
11
comment Unit testing to prove balanced tree
Yeah, this probably is the way to go. I just wasn't sure if it would work for red-black. (I've done AVL trees a couple times in various languages, but this is my first time experimenting with other types of balanced trees.)
Nov
11
comment Unit testing to prove balanced tree
Is the depth-difference of no greater than 1 at every node guaranteed for red-black? I know this would work for AVL trees, but I remember reading somewhere that other balanced trees don't necessarily have this property despite being relatively balanced. I'd think something like comparing the maximum depth to the log(n) would a more general solution, but I think there's some wiggle-room there as well...
Nov
11
asked Unit testing to prove balanced tree
Oct
9
awarded  Yearling
Aug
12
comment What is beautiful code?
@Jubbat Indeed - sometimes the most efficient solution actually leads to very ugly code. (E.g. the classic Fast Inverse Square Root function)
Aug
2
comment Is there a name for a randomized heap?
It's a fine balance, though - Over how many hits should the 30% hit rate be a guarantee? Over too small a range (e.g. 3 out of 10), and it's only slightly random, almost predictable. Make the range too large (300 out of 1000), and it's almost no different from just purely random. In either case, it'd be very different to tell whether the chances were calculated ahead of time or on the fly. Do you expect the average player to sit and count exactly how many hits per 100 swings occur? A few might, but most wouldn't care.
Aug
2
comment Is there a name for a randomized heap?
True, performance-wise, there's no real difference, but if I just wanted a random ordering without depopulating the container, I'd have to pop everything, store it all in another location, and then reinsert them all again. The iterator method is merely a convenient way to avoid all that extra code. The one-at-a-time pop would probably be the more common usage though.
Jul
31
comment Is there a name for a randomized heap?
I'm not sure your example about the orc's 30% hit rate is the best example - you could get close to that simply by calculating a random number at the time of attack. (e.g. if (rand(100) < 30)) It might not end up being exactly 30% due to randomness, but nobody would notice. If the Ace of Spades turns up twice in a deck of cards, however, it's a bigger problem. Of course you know the size of a standard deck in advance: 52 cards. But imagine a scenario where you don't know that, and it might change frequently over time. I'd say both methods have valid use-cases.
Jul
31
awarded  Commentator
Jul
31
comment Is there a name for a randomized heap?
The difference with this is that you must know the size of the array before creating it. With my implementation, you can put any arbitrary number of elements in, either at the beginning or at any point later on. It is true that all inserted elements will end up as leaf nodes, but since popping the top causes random percolation, they might not stay down there. It means that a recently added element is less likely to reappear right away, which is not necessarily a bad thing. (Think of the shuffle feature on an MP3 player - you don't WANT the same song twice in a row.)
Jul
31
comment Is there a name for a randomized heap?
That's because there's two ways to use it - You can pop elements from the top one at a time, which doesn't require a reshuffle, or you can use an iterator to get a whole list without popping - in the latter case you must reshuffle or you'll get the same order every time.
Jul
30
asked Is there a name for a randomized heap?
Jul
30
awarded  Fanatic
Jul
20
comment Is there a name for this tree variant?
Internally, yes. But from the user's side, they'd see it as just a single structure. Create once, insert each item once, and then you can iterate or search just like a single BST, only you have to provide a key. (Or not - it actually defaults to the first key in the list if you don't, but that's trivial.) Plus the items it stores must have a given structure so that it can search for named keys, but I'd already built that.
Jul
20
comment Is there a name for this tree variant?
@JimmyHoffa Which I can't even use because Boost is C++ and I'm using C#. Mind you, C# does have this kind of thing via Linq expressions, but I'm mainly creating a library here for self-improvement and practice, even though I know that better implementations exist already. However, it is helpful to know what name other libraries have used for this structure.