[HN Gopher] Sparse Sets (2021)
       ___________________________________________________________________
        
       Sparse Sets (2021)
        
       Author : signa11
       Score  : 10 points
       Date   : 2023-09-01 09:24 UTC (13 hours ago)
        
 (HTM) web link (manenko.com)
 (TXT) w3m dump (manenko.com)
        
       | pipo234 wrote:
       | Interesting Big-O time characteristics, but bit of a pity that
       | addition, removal and membership check require 2 (random) memory
       | accesses. Also, Big-O memory proportional to element type is a
       | bit of a non-starter in many cases.
        
       | pklausler wrote:
       | Same data structure appears in Preston Briggs' 1992 PhD thesis
       | (https://www.cs.utexas.edu/users/mckinley/380C/lecs/briggs-
       | th...).
       | 
       | I have used these fast sets many times over the years, but less
       | often than before because they elicit valid but irrelevant
       | warnings from Valgrind due to the (safe) use of uninitialized
       | data.
        
       ___________________________________________________________________
       (page generated 2023-09-01 23:01 UTC)