impl a collection

V

vicky

I want to know if there is any efficient way to implement something
;like a hashmap which has the entries in the form
(key,valu1,value2).The structure should also work for getting the key
using any one of the values.

any thought on this?? is there any java libraries which implements
this??

-vick
 
M

Michael Borgwardt

vicky said:
I want to know if there is any efficient way to implement something
;like a hashmap which has the entries in the form
(key,valu1,value2).The structure should also work for getting the key
using any one of the values.

any thought on this?? is there any java libraries which implements
this??

HashMap implements this. Use three instances, one with your key as key
and an array with the two values as elements as value, and two with
the respective values as key and the key as value.
 
V

vicky

Using three instances would be very expensive in terms of storage.
jakarta doubleorderedmap might be a good solution if the values are
used in an array.

vick.
 
M

Michael Borgwardt

vicky said:
Using three instances would be very expensive in terms of storage.

Is the number of items really that large or your RAM so small?
Programming ain't magic. If you want to efficiently search for
three fields, you need three indexes, no way around it.
jakarta doubleorderedmap might be a good solution if the values are
used in an array.

You couldn't look for one value then, only a pair. Besides, the
API documentation for that class is misleading in regard to its space
saving. I found the claims (and the concept) intriguing and had a
look at the code. The only space it saves is the object overhead of
the node objects and the second copy of the key and value references,
and some of that is squandered on a pointless caching of hash values.
With an object overhead of 8 bytes that's less than 20% space saved
compared to two TreeSet instances with the same data.
 
J

Job Numbers

vicky said:
I want to know if there is any efficient way to implement something
;like a hashmap which has the entries in the form
(key,valu1,value2).The structure should also work for getting the key
using any one of the values.

any thought on this?? is there any java libraries which implements
this??

-vick

This might sound like a stupid question, but why are you doing something a
database could do for you?
 
K

Kevin McMurtrie

I want to know if there is any efficient way to implement something
;like a hashmap which has the entries in the form
(key,valu1,value2).The structure should also work for getting the key
using any one of the values.

any thought on this?? is there any java libraries which implements
this??

-vick

Use three maps, each with a different object as the key, and all three
sharing the same result Object.

class FooElement
{
final Object key;
final Object value1;
final Object value2;
public FooElement (Object key, Object value1, Object value2)
{
this.key= key;
this.value1= value1;
this.value2= value2;
}
}

final HashMap m_keyMap= new HashMap ();
final HashMap m_value1Map= new HashMap ();
final HashMap m_value2Map= new HashMap ();

void put (Object key, Object value1, Object value2)
{
FooElement f= new FooElement(key, value1, value2);
m_keyMap(key, f);
m_value1Map(value1, f);
m_value2Map(value2, f);
}

Object getKeyByValue1 (Object value1)
{
FooElement f= (FooElement)m_value1Map.get (value1);
return (f == null) ? null : f.key;
}

// etc...

This is a somewhat tedious example so adjust it to suit your needs.
You'll also need to figure out what happens when the mappings aren't
1:1. If your mapping needs to be large, complex, rule-based, shared, or
have persistence, a database is exactly what you'll want. The code gets
to be a mess beyond simple cases like I've shown above.
 
R

Roedy Green

I want to know if there is any efficient way to implement something
;like a hashmap which has the entries in the form
(key,valu1,value2).The structure should also work for getting the key
using any one of the values.

You create a Glue object which contains references (possibly to the
key) and the two data values. Then you do a lookup by key to the Glue
object.


A simple Glue object could be new Object[] pair = { value1 , value2 };

adjust as necessary if value1 and value2 are primitives.
 
J

Job Numbers

Kevin McMurtrie said:
Use three maps, each with a different object as the key, and all three
sharing the same result Object.

class FooElement
{
final Object key;
final Object value1;
final Object value2;
public FooElement (Object key, Object value1, Object value2)
{
this.key= key;
this.value1= value1;
this.value2= value2;
}
}

final HashMap m_keyMap= new HashMap ();
final HashMap m_value1Map= new HashMap ();
final HashMap m_value2Map= new HashMap ();

void put (Object key, Object value1, Object value2)
{
FooElement f= new FooElement(key, value1, value2);
m_keyMap(key, f);
m_value1Map(value1, f);
m_value2Map(value2, f);
}

Object getKeyByValue1 (Object value1)
{
FooElement f= (FooElement)m_value1Map.get (value1);
return (f == null) ? null : f.key;
}

// etc...

This is a somewhat tedious example so adjust it to suit your needs.
You'll also need to figure out what happens when the mappings aren't
1:1. If your mapping needs to be large, complex, rule-based, shared, or
have persistence, a database is exactly what you'll want. The code gets
to be a mess beyond simple cases like I've shown above.

Exactly
 
N

NOBODY

This might sound like a stupid question, but why are you doing
something a database could do for you?


You are truly misleading people. Using a DB for that case is really
overkill, and WILL kill your performance.
 
N

NOBODY

An array costs ~14 +/- 2 bytes , plus the 2 object ref you intent to put
in. that is 24 bytes. Writing an object with 2 fields will cost you 8 bytes
for the object and 2x4 bytes for the refs, 16 bytes total, and you get
compile time safety.

concl.: don't use arrays.




(e-mail address removed) (vicky) wrote in @posting.google.com:
 
N

NOBODY

FYI, start by mutating your strings... let me explain.

If you use strings from a substring operation, you must know that the
new string is just refering to the same char[] but with different
offset/count. That is, if you read a 1k ascii line from a file, then
substring only the first word (let's say from stringtokenizer) then
discard the 1k ascii line, YOU ARE STILL HOLDING the 1000 char string
that takes about 2040 bytes.

If you can't afford this space and agree to get a small perf hit, you
can mutate the string with new String(line.getChars()) in which case the
class is forced to system.arraycopy() the subsection of char[] for you
to protect the immutable string.




(e-mail address removed) (vicky) wrote in
 
N

NOBODY

can mutate the string with new String(line.getChars()) in which case the

Sorry, I meant new String(substring_of_line.getChars())
 
T

Tony Morris

NOBODY said:
FYI, start by mutating your strings... let me explain.

If you use strings from a substring operation, you must know that the
new string is just refering to the same char[] but with different
offset/count. That is, if you read a 1k ascii line from a file, then
substring only the first word (let's say from stringtokenizer) then
discard the 1k ascii line, YOU ARE STILL HOLDING the 1000 char string
that takes about 2040 bytes.


No you aren't.
Where are you receiving this false information?

--
Tony Morris
(BInfTech, Cert 3 I.T.)
Software Engineer
(2003 VTR1000F)
Sun Certified Programmer for the Java 2 Platform (1.4)
Sun Certified Developer for the Java 2 Platform
 
R

Roedy Green

An array costs ~14 +/- 2 bytes , plus the 2 object ref you intent to put
in. that is 24 bytes. Writing an object with 2 fields will cost you 8 bytes
for the object and 2x4 bytes for the refs, 16 bytes total, and you get
compile time safety.

concl.: don't use arrays.

You can get 512 MB of RAM for about $60 US on Ebay.

The cost of that RAM overhead you are so upset about is

is $.0000018

And it is reusable.

Granted you are possibly an old fart like me and can easily remember
when RAM prices first dropped below $1 million per megabyte, but they
CONTINUED dropping.

back then it would have cost you $15.25.

People are still often acting as if nothing changed.
 
R

Roedy Green

If you can't afford this space and agree to get a small perf hit, you
can mutate the string with new String(line.getChars()) in which case the
class is forced to system.arraycopy() the subsection of char[] for you
to protect the immutable string.

on the other hand if you are going to process the whole thing as a
zillion substrings then discard it all, it is more efficient NOT to
use new String. You save the overhead of all that copying and wasted
duplicate RAM.

another option is intern.

See http://mindprod.com/jgloss/intern.html
 
R

Roedy Green

can mutate the string with new String(line.getChars())

That's a bit of a misnomer. Nothing is changed. All you do is make an
immutable copy of part of the original String.

What you are doing I called "unencumbering" the string.
 
R

Roedy Green

No you aren't.
Where are you receiving this false information?

It is correct. Go look at the code for substring.

and similar code for StringBuffer.toString.
 
T

Tony Morris

Roedy Green said:
It is correct. Go look at the code for substring.
and similar code for StringBuffer.toString.

The original statement was generalised - the topic of this forum is Java so
it was assumed that the statement was related to Java, in which case, it is
incorrect.

Is there a particular VM implementation that behaves in that fashion?
No VM implementation that I am looking at causes that statement to become
true (even after being given a context).

--
Tony Morris
(BInfTech, Cert 3 I.T.)
Software Engineer
(2003 VTR1000F)
Sun Certified Programmer for the Java 2 Platform (1.4)
Sun Certified Developer for the Java 2 Platform
 
S

Sudsy

Roedy Green wrote:
You can get 512 MB of RAM for about $60 US on Ebay.

The cost of that RAM overhead you are so upset about is

is $.0000018

And it is reusable.

Granted you are possibly an old fart like me and can easily remember
when RAM prices first dropped below $1 million per megabyte, but they
CONTINUED dropping.

back then it would have cost you $15.25.

People are still often acting as if nothing changed.

Roedy: I hate to mention this, but you're one of those people.
You recently ranted against XML. We can now justify using a text-
based interchange format precisely because the costs of memory
and bandwidth have dropped. We previously used various encoded
formats simply because it was cost-effective. When you've only
got 2.4 Kb of bandwidth then you've got to pack as much data as
possible into short messages. It's not so important when you're
using 2 Mb/s (T1/DS1+) links to the 'net.
XML combined with base64 encoding also accomodates encryption,
enveloped, enveloping, whatever. It's a prudent choice for extra-
net communications. As a text-based format, it also lends itself
well to secure communications using HTTPS.
Kind of ironic that you mentioned one of the primary motivators
for the adoption of XML, eh?
 
R

Roedy Green

Is there a particular VM implementation that behaves in that fashion?
No VM implementation that I am looking at causes that statement to become
true (even after being given a context).


Hmm. The String class code has changed. The new code avoids pinning
large blocks of RAM, but it does more System.arrayCopys.

public String substring(int beginIndex, int endIndex) {
if (beginIndex < 0) {
throw new StringIndexOutOfBoundsException(beginIndex);
}
if (endIndex > count) {
throw new StringIndexOutOfBoundsException(endIndex);
}
if (beginIndex > endIndex) {
throw new StringIndexOutOfBoundsException(endIndex -
beginIndex);
}
return ((beginIndex == 0) && (endIndex == count)) ? this :
new String(offset + beginIndex, endIndex - beginIndex,
value);
}

Note that new String does not necessarily make a copy, though it does
create a new String object.

public String(String original) {
this.count = original.count;
if (original.value.length > this.count) {
// The array representing the String is bigger than the
new
// String itself. Perhaps this constructor is being
called
// in order to trim the baggage, so make a copy of the
array.
this.value = new char[this.count];
System.arraycopy(original.value, original.offset,
this.value, 0, this.count);
} else {
// The array representing the String is the same
// size as the String, so no point in making a copy.
this.value = original.value;
}

Similarly to the way a StringBuffer temporarily gets turned to a
String after a toString until it is changed is gone.

The question now is, when did it change?

This is the sort of thing I would have dug into in Java 1.0.2 days.

It happened somewhere between then and Java 1.4.2_04.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,769
Messages
2,569,580
Members
45,055
Latest member
SlimSparkKetoACVReview

Latest Threads

Top