Re: How to quickly compare equality of structs ...

[Keith David Bershatsky <esq@lawlist.com>]

Thank you, Stefan, for your insight regarding this issue.

I was thinking that if each fake cursor had a unique key based upon the x/y coordinates, then I could reduce my comparison for each fake cursor to just one (1) potential match.

If for example, the old cache contains a fake cursor with an x of 0 and a y of 3, then the key is 9.  I would search the new tentative cache for a key of 9 -- if none is found, then this fake cursor must be erased.  If a key of 9 is found in the new tentative cache, then proceed to do one of the methods suggested by Paul -- i.e., "compare each member of the struct" or use memcmp (provided that memset was used when initializing to remove padding).  Once that comparison is done, the fake cursor is deleted if there is no exact match; or, left right where it is if there is an exact match.

With an arbitrary estimated need of approximately 250 or so fake cursors for any live window, a "for" loop to search for a unique key in the new tentative cache is probably sufficiently effective.  I was; however, also thinking about the possibility of using a key in the context of a hash table if that would be more prudent.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

> From:  Stefan Monnier
> Subject:  Re: How to quickly compare equality of structs ...
> Date:  Mon, 06 May 2019 20:49:23 -0400
> 
> > This afternoon, I came across the Cantor's Pairing Function that can be used
> > to create a unique ID for each fake cursor.  With that unique ID, I can
> > limit the quantity of comparisons ....
> >  n = ((x + y)*(x + y + 1)/2) + y
> 
> Not sure why you care about limiting the number of comparisons.
> Replacing two comparisons with one-comparison-plus-two-mults (and
> reducing the range of x and y to sqrt(MAXINT) along thre way) doesn't
> sound like much of a win.
> 
> 
>         Stefan