次のような正の値のみを持つn:nマトリックスがあるとします。short
0 1 0 3
1 0 5 6
7 1 0 4
6 2 7 9
m:mこの行列内で、0 より大きい値を最も多く含む行列を探しています。私の問題は、これまでの解決策がn(nor m) でうまくスケーリングされないことです。
実際、n:nマトリックスは製品の価格を表し、軸は特定の (任意の) 日からの日数を表しています。そのため、特定の時間間隔で価格を検索できます。マトリックスは実際にはm:m、価格のサブセット (ビューなど) を含む 7 x 7 マトリックスです。n:n最も多くの価格が記入されているマトリックスの部分を探しています。
上記の例では、m:mマトリックスは
7 1
6 2
2 はどこmですか。
これまでに作成したプロトタイプの関連部分は次のとおりです。
private static class ResultMatrixData {
private byte fillCount;
private short distanceFromToday;
public ResultMatrixData() {
fillCount = 0;
distanceFromToday = Short.MAX_VALUE;
}
public ResultMatrixData(short[][] pricesMatrix, short iArg, short jArg) {
byte fillCount = 0;
for (int i = iArg; i < iArg + 7; i++) {
for (int j = jArg; j < jArg + 7; j++) {
if (pricesMatrix[i][j] > 0) {
fillCount++;
}
}
}
this.fillCount = fillCount;
distanceFromToday = iArg > jArg ? iArg : jArg;
}
}
private ResultMatrixData calculateSingleResult(short[][] pricesMatrix) {
ResultMatrixData bestSoFar = new ResultMatrixData();
ResultMatrixDataComparator comparator = new ResultMatrixDataComparator();
for (short i = 0; i < NUMBER_OF_DAYS - 6; i++) {
for (short j = 0; j < NUMBER_OF_DAYS - 6; j++) {
ResultMatrixData current = new ResultMatrixData(pricesMatrix, i, j);
if (comparator.compare(current, bestSoFar) >= ResultMatrixDataComparator.GREATER_THAN) {
bestSoFar = current;
}
}
}
return bestSoFar;
}
private static class ResultMatrixDataComparator implements Comparator<ResultMatrixData> {
private static final int LESS_THAN = -1;
private static final int EQUAL = 0;
private static final int GREATER_THAN = 1;
@Override
public int compare(ResultMatrixData first, ResultMatrixData second) {
if (first.fillCount > second.fillCount) {
return GREATER_THAN;
} else if (first.fillCount < second.fillCount) {
return LESS_THAN;
} else {
if (first.distanceFromToday < second.distanceFromToday) {
return GREATER_THAN;
} else if (first.distanceFromToday > second.distanceFromToday) {
return LESS_THAN;
}
}
return EQUAL;
}
}
私の問題は、実行時間が二次または指数関数的に見えることです（正確な漸近分析を実行しませんでした）：
n (days) | running time in ms
1 * 365 | 48
2 * 365 | 123
3 * 365 | 278
4 * 365 | 482
5 * 365 | 733
6 * 365 | 1069
7 * 365 | 1438
8 * 365 | 1890
9 * 365 | 2383
10 * 365 | 2926
11 * 365 | 3646
12 * 365 | 4208
13 * 365 | 5009
このアルゴリズムを最適化する方法について何か提案はありますか?
注: これは宿題の演習ではありません。
編集：他の人が答えで言ったように、ここでの時間の複雑さは約O（（n- m）^ 2）です。nサブ二次であり、無限に収束しながらうまくスケーリングするものを探しています。