The faster way I can think of, is to create a data structure which mirrors this objects property values and hold the internal index for each value has.
When a value is searched, this internal data structure will return the index using binary search.
The only requirement is your object must register and update this structure.
Something like the following imaginary UML/Python like code:
// 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
Oops
I hope this is understandable.
The point is, if you really what to have this really fast, you have to hold the indexes by property
- An array for the data
- An array for each property, which in turn would have the index of data
For instance if you have the following array:
a = [ Object(name="Mike", lastName="Z" )
Object(name="Oscar", lastName="Reyes" ) ,
Object(name="Rahul", lastName="G" ) ,
Object(name="Pie", lastName="154" ) ]
They would have the positions:
0 = Mike ...
1 = Oscar ...
2 = Rahul ...
3 = Pie ...
And you'll have two ( in this case ) separate arrays which after being sorted would be:
nameArray = ["Mike=0", "Oscar=1", "Pie=3", "Rahul=2"]
and
lastNameArray = ["154=3", "G=2", "Reyes=1", "Z=0"]
When you search for a given attribute, you take the corresponding array, for instance, if you wan to search the last name "Reyes" you'll take "lastName" array
["154=3", "G=2", "Reyes=1", "Z=0"]
And will perform binarySearch on it for "Reyes" which will return the element at position 2, which in turn will return the index = 1 whih is the position "Oscar" has in the original array.
This should keep things under O(log n)
