The arrays themselves can’t be swapped for the reasons given last week. However, the elements of the arrays can be swapped, and that’s the trick.
The first condition is that the two arrays’ element types be the same. The second condition is that the arrays have the same number of elements. The implementation is an element-by-element swap:
void swap(T a1[], T a2[])
for (int i = a1.length - 1; i > -1; i--)
T e = a1[i]
a1[i] = a2[i]
a2[i] = t
where T is the element type.
The answers, approximately verbatim, in no particular order, and with comments in italic:
Like C++, Java has a method similar to the copy constructor.1 Because an array is just a class2 (unlike C++) you can use the copy constructor to create a new array with the values from first.3 Then you can change the reference of first to be second’s reference.4 Then second’s reference gets changed to the new array that we created. All of the objects that we don’t need anymore get destroyed and garbage collected.
1: Not really. C++ has copy constructors because you can access class instances directly as storage blocks rather than always through pointers as in Java. Direct class-instance access raises questions about copying, as when passing class-instance blocks as by-value parameters or returning them as function values. In Java, all class-instance access is through references (pointers) and copying around references is trivial, although the semantic consequences of that copying may not be.
Even so, copying class-instance blocks in C++ wouldn’t be much of a problem if it weren’t for a second difference between C++ and Java: pointers as a program-level data type. For reasons that should be well-known to you, a simple byte-by-byte copy constructor produces disastrous results for classes with pointer-typed instance values. Such classes require custom copy constructors. Java avoids the problem by making it much less likely that class-instance blocks need to be copied.
Note, however, that Java doesn’t solve the problem, it just puts it off. As we’ll see later this semester, writing a copy method for a class can be difficult if the class contains instance variables that contain references to other class instances.
2: Not really. Java arrays are best thought of as a primitive data type overlayed with a veneer of class-like syntax. For example, you can’t find any documentation about basic arrays in the class-API documentation (you can find array classes, but those have to do with reflection and SQL, not with the basic array type).
3: Why make a copy? When does your algorithm ever touch the array instance itself, rather than the reference to the instance?
4: Yes, but how? The point of last week’s question is that call-by-value makes that change impossible from within a method.
When you want to keep the original Data5 and you don’t need the Data in new places. You implement this by creating an intermediate array, set this array to equal A1, set A1 to equal A2 and A2 to equal the intermediary.
When you want to keep the original Data but also want to manipulate. To do this you can use the Array class’s copy function.6
5: Which you do, because that’s how swap is defined.
6: Is this a swap?
1. Of the same type.7
2. The new array8 has allocated enough space for the array being swapped with it.
By using the copyOf method associated with the array class you can [?] an array reference to another array9 which contains a copy of all of the elements of the array.10
7: What’s of the same type?
8: Which new array? There are two arrays passed in as parameters, but they’re both old, or if they’re not, it’s not clear which is the new one and which is the old one (and they both can’t be new because there’s apparently only one new array).
9: Which other array?
10: If the other array already contains the elements, why make a copy?
To swap two arrays you can use the copyOf() method. Arrays cannot be set equal to one another because the original array and the copy will contain the same value for each i-th value.11 If you copy each array to another array and then copy those temp arrays to the opposite arrays they were originally,12 you can swap them.
11: True, but that just means you have to do the t = a1; a1 = a2; a2 =
t dance.
12: Or something like that.
1. The 1st condition is when you have 2 arrays that have pointers.13
2. ?
Method 2 arrays that have pointers to them just swap the pointers and then the values change.14
13: Have pointers where?
14: Right, but how do you do that within a swap method? Also: which values?
One condition for a swapping 2 arrays is when you are swapping strings.15 A second condition is when [?]
To swap 2 arrays (assuming 2 original arrays exist)
15: That’s a C-ism; strings in Java aren’t arrays of characters, or arrays of anything.
The StringBuilder class is preferable when strings are going to be subject to repeated changes by, for example catenations or substring assignment. The StringBuilder class produces mutable instances, which can handle change more efficiently than the immutable instances produced by the String class.
The answers, approximately verbatim, in no particular order, and with comments in italic:
Since the string class can use specific method to create a string it is sometimes easier for the StringBuilder to do this without having to call a String class. It is faster than having to declare a string variable.1
1: Hard to say without measurements, but I wouldn’t think that’s true
because variable declarations are a compile-time feature, and string variable
declarations with initialization (as in String msg = "hello!" also occur
at compile time. On the other hand, a StringBuilder variable declaration with
initialization (as in StringBuilder msg = new StringBuilder("hello")
involves run-time execution
It is better to use the StringBuilder because it is easier to change
part of the string. For example, strings are immutable, so using the String
class you cannot change part of the string you want. Say you have the string
"Hello" but want to change it to "Help!". Simply print the string from
the 0 to 3 location and catenate the "p!"
When you are reading in from a file or from prompts in the program the user answers, it is better to use StringBuilder over the String class. StringBulider saves processing time that would otherwise be taken up by the String class’s concatenate function.2 It also saves the overhead of having to create multiple strings that would be needed for read-in otherwise.
2: Or rather, the StringBuilder catenate is cheaper in time and space than is the String’s catenate.
If you are concatenating a series of strings, it is better to use the StringBuilder class over the String class. Using the StringBuilder class uses less memory. If you use the String class, each time you append the original string, a new object is created which uses more memory.
The String class is immutable for performance reasons but the StringBuilder class allows for mutability. When a string has to be changed often it is best to use StringBuilder but when a string is not changed the String class has the best performance.
If you were doing something repeatedly, such as building an SQL query, StringBuilder is better. You can not trivially concatenate 2 strings.
String A blahIf you say A = A + B; a third string is created with the value
String B hello
"blah hello" and the first 2
are destroyed and must be garbage collected. This makes it difficult to do
string concatenation and requires a lot of overhead. StringBuilder uses a
buffer approach, and does not create and destroy needless objects.
| This page last modified on 16 February 2009. |