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

Groups > comp.lang.java.programmer > #12505

Re: lookup by EnumSet

Show all headers | View raw

On 28.02.2012 14:55, Roedy Green wrote:
> I had a long and annoying dream that there was a Java Collection that
> let you look up by EnumSet.  It was not a simple Map.
>
> It worked something like this: You could assign a set of binary
> attributes to a Person, e.g. male/female, fat, thin, average, atheist,
> Christian, Moslem, Jew, Buddhist. Asian, European, African, North
> American, South American..
>
> Then you could ask for all the fat or average females, Buddhist but
> not Asian.
>
> You might specify an EnumSet for what you want and one for what you
> don't want.  Anything not specified in either does not matter.

You need a multi dimensional index which can efficiently select from any 
subset of dimensions given.  Whether properties are boolean or need more 
than one bit to represent is just a minor challenge here.

> In the dream I was trying to write example code and an entry in the
> Java glossary. When I woke, I could not think of such a class, and
> further it was not obvious how one could be implemented.
>
> I wondered how you would do it.

The most straightforward solution in memory would probably be something 
like Map<${PropertyType},Set<Person>> per property.  Depending on 
application logic you would build these just once when reading the data 
or update indexes whenever you update fields.  Querying would use set 
operations to reduce the set of results.

> I thought you might extract the attributes into an array of longs and
> check each one for compliance with your masks.
>
> If the sets were stable, you might extract a BitSet for each
> attribute, and do logical operations on giant bit strings of the
> relevant bits.

There would be another use for BitSets: you create a BitSet per instance 
which represents key state.  And you store these keys along with the 
data in a Map<BitSet,Person>.  Downside: this only works good for static 
data and exact matches.

> I vaguely recall SQL databases optimising queries of this type by
> transparently building inverse look up indexed.

There are two ways with RDBMS:

1. Create an index for every subset of properties that you want to use 
as filter in a query.  Note: indexes whose columns are a subset of 
another index can be left out if you manage to make those columns 
leading columns.

2. Create a bitmap index (in Oracle) for example.  Bitmap indexes in 
Oracle need coarse grained locks and thusly are not suited for OLTP 
applications - they are usually used in DWH applications.

http://docs.oracle.com/cd/E11882_01/server.112/e25789/indexiot.htm#autoId12

In memory you could do the same although the bitmap type index would 
probably contain references to objects instead of bits identifying 
rowids.  If memory is tight using a BitSet to point into a List<Person> 
or Person[] might be worthwhile.

Kind regards

	robert


-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

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

Thread

lookup by EnumSet Roedy Green <see_website@mindprod.com.invalid> - 2012-02-28 05:55 -0800
  Re: lookup by EnumSet Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-02-28 07:03 -0800
    Re: lookup by EnumSet Roedy Green <see_website@mindprod.com.invalid> - 2012-02-28 15:22 -0800
  Re: lookup by EnumSet Leif Roar Moldskred <leifm@dimnakorr.com> - 2012-02-28 09:27 -0600
    Re: lookup by EnumSet Lew <noone@lewscanon.com> - 2012-02-28 09:31 -0800
      Re: lookup by EnumSet Robert Klemme <shortcutter@googlemail.com> - 2012-02-28 23:08 +0100
  Re: lookup by EnumSet Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-02-28 08:51 -0800
  Re: lookup by EnumSet Robert Klemme <shortcutter@googlemail.com> - 2012-02-28 23:08 +0100
    Re: lookup by EnumSet Robert Klemme <shortcutter@googlemail.com> - 2012-03-01 01:22 -0800
  Re: lookup by EnumSet Wanja Gayk <brixomatic@yahoo.com> - 2012-02-29 11:06 +0100

csiph-web