前処理が許可されていて、時間の複雑さにカウントされない場合は、それを使用してサブリストを作成し、探している要素を効率的に見つけることができます。ほとんどの最適化と同様に、これはスペースを時間と交換します。
前処理のステップは、元のn数字のリストを取得して、いくつかの新しいサブリストを作成することです。
これらのサブリストのそれぞれは、元の要素の一部であり、要素 th から始まり、要素nに拡張されてから並べ替えられます。したがって、元のリストは次のとおりです。m
{3, 1, 7, 5, 9}
あなたにあげる：
list[0][0] = {3}
list[0][1] = {1, 3}
list[0][2] = {1, 3, 7}
list[0][3] = {1, 3, 5, 7}
list[0][4] = {1, 3, 5, 7, 9}
list[1][0] = {1}
list[1][1] = {1, 7}
list[1][2] = {1, 5, 7}
list[1][3] = {1, 5, 7, 9}
list[2][0] = {7}
list[2][1] = {5, 7}
list[2][2] = {5, 7, 9}
list[3][0] = {5}
list[3][1] = {5,9}
list[4][0] = {9}
これは (時間的または空間的に) 安価な操作ではないため、変更操作 (挿入、削除、変更) を行った後、最初にのみ実行するように、リストに「ダーティ」フラグを維持することをお勧めします。
実際、遅延評価を使用してさらに効率を高めることができます。基本的に、開始時および変更操作を実行するたびに、すべてのサブリストを空のリストに設定します。次に、サブリストにアクセスしようとしてそれが空である場合は常に、そのサブリスト (およびその 1 つだけ) を計算してkから、そこから th 値を取得しようとします。
これにより、サブリストが必要な場合にのみ評価され、不必要な再計算を防ぐためにキャッシュされます。たとえば、3 ～ 6 のサブリストの値を要求しない場合、その値は計算されません。
すべてのサブリストを作成するための疑似コードは、基本的に次のとおりです (for両端を含むループ):
for n = 0 to a.lastindex:
create array list[n]
for m = 0 to a.lastindex - n
create array list[n][m]
for i = 0 to m:
list[n][m][i] = a[n+i]
sort list[n][m]
遅延評価のコードはもう少し複雑なので (少しだけ)、そのための疑似コードは提供しません。
次に、(とは元のインデックス) の範囲内で 4 番目に小さい数を見つけるには、非常に高速な O(1) 操作である を検索するだけkです。ijijlists[i][j-i][k-1]
+--------------------------+
| |
| v
1st in range [3,4] (values 5,9), list[3][4-3=1][1-1-0] = 5
2nd in range [1,3] (values 1,7,5), list[1][3-1=2][2-1=1] = 5
3rd in range [0,2] (values 3,1,7), list[0][2-0=2][3-1=2] = 7
| | ^ ^ ^
| | | | |
| +-------------------------+----+ |
| |
+-------------------------------------------------+
これが実際に動作していることを示す Python コードを次に示します。
orig = [3,1,7,5,9]
print orig
print "====="
list = []
for n in range (len(orig)):
list.append([])
for m in range (len(orig) - n):
list[-1].append([])
for i in range (m+1):
list[-1][-1].append(orig[n+i])
list[-1][-1] = sorted(list[-1][-1])
print "(%d,%d)=%s"%(n,m,list[-1][-1])
print "====="
# Gives xth smallest in index range y through z inclusive.
x = 1; y = 3; z = 4; print "(%d,%d,%d)=%d"%(x,y,z,list[y][z-y][x-1])
x = 2; y = 1; z = 3; print "(%d,%d,%d)=%d"%(x,y,z,list[y][z-y][x-1])
x = 3; y = 0; z = 2; print "(%d,%d,%d)=%d"%(x,y,z,list[y][z-y][x-1])
print "====="
予想通り、出力は次のとおりです。
[3, 1, 7, 5, 9]
=====
(0,0)=[3]
(0,1)=[1, 3]
(0,2)=[1, 3, 7]
(0,3)=[1, 3, 5, 7]
(0,4)=[1, 3, 5, 7, 9]
(1,0)=[1]
(1,1)=[1, 7]
(1,2)=[1, 5, 7]
(1,3)=[1, 5, 7, 9]
(2,0)=[7]
(2,1)=[5, 7]
(2,2)=[5, 7, 9]
(3,0)=[5]
(3,1)=[5, 9]
(4,0)=[9]
=====
(1,3,4)=5
(2,1,3)=5
(3,0,2)=7
=====