BZComplexForumGalleryBug TrackerWikiBlog
* Login  * FAQ    * Search
It is currently Sat Jan 23, 2021 8:08 am

View unanswered posts | View active topics


Board index » Programmer's Corner » Programming

All times are UTC


Double-indexed arrays in Java



Post new topic Reply to topic  Page 1 of 1
 [ 10 posts ] 
  Print view Previous topic | Next topic 
Author Message
sabrebattletank
 Post subject: Double-indexed arrays in Java
PostPosted: Mon Feb 21, 2011 5:27 pm 
Offline
User avatar

Joined: Tue Feb 09, 2010 12:45 am
Posts: 10
Gender: None specified
Can you have double-index arrays in Java?


Top
  Profile 
 
Nielk1
 Post subject: Re: Double-indexed arrays in Java
PostPosted: Mon Feb 21, 2011 11:52 pm 
Offline
Site Admin
User avatar

Joined: Tue Dec 25, 2007 8:58 am
Posts: 300
Location: New Jersey, USA
Gender: Male
WordPress Blog: Visit User's Blog
What do you mean, a 2D array, or an array where an index, lets say 5 and 9, both point to the same thing?

_________________
"Failure isn't an option. It comes bundled with your Microsoft product."


Top
  ProfileYIMICQ 
 
sabrebattletank
 Post subject: Re: Double-indexed arrays in Java
PostPosted: Tue Feb 22, 2011 5:08 am 
Offline
User avatar

Joined: Tue Feb 09, 2010 12:45 am
Posts: 10
Gender: None specified
An array where there are multiple indices that point to the same thing. OM pointed me towards google, and we had a good chat.

For example:

Code:
deadPeople[4] and deadPeople["bestFriend"] both point to the value "Joe"


http://stackoverflow.com/questions/2501 ... c-solution

http://jackrabbit.apache.org/api/1.3/or ... Index.html

http://lmgtfy.com/?q=multi+index+java


Top
  Profile 
 
Nielk1
 Post subject: Re: Double-indexed arrays in Java
PostPosted: Tue Feb 22, 2011 6:25 am 
Offline
Site Admin
User avatar

Joined: Tue Dec 25, 2007 8:58 am
Posts: 300
Location: New Jersey, USA
Gender: Male
WordPress Blog: Visit User's Blog
Arrays use contiguous integers as indexes. Maps use String or other objects as keys.

As an interesting note, Java DOES have pointers, but not like c or c++. In java, all objects, that means any datatype that does not start with a lowercase letter (those are primitives, int, boolean, char, etc) are objects. Technically String is a hybrid but that is not important. The odd thing with Java is that all function parameters are by value, however, the objects are referenced by memory address. This means the memory address is copied, which means you alter an object in a function that was a parameter it alters the real object. But if you set the parameter to point to another object, this has no effect.

Now why did I explain all this? Well simply, if your array is of Strings or any Object derived type, it is an array of pointers. This means that two of them may point to the same object instance. HOWEVER, the following is also true:

(Note that == used with objects checks the memory address while .equals checks the values, though I do not use it here that can be important. Also, if you define two identical constants in code, they will be optimized to be the same exact mem-address.)

array[1] = new String("foo");
array[5] = array[1];
array[1].append("bar");
System.out.println(array[1]); // foobar, technically a pointer to the String foobar
System.out.println(array[5]); // foobar, technically a differnt pointer to the same String foobar
array[5] = new String("yack");
System.out.println(array[1]); // foobar, same as before
System.out.println(array[5]); // yack, same pointer, but pointing at a now new String

Another important note is that the way Java works, if you set array[1] to point to something else so that the String "foobar" is not pointed to by anything, the garbage collector will delete it. In languages like c and c++ you have to delete that memory manually if explicitly using pointers.

And to better illustrate what I was saying about primitives vs Objects, here is the same code with an integer array:

array[1] = 10;
array[5] = array[1];
array[1]+=15;
System.out.println(""+array[1]); // 25, this is the exact value, not a pointer
System.out.println(""+array[5]); // 10, this is the exact value, not a pointer
array[5] = 75;
System.out.println(array[1]); // 25
System.out.println(array[5]); // 75, note how this time they acted more as you expect they should


Many who use Java do not know that all work is done with By Value operations on literal values for primitives, and By Value operations on the literal ADDRESSES for objects (pointers). Once you understand this, it all makes a LOT more sense. Basically, no object in Java is in the var you say it is. All the var says is "look over there for it", however, operations done on these values all get passed to the real object, EXCEPT assignment operations.

Did you understand all of that? It is a bit of the key behind how Java works.

This btw is why wrapper classes like Integer exists. They are to hold a primitive but be able to use it like an object.

_________________
"Failure isn't an option. It comes bundled with your Microsoft product."


Top
  ProfileYIMICQ 
 
OvermindDL1
 Post subject: Re: Double-indexed arrays in Java
PostPosted: Tue Feb 22, 2011 7:37 am 
Offline
User avatar

Joined: Thu Feb 28, 2008 9:42 am
Posts: 31
Gender: Male
Based on what I was speaking of with him I think he was of something like C++'s multi_index_container.
Multi_index_container actually acts a lot like a database, you have your data 'chunk' and multiple different 'index' fields.

It is *vastly* more powerful then what I demonstrate here, and I started typing that up in this post, but I figured something more directly what he is wanting above would be better to show. As an example, lets combine the fast begin/end insertion of a list with the fast lookups of an array. You'd might jump straight to map, but that has slower aspects then either, plus it has a *horrible* worst case if your data count might be 'huge'.

As an example, read over this linke as it is a fast lookup over a list example. The gist of it is this type:
Code:
typedef multi_index_container<
  std::string,
  indexed_by<
    sequenced<>, // list-like index
    ordered_non_unique<identity<std::string> > // words by alphabetical order
  >
> text_container;


What this gives you is a string value (and you can index into different parts of a struct if you were using a struct, it is pretty infinitely extensible) with a sequenced (std::list basically, although not), and an ordered lookup (like a map, but a map is unordered, this is ordered, there are lots of types). You can mix and match and grow that all you want. The are combined to create the most optimized mix of synchronized containers internally (if you specify, say 10 indexes, but they can be handled internally by 3 synchronized containers, then it will).

As you see, since sequenced<> is the first time listed, the default 'exposure' of the type is identical to std::list (even if internally it is very different). To get the access to the ordered non unique type you call it with .get<1> (<0> is the sequence one) and you can treat that just like the normal object, but with a map kind of semantics (even if internally it is different).

I have used these on various occasions and they have been a tremendous help. This is what I think he is looking for. The various types do not only have to have different access patterns, but they can have different orderings (you can have three list orderings for example, where one is ordered case-sensitive, the second is reversed case-sensitive, and the third is case-insensitive) as well as many other things, exploding into an infinite amount of patterns when the value type is a struct and you can index based on various fields or even mixtures there-of.

If you truly wants an array or map with multiple indices pointing to the same object, he could always just store the same reference in both locations, but that only gives one access pattern and ordering and so forth. Based on the chat in IRC it sounded like he needed different access patterns. I am not sure Java can supply that generically, it would have to be hand built each and every time due to language limitations.


Also, to be technical, Java has references, not pointers.

Say you have this:
Code:
// C++
std::vector<int> vecInt(10, int());
// Java
Vector<int> vecInt; // initialize to 10 default elements however you do it in Java


And you get the first element using whatever:
Code:
// C++
int &val0 = vecInt[0];
// Java
int val0 = vecInt.at(0); // or however it is done


Now, try to get the next element from just this element:
Code:
// C++
int &val1 = (&val0)++; // Pointer arithmetic, do not do this in real code
// Java
I have no clue how, does anyone here know?


Do note, C++ References are not 'true' references like Java references are, C++ references are just pointers, Java References have strict type binding, no pointer arithmetic is allowed.


Another point, as to why the multi-index is not generically possible in Java. In Java it is not possible to mutate functionality at compile time (without some *REALLY* nasty Java assembly hacking, and even then to duplicate the functionality of multi_index in Java would involved writing about a duplicate of the Java compiler, not easily feasible), where as in C++, well, as the example from above:
Code:
typedef multi_index_container<
  std::string,
  indexed_by<
    sequenced<>, // list-like index
    ordered_non_unique<identity<std::string> > // words by alphabetical order
  >
> text_container;

std::string sets the type, basically what the memory 'is' of this type, the first sequenced<> sets how the primary 'type' 'acts' (like a list, even though it is not), and all the ones after it are accessible from the .get<N> (based on index), and what the .get<N> returns is just another proxy of this exact type, but with the 'type' of whatever you asked for (and you can still use .get<N> to get access to yet another type from inside that). That kind of recursive type is impossible in Java, all Types are statically defined.

Edit: Well, I guess it would be 'possible' to emulate with an extensive class hierarchy, but it would be horribly inefficiency compared to the C++ version since the C++ version actually optimizes its type to reduce the amount of duplicates, that would not be possible in the Java version due to the lack of modifiable functionality in types.

EDIT: Also, one more edit, if you do not like the .get<N>, you can also give them names, so something like this works fine: myType.get<byName>

_________________
Image


Top
  ProfileYIMICQ 
 
sabrebattletank
 Post subject: Re: Double-indexed arrays in Java
PostPosted: Tue Feb 22, 2011 4:29 pm 
Offline
User avatar

Joined: Tue Feb 09, 2010 12:45 am
Posts: 10
Gender: None specified
Actually, I just dove into 2d arrays. I'm using them to manage some buttons currently.

We're doing objects today.

Nielk1 wrote:
Did you understand all of that? It is a bit of the key behind how Java works.


Yeah, I followed.

I followed the what. But the why -- my best guess is that it was an optimization decision. Is that right?


Top
  Profile 
 
Nielk1
 Post subject: Re: Double-indexed arrays in Java
PostPosted: Tue Feb 22, 2011 6:54 pm 
Offline
Site Admin
User avatar

Joined: Tue Dec 25, 2007 8:58 am
Posts: 300
Location: New Jersey, USA
Gender: Male
WordPress Blog: Visit User's Blog
sabrebattletank wrote:
Actually, I just dove into 2d arrays. I'm using them to manage some buttons currently.

We're doing objects today.

Nielk1 wrote:
Did you understand all of that? It is a bit of the key behind how Java works.


Yeah, I followed.

I followed the what. But the why -- my best guess is that it was an optimization decision. Is that right?


The why to the why of the what is a mystery.

_________________
"Failure isn't an option. It comes bundled with your Microsoft product."


Top
  ProfileYIMICQ 
 
PostThis post was deleted by sabrebattletank on Sat Mar 05, 2011 5:31 pm.
sabrebattletank
 Post subject: Re: Double-indexed arrays in Java
PostPosted: Mon Mar 07, 2011 3:21 pm 
Offline
User avatar

Joined: Tue Feb 09, 2010 12:45 am
Posts: 10
Gender: None specified
There is a vector class in Java, ( http://download.oracle.com/javase/1.4.2 ... ector.html ), but I haven't really played with it.


Top
  Profile 
 
Nielk1
 Post subject: Re: Double-indexed arrays in Java
PostPosted: Mon Mar 07, 2011 5:43 pm 
Offline
Site Admin
User avatar

Joined: Tue Dec 25, 2007 8:58 am
Posts: 300
Location: New Jersey, USA
Gender: Male
WordPress Blog: Visit User's Blog
Vectors are arrays that re-allocate memory logarithmically when they need to enlarge.

ArrayLists are lists of arrays that simply add more nodes with progressively larger arrays. Thus in a theoretical model, index 8 might mean next()[0], index 25 might be next().next()[1], and other oddities like that. It knows what it really is to speed up the work.

This means a Vector is fast access but ArrayLists are fast insertion (lower space re-allocation time). They have identical interfaces however so many use them interchangeably without thinking of the application.

_________________
"Failure isn't an option. It comes bundled with your Microsoft product."


Top
  ProfileYIMICQ 
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 1
 [ 10 posts ] 

Board index » Programmer's Corner » Programming

All times are UTC


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
      Powered by MediaWiki