Более быстрый способ, о котором я могу думать, заключается в создании структуры данных, которая отражает эти значения свойств объекта и удерживает внутренний индекс для каждого значения.
При поиске значения эта внутренняя структура данных вернет индекс, используя двоичный поиск.
Единственное требование - ваш объект должен зарегистрировать и обновить эту структуру.
что-то вроде следующего мысленного 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 ...
И вы будете иметь два (в данном случае) отдельные массивы, которые после сортировки будут:
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"]
И выполнит бинарный поиск на нем для «Reyes», который вернет элемент в позиции 2, который, в свою очередь, вернет индекс = 1, который является позицией «Оскар» в исходном массиве.
Это должен держать все под O (журнал N)
Преждевременная оптимизация? –
вам не следует использовать Массивы, если вам не нужно, списки - лучшее решение в 99.99999% всех случаев. –
Почему это вопрос Java Object Question? – fastcodejava