Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #10634

Re: Sparse sets

Show all headers | View raw

>>>>> "Marcel" == Marcel Hendrix <mhx@iae.nl> writes:

> I have a hard time believing the quoted advantages of sparse sets
> myself, but it is a nice exercise where one can drop in a small Forth
> twist.

Hah, didn't know this data representation trick.  Interesting read.

BTW the sparse set stuff is reminiscent of the Bloom Filter.  Bloom
Filter sets have constant time element insertion and lookup, and
constant memory requirement in the order of set members, not universe
size.  At the cost of allowing false positives (i.e. membership tests
sometimes returns true on an element *not* being in the set, however
when it returns false, you can be sure that an elment is not in the
set).  Usually Bloom Filters are used as a cheap short-cut check for
element membership in cases where you expect a high miss rate.

  https://en.wikipedia.org/wiki/Bloom_filter

cheers,

David
-- 
GnuPG public key: http://dvdkhlng.users.sourceforge.net/dk.gpg
Fingerprint: B17A DC95 D293 657B 4205  D016 7DEF 5323 C174 7D40

Back to comp.lang.forth | Previous | Next — Previous in thread | Find similar

Thread

Sparse sets mhx@iae.nl (Marcel Hendrix) - 2012-03-26 20:49 +0200
  Re: Sparse sets anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2012-03-27 14:43 +0000
  Re: Sparse sets David Kuehling <dvdkhlng@gmx.de> - 2012-03-28 23:41 +0200

csiph-web