I spent a bit of time thinking about all the indirections in my code and decided I'm going hybrid functional/procedural on this, and minimising the visible overhead that the OOP constructs are clearly creating. One nice thing about Go's hostile attitude towards OOP is that when you find the way to do it, you realise 'oh, that's why go doesn't like it'.
soo, </thread> for me :) unsubscribing and not ruminating any further (*sigh of relief in the peanut gallery*) :D On Tuesday, 24 April 2018 14:59:22 UTC+3, Louki Sumirniy wrote: > > I'll just be brief this time and hit the points quickly: > > Yes, technically it is a Complete Binary Tree but you won't find a > Complete Implementation of one anywhere, I have looked, and there isn't. > The concept has been rejected without being tested by anyone who has > considered it at least what I can find. > > Those relational functions you mentioned are not correct for a tree with > the array index 0 being the root, this is them here: > > Parent: > > c.Index = c.Index>>1 - (c.Index+1)%2 > > Left Child: > > c.Index = c.Index<<1 ^ 1 > > Right Child: > > c.Index = c.Index<<1 + 2 > > I have used bitwise operators because it is always powers of two, and thus > will be faster on a processor with bitshift and no worse than using *2 > without. I used an XOR on left because the shift is left and thus the LSB > can be flipped without computation to add one. The right one adds two, this > is related to using 0 as the root also. > > The parent function is the one that got me the most excited when I came up > with it - it avoids the use of comparison/branch functions by taking > advantage of the property of the tree rooted at 0, that every left child is > odd and every right is even (that's what the IsOdd function returns - and > computes it with &1, and is used in my Left and Right walk functions that > 'flatten' the tree and walk it like it's a sorted list). By adding one to > the index you flip its' odd/even status, gives you a 1 if it then becomes > odd. This effectively is a 'move inwards' operation. It saves on comparison > and branching and I know on 32 bit integers bit shift, addition and modulus > are very fast. (and the code is very short in the cache) > > By rooting the tree at array index 0 it becomes possible to pick any given > index and know if it's a left or right child by whether it's odd or even, > and the special case of zero, which is neither (yes, I know it's referred > to as even but it's not really a number, according to number theory), tells > you also you can't move upwards. > > Compared to a potential and mostly filled tree of 30 rows, the amount of > space taken up by the code is quite small, with the separation of functions > for tree and data type, there is no wasted space repeating functionality > that can be abstracted. Plus, for up to around 20 rows of tree, the array > will fit mostly within a cpu cache, and since operations take place on one > side and the other, and mainly affect small segments of the subtree, each > subsequent row does not have to be fully loaded into the cache for most > operations. > > Technically my approach is more like a functional programming approach to > the problem, as I am passing pointers to functions in order to implement > the data specific elements, only the interface for the array store is OOP > style (and it DOES have to be encapsulated in a struct because Go slices do > not work with interfaces). > > As to exposing things, in fact an external payload data type library can > decide exactly what it will expose. I am only writing a base implementation > with uint32 because to test it I have to fill the data with *something* and > quite likely 32 bit hashes will be actually used in my intended application > for this library, as the heads and tails from 64bit hashes. > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
