Если у вас есть набор Python (без упорядочивания), невозможно выбрать все релевантные элементы, по крайней мере, не глядя на все элементы, поэтому невозможно, чтобы какое-либо решение было «сублинейным» (по количеству элементов) как вам требуется.
Если у вас есть список, а не набор, его можно упорядочить, но этого нельзя достичь за линейное время в общем случае (O(N log N), несомненно, лучшее, что вы можете сделать для сортировки в общем случае) - и построение отсортированных индексов будет аналогичным - если только нет ограничений, которые позволят вам использовать подходы типа сортировки по сегментам). Вы можете распределить время, необходимое для сохранения индексов по всем вставкам в структуре данных, но это не сократит общее время, необходимое для построения таких индексов, просто, как я уже сказал, распределите их вокруг.
Индексы, основанные на хэше (не отсортированные), могут быть быстрее для вашего особого случая (когда вам нужно выбирать только по равенству, а не по «меньше чем» & c), но время для создания таких индексов линейно по числу элементов (очевидно, вы не можете создать такой индекс, не смотря хотя бы один раз на каждый элемент - сублинейное время требует некоторой магии, которая позволяет полностью игнорировать определенные элементы, и это не может произойти без поддержки «структуры» (такой как сортировка ) что, в свою очередь, требует времени для достижения (хотя это может быть достигнуто «постепенно» заранее, такой подход не сокращает общее требуемое время).
Итак, в буквальном смысле ваши требования кажутся чрезмерными: ни Python, ни какой-либо другой язык, ни какой-либо механизм базы данных и т. Д. Не могут их достичь - если интерпретировать их буквально в том виде, в каком вы их изложили. Если «инкрементная работа, выполненная раньше времени» не учитывается (как нарушение требований линейности и сублинейности), если вы выбираете поведение, ожидаемое / типичное, а не наихудшее (и ваши элементы имеют дружественные распределения вероятностей) и т. Д., То близко может удовлетворить ваши очень требовательные запросы.
Например, рассмотрите возможность сохранения для каждого из измерений векторов D словаря, отображающего значение, которое элемент имеет в этом измерении, на набор индексов таких элементов; затем, выбирая элементы, которые удовлетворяют требованиям равенства D-1 для каждого измерения, но i th, можно выполнить с помощью установленных пересечений. Соответствует ли это вашим требованиям? Не сводя последнее строго к букве, как я объяснил выше, но возможно, в зависимости от того, насколько каждое требование может быть принято в более «расслабленном» смысле.
Кстати, я не понимаю, что здесь подразумевается под «группой по», поскольку все векторы в каждой группе будут идентичны (поскольку вы сказали, что все измерения, кроме одного, определены равенством), так что, возможно, вы пропустил COUNT(*) в вашем SQL-эквиваленте - т. е. вам нужно подсчитать, сколько таких векторов имеют заданное значение в i-м измерении. В этом случае это было бы достижимо с помощью вышеуказанного подхода.
Редактировать : поскольку ФП несколько разъяснил в комментариях и редактировании своего Q, я могу предложить подход более подробно:
import collections
class Searchable(object):
def __init__(self, toindex=None):
self.toindex = toindex
self.data = []
self.indices = None
def makeindices(self):
if self.indices is not None:
return
self.indices = dict((i, collections.defaultdict(set))
for i in self.toindex)
def add(self, record):
if self.toindex is None:
self.toindex = range(len(record))
self.makeindices()
where = len(self.data)
self.data.append(record)
for i in self.toindex:
self.indices[i][record[i]].add(where)
def get(self, indices_and_values, indices_to_get):
ok = set(range(len(self.data)))
for i, v in indices_and_values:
ok.intersection_update(self.indices[i][v])
result = set()
for rec in (self.data[i] for i in ok):
t = tuple(rec[i] for i in indices_to_get)
result.add(t)
return result
def main():
c = Searchable()
for r in ((1,2,3), (1,2,4), (1,5,4)):
c.add(r)
print c.get([(0,1),(1,2)], [2])
main()
Это печатает
set([(3,), (4,)])
и, конечно, может быть легко специализирован для возврата результатов в других форматах, принятия индексов (для индексации и / или для возврата) различными способами и т. Д. Я считаю, что это соответствует требованиям, которые были отредактированы / уточнены, поскольку дополнительное хранилище, для каждого индексированного измерения / значения - набор индексов, при которых упомянутое значение встречается в этом измерении, а время поиска - это одно пересечение наборов для каждого индексированного измерения плюс цикл по числу элементов, которые должны быть возвращены.