True multidimensional arrays - Java SE (Archived)

You say we don't need a full-blown FORTRAN clone because "less than 1% of Java apps need this kind of functionality."
I feel completely sure that less than 1% of Java applications need multi-dimensional array support beyond the int[][]..[] support that already exists. I know I've never written a Java application that needed this.

Why can't you just wrap a one dimensional array in a class and provide methods to make it look like it's multi dimensional?

Maybe you don't use multi-dimensional arrays directly, but things like graphics are full of them. So if this feature brings faster access and smaller matrixes, it would lead to applications with lesser memory footprint and better GUI for everyone, for example..

I second this wrapping idea. That way it is very easy to do light weight slicing and sectioning.[/i]

Exactly my thought as well,
arr[1, 2]
  is same as
arr[1 + 2 * width]
However, since adding it would only be syntactic sugar, it would be easy to add and not break anything..
Whatever.. :)
Cheers,
Mikael

> I feel completely sure that less than 1% of Java
> applications need multi-dimensional array support
> beyond the int[][]..[] support that already exists. I
My point is that 99% of nontrivial Java apps use square arrays-of-arrays, and we seem to agree up to this point; now ALL these apps (if updated to use MD arrays) would become simpler, run faster and use less memory. And like others noticed, even if you don't use arrays of any kind, or use only a few small arrays so the benefits would't appear in your radar, you may depend on libraries that use large/complex arrays and you would benefit indirectly.

In terms of scientific computing , yes we do need them.

I'm all in favour of multidimensional arrays, because adding a new type of array should enable other improvements which can't quite be done with existing arrays:
1. Make arrays fully-fledged Collections (and integrate them with generics):
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4654312
2. New arrays could support one of the various proposals for lightweight objects. If you have huge array of Points, say, it's much more efficient for each Point to be stored 'inline' in the array instead of as separate objects referred to by the array. This fits well with schemes which disallow null references to lightweight objects.
IMHO a new type of array would have enough new benefits that existing arrays could be semi-deprecated, though obviously they should easily interoperate with the new ones.

BTW the classic example showing the need for multidimensional arrays and lightweight objects in combination, is a matrix of complex numbers. If these were stored as a block of memory containing the Complex fields directly (not references to separate objects), it would be very efficient.
Java at the moment would handle these very inefficiently:
* Existing arrays allow the possibility of aliasing, because in an array-of-arrays, two subarrays might be the same object. This creates CPU bottlenecks.
* Wasted memory because you need both an array of references, and a separate object for each reference to refer to, with extra headers
* Wasted time because you need to create, and later garbage collect, each separate Complex object.

Put me down for some of those multidimensional arrays, and lightweight objects too.  Sounds good to me.

Related

dynamic resizing array-like class

I asked everyone I know at my company, searched the online Java docs, searched this forum with a few select keywords in various combinations, and the general consensus is that Java does not have what I want in the standard library and language.
Specifically, I want the functionality of the C++ vector function resize. It sets the size of the vector, not the capacity. For example, in C++, I can write:
vector<int> x;
x.resize(5);
x[4] = 1;
x.resize(10);
x[9] = 1;
I realize that I could write my own class to do this very easily. I also realize I could accomplish the same thing by appending x times. I am asking if there is an efficient way to do this with the standard Java language and libraries, as otherwise it is hard to get the rest of my company to adopt my new class, to make sure it's just as fast as ArrayList, etc. I'm not a library writer, nor do I claim to be one.
I am posting here to ask if I overlooked something, and there is a built in class or language feature to do this Java. If there is not, then the point of this post is to put pressure on the Java developers to add basic functionality to a class that seems to be an attempt to mimic the c++ vector.
The reply I received most from some Java people is that resize is not needed functionality. They say you could write it differently to avoid needing resize. I disagree.
My real world use case is the following.
I need to be able to read from a file into a 2 dimensional array of integers. From another file, I read in some metadata which specifies some rules to apply to this data to receive another 2 dimensional array of integers. For example, it could be as simple as "read in this n x 2 matrix, and produce a new n x 1 matrix which is the sum of each row". Then suppose these rules could be applied after another. Because these rules are defined by the user, it would be non-trivial to refactor the code to make sure the rules visit the entries in the resultant matrix in the correct order as the rules are specified by the user (and even if it were possible, it would be unnecessary, as I have a working algorithm already). Moreover, such a change could require a change to our APIs, which is quite unacceptable. So I need a resizing array-like class which is possible to set its size so that I can visit the elements in an arbitrary order.
I'm pretty sure there are ways to change it to not need a dynamic resize, but those ways would be no more efficient, and they would not be as easy to understand as they are less obvious.
I'm sure plenty of other cases exist.
I'm also sure that there exists cases where it is not possible to convert it to not needing resize, able to use standard language features and classes, and still be as efficient. 
Well, your first problem is that any java collection is only going to hold Integer instead of int. are you okay with that? if not, then you may be best writing your own implementation. if your implementation does not need to be a proper "List", it would be fairly simple to implement a very basic dynamicly resizing array/matrix.
If you want to leverage an existing class, "commons primitives" has an ArrayIntList which should almost fit the bill:
http://commons.apache.org/primitives/api-release/org/apache/commons/collections/primitives/ArrayIntList.html
it doesn't have the resize() method, but you could either:
- copy the code and modify it to suit your needs (the apache license is very liberal)
- do something slightly hacky like the code below:
public void resize(int newSize) {
  if(size() < newSize) {
    ensureCapacity(newSize);
    Field sizeF = getClass().getDeclaredField("_size");
    sizeF.setAccessible(true);
    sizeF.set(this, newSize);
  }
}Edited by: jtahlborn on Mar 31, 2008 10:16 PM
Edited by: jtahlborn on Mar 31, 2008 10:20 PM 
java.util.Vector will do what you've asked. setSize() is the equivalent of resize(). As was pointed out, it too will store Integer objects instead of int primitives. It also has the disadvantage of being synchronized so there's a bit of a performance penalty. 
Well, the int in my example was somewhat for show. It could and will include other data types. My alternative at the moment is to do appends in a for loop, which depending on if the java compiler can optimize away the critical sections in vector, it'll be faster.
Which further begs the question, why is this function not in ArrayList? 
JoshInnominate wrote:
Well, the int in my example was somewhat for show. It could and will include other data types. My alternative at the moment is to do appends in a for loop, which depending on if the java compiler can optimize away the critical sections in vector, it'll be faster. Instead of appends, you could do a little trick that may be quicker:
theArrayList.addAll(Collections.nCopies(noOfEntries, null));The nCopies() method will not create a real List but some immutable container, so it's fast (it may need some Generic argument, if it does not infer properly).
The addAll() will make the ArrayList update it's capacity based on missing.size() and do the "append" for you.
You could actually subclass ArrayList and add a "setSize" method using the above trick for increasing the size.
Which further begs the question, why is this function not in ArrayList?Good question. Maybe the authors didn't think of it being desirable. 
JoshInnominate wrote:
Which further begs the question, why is this function not in ArrayList?Beause in general usage, there's no need to set the size. The size is an implementation detail. As a List implementation, all it really needs to do is add, remove, iterate. The notion of adding a bunch of elements to the end of the list and populating with a default value is not a common use case.
Given that the Java language provides no direct way to do that anyway, at some level you'll have to do a bunch of setting in a loop, unless the initial values you want are default values. But of course, then you'd still have to either copy over the old values to the new larger array, or maintain a list of arrays that are exposed as a single list. 
First, I disagree with jverd when he says size is an implementation detail. Size is exposed to the user. I know if the ArrayList has 100 size or 0 size. It determines whether "get"ting or "set"ting throws an out of bounds exception. Capacity is much more of a implementation detail than size.
jverd does raise an interesting point concerning what a "List" should do, which is where this discussion is heading. I felt that ArrayList is analogous to vector, as I was seizing on the "Array" part, and the lack of any other suitable standard data structure, whereas jverd et al put more stock on the "List" part. But this is not a linked list; Java has an implementation class for that. A List in Java is an ordered sequence of Objects, very much like the C++ definition of sequence containers, including std::vector, std::deque, and std::list (a linked list).
jverd, when you say Java has no direct way of letting you do that, I do not understand. It does. I could use the canonical implementation to do it very much like the implementation of std::vector. It already must do exactly that under the covers. I'm sure ArrayList.add is implemented in the canonical way, doubling the array when the size reaches the capacity, then copying over the data to the new array. To add in the setSize function, it would just potentially increase capacity (which it must already be capable of doing), change the size member variable, and if the size increased default the new Object references to null.
Finally, and perhaps most importantly, jverd echoes the common theme of replies I get from Java people, "Why would you want to do that?" I suppose it's not the most common of use cases, to require a data structure that can dynamically resize to an arbitrary size with some default or garbage value (default in the case of Java). Going back to stefan.schulz, I think it's not there because of some (potentially misguided) attempt by Java designers to protect the programmer from bad algorithm choices, which I think is wrong. Then again, I am a C++ guy, so my opinion is probably already moot. 
JoshInnominate wrote:
Finally, and perhaps most importantly, jverd echoes the common theme of replies I get from Java people, "Why would you want to do that?" I suppose it's not the most common of use cases, to require a data structure that can dynamically resize to an arbitrary size with some default or garbage value (default in the case of Java). Going back to stefan.schulz, I think it's not there because of some (potentially misguided) attempt by Java designers to protect the programmer from bad algorithm choices, which I think is wrong. Then again, I am a C++ guy, so my opinion is probably already moot.Your opinion is not moot of course, but you have to realize that Java and C++ indeed have quite different approaches to development and evolution of the language and the libraries.
C++ tends to do everything for everyone as long as you are willing to investigate quite a bit of time to learn all the details. C++ is more complex than Java. That's fine. It's not automatically a disadvantage.
A good example is evolution of the langue: When I look at the last revisions of Java (1.4, 5.0 and 6.0) and what new language-level features they introduced, then I don't see a lot of chnages:
1.4: asserts: nothing more than glorified debug code
5.0: generics (the biggest thing! still only syntactic sugar), enums (nothing too special, they are just classes), the for-each loop (again: more syntactic sugar)
6.0: nothing? (apart from minor changes in how #Override is handled)
And even then I see lots of people claiming "feature-X killed Java! Oh noes!!!!111!!!one"
So in general the changes are very conservative and tend not to change how development is done in any major way.
When I compare that list to the list of features planned for [the next C++ standard|http://en.wikipedia.org/wiki/C%2B%2B0x], then I see some rather major changes (I'm skipping many items, read the article for details):
* lambda functions and expressions
* Concepts (a major change/addition in my opinion!)
* User-defined literals (interesting stuff, seems like a major language change to me)
* tons and tons of smaller changes
While C++ seems to aim for "give all the power that the language can handle", Java aims more for "give all the power that the average developer can handle". You might say it's dumbed-down, I prefer to call it streamlined.
So yes, the absence of the methods you want is probably due to different targets in C++ and Java.
Then again the wonderful thing about the List interface is, that nothing stops you from implementing your own List with all the features you want and as long as the List contract is fulfilled you can use it wherever a List (or Collection) is used in any Java library. 
Plus: if I wanted to add 10 null values to a List, then I'd write something like this:
myList.addAll(Collections.nCopies(10, null));And I can be pretty sure that this will implemented in a pretty efficient way (probably not the most efficient way possible, but still) and the code reflects my intent quite clearly. 
Honestly, i think the biggest disconnect is that since an ArrayList acts like a Vector, you are treating it the same way. By your own admission, you are looking for a sparse matrix implementation, not a list. you have seized upon ArrayList as part of the implementation because it implements a dynamically sized array. however, as others have pointed out, that is an implementation detail of the ArrayList implementation (which happens to have good performance characteristics in many common list usage scenarios). instead, you should be looking for a sparse matrix implementation. i don't believe there are any in the jdk, but i would bet that a google search would turn up any number of open source packages with various types of matrix implementations (probably for math-type libraries). 
Going back to stefan.schulz, I think it's not there because of some (potentially misguided) attempt by Java designers to protect the programmer from bad algorithm choices, which I think is wrong. Then again, I am a C++ guy, so my opinion is probably already moot. This is a common frustration I've heard from C++ developers trying to use Java so know that you're not alone in this. Which philosophy is better? I'll let the other, smarter, know-it-alls argue about that. I drank the kool-aide a long time ago and all I can say is that I prefer Java.
Honestly, i think the biggest disconnect is that since an ArrayList acts like a Vector, you are treating it the same way.
instead, you should be looking for a sparse matrix implementation. i don't believe there are any in the jdk,The JavaDoc tells you to treat them the same way. From the first paragraph of the ArrayList Javadoc: "This class is roughly equivalent to Vector, except that it is unsynchronized."
Also, isn't the java.util.Vector class a 1D sparse matrix implementation?
I think one problem is that Java treats a Vector like a List (when it really shouldn't). Then again, Java considers Vector to be a "legacy" class retrofitted to the Collections Framework... so maybe they really don't want Vector being used like a C++ vector. 
James_Schek wrote:
The JavaDoc tells you to treat them the same way. From the first paragraph of the ArrayList Javadoc: "This class is roughly equivalent to Vector, except that it is unsynchronized."
Also, isn't the java.util.Vector class a 1D sparse matrix implementation?
I think one problem is that Java treats a Vector like a List (when it really shouldn't). Then again, Java considers Vector to be a "legacy" class retrofitted to the Collections Framework... so maybe they really don't want Vector being used like a C++ vector.Sorry i was a bit unclear here. i'm saying that the java ArrayList and Vector are not really the same as the C++ vector. the c++ vector is really designed to be a dynamic array, which means that you can use it like a list, and you can use it like an array. the java Vector really just copies the "list" part of that (albeit using a similar internal implementation). in many cases, a list and an array can be used for similar purposes. however, when you start talking about matrices, the c++ vector may still make sense, but the java Vector probably does not. 
jtahlborn wrote:
Sorry i was a bit unclear here. i'm saying that the java ArrayList and Vector are not really the same as the C++ vector. the c++ vector is really designed to be a dynamic array, which means that you can use it like a list, and you can use it like an array. the java Vector really just copies the "list" part of that (albeit using a similar internal implementation). Yeah, the ArrayList is definately not a C++ vector. I still think the Java Vector is a fairly similar to a C++ vector.
Vector javadoc:
"The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created."
Also, as far as functions:
vector::resize() = http://java.sun.com/j2se/1.4.2/docs/api/java/util/Vector.html#setSize(int)
vector::reserve() = http://java.sun.com/j2se/1.4.2/docs/api/java/util/Vector.html#ensureCapacity(int)
I think resize() is what makes it like a C++ vector. The ArrayList is missing that function which really makes it a list.
however, when you start talking about matrices, the c++ vector may still make sense, but the java Vector probably does not. I agree with you here, though mostly because of the autoboxing/unboxing performance hit on primitive types. 
Again, my use case has the function setting every entry of the resultant matrix. It's not a sparse matrix. It's because the rules are user specified that I cannot easily predict the order of writing to the resultant matrix.
I'd also like to emphasize a point of mine that didn't seem to be addressed. From Sun's docs:
+[List] An ordered collection (also known as a sequence). The user of this interface has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list.+
java.util.List is, by doc and visible intent, exactly a sequence container. ArrayList, by name, intent, and asymptotic time guarantees, is exactly what std::vector is. I see some direct parallels, c++ sequence container and java.util.List, std::vector and java.util.ArrayList, std::list and java.util.LinkedList. 
It sounds like java Vector does what you want with the setSize() method. are you looking for something more than that?

High speed Java: any performance improvement info?

Are there any articles about how to write Java code for optimal speed performance? My requirements are
- pure Java (no JNI usage)
- memory usage not (very) important => usage of caches to hold database data
I'm looking for some discussions about whether to use/avoid objects (instantions), many (clearly structured) methods, etc. In Brief: if one object holds all data it needs (i.e. no access to external data like file, jdbc, etc.), what's the fastest way to process them? (Avoid inner classes? Avoid object creation? Avoid many methods and write less but bigger methods? Use many global fields? Reuse Objects (by clearing its fields)?
http://www.javaperformancetuning.com/ 
Are there any articles about how to write Java code
for optimal speed performance?The all-time winner is: Identify the performance bottleneck and remove as much as possible from the innermost loop. Let it run in a small method to encourage Hotspot compiling.
does this mean, that small methods are more likely to be compiled/optimzed by the HotSpot VM? So, it's better to have more small methods than less big methods? 
if you really care about performance than you'll need to target
your applications at different os's anyway, to make use of the
fastest things on each (hence: no java).
if you don't care that much, then if your application is written well
(i.e. not crap) then i imagine you would be making the most of
java anyway.
it's probably more beneficially to write a application in a nice oo-way
and not chuck everything in a gigantic class with global variables all
over the place.
most speed benefits will come from the most effective algorithm
and design, not the language. If you are concerned about that
slight difference, (i.e. algo in java vs algo in assembly) then you have
to bite the bullet and write it in the other language; but don't forget
about all the nice features of java you leave behind...
in short: just design the app well and choose the best algos and it'll be fast 
my question is not philosophical. we already have a server application written in Java. there are several "plug-in" modules to process different kind of data. now there is a new module to implement (that of course has to run in the exsitign java server environment) that is not very complicated but has one important request: processing of on data record in about less than 2 seconds. basically each "record" first reads some data from SQL, then starts processing (calculations) and finally writes the results back to the database. For the first part, i once read all data into an internal cache (basically a 2dimensional Object array. For the last part, i use prepared statements/batch updates. The critical part is the calculation which uses quite simple mathematical operations but quite a lot of them. So' I'm looking for optimizing them (without using JNI or such - pure Java). The goal is not "as fast as possible" but "as fast as possible in Java". 
i once read all data
into an internal cache (basically a 2dimensional
Object array. For the last part, i use prepared
statements/batch updates. The critical part is the
calculation which uses quite simple mathematical
operations but quite a lot of them.It's impossible to say something general other then I already did. If you want more specific hints you'll have to post the relevant code section.
my question is not philosophical.and my answer was not philosophical. 
It's impossible to say something general other then I
already did. If you want more specific hints you'll
have to post the relevant code section.Well, the code doesn't exist so far, i'm in the architecture phase of this module. I just want to implement the calculation code with speed as the first priority from the beginning. Therefore i ask about general rules of what to avoid and what to do for fast processing. One point i already read is to have small methods to make the HotSpot compiler happy. In annother thread i read that ArrayList is faster than Vector (but which is thread safe). I try to avoid such things as Vectors and Lists and prefer arrays, if possible. I also have to investigate if calculate with float or double values is good enough so that i don't need objects like BigDecimal. I'm looking for such hints.
Well, as UJ said the most important general rule is use fast algorithms. Other than that and the things you've already said, have you looked at the link supplied? It probably mentions things like object pooling, caching, and other ideas. 
If all you're doing are standard mathematical operations on base types, your program won't be slower in Java than in other languages. According to recent benchmark results, the latest Java VM's are equal or faster on average than most C/C++ compilers. This is due to the advantages of dynamic compiling (VM's with optimizations for a given architecture vs. C programs trying to be portable, etc.) and other features of Java such as garbage collection.
If you're using objects such as lists, integer wrappers, BigDecimals and suchlike, and you really want speed, you must be careful. Be aware that object creation is quite expensive, you shouldn't be creating objects all the time, share them when possible. Also, wrappers and lists take up space, and spending lots of memory makes programs go slower (remember the cache and all that). An array of 10 int is 4 bytes per int * 10 ints = 40 bytes, plus an object shell, plus an int for the length = something like 60 bytes. A list of 10 Integer is 4 bytes per reference to Integer * 10 references = 40 bytes, plus 10 object shells for the Integer, plus 10 ints... it can go easily beyond 120 bytes.
As they told you, some collection classes are inherently faster than others because they are unsynchronized. And also watch for different implementations of the same type of collection (an ArrayList and a LinkedList don't work the same way!)
Anyway, don't think too much about optimizations at first, most of the times it's better to code the algorithm and then run a profiler to see where exactly the bottlenecks are. You can guess that with experience, but it's frequent to get surprises anyway. 
I read an article in the JDJ once about writing real-time Java applications. The goal was to minimize big pauses caused by the Garbage collector down to a set tolerance. This requirement fed a design that was pretty non-intuitive. Is that the kind of thing you are looking for? 
Be aware that object
creation is quite expensive, Says who? Seriously, what's your reference for this statement? 
Says who? Seriously, what's your reference for this statement? http://www.oreilly.com/catalog/javapt/chapter/ch04.html
http://www.javaworld.com/javaworld/jw-02-2001/jw-0223-performance.html
Anyway, my statement shouldn't be taken literally... What I mean is that it's expensive to create lots of small objects, so sometimes sharing, caching, or using things like copy-on-write proxies or the Flyweight design patterns helps performance.
Well, Object creation is time consuming on two fronts. When the Object is created and when it is GC'd. The longer the Object hangs around, the longer it takes to GC (basically.)

locks: Object versus empty byte array

Hello,
In the book "Practical Java", Peter Haggar suggests using an empty byte array instead of an Object as a lock (see pages 169 and 170). Since an array is an Object, this indeed is functionally correct.
He claims that a byte array is cheaper, because the generated byte code is smaller, which indeed is correct for the java compiler I use.
Further, he claims that constructing an empty byte array is faster than creating an Object, because no constructor is called. But this seems to contradict the fact that an byte array is an Object (and therefore should also be initialised when it is created).
I have performed some measurements with two Java Virtual Machines (SUN JDK 1.3.0 and a VM on an embedded device, which is based on SUN's VM). These measurements show that creating an Object is actually slightly faster than creating an empty byte array. Further, it shows that an empty byte array is at least the size of an Object and on SUN's VM it is even bigger (16 bytes for byte array versus 8 bytes for an Object)!
As far as I know (I have searched these forums and searched in a number of books) it really depends on the implementation of the Virtual Machine whether an empty byte array is worse than an Object. The only advantage is that the generated byte codes are smaller, which might be an advantage for embedded systems.
Therefore, to decide between empty byte arrays and Objects, one should take into account the size of the generated byte codes and measure the speed and used memory. Depending on the goal (speed, memory size, and/or code size) a choice can be made.
(About "Practical Java", page 169: I think that the newarray byte code on many Virtual Machines implicitly calls a constructor. This shows that performance of bytecode does not depend only on the number of bytecodes to be executed, but also on the bytecodes itself! Probably, the newarray bytecode consumes a lot of time compared to other bytecodes!)
Can anyone give me more information on how arrays are implemented by a Virtual Machine? As far as I know, the JVM specification leaves it up to the JVM implementers to choose an implementation...
Greetings,
     Sander Kooijmans 
Most VMs optimize array creation/construction, but as you correctly assume there remains initialization overhead. I'm not sure how much of the overhead can be optimized away. Regardless, I would argue most designers should not fret over the efficiency between object and array construction esp. in the context of locking strategies. In other words the lock's construction overhead is miniscule compared with the overall complexity of the locking algorithm. 
That's such a small amount of space and time. I don't think it's worth bothering about. Optimizations like this one, which don't save you anything worth speaking of, just muddy up your code. 
I agree with Jetset_Willy.
Besides, I consider it as good style to use an Object where it suffices, that is, where only the facilities provided by a generic Object are needed as typically locking. Anything "more" than a plain Object is an unnecessary artifact.
While it might (or might not) have been true for a given version of a virtual machine that a byte array was faster to create than a plain Object, this "advantage" weighs less then the style and even if it was there, it disappeared since. 
Concurrent Java Programming - you might want to read it. 
Concurrent Java Programming - you might want to read
it.What does that have to do the the question? Does Doug Lea specifically address this point? If he does, where is it and in which edition? Just telling him to read a rather large and complex book is not of much use.

Need help planning the structure of my program

Hi, I'm not very experienced in Java programming, I have written 2 bigger programs so far and now I face the challenge to simulate a system consisting of thousands of objects - efficiency of my code is very important.
I won't go into the details of what I'm doing because it probably wouldn't interest you at all, but I'll simply explain the technical details and my first idea of the program.
I'm simulating a system which consists of thousands of objects. New objects are constantly added to the system, existing objects are constantly decaying and need to be deleted, some objects merge together etc. All these objects are of the same type (same class, just different parameters).
These objects live in space which is divided into grid cells (there will be a lot of them as well). During the simulation at each time step I will need to check how one of the objects interacts with each other objects in neighboring grid cells.
The order in which the objects move depends on a special parameter. This parameter will change for one of the objects after each time step. So, the objects will have to be sorted according to this parameter.
And I thought of dealing with this problem the following way:
Firstly the grid: I thought of making a 2 dimensional array of GridCell objects and every time an object goes into a grid cell I will create a reference to it in the grid cell. I'm not sure if this is possible though because I have never used references and i'm not sure how do they work in practice. I just found this in the java documentation:
[JAVA API - Reference|http://java.sun.com/j2se/1.4.2/docs/api/java/lang/ref/Reference.html]. So I thought that a GridCell object could just be an object that has a vector of references in it. Can you give me a hint how references are made in practice (this is very confusing)?
And for the the objects I will be simulating I thought of using the SortedList. But there will be thousands of objects in the list and at every time step, when the parameter of an object changes the computer will have to re-sort the list. Would it be better If i just make the objects separately of the list and just make a list of ParameterObjects which would only have information about this parameter of interest and references to objects? Would that be easier for the computer to deal with? I found a tutorial on sorted lists and another question arose: should I make a linked list or just use the array implementation? Which one would make more sense in this case.
Thank You in advance for any suggestions, I'm really not sure how to deal with this simulation at this point. 
If you've ever written any non-trivial Java program, you've used references. Look:
String name = "Bob";"name" is a reference to an object of type String.
Maybe you meant something like weak references...but they don't sound appropriate for your project.
You have a reference to an outdated version of the JDK. Poke around the Sun site for the latest version.
There is no standard class called "SortedList". There are lists; you can sort them. Anyway I didn't see anything in your description which suggested a need to sort any lists.
As for the rest of your description... it's all hand-waving and I don't see how anyone could derive any conclusions from it.
I'd suggest that you take a step back and:
1) read some more introductory tutorials
2) look at the requirements for this project and think about what it needs to do rather than implementations. It seems like you're letting yourself get overwhelmed by worries about potential problems and you're trying to come up with solutions to things that aren't actually problems yet. Just come up with a clean design in which each part has well-defined responsibilities, and in which the relationships between the parts are clear. Don't even think about implementing them yet, just work out these responsibilities and relationships. 
I agree with the previous post. I think it would be better use of your time designing a good system than worrying about performance issues at this time. After you get your system to work as you want, refactor it over and over to get a cleaner design. Only then look at any bottlenecks. Today's computers are very fast and have a lot of memory to use. If your system does crash because of memory, search google for 'java -xmx' on how to let your program use more memory. I know of a lot of developers that make their programs too complicated to understand by others by trying to optimize small performance gains.
As for using references, all your object manipulations such as putting them into some type of collection and sorting them don't actually move objects around. They stay put in memory. All they do is manipulate the references. As for garbage collection when you are done with the object, the garbage collector is very sophisticated and knows when to run. You can't really tell it when to run or how to do its job better. I wouldn't worry about it. 
trelek2 wrote:
I'm simulating a system which consists of thousands of objects. New objects are constantly added to the system, existing objects are constantly decaying and need to be deleted, some objects merge together etc. All these objects are of the same type (same class, just different parameters).Thousands of objects is easy. Millions might be a different matter.
These objects live in space which is divided into grid cells (there will be a lot of them as well). During the simulation at each time step I will need to check how one of the objects interacts with each other objects in neighboring grid cells...The order in which the objects move depends on a special parameter. This parameter will change for one of the objects after each time step. So, the objects will have to be sorted according to this parameter.Sounds a bit like the game of Life to me.
Firstly the grid: I thought of making a 2 dimensional array of GridCell objects and every time an object goes into a grid cell I will create a reference to it in the grid cell.How you design your grid might well depend on how densely populated it is. If it only ever has 10% of it's cells "populated" you may be wasting a lot of space; and an alternative might be to use a Map that is keyed by a grid reference (one possibility for such a key is the Point class).
And for the the objects I will be simulating I thought of using the SortedList. But there will be thousands of objects in the list and at every time step, when the parameter of an object changes the computer will have to re-sort the list.There's nothing to stop you keeping two Maps of your grid objects in different orders: one by its grid reference, and one by some sort of timestamp (or Age?). Just remember to keep them in sync :-).
It would help to know a little more about how you select the objects to be "morphed" if you want more concrete suggestions, but I entirely agree with njb7ty: DON'T WORRY ABOUT OPTIMIZATION. At least not at this stage.
Winston 
thanks for the helpful suggestions, i'll try to write some code now:) 
By the way, rather than letting your object be garbage collected, you can create an object pool and return them to the pool. However, I think that's an advanced topic that you shouldn't mess with until you are a lot more experienced in coding.

Complex Numbers: better implementation

I've already created a Complex class, with all the mathematical methods necessary. But I've seen at the Internet several attempts to do such classes, and one preferred to make a compiler that accepts complex as a primitive type. And he's right. Creating a class to represent the complex numbers takes too much memory and time only to store two doubles. Using C/C++, complex numbers could be made with structs, and a Complex class would be used to implement the necessary methods, wrapping the complex type, like Double wraps a double.
So, I'd like to suggest a new type of class. This class would act like
an C/C++ struct, being able to store only fields and constructors. I believe that this way would make it waste less memory, and enable faster use of this class. It would work like this:
public value class complex {
  public double real;
  public double imag;
}
public class Complex {
  public static final complex I;
  I.real = 0; I.imag = 1;
  // ...
}What do you guys think? 
Hey, I think this is a great idea. Right now I'm working on implementing modules into a data mining program (coded in Java) that can perform various fourier and wavelet transformations on the data. This involves complex numbers and since memory concerns are definitely a concern of ours (we're working with gigabyte sized files) a complex primitive data type would be much preferred.
I found this site on sun's network on how to implement it:
http://java.sun.com/people/darcy/complex-proposal.html#need
I haven't read it yet, so I don't know how much of a 'how-to' guide it is, as much as a proposal outlining issues surrounding the implementation (as the url implies).
If you're serious about this, get my email and we can work on doing it and possibly writing a tutorial for others to use. 
Hrm... well, I guess the emails aren't in the user profiles. You (or anyone who wants to do this) can reach me at:
"h"u"n&a&m#y&a*h*o^o*.c$o$m (ommitting all unnecessary nonalphabetic characters of course)
~Lije 
Creating a class to represent the complex
numbers takes too much memory and time only to store two doubles.If the only fields in the Complex object are two doubles, how much more memory does a Complex object take up? The methods would only appear in the Class object, not each Complex instance. Right?
I guess you have one reference on the stack and two doubles on the heap, as opposed to two doubles on the stack and nothing in the heap.
So, I'd like to suggest a new type of class. This
class would act like an C/C++ struct, being able to store only
fields and constructors. I believe that this way would
make it waste less memory, and enable faster use of this class.At this point I wonder whether there'd really be a big memory savings, and whether it would be worth watering down the OOP-ness of the language.
Defining a complex primitive is another issue.
Issues like ordering and equality would seem to make the problem really...complex... Perhaps any choice for those issues would only satisfy a third of the interested parties, and any design would satisfy no one.
Java Grande has a proposed Java API for a class Complex.
http://www.vni.com/corner/garage/grande/index.html
I think a complex primitive type would be the best solution. I mean why not? Java is used for number crunching too, and complex numbers really are as primitive and "basic" as doubles.
I think a complex primitive type would be the best
solution. I mean why not? Java is used for number
crunching too, and complex numbers really are as
primitive and "basic" as doubles.I agree that a primitive type is better than introducing C-style structures.
But I wonder if once you get down to details, there will be an ongoing lack of consensus.
For example, IIRC, complex numbers don't have an intrinsic logical ordering. So you could disallow the use of comparison operators on complex numbers. But then perhaps there's some application which requires an ordering on the complex numbers anyway. So I wonder if eventually you have this situation where you'd need one package of complex number support for number theory, another for engineering, etc. That situation is better solved with class libraries than with new primitives whose semantics are necessarily the same across applications.
Or maybe not. I could easily be misremembering the details of complex numbers, and on a Saturday night there's no way I'm going to look it up. For that matter, why am I posting here now? 
I agree that a primitive type is better than
introducing C-style structures.
But I wonder if once you get down to details, there
will be an ongoing lack of consensus.My concern is mostly speed. If complex was a primitive type calculations would be fast. No method call and heap allocation overhead.
There's always going to be someone who isn't happy. But there must be some international standard that will satisfy the majority of needs. If you need something else you can always write you own Complex library -:)
PS. I think some sort of "lightweight" classes or "leightwight" object behaviour will be added to Java some day. The autoboxing feature of version 1.5 is a first step in this direction I think.
I do not think that the notion of non-primitive type complex numbers taking too much memory refers to a well established fact.
For example, an instance of the class Complex in the package com.imsl.math in the library downloadable from the next linked page is not very memory consuming compared with the primitive type int.
http://hoschek.home.cern.ch/hoschek/colt/
I do not think that the notion of non-primitive type
complex numbers taking too much memory refers to a
well established fact.It's a fact because of the object overhead (which is about 16 bytes per object). Two doubles would be 16 bytes whereas a Complex object containing two doubles would be 16+16 = 32 bytes.
Two doubles are needed irrespective of a complex number being an Object or being a primitive. I mean there can be no difference in the order of the required size (of memory). 
if you are concerned about memory usage when wrapping a few primatives in an Object, could you not use some arrays?
the first objection i think youll mention is the problem of de-allocating unused entries, but think on..
the sort of task that would require these numbers of Objects, i think would lend thenselves quite well to arrays, large sequences of values read, processed and disposed either in order or as a chunk
the "in order" case: process the last n samples
easy enough to implement a cyclic buffer
the "chunk" case: process a frame of samples
simply over write with the new frame 
Two doubles are needed irrespective of a complex
number being an Object or being a primitive. I mean
there can be no difference in the order of the
required size (of memory). It's true that 2 doubles (16 bytes) are needed both cases. But an object doesn't come for free. As I said, each object has an overhead of about 16 bytes. So it costs 16 extra bytes to have two doubles wrapped in a Complex object.
Pete_the_Hat: sounds almost like vector multiprocessing.
I wonder if anyone has ported java to a vector multiprocessing machine, and if so how/if they extended/used java for that environment?
Oh, well, something to google someday. 
http://developer.java.sun.com/developer/bugParade/bugs/4384324.html
Don't see it myself - I'd rather have control over the conversions between Cartesian and Polar forms.

Categories

Resources