python - 可以进行 "select distinct X where W=w and Y=y and Z=z and ..."类型查找的数据结构

Question

我有一组独特的向量(值(value) 10k)。对于任何选定的列，我需要提取在该列中看到的值集，在所有其他列都被赋予值的行中。

我希望解决方案在时间上是次线性的(关于项目计数)，在空间上至多是线性的(关于所有项目的总大小)，最好是次线性的额外空间而不是仅存储项目。

我能得到那个或更好的吗？

顺便说一句:它将通过 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 是标准库的一部分，可以在磁盘上或完全在内存中使用。