Valentin, On Mon, Aug 28, 2017 at 3:58 PM, Val <delepl...@gmail.com> wrote:
> @Jakob sorry what I wrote was confusing, I meant : vertices have strong > identity (same pointer), and triangles are just keys for the map so they > need to be very stable. A triangle pointer wouldn't solve the case. When I > encounter 3 vertex pointers A, B, C, then I need a "key" to determine if > triangle ABC (or CAB, etc.) is already in the map. > > @Axel indeed I had not taken into account that the GC may "change the > pointers, while preserving ==" so basically yes ordering pointers looks > unreliable. > > @Kulti checking equality of triangles by checking combinations of vertex > equality would be interesting but it would make the program really super > slow: instead of a O(1) map lookup, each existence check would cost O(n) to > traverse all the existing triangles, which is too slow because we have 1M+ > triangles. This is because we can't use Triangle as a map key when equality > is computed by a func instead of ==. > > @Egon those are nice workarounds, thanks. X,Y,Z are weak, they change all > the time. > > I will try to minimize code clutter, minimize memory and cpu overhead, > maximize safety and readability. So I think the best tradeoff so far is to > add a field Vertex.ID, because I have the chance to do it, though it does > clutter a little a fundamental data structure of the whole program. > not sure if that would help but, in the context of a Delaunay triangulation, we had to implement a few things that sound like related to your issue: - https://godoc.org/go-hep.org/x/hep/fastjet/internal/predicates - https://godoc.org/go-hep.org/x/hep/fastjet/internal/delaunay hth, -s Thank you all for insights! > > On Monday, August 28, 2017 at 3:20:39 PM UTC+2, Axel Wagner wrote: >> >> FTR, I don't think ordering by pointer (no matter whether using unsafe or >> not) is reliable and safe. The GC is free to move data around at any point, >> including during your sort. >> I don't think there are a lot of ways around that. You could basically >> build your own allocator and add a way for it to return a reliable id. e.g. >> it allocates a []Vertex and the id is the index of the vertex in that >> slice. You can calculate it using unsafe by (roughly. No guarantees here. >> Unsafe is subtle) >> >> func ID(v *Vertex) int { >> i := int(uintptr(unsafe.Pointer(v))) - int(uintptr(unsafe.Pointer(&Ve >> rtex[0]))) >> if i < 0 || i > len(pool) { >> panic("not pool-allocated") >> } >> return i >> } >> >> (not that you need to take care to do both conversions in the same >> expression, to satisfy the unsafe.Pointer >> <https://godoc.org/unsafe#Pointer> rules). >> >> Apart from that, Egon gave a couple of good suggestions :) >> >> On Mon, Aug 28, 2017 at 3:02 PM, Jakob Borg <ja...@kastelo.net> wrote: >> >>> In that case, maybe use *Triangle pointers instead of Triangle values, >>> and let that address be the identity for map purposes? Then the Vertex >>> order etc doesn't matter any more. >>> >>> //jb >>> >>> > On 28 Aug 2017, at 14:03, Val <dele...@gmail.com> wrote: >>> > >>> > That's actually a clever idea, I had not thought of that when >>> dismissing the vertex struct inspection. Thanks! >>> > >>> > But it turns out that X,Y,Z will change often during my program >>> execution: vertices move, but their identity (and the triangles identity) >>> must be strongly preserved. >>> > >>> > On Monday, August 28, 2017 at 1:42:35 PM UTC+2, Jakob Borg wrote: >>> > On 28 Aug 2017, at 13:13, Val <dele...@gmail.com> wrote: >>> > > >>> > > To achieve this, I consider normalizing the triplet so that all keys >>> of the map verify >>> > > A < B < C >>> > > for some arbitrary definition of < . This ensures that I can detect >>> any Triangle already present as key in the map, regardless the order of its >>> Vertex pointers. >>> > >>> > Can't you sort the Vertex slice by their X,Y,Z position? (You're then >>> not relying on the coordinates for identity, only for order. This breaks >>> for triangles that are actually lines or points, which may or may not be an >>> issue and can be handled separately...) >>> > >>> > //jb >>> > >>> > -- >>> > 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...@googlegroups.com. >>> > For more options, visit https://groups.google.com/d/optout. >>> >>> -- >>> 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...@googlegroups.com. >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> -- > 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. > -- 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.
