私が考えることができるより速い方法は、このオブジェクトのプロパティ値をミラーリングし、各値の内部インデックスを保持するデータ構造を作成することです。
値が検索されると、この内部データ構造はバイナリ検索を使用してインデックスを返します。
唯一の要件は、オブジェクトがこの構造を登録および更新する必要があることです。
次の架空の UML/Python のようなコードのようなもの:
// Holds the index number of a given value
// for instance, name="Oscar" may be at index 42...
IndexValuePair
index : Int
value : String
+_ new( value: String, index: Int )
return IndexValuePair( value, index )
ValuePairComparator --> Comparator
+ compareTo( a: IndexValuePair, b: IndexValuePair ) : Int
return a.value.compareTo( b.value )
SearchStructure
- data = Object[] // The original array which contains your applicants
// a list of arrays each one containing the property value, and the index on "data" where that value appears
- dataIndexes = List(IndexValuePair)[String] // Map<List<IndexValuePair>>
- dataIndexexInitialized = false
// Add an object to this structure
+ addObject( o: Object )
if( ! dataIndexesInitialized,
initIndexesWith( o )
)
index = data.add( o ) // returns the index at which "o" was inserted
addToIndexes( o, index )
// Register all the properties values of the given object
// along with the index where they appear in the original array
- addToIndexes( object: Object, index: Int )
forEach( property in Object ,
list = dataIndexes[property]
list.add( IndexValuePair.new( property.value, index ) )
)
// Create empty array for each property ..
- initIndexesWith( object : Object )
forEach( property in object ,
comparator = ValuePairComparator()
list = List<IndexValuePair>()
list.setComparator( )
dataIndexes[property] = list
)
dataIndexesInitialized = true
// Search an object using the given criteria ( a Map<String, String> = key=value )
+ search( criteria: String[String] ) : List<Object>
result = Set<Object>()
// let's say criteria has:
// ["name":"Oscar", "lastName"="Reyes"]
forEach( key in criteria,
list = dataIndexes[key] // "name", "lastname" ..etc.
valuePair = list.binarySearch( criteria[key] ) // first Oscar, later Reyes
result.add( data[valuePair.index] )
)
return result
おっとっと
これが理解できることを願っています。
ポイントは、これを本当に高速にするには、プロパティごとにインデックスを保持する必要があるということです
- データの配列
- 各プロパティの配列。これにはデータのインデックスが含まれます。
たとえば、次の配列がある場合:
a = [ Object(name="Mike", lastName="Z" )
Object(name="Oscar", lastName="Reyes" ) ,
Object(name="Rahul", lastName="G" ) ,
Object(name="Pie", lastName="154" ) ]
彼らはポジションを持っています：
0 = Mike ...
1 = Oscar ...
2 = Rahul ...
3 = Pie ...
そして、2 つ (この場合) の別々の配列があり、並べ替えた後は次のようになります。
nameArray = ["Mike=0", "Oscar=1", "Pie=3", "Rahul=2"]
と
lastNameArray = ["154=3", "G=2", "Reyes=1", "Z=0"]
特定の属性を検索するときは、対応する配列を取得します。たとえば、姓「Reyes」を検索する場合は、「lastName」配列を取得します
["154=3", "G=2", "Reyes=1", "Z=0"]
そして、位置 2 の要素を返す "Reyes" に対して binarySearch を実行し、元の配列での "Oscar" の位置である index = 1 を返します。
これにより、O（log n）以下に保つ必要があります