より効率的なTimerクラスの利用方法

[nod_chip]

nod_chipと申します。

複雑で重くなった JavaScript を超高速化する方法３ - IT戦記
http://d.hatena.ne.jp/amachang/20060924/1159084608

こちらのページに触発され、似たような機能を持つクラスをGWTを用いて実装してみました。
個人で運営しているWEBサービスに乗せてみたところ、
ページの動作が軽くなったという御意見を頂けました。

JRE Emulation LibraryにTreeSet/TreeMapが含まれていないため
当初予定していたものより非効率な物となってしまいました。
(計算量オーダーO(log(N))で済む部分がO(N)になってしまっています。)

タスクリスト周りをもう少しカプセル化すべきなのですが、
プロトタイプということで御許しください。

以下にソースコードを載せます。
皆様の御意見を御聞かせいただけると幸いです。宜しくお願いいたします。

/**
* Timerクラスを拡張し、一つのタイマーインスタンスで複数のタイマーを取り扱えるようにしたもの。
*
* 複数のタイマーインスタンスを使用するとJavaScriptの実行環境によっては動作が遅くなってしまうが、インスタンスを一つに纏める事に
よって効率化・高速化することができる。参照URL:http://d.hatena.ne.jp/amachang/
20060924/1159084608
*
* また、実行環境によってタイマーの実行タイミングが変わってしまう現象を最小限に抑えることができる。
*
* @author nod_chip
*/
public abstract class SerialTimer extends Timer {
/**
* removeRange()をpublicにしたArrayListクラス
*
* SerialTimerの内部で使用する
*
* @author nod_chip
*/
public static class ArrayListEx extends ArrayList {
public void removeRange(int fromIndex, int toIndex) {
super.removeRange(fromIndex, toIndex);
}
}

/**
* タイマーのインスタンスが実行するタイマータスクのリスト。実行時間順の昇順で格納される。実行済みのタスク、キャンセルされたタスクの部分に
はnullが代入される。
*/
private static ArrayListEx tasks = new ArrayListEx();
/**
* tasksの先頭何個にnullが入った場合にtasksを整理するかの閾値。TreeSet又はTreeMapが実装されれば不要となる。
*/
private static final int COMPRESS_THRESHOLD = 8;
/**
* 次に実行するタスクのtasks内での位置
*/
private static int headOffset = 0;
/**
* タイマーのインスタンスが実行中かどうか
*/
private static boolean executorStarted = false;
/**
* タスクを実際に実行するタイマーのインスタンス
*/
private static final Timer timer = new Timer() {
public void run() {
execute();
}
};

/**
* 次に実行するタイマータスクのindexを返す
*
* @return 次に実行するタスクのindex。タスクが見つからない場合は-1を返す。
*/
private static int findNextTask() {
for (int index = headOffset; index < tasks.size(); ++index) {
if (tasks.get(index) != null) {
return index;
}
}
return -1;
}

/**
* 登録されたタイマータスクを実行する
*/
private static void execute() {
SerialTimer task = (SerialTimer) tasks.get(headOffset);
if (task != null) {
// タイマータスクを実行済みとする
tasks.set(headOffset, null);
task.isReserved = false;

// タイマータスクがリピート設定されている場合は次のタスクを予約する
if (task.duration > 0) {
task.executeTime += task.duration;
insertTask(task);
}

// タスクを実行する
try {
task.run();
} catch (Exception e) {
e.printStackTrace();
}
}

// 次に実行されるタスクを見つける
headOffset = findNextTask();

// 指定された場所にタスクが見つからなかった場合は実行し直す
if (task == null) {
execute();
return;
}

// タスクが登録されていない場合はタスクリストを消去し、タイマーを止める
if (headOffset < 0) {
tasks.clear();
headOffset = 0;
executorStarted = false;
return;
}

// タスクリスト先頭のnull多くなった場合、タスクリストを圧縮する
if (headOffset > COMPRESS_THRESHOLD) {
tasks.removeRange(0, headOffset);
headOffset = 0;
}

// 次のタイマータスクを実行するためのタイマーインスタンスを起動する
final SerialTimer nextTask = (SerialTimer) tasks.get(headOffset);
int time = (int) (nextTask.executeTime -
System.currentTimeMillis());
time = Math.max(1, time);
timer.schedule(time);
}

/**
* タイマータスクをタスクリストに予約する
*
* @param t
* 予約するタイマータスク
*/
private static void insertTask(SerialTimer t) {
if (t.isReserved) {
t.cancel();
}

// 二分探索で挿入できる場所を探す
final int sizeOfTasks = tasks.size();
int index = headOffset;
int delta = (sizeOfTasks - headOffset) / 2;
final long targetExecuteTime = t.executeTime;
while (delta != 0) {
final SerialTimer task = (SerialTimer) tasks.get(index + delta);
if (task != null && targetExecuteTime >= task.executeTime) {
index += delta;
}

delta /= 2;
}

// 二分探索が少しずれるので補正する
for (; index < sizeOfTasks; ++index) {
final SerialTimer task = (SerialTimer) tasks.get(index);
if (task == null) {
continue;
}
if (targetExecuteTime < task.executeTime) {
break;
}
}

// タイマータスクをタスクリストに挿入する
ArrayListEx tasks = SerialTimer.tasks;
tasks.add(index, t);
t.isReserved = true;

// タイマーインスタンスが実行中でない場合、及びタスクリストの先頭にタイマータスクが挿入された場合にタイマーインスタンスを起動する
if (!executorStarted || index == headOffset) {
executorStarted = true;
int time = (int) (t.executeTime - System.currentTimeMillis());
time = Math.max(1, time);
timer.schedule(time);
}
}

/**
* 実行予定時刻
*/
private long executeTime;
/**
* リピート間隔。 0の場合はリピートしないことを表す。
*/
private int duration = 0;
/**
* タスクリストに予約されたかどうか。
*/
private boolean isReserved = false;

public void schedule(int delayMillis) {
duration = 0;
executeTime = System.currentTimeMillis() + delayMillis;
insertTask(this);
}

public void scheduleRepeating(int periodMillis) {
duration = periodMillis;
executeTime = System.currentTimeMillis() + periodMillis;
insertTask(this);
}

public void cancel() {
// タスクリストから削除する
if (isReserved) {
int index = tasks.indexOf(this);
tasks.set(index, null);
isReserved = false;
}
}
}

使用法:
Timerクラスを使用している部分をSerialTimerに置き換える。

例:
Timer timer = new Timer() {
public void run() {
hoge();
}
};
↓
Timer timer = new SerialTimer() {
public void run() {
hoge();
}
};

[nod_chip]

自己レス失礼致します。
SerialTimerの内部タスクの表現をヒープ構造に置き換えた物を作りました。こちらにて公開させていただきます。
配布ライセンスはApache License 2.0としたいと思います。

----ここからSerialTimer.java----
import com.google.gwt.user.client.Timer;

/**
* Timerクラスを拡張し、一つのタイマーインスタンスで複数のタイマーを取り扱えるようにしたもの。
*
* 複数のタイマーインスタンスを使用するとJavaScriptの実行環境によっては動作が遅くなってしまうが、インスタンスを一つに纏める事に
よって効率化・高速化することができる。参照URL:http://d.hatena.ne.jp/amachang/
20060924/1159084608
*
* また、実行環境によってタイマーの実行タイミングが変わってしまう現象を最小限に抑えることができる。
*
* @author nod_chip
*/

public abstract class SerialTimer extends Timer implements Comparable
{

/**
* タイマーのインスタンスが実行中かどうか
*/
private static boolean executorStarted = false;
/**
* タスクを実際に実行するタイマーのインスタンス
*/
private static final Timer timer = new Timer() {
public void run() {
execute();
}
};
/**

* タスクを保持するヒープ
*/
private static final Heap heap = new Heap();

/**
* 登録されたタイマータスクを実行する
*/
private static void execute() {

SerialTimer task = (SerialTimer) heap.pop();
if (task == null) {
System.err.println("空のタスクが実行されようとしました");
executorStarted = false;
return;
}

// タイマータスクを実行済みとする

task.isReserved = false;

// タイマータスクがリピート設定されている場合は次のタスクを予約する
if (task.duration > 0) {
task.executeTime += task.duration;
insertTask(task);
}

// タスクを実行する
try {
task.run();
} catch (Exception e) {
e.printStackTrace();
}

// 次に実行されるタスク

SerialTimer nextTask = (SerialTimer) heap.head();

// タスクが登録されていない場合はタイマーを止める
if (nextTask == null) {
executorStarted = false;
return;
}

// 次のタイマータスクを実行するためのタイマーインスタンスを起動する

int time = (int) (nextTask.executeTime -
System.currentTimeMillis());
time = Math.max(1, time);
timer.schedule(time);
}

/**
* タイマータスクをタスクリストに予約する
*
* @param t
* 予約するタイマータスク
*/
private static void insertTask(SerialTimer t) {
if (t.isReserved) {
t.cancel();
}

t.isReserved = true;
heap.push(t);

// タイマーインスタンスが実行中でない場合、及びタスクリストの先頭にタイマータスクが挿入された場合にタイマーインスタンスを起動する
if (!executorStarted || heap.head() == t) {

executorStarted = true;
int time = (int) (t.executeTime - System.currentTimeMillis());
time = Math.max(1, time);
timer.schedule(time);
}
}

/**
* 実行予定時刻
*/
private long executeTime;
/**
* リピート間隔。 0の場合はリピートしないことを表す。
*/
private int duration = 0;
/**
* タスクリストに予約されたかどうか。
*/
private boolean isReserved = false;

/*
* (non-Javadoc)
*
* @see com.google.gwt.user.client.Timer#schedule(int)
*/

public void schedule(int delayMillis) {
duration = 0;
executeTime = System.currentTimeMillis() + delayMillis;
insertTask(this);
}

/*
* (non-Javadoc)
*
* @see com.google.gwt.user.client.Timer#scheduleRepeating(int)
*/

public void scheduleRepeating(int periodMillis) {
duration = periodMillis;
executeTime = System.currentTimeMillis() + periodMillis;
insertTask(this);
}

/*
* (non-Javadoc)
*
* @see com.google.gwt.user.client.Timer#cancel()
*/

public void cancel() {
// タスクリストから削除する
if (isReserved) {

isReserved = false;

if (heap.head() == this) {
// 自分が先頭のタスクだった場合
// 次のタスクを予約し直す
heap.pop();
insertTask((SerialTimer) heap.pop());
} else {
heap.remove(this);
}
}
}

/*
* (non-Javadoc)
*
* @see java.lang.Comparable#compareTo(java.lang.Object)
*/
public int compareTo(Object o) {
return (int) (executeTime - ((SerialTimer) o).executeTime);
}
}
----ここまでSerialTimer.java----

----ここからHeap.java----
import java.util.Comparator;

/**
* ヒープ構造を実現するクラス
*
* 各メソッドの計算量オーダーはNをインスタンスが保持しているオブジェクトの総数として、 push…O(log(N))、pop…
O(log(N))、head…O(1)、remove…O(N)
*
* @author nod_chip
*
*/
public class Heap {
/**
* Comparatorが指定されなかったときに利用されるデフォルトのComparator。 オブジェクト自身のcompareToを使用す
る。
*/
private static final Comparator DEFAULT_COMPARATOR = new Comparator()
{
public int compare(Object o1, Object o2) {
return ((Comparable) o1).compareTo(o2);
}
};
/**
* オブジェクトを格納する配列の長さの初期値
*/
private static final int DEFAULT_INITIAL_CAPACITY = 16;
/**
* オブジェクトの比較で使用するComparator
*/
private final Comparator comparator;
/**
* オブジェクトを格納する配列
*/
private Object[] objects;
/**
* 保持しているオブジェクトの数
*/
private int size = 0;

/**
* デフォルトのComparatorと配列の長さを使用してインスタンスを構築する。
*/
public Heap() {
this(DEFAULT_COMPARATOR, DEFAULT_INITIAL_CAPACITY);
}

/**
* デフォルトのComparatorと指定された配列の長さを使用してインスタンスを構築する。
*
* @param initialCapacity
* オブジェクトを保持する配列の長さの初期値
*/
public Heap(int initialCapacity) {
this(DEFAULT_COMPARATOR, initialCapacity);
}

/**
* 指定されたComparatorとデフォルトの配列の長さを使用してインスタンスを構築する。
*
* @param comparator
* 比較に使用するComparator
*/
public Heap(Comparator comparator) {
this(comparator, DEFAULT_INITIAL_CAPACITY);
}

/**
* 指定されたComparatorと配列の長さを使用してインスタンスを構築する。
*
* @param comparator
* 比較に使用するComparator
* @param initialCapacity
* オブジェクトを保持する配列の長さの初期値
*/
public Heap(Comparator comparator, int initialCapacity) {
this.comparator = comparator;
objects = new Object[initialCapacity];
}

/**
* ヒープ構造にオブジェクトを追加する。
*
* @param object
* 追加するオブジェクト
*/
public void push(Object object) {
int n = ++size;

// 領域が足りない場合は拡張する
while (n >= objects.length) {
expand();
}

objects[n] = object;
toRoot(n);
}

/**
* ヒープ構造の先頭にあるオブジェクトを返す。取り出されたオブジェクトはヒープ構造から取り除かれる。
*
* @return 先頭のオブジェクト
*/
public Object pop() {
Object result = objects[1];

if (result == null) {
return null;
}

int n = size--;
objects[1] = objects[n];
objects[n] = null;
toLeaf(1);
return result;
}

/**
* ヒープ構造の先頭にあるオブジェクトを返す。取り出されたオブジェクトをヒープ構造から取り除かれない。
*
* @return 先頭のオブジェクト
*/
public Object head() {
final Object result = objects[1];

return result;
}

/**
* ヒープ構造からオブジェクトを取り除く
*
* @param object
* 取り除くオブジェクト
*/
public void remove(Object object) {
int n = find(object);
if (n == -1) {
return;
}

objects[n] = objects[size];
objects[size--] = null;
toRoot(n);
toLeaf(n);

int temp = 0;
}

/**
* 葉から根に向かってヒープを更新する。
*
* @param n
* 更新を始める位置を表す配列の添え字
*/
private void toRoot(int n) {
if (objects[n] == null) {
return;
}

int n2;
while (1 < n && less(objects[n], objects[n2 = n / 2])) {
swap(n2, n);
n = n2;
}
}

/**
* 根から葉に向かってヒープを更新する
*
* @param n
* 更新を始める位置を表す配列の添え字
*/
private void toLeaf(int n) {
if (objects[n] == null) {
return;
}

int n2, n21;

while ((n2 = n * 2) <= size) {
int nextN = 0;

// 親より左の子が小さい場合
if (less(objects[n2], objects[n])) {
nextN = n2;
}

// 親より右の子が小さく、左の子より右の子の方が小さい場合
if ((n21 = n2 + 1) <= size && less(objects[n21], objects[n]) &&
less(objects[n21], objects[n2])) {
nextN = n21;
}

if (nextN != 0) {
swap(n, nextN);
n = nextN;
} else {
break;
}
}
}

/**
* 保持しているComparatorを使用してオブジェクト同士を比較する。operator<()互換。
*
* @param o1
* 左辺
* @param o2
* 右辺
* @return &lt;が成立すればture
*/
private boolean less(Object o1, Object o2) {
try {
return comparator.compare(o1, o2) < 0;
} catch (Exception e) {
e.printStackTrace();
}
return false;
}

/**
* 配列中のオブジェクトを交換する
*
* @param i
* 左辺
* @param j
* 右辺
*/
private void swap(int i, int j) {
Object o = objects[i];
objects[i] = objects[j];
objects[j] = o;
}

/**
* 配列中から線形探索でオブジェクトを探す
*
* @param object
* 探すオブジェクト
* @return オブジェクトの位置。見つからなかった場合は-1を返す。
*/
private int find(Object object) {
for (int i = 1; i <= size; ++i) {
if (object == objects[i]) {
return i;
}
}

return -1;
}

/**
* 配列の長さを拡張する
*/
private void expand() {
Object[] newObjects = new Object[objects.length * 2];
for (int i = 1; i < objects.length; ++i) {
objects[i] = newObjects[i];
}
objects = newObjects;
}
}
----ここまでHeap.java----