[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Keith David Bershatsky
Subject: Re: How to quickly compare equality of structs ...
Date: Mon, 06 May 2019 19:59:43 -0700

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]