Overview
Here are some examples of broken code. I find the interesting to understand what they don't do what they appear to.
Can you work out why these don't work? ;)
Loop every second value
List list = new ArrayList<>();
for (int i = 0; i < 10; i++) list.add(i);
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
list.remove(i);
}
prints
0
2
4
6
8
Endless loop
This prints all the characters which have value
for(char ch = Character.MIN_VALUE; ch<= Character.MAX_VALUE; ch++) {
int i = Character.getNumericValue(ch);
if (i >= 0)
System.out.println("char "+ch + ' ' + (int) ch+" = "+i);
}
However it doesn't stop. Can you change the code to use a do/while loop so that every char is considered but it does stop? (Without using a larger type)
What am I waiting for?
This "program" deadlocks. The main method is optional ;)
class Main {
static int value;
static {
final Thread t = new Thread() {
@Override
public void run() {
value = 1;
}
};
t.start();
System.out.println("Dead locking");
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Released");
}
}
Can you see why it deadlocks?
The last two puzzles are based on puzzles from
Java Puzzlers by Joshua Bloch and Neal Gafter If you liked these, you will love this book. ;)
Sample Solutions
LOOP EVERY SECOND VALUE
ReplyDeleteThe list is shrinking with every call to .remove() but the index keeps moving forward.
At the beginning of the first iteration
i: 0 V
list: 0123456789
size: 10
At the beginning of the second iteration
i: 1 V
list: 123456789
size: 9
At the beginning of the third iteration
i: 2 V
list: 23456789
size: 8
At the beginning of the fourth iteration
i: 3 V
list: 3456789
size: 7
At the beginning of the fifth iteration
i: 4 V
list: 456789
size: 6
At the beginning of the sixth iteration, which does not execute because i is no longer less than list.size().
i: 5 V
list: 56789
size: 5
@rushcoding A very good explanation. :)
ReplyDeleteI would have guessed the first one would throw an ConcurrentModificationException. Other than that It didn't suprise me much.
ReplyDeleteSecond one deadlock's because (Character.MAX_VALUE + 1) goes back to zero.
Third one I guess it has something to do with static initialization rules but weired :)
1. to fix for i = 0; while(i != list.size(){}
ReplyDelete2. Character.MAX_VALUE + 1 = Character.MIN_VALUE,
so for(char ch = Character.MIN_VALUE; ch< Character.MAX_VALUE; ch++) {} - remove equals
3. class initialization happens in one thread, so t.join stops the main application thread and the thread above cannot be run until the main application thread finishes. it might be the reason.
@vasste
ReplyDelete1. This is an infinite loop unless I am missing something.
2. That doesn't consider all values, it avoid the troublesome one.
3. basically correct.
1. no. the list size is getting smaller:
ReplyDeleteSystem.out.println(list.get(i)+","+list.size());
0,10
1,9
2,8
3,7
4,6
5,5
6,4
7,3
8,2
9,1
@vasste Can you provide the whole code? I don't see exactly what you mean.
ReplyDeleteList list = new ArrayList();
ReplyDeletefor (int i = 0; i < 10; i++) list.add(i);
int i = 0;
while(i != list.size()) { System.out.println(list.get(i)+","+list.size());
list.remove(i);
}
@vasste I see now. "i" is always 0 which means its much the same as
ReplyDeletewhile(!list.isEmpty())
/**/ System.out.println(list.remove(0) + "," + list.size());
1.- Well explained by @rushcoding
ReplyDelete2.- Easy as well, because none character will reach the value Character.MAX_VALUE.
I solved with (ch<= Character.MAX_VALUE -1), so I think I'm a little bit obtuse.
3.- I'm looking forward to reading your book about threads ;)
I don't know what is happening, I don't know if there's even executing threads :|
Well, there is a thread defined in a static block and it has even "started". However, I needed a main method to execute/debug the program and it's like the Heisenberg principle, I'm altering the program in order to know it.
The thread t seems not to finish after some "main" execution. That it's, the thread and all the stuff are allocated in the static block, but it won't finish, unless an execution (a main method) begins.
My solution is to use the join method with timeout:
t.join(5000);
However, you never know if control returns due to a normal finish of the thread or because the time out.
I think always applies the former.
The first one is like running on a treadmill - for every step you make the belt moves 2 steps underneath you.
ReplyDelete@Javier 2. ch doesn't become MAX_VALUE if you use ch <= Character.MAX_VALUE -1
ReplyDelete3. You can add a main method if you like, but it won't be called due to the dead lock.
Hello Peter,
ReplyDeleteWhat I tried is first understand the problem and second find a solution.
I found funny that I tried to subtract 1 to the maximum instead of using the < operator (without =)
Regarding the "WHAT AM I WAITING FOR?", I know that the program deadlocks because the join method means that the current thread will execute after the finishing of the target thread.
So, if the thread never ends, there will be a deadlock.
My problem is that I don't know why the thread doesn't end.
However, the solution is easy: you can use a timeout join (join(5000))
[I put a main method because I want to Run/Debug the program as a Java application in Eclipse]
2) move the termination statement
ReplyDeletefor(char ch = Character.MIN_VALUE; true; ch++) {
int i = Character.getNumericValue(ch);
if (i > 0)
System.out.println("char "+ch + ' ' + (int) ch+" = "+i);
if(ch == Character.MAX_VALUE) break;
}
@tylermac Can you think of a loop type where the check is at the end instead of the start. ;)
ReplyDeleteThe condition should be if (i >= 0) which was my mistake.