Java array problem

[Jason de Vere]

I have an array with two elements in a field in a class. After the object is instantiated, I need to extend the array occasionally by adding elements. The way I appoched this was to create an temporary array with the right number of elements, and copy the original array to it, element by element. However, I now need to get rid of the original array and make a new one with more elements in it, so I can copy the temporary array to it, element by element. How can I do this from within a method of the object?

class Thing
{
    int [] array1;

    public Thing
    {  
        array1 = new int [2]; 
    }
	
	void enlarge()
	{
	    int[] temp = new int[array1.length + 1];
        
        for (int i = 0; i < array1.length; i++)
        {
            temp[i] = array1[i];
        }	

        // Now what?

	}
}

It seems I need to create a new array with more elements using the same name as the old one, but how?
I know there are other approaches to this using lists and more abstract Java methods, but I want to solve it in a basic way using basic tools.

[Piet Souris]

Hi Jason,

Welcome to the Ranch and enjoy the stay!

What about

array1 = temp;

But wouldn't an ArrayList not be handier?

[Jason de Vere]

Hi... thanks just as simple as making array1 point to the new array. Thanks! Of course ArrayList would be easier. But I'm learning algorithms :-)

[Matthew Bendford]

Well, beware of what algorithm you choose:
Take a look at Vector vs ArrayList as an example: Vector was designed very conservative - on every enlargement its size doubled - starting with a vector with its size equal to a power of two you can see this gets really big rather quick. ArrayList on the other hand was done more smarter: It only increases the backing array only by half its current size. A list with an initial size of 8 would go 12, then 18, then 27 and so on - a vector would already at 32 or even at 64.

Sure, you can go "+1" each step - but that's not really an algorithm - but rather a very compilcated way of implementing a LinkedList - which doesn't follow any enlargement algorithm but just chains the next element after the last one and hence also only growing by +1 each time.

[Mike Simmons]

Matthew Bendford wrote:Take a look at Vector vs ArrayList as an example:

It's probably a bad idea for anyone learning beginning Java to be distracted with Vector.  They should probably just use ArrayList (or LinkedList, or another Collection entirely) and forget anyone ever heard of Vector.  We've been in the twenty-first century for a while now.

But because some of us still like discussing such esoterica...

Matthew Bendford wrote:Vector was designed very conservative - on every enlargement its size doubled - starting with a vector with its size equal to a power of two you can see this gets really big rather quick. ArrayList on the other hand was done more smarter: It only increases the backing array only by half its current size. A list with an initial size of 8 would go 12, then 18, then 27 and so on - a vector would already at 32 or even at 64.

I think that's a misleading description.  As you add elements one at a time, the vector won't have to resize as often as the arraylist.  So its resizes are bigger, but less frequent - those balance pretty well.  At any given time the vector may be up to 33% bigger than the arraylist, but that lead does not continue to grow exponentially.

The real effect of their difference in growth factors is a tradeoff between speed and memory usage.  The vector uses a more memory on average, but spends less time re-copying data each time it re-sizes.  It's not really clear to me which of these is better.  I certainly prefer ArrayList in general for other reasons, but this particular implementation difference doesn't seem like a big difference, to me.

Matthew Bendford wrote:Sure, you can go "+1" each step - but that's not really an algorithm - but rather a very compilcated way of implementing a LinkedList - which doesn't follow any enlargement algorithm but just chains the next element after the last one and hence also only growing by +1 each time.

Well, it would still not really be a linked list, but an arraylist with remarkably poor add() performance as it gets bigger and bigger.  It wouldn't waste any memory (aside from everything waiting for GC), but that's not worth the crappy performance you'd get overall.

[Piet Souris]

Jason De Vere wrote:But I'm learning algorithms :-)

[Campbell Ritchie]

Piet Souris wrote:. . .

array1 = temp;

. . .

That code doesn't copy the array, but only its reference, causing aliasing problems. Any changes to array1 are reflected in temp, because the two point to the same object
If somebody has to write their own algorithm to copy an array one element longer, JDV's suggestion looks as good as anything. In real life, I would use System#arraycopy() or, more likely, Arrays#copyOfRange().

Mike Simmons wrote:It's not really clear to me which of these is better.

I suspect the two will average themselves out so there isn't actually a difference. Apart from the fact that all ArrayList operations run faster than Vector's because there is no synchronisation overhead.

And, JDV, welcome to the Ranch (again)

[Jason de Vere]

Campbell Ritchie wrote:That code doesn't copy the array, but only its reference, causing aliasing problems. Any changes to array1 are reflected in temp, because the two point to the same object

It doesn't need to copy the array--I'm done with temp. As long as array1 is point to the right data, I don't see what problem is caused.

Campbell Ritchie wrote:
And, JDV, welcome to the Ranch (again)

Thanks.

[Campbell Ritchie]

A straight copy of references wouldn't enlarge the array.

[Junilu Lacar]

Campbell Ritchie wrote:A straight copy of references wouldn't enlarge the array.

You seem to be taking the assignment statement out of context. This is the code being discussed:

OP wrote:

class Thing
{
    int [] array1;
 
    public Thing
    {  
        array1 = new int [2]; 
    }
     
    void enlarge()
    {
        int[] temp = new int[array1.length + 1];
         
        for (int i = 0; i < array1.length; i++)
        {
            temp[i] = array1[i];
        }   
 
        // Now what?
        array1 = temp;  // advice given by Piet
 
    }
}

In this case, a reference to a larger array is actually being assigned to array1 so viewed from outside of enlarge() the array does indeed appear to grow in size. Probably not as clean as it could be because of the side-effect-iness of the design. If you want it a little more functional, you might write it this way:

array1 = expanded(array1);
...

private int[] expanded(final int[] original) {
    int[] bigger = new int[original.length + Math.max(1, original.length/2)];
    for (int i = 0; i < original.length; i++) {
         bigger[i] = original[i];
    }
    return bigger;
}

// alternatively, if you just want the results and not bother with the details
private int[] expanded(final int[] original) {
    return Arrays.copyOf(original, original.length + Math.max(1, original.length/2));
}

[Jason de Vere]

Yes, thanks Junilu.  I realize my code is not very clean and the methods have side effects.

This was my solution. I think at this stage the important thing is that it makes sense to me and reflects my thought processes. It can always be improved later, and I value all the help I've been getting for that.

The variable 'm' represents the size of the original array:
'keyCount' is another nasty global that keeps track of how many keys have been inserted. I used to calculate the load factor later.

 public void enlarge()
    {
        // To enlarge, I chose to double the size of the array
             
        m = m * 2;        
        int[] extended = new int[m];
        
        // fill new array with -1s
        for (int i = 0; i < m; i++)
        {
            extended[i] = -1; 
        }
        
        // REHASH ******************************************************        
        // STEP 1: Store keys from old table in a temporary array 'temp'
        int[] temp  = new int[keyCount];
        int j = 0;
        for (int i = 0; i < m / 2; i++)
        {
            if(array[i] != -1)
            {
                temp[j] = array[i];
                j = j + 1;
            }
        }
        
        // STEP 2:
        // point 'array* to the new 'extended' array
        array = extended;        
       
        // STEP 3: insert the values from temp using insert(key) method:
        int keys = keyCount;
        keyCount = 0; // reset keyCount so we can start counting from scratch
        System.out.println("Rehashing...");
        for (int i = 0; i < keys; i++)
        {
            insert(temp[i]);
        }
    }

Obviously not all the code is here, and I have another algorithm to insert the values into 'array', as the exercise was about hash tables. I have tested the final result and it's working.

[Paul Clapham]

Jason de Vere wrote:But I'm learning algorithms :-)

Not exactly algorithms, but basic programming. Professional programmers wouldn't write anything like the code you're learning to write there, and Java has had methods like Array.copyOf which do that for you for the last 25 years. But it's still basic programming techniques which you need to know. Just like when you learn to drive a car, you start by learning basic maintenance, like how to change spark plugs.

[Winston Gutkowski]

I think you're doing fine, and I particularly like the fact that you're explaining each step in your code. You'd be amazed how many experienced programmers forget to do that.

I also like the fact that you've named your method expand(), because that's exactly what it's doing. It's also a verb, and methods are usually actions of some sort.

However, what I don't like is that your method takes no parameters and returns no value. This makes it highly "coupled" - meaning that it doesn't stand on its own.

If you look at Junilu's example, his method takes the original array as a parameter and spits back a "modified" array, so the only thing left to do is assign it somewhere. And his code never references anything outside the method.
This is called "re-usability" and means you can - for example - copy and paste it into another program to do something similar, or (probably better) add it to a static library of generic "Array" methods, which is precisely what java.util.Arrays is.

As you go forward, what you'll discover is that most methods follow the "IPO" pattern - IPO standing for "Input - Process - Output".
That is: they take an input (in your case, an array), perform some sort of process on it (in your case enlarging it), and produce a result (the expanded array).

So the general signature pattern for most methods is:
{public/protected/private} final return-value method-name(parameter1, [parameter2, ...])

And don't forget that "final", even though it's redundant for private methods. Just get into the habit of adding it, because one of these days it will save your bacon. :-)

HIH

Winston

[Campbell Ritchie]

Winston, welcome back

[Winston Gutkowski]

Campbell Ritchie wrote:Winston, welcome back

Thanks mate. Thought I'd look around the old homestead.

[Junilu Lacar]

An alternative to commenting your code copiously is refactoring your code mercilessly. I was just discussing the idea of code comments as a "smell" with a colleague yesterday, actually. That is, comments are often an indication that there's something not quite right with the code that's being commented on.

In the book Refactoring - Improving the Design of Existing Code (both the first and second editions)

The author, Martin Fowler wrote:In our olfactory analogy, comments aren’t a bad smell; indeed they are a sweet smell. The reason we mention comments here is that comments often are used as a deodorant. It’s surprising how often you look at thickly commented code and notice that the comments are there because the code is bad… Our first action is to remove the bad smells by refactoring. When we’re finished, we often find that the comments are superfluous.

Refactoring your code to be more self-explanatory could be as simple as extracting each commented section to its own method and giving each method an expressive name, for example:

    int[] extended = doubleSized(original);
    copyValues(original, extended);

In the book, Fowler also points out that the best comments explain why something is being done the way it is in the code. Explaining the what and how should be done by refactoring and making the code expressive.

[Junilu Lacar]

Jason de Vere wrote:I have tested the final result and it's working.

If you're really serious about becoming a better programmer, you'll want to start looking into automated testing. For Java, the de facto standard test framework is JUnit. Getting into the habit of unit testing your code frequently as you develop it will also save your bacon. Getting into the habit of writing code with testability in mind will put you head and shoulders above your peers.

[Jason de Vere]

Winston Gutkowski wrote:I think you're doing fine, and I particularly like the fact that you're explaining each step in your code. You'd be amazed how many experienced programmers forget to do that.

I also like the fact that you've named your method expand(), because that's exactly what it's doing. It's also a verb, and methods are usually actions of some sort.

However, what I don't like is that your method takes no parameters and returns no value. This makes it highly "coupled" - meaning that it doesn't stand on its own.

If you look at Junilu's example, his method takes the original array as a parameter and spits back a "modified" array, so the only thing left to do is assign it somewhere. And his code never references anything outside the method.
This is called "re-usability" and means you can - for example - copy and paste it into another program to do something similar, or (probably better) add it to a static library of generic "Array" methods, which is precisely what java.util.Arrays is.

As you go forward, what you'll discover is that most methods follow the "IPO" pattern - IPO standing for "Input - Process - Output".
That is: they take an input (in your case, an array), perform some sort of process on it (in your case enlarging it), and produce a result (the expanded array).

So the general signature pattern for most methods is:
{public/protected/private} final return-value method-name(parameter1, [parameter2, ...])

And don't forget that "final", even though it's redundant for private methods. Just get into the habit of adding it, because one of these days it will save your bacon. :-)

HIH

Winston

Thanks for your feedback.

At the moment I'd doing a course in Algorithms and Datastructures, where most of the time we are discussing mathematical concepts and using pseudocode. The lecturers advise us to use C++ to implement it if we want to try it out. However, I haven't got a clue about C++ so I was doing it with Java. That is why I am avoiding using any advanced methods.

[Campbell Ritchie]

This is one of those occasions when you do have to write your own algorithms. You are in a situation rather like a carpenter's apprentice, who has to cut mortices with a chisel and mallet, and isn't allowed near the electric router until they can cut perfect mortices by hand.

[Junilu Lacar]

Jason de Vere wrote:At the moment I'd doing a course in Algorithms and Datastructures, where most of the time we are discussing mathematical concepts and using pseudocode. The lecturers advise us to use C++ to implement it if we want to try it out. However, I haven't got a clue about C++ so I was doing it with Java. That is why I am avoiding using any advanced methods.

There's not much difference in C++ and Java as it relates to writing a program like this. The implementation language is not that important here. It's how you organize the ideas that make up your solution that's crucial. If you're studying algorithms and data structures then sure, you're going to have build almost everything yourself instead of using parts/assemblies that are already available for you to just use.

[Junilu Lacar]

The CS curriculum (over 30 years ago now) I went through had us learn a programming language first before we studied algorithms and data structures. That is, CS101 - Computer Programming (in Pascal) was a pre-requisite for CS204 Algorithms and Data Structures (in Pascal). It seems it would be difficult to learn about the latter if you didn't already have some basic mastery of the implementation language you were using.

[Jason de Vere]

Junilu Lacar wrote:The CS curriculum (over 30 years ago now) I went through had us learn a programming language first before we studied algorithms and data structures. That is, CS101 - Computer Programming (in Pascal) was a pre-requisite for CS204 Algorithms and Data Structures (in Pascal). It seems it would be difficult to learn about the latter if you didn't already have some basic mastery of the implementation language you were using.

I know. it's a bit strange. This is ADS2, Algorithms and Data Structures 2, a computer science course at London University. It is a level 6 course and the only prerequisite was that students have completed the required level 5 courses, none of which involved C++. In fact, one of them was ADS1, where they used JavaScript. C++ was offered only as an optional summer course, but I missed that opportunity because I transferred from another programme where we'd been doing Java. Although they have said that it is not mandatory to use C++ in ADS2. It would be nice to know the basics of C++ but having just invested some time in Java, I want to keep learning that for now.

[Jason de Vere]

Junilu Lacar wrote:

Jason de Vere wrote:At the moment I'd doing a course in Algorithms and Datastructures, where most of the time we are discussing mathematical concepts and using pseudocode. The lecturers advise us to use C++ to implement it if we want to try it out. However, I haven't got a clue about C++ so I was doing it with Java. That is why I am avoiding using any advanced methods.

There's not much difference in C++ and Java as it relates to writing a program like this. The implementation language is not that important here. It's how you organize the ideas that make up your solution that's crucial. If you're studying algorithms and data structures then sure, you're going to have build almost everything yourself instead of using parts/assemblies that are already available for you to just use.

This is what i thought. I did some tutorials on C++ and it seemed straight forward enough. Then one of the University exercises provided us with some skeletal code in C++, in the form of one .hpp file and one .cpp file. The header seemed to be a just declarations of methods, while the cpp seemed to be the actual method minus their code. It looked straight forward but not matter what i did I could not get it to compile. The problem for me there is understanding the program structure and approach, rather than the ins and outs of using statements. So I did that in Java too.

[Junilu Lacar]

As with everything in programming, it's easier to incrementally add to something that's already working rather than try to write a whole bunch of code at once, then expect it to work at first compile.

Start with a small, empty program and get it to compile. Add one statement and get that to work. If it doesn't then you know the problem is in that one small change you made. Back it out and get back to something that does work. Then try making one other small change. See if that works. Rinse and repeat.

Successful programming is about making small, incremental progress, always making sure that what you have so far works before you add on a little bit more to it.

Try that approach with your C++ code.