Is the need for a memory efficient implementation backed by a performance
profile?
Matt
On Monday, April 23, 2018 at 10:26:41 AM UTC-5, Louki Sumirniy wrote:
>
> First issue is that BAST does not use references. This is so that searches
> proceed linearly through memory. Instead it uses a flat array that it cuts
> into sequentially doubling sized rows, representing the slots that a binary
> tree has.
>
> Secondly, you just complicated my design even further with 'is left
> equal'. why not just 'go left' 'is this equal'?
>
> The implementation of the comparison could be different for all kinds of
> reasons. Number one reason that is already on my plan of action is where I
> have an arbitrary bit-width data, say 64 bits, but I want to sort one tree
> by the first 32 bits, and the same data feed into another tree at the same
> time that searches/sorts by the second 32 bits. This is the main reason for
> needing this flexibility. Mainly I want to stick to small blobs of memory,
> just numbers, mostly, but that at least includes 256 bit values. Much
> beyond that will destroy the advantage of this scheme, in that the tree
> will be too big in memory because of how large the probably 1/4 to
> half-filled node collection will generally be.
>
> On Monday, 23 April 2018 17:28:09 UTC+3, matthe...@gmail.com wrote:
>>
>> But I don't want to tie my users down to integers and floats. What if
>>> they want to sort strings? What if they want to sort complex numbers,
>>> matrixes, or what have you?
>>
>>
>> This is what the interface concept was made for.
>>
>> Why would the implementation of IsLeft be different if the BAST data is
>> organized another way? I think the abstraction you're expressed isn't
>> narrow enough.
>>
>> I don’t know the BAST details, but why not start here?
>>
>> type Node struct {
>> Element
>> Left *Node
>> Right *Node
>> }
>>
>> func (a Node) LeftEqual() bool {
>> if a.Left == nil {
>> return false
>> }
>> return a.Equal(a.Left.Element)
>> }
>>
>> type Element interface {
>> Equal(Element) bool
>> Null() bool
>> }
>>
>> Matt
>>
>> On Monday, April 23, 2018 at 8:55:14 AM UTC-5, Louki Sumirniy wrote:
>>>
>>> I did look at the Red/Black tree on Github and that was what got me
>>> started. But you need to understand exactly why those functions seem great
>>> in number. First of all, of course you could swap out 3 of those
>>> comparators for 1, and you probably don't even get why there is the 'empty'
>>> one. The datatype uses zero as a null value, as it is aimed at hashes and
>>> pretty much nothing hashes to zero (99.99999999% to understate it).
>>>
>>> In the code the caller would have to use, and this starts with my own
>>> code, so I am considering my own capacity to decode my code versus writing
>>> it in such a way that it is simple to understand. If I collapse those three
>>> functions into one, I either have to define a set of constants to put a
>>> human readable name on it - or, for a very small cost of maybe 10-15 bytes
>>> extra, human can read the code and know what it does and why it isn't
>>> incorrect. When you look further down to see what these functions are
>>> actually implemented with, you'll discover they are mostly one-liners. On
>>> the micro scale, it might seem making separate calls for these is a waste.
>>> But on the other side, if my caller code has to run a 3 level or longer
>>> if/then or switch/case, did I, as the programmer of the library, do my
>>> users (my fellow programmers) any favours? Nope!
>>>
>>> With this, the user can just say 'b.IsLeft(number, cursor)'. Sure, maybe
>>> there is no point in even having more than two conditions, since !IsLeft is
>>> the same as IsRight. But what if I wanted to descend the sort order. Then
>>> my code is riddled with '!IsRight' while I am trying to travel left. It's
>>> not good for the reader, and not good to read is hard to maintain, hard to
>>> maintain is expensive, and probably will be replaced by something else
>>> later. Reusability is very important for low level functions. It would be
>>> better for everyone if someone did the job right, first time, and for a
>>> long time afterwards, everyone can depend on it.
>>>
>>> And coming back full circle to how I came up with this, it was precisely
>>> by reading the cryptic and difficult to understand code of others, like
>>> that Red/Black tree. Computer programming is a heavy cognitive load task as
>>> it is. Arbitrary concepts of efficiency that don't take account for the
>>> cost of decoding the results of this theory tend to lead to reinventing the
>>> wheel, because the wheel was too cryptically constructed to simply modify
>>> it.
>>>
>>> </rant>
>>>
>>> The IsNull function is actually just a way of implementing x == 0. But I
>>> don't want to tie my users down to integers and floats. What if they want
>>> to sort strings? What if they want to sort complex numbers, matrixes, or
>>> what have you? I can't overload the equality operator, and even if I could,
>>> then there would be the issue of type inference, implicit casts, or the
>>> wordiness of explicit casts. Instead, the IsNull is already typed to the
>>> data you want to work with, it can have something other than zero as its
>>> null sentinel, or in other words, my slightly wordy interface means your
>>> sleek, svelte application that is easy to debug.
>>>
>>> On Monday, 23 April 2018 16:25:17 UTC+3, matthe...@gmail.com wrote:
>>>>
>>>> This is a code smell for me:
>>>>
>>>> type BAST interface {
>>>> AddRow() error
>>>> IsLeft(interface{}, Cursor) bool
>>>> IsRight(interface{}, Cursor) bool
>>>> IsEqual(interface{}, Cursor) bool
>>>> IsEmpty(Cursor) bool
>>>> …
>>>>
>>>> Interfaces should be small. This looks like a class definition which
>>>> isn’t a Go pattern. Also I would avoid interface{} if possible, and the
>>>> function types seem more complicated than necessary. I’m not convinced
>>>> your
>>>> types/API are optimal.
>>>>
>>>> I still don’t exactly understand the goal, but this is my thinking
>>>> about the playground example: https://play.golang.org/p/KNdrYbebpuo
>>>>
>>>> Matt
>>>>
>>>> On Monday, April 23, 2018 at 3:46:03 AM UTC-5, Louki Sumirniy wrote:
>>>>>
>>>>> I spent two hours wrestling with this, but as you can see in this
>>>>> playground, the method I proposed totally works:
>>>>> https://play.golang.org/p/FMvisWS9tuP
>>>>>
>>>>> I propose that the type builtin when dealing with functions should
>>>>> have an extension made to it to add the method binding to the type
>>>>> signature so this workaround is not necessary. It would not break the
>>>>> spec,
>>>>> old code, or any of the goals that Go works towards. It would actually
>>>>> help
>>>>> with getting adoption by OOP programmers, in my view, because method
>>>>> overriding for this exact purpose of enabling the abstraction of backend
>>>>> type stuff (in my case it's just an array, but it could easily be a
>>>>> storage
>>>>> protocol or network protocol) would help immensely in implementing
>>>>> pluggable architectures.
>>>>>
>>>>> On Monday, 23 April 2018 08:23:24 UTC+3, Louki Sumirniy wrote:
>>>>>>
>>>>>> https://github.com/golang/go/issues/24996#issuecomment-383424588
>>>>>>
>>>>>> It seems that (Type).FuncName in the assignment binds to the
>>>>>> struct... I am glad I found an answer so quickly because my hackish
>>>>>> solution was gonna be implemented today.
>>>>>>
>>>>>> On Monday, 23 April 2018 02:20:47 UTC+3, Louki Sumirniy wrote:
>>>>>>>
>>>>>>> You will see in the code I linked in the previous message that I
>>>>>>> already do have the interfaces in there. They can't be bound to the
>>>>>>> struct
>>>>>>> directly because I can't specify a function type that matches the
>>>>>>> signature, thus the use of a wrapper, and the interface types in the
>>>>>>> parameters.
>>>>>>>
>>>>>>> I just can't override them, and the great bulk of the code is not
>>>>>>> these small set of initialiser/allocator/comparator/getter/setter
>>>>>>> functions, so to have to search and replace through the whole thing,
>>>>>>> and
>>>>>>> maintain multiple nearly identical pieces of source code for the sake
>>>>>>> of 7
>>>>>>> functions that are all very short, and differ between these versions,
>>>>>>> when
>>>>>>> everything else is the same... then I find a bug in one version, in the
>>>>>>> outer shell of the code and I have to merge every change of it into the
>>>>>>> other 5 versions... it's extremely cumbersome.
>>>>>>>
>>>>>>> The solution I have shown is just the first thing that looks to me
>>>>>>> like it would work. I have read tons of tutorials about composition and
>>>>>>> polymorphism and embedding in go, and in the end I pieced this together
>>>>>>> from several different things I learned. I tried several different
>>>>>>> things.
>>>>>>> It just makes absolutely no sense to have to go through and add a load
>>>>>>> of
>>>>>>> maintenance work to my code just so I can create, expand, read, write
>>>>>>> and
>>>>>>> compare values stored within the otherwise identical data structure.
>>>>>>>
>>>>>>> On Monday, 23 April 2018 01:44:43 UTC+3, matthe...@gmail.com wrote:
>>>>>>>>
>>>>>>>> Interface types are useful when the data structure is varied. Why
>>>>>>>> not an interface containing these varying functions as methods instead
>>>>>>>> of
>>>>>>>> function types?
>>>>>>>>
>>>>>>>> Matt
>>>>>>>>
>>>>>>>> On Sunday, April 22, 2018 at 5:20:12 PM UTC-5, Louki Sumirniy wrote:
>>>>>>>>>
>>>>>>>>> I essentially am trying to find an effective method in Go,
>>>>>>>>> preferably not too wordy, that lets me create an abstract data type,
>>>>>>>>> a
>>>>>>>>> struct, and a set of functions that bind to a different data type,
>>>>>>>>> and that
>>>>>>>>> I can write, preferably not in too much code, a change that allows
>>>>>>>>> the data
>>>>>>>>> type of the embedded data to be changed. It's basically kinda
>>>>>>>>> inheritance,
>>>>>>>>> but after much fiddling I found a hackish sorta way that isn't *too*
>>>>>>>>> boilerplate filled:
>>>>>>>>>
>>>>>>>>> type nullTester func(*Bast, uint32) bool
>>>>>>>>>
>>>>>>>>> type Bast struct {
>>>>>>>>> ...
>>>>>>>>> isNull nullTester
>>>>>>>>> ...
>>>>>>>>> }
>>>>>>>>>
>>>>>>>>> func isNull(b *Bast, d uint32) bool {
>>>>>>>>> return d == 0
>>>>>>>>> }
>>>>>>>>>
>>>>>>>>> func NewBast() (b *Bast) {
>>>>>>>>> ...
>>>>>>>>> b.isNull = isNull
>>>>>>>>> ...
>>>>>>>>> }
>>>>>>>>>
>>>>>>>>> // IsNull - tests if a value in the tree is null
>>>>>>>>> func (b *Bast) IsNull(d uint32) bool {
>>>>>>>>> return b.isNull(b, d)
>>>>>>>>> }
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Now, bear in mind I haven't shown all of the code. But there is a
>>>>>>>>> slice array in the Bast struct, and I it is defined as an interface{}
>>>>>>>>> and
>>>>>>>>> isNull is one of a set of operators that have to be written to match
>>>>>>>>> the
>>>>>>>>> type used in the slice store, this might be a bad example because it
>>>>>>>>> doesn't actually act on the interface typed slice, but the point here
>>>>>>>>> is
>>>>>>>>> just this:
>>>>>>>>>
>>>>>>>>> It does not appear to be possible to make the type specification
>>>>>>>>> from the top line match the function signature of the type-bound
>>>>>>>>> function
>>>>>>>>> in the bottom of the code snippet. I haven't been able to find
>>>>>>>>> anything
>>>>>>>>> that shows that a func type can have a method binding.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> https://github.com/calibrae-project/bast/blob/master/pkg/bast/bast.go
>>>>>>>>> is where my WiP lives. This slightly hacky solution seems sound to
>>>>>>>>> me, I
>>>>>>>>> just don't like to be forced to use workarounds like this. If a type
>>>>>>>>> signature cannot be written that matches a method, yet I can do it
>>>>>>>>> this
>>>>>>>>> way, I don't see what purpose this serves as far as any kind of
>>>>>>>>> correctness
>>>>>>>>> and bug-resistance issues go. I would have to deal with a lot more
>>>>>>>>> potential bugs if I had to concretely implemennt this library for the
>>>>>>>>> sake
>>>>>>>>> of 1 slice and 7 functions out of a much larger library that
>>>>>>>>> conceptually
>>>>>>>>> is intended to only deal with comparable, mainly numerical values
>>>>>>>>> anyway.
>>>>>>>>>
>>>>>>>>
--
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.
