Re: Seeking computer-programming job (Sunnyvale, CA)
eric-and-jane-smith wrote:
Seamus MacRae <smacrae319@live.ca.nospam> wrote in
news:guhr3h$ffm$1@news.motzarella.org:
If it merely transforms the list, and doesn't care whether they're
runnable, it should not matter. Suppose it sorts the list by priority.
But what if it does care? What if it takes a list of a million objects,
and deletes 17 of them from that list, because those 17 aren't runnable?
In Common Lisp, deleting 17 objects from a list of a million can be done
quickly and efficiently. But you seem to be implying you have to copy the
other 999983 objects to a list of runnables, because otherwise they would
be in a list of objects, even though they're all runnable.
Not in Java. In Java, you can use:
/**
* Removes non-<code>Runnable</code> objects from <code>list</code>
* and returns pruned list as a <code>List<Runnable></code>;
* caller is responsible for synchronizing the list if necessary.
*/
@SuppressWarnings("unchecked")
/*
* Justification: the only unchecked cast is in the return
* line, and all non-Runnables have been removed from the
* list at that time. The returned list is a list of
* Runnables unless a data race occurred. Correct behavior,
* as ever, depends on the caller synchronizing where
* appropriate.
*/
public List<Runnable> pruneList (List<?> list) {
for (Iterator<?> i = list.iterator(); i.hasNext();) {
// Old "for" used intentionally
Object o = i.next();
if (!(o instanceof Runnable)) i.remove();
}
return (List<Runnable>)list;
}
Untested. The intent should be pretty clear, though. The reason for
using the old "for" is to get efficient removal. Performance is O(n) for
a LinkedList, and no copying is done.
A version that copies the list would be thread-safer:
/**
* Makes and returns a copy of <code>list</code> with only the
* <code>Runnable</code> objects, whose order is preserved;
* caller is responsible for synchronizing the list if necessary.
*/
public List<Runnable> pruneList2 (List<?> list) {
List<Runnable> ret = new ArrayList<Runnable>(list.size());
for (Object o : list) {
if (o instanceof Runnable) ret.add((Runnable)o);
}
return ret;
}
This makes a copy with only the runnable objects. Copy cost is O(number
of runnables in source list). Only pointers are copied, rather than the
actual objects in the list. The cast to Runnable should never fail. No
unchecked cast is used in this version. With respect to threading, since
the result list is local until the method exits and the object is local
from before the instanceof test until insertion in the result list:
1. The result list will never, EVEN WITH a data race, come out
containing a non-Runnable.
2. A weak consistency may apply to concurrent use of the source list:
an object in the output list will have been in the input list at the
time of the method call or added while it was running, and an object
not in the output list either was not in the input list at the
time of the method call, was removed while it was running, or was not
Runnable. Whether this actually works depends on whether the source
list has (at least) weakly consistent concurrent iteration and
modification. The java.util lists don't; this method may throw
ConcurrentModificationException. The java.util.concurrent lists are
another matter (for instance, CopyOnWriteArrayList).