数据结构,可以做"选择不同的X,其中W = w和Y = y和Z = z和......"类型查找

Question

我有一组独特的向量(10k的价值).对于任何选定的列,我需要提取在该列中看到的值集,其中所有其他列都是给定值的行.

我希望在空间中提供一个亚线性(项目计数)和最多线性(所有项目的总大小)的解决方案,最好是仅存储项目的子线性额外空间.

我能得到那个还是更好？

BTW:它将从python访问,需要简单编程或成为现有常用库的一部分.

---

编辑:成本用于查找,并且不包括构建结构的时间.在进行第一次查询之前,所有将被索引的数据都可用.

---

看起来我在描述我正在寻找的东西方面做得不好,所以这里有一个接近的解决方案:

class Index:
  dep __init__(self, stuff):  # don't care about this O() time
    self.all = set(stuff)
    self.index = {}
    for item in stuff:
      for i,v in item:
        self.index.getdefault(i,set()).add(v)

  def Get(self, col, have):  # this O() matters
    ret = []
    t = array(have)  # make a copy.
    for i in self.index[col]:
      t[col] = i
      if t in self.all:
        ret.append(i)
    return ret

问题是,这给了真正糟糕的(O(n))最坏情况.

Answer 1

既然您要求类似SQL的查询,那么使用关系数据库呢？SQLite是标准库的一部分,可以在磁盘上使用,也可以在内存中使用.

Answer 2

如果你有一套Python套装(没有订购),那么在没有至少查看所有项目的情况下无法选择所有相关项目 - 因此任何解决方案都不可能是"子线性"(根据项目数量) .

如果你有一个列表,而不是一个集合,那么它可以被订购 - 但是在一般情况下无法在线性时间内实现(O(N log N)可证明是你可以做的最好的一般案例排序 - 并建立排序的索引会有类似的 - 除非有限制让你使用"桶式排序"方法).你可以在数据结构中保持索引覆盖所有插入所花费的时间 - 但这不会减少构建这些索引所需的总时间,正如我所说,只是将它们传播开来.

基于散列(未排序)的索引可以更快地针对您的特殊情况(您只需要通过相等而不是"小于"&c)进行选择 - 但构建此类索引的时间与项目数量呈线性关系(显然你不能构建这样一个索引而不至少在每个项目上查看一次 - 次线性时间需要一些魔法让你完全忽略某些项目,并且如果不支持"结构"(例如排序)就不会发生转弯需要时间来实现(虽然它可以提前"递增"地实现,但这种方法不会减少所需的总时间).

所以,接受这封信,你的要求似乎过度约束:无论是Python,任何其他语言,还是任何数据库引擎等,都无法实现它们 - 如果按字面意思解释就像你说的那样.如果"提前完成的增量工作"不计算(违反您对线性和次线性的要求),如果您采取预期/典型而不是最坏情况的行为(并且您的项目具有友好的概率分布)等,那么有可能接近实现您非常苛刻的要求.

例如,考虑为每个向量的D维度维护一个字典,该字典将项目在该维度中具有的值映射到这些项目的一组索引; 然后,为每个维度选择满足D-1相等要求的项目,但是i可以通过设置交叉点来完成.这符合您的要求吗？正如我上面所解释的那样,不是将后者严格地写在字母上 - 但也许,取决于每个要求可以在更"轻松"的意义上采取多少.

顺便说一句,我不明白什么是"分组依据"意味着在这里,因为每个组中的所有向量是相同的(因为你说的所有方面,但一个由平等指定的),所以它可能是你已经跳了COUNT(*)在你的SQL等价物 - 也就是说,你需要计算在第i个维度中有多少这样的向量具有给定值.在这种情况下,通过上述方法可以实现.

编辑:由于OP在评论中有所澄清,他的QI编辑可以提出更详细的方法:

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,)])

当然可以很容易地专门用于以其他格式返回结果,以不同的方式接受索引(索引和/或返回)等等.我相信它满足编辑/澄清的要求,因为额外的存储是,对于每个索引维度/值,在该维度上出现所述值的一组索引,搜索时间是每个索引维度的一个集合交集加上要返回的项目数的循环.