Есть ли код для подкласса, установленного в Python для больших xranges?

Question

Я пытаюсь написать некоторый код Python, который включает объединение / пересечение множеств, которые потенциально могут быть очень большими. В большинстве случаев эти наборы будут по существу set(xrange(1<<32)) или чем-то в этом роде, но часто встречаются диапазоны значений, которые не принадлежат к набору (скажем, «бит 5 не может быть очищен»), или выбрасываются дополнительные значения в. По большей части заданное содержимое может быть выражено алгоритмически.

Я могу пойти и сделать грязную работу для подкласса set и создать что-то, но я чувствую, что это должно быть то, что было сделано раньше, и я не хочу тратить дни на переосмысление колеса.

Да, и чтобы сделать это еще сложнее, после того, как я создал набор, мне нужно иметь возможность перебирать его в произвольном порядке. Быстро. Даже если в наборе есть миллиард записей. (И этот набор с миллиардами записей лучше не занимать гигабайты, потому что их у меня будет много.)

Есть ли там код? У кого-нибудь есть аккуратные трюки? Я спрашиваю о луне?

Answer 1

Вы говорите:

По большей части заданное содержимое может быть выражено алгоритмически.

Как насчет написания класса, который представляет весь набор API, но определяет включение множества в алгоритм. Затем с несколькими классами, которые оборачиваются вокруг других наборов для алгоритмического объединения и пересечения.

Например, если у вас есть набор a и набор b, которые являются экземплярами этих псевдо-наборов:

>>> u = Union(a, b)

И затем вы используете u с полным набором API, который развернется и запросит a и b, используя правильную логику. Все методы set могут быть спроектированы так, чтобы автоматически возвращать эти псевдо-объединения / пересечения, поэтому весь процесс прозрачен.

Редактировать: Быстрый пример с очень ограниченным API:

class Base(object):

    def union(self, other):
        return Union(self, other)

    def intersection(self, other):
        return Intersection(self, other)

class RangeSet(Base):

    def __init__(self, low, high):
        self.low = low
        self.high = high

    def __contains__(self, value):
        return value >= self.low and value < self.high

class Union(Base):
    def __init__(self, *sets):
        self.sets = sets

    def __contains__(self, value):
        return any(value in x for x in self.sets)

class Intersection(Base):

    def __init__(self, *sets):
        self.sets = sets

    def __contains__(self, value):
        return all(value in x for x in self.sets)


a = RangeSet(0, 10)
b = RangeSet(5, 15)

u = a.union(b)
i = a.intersection(b)

print 3 in u
print 7 in u
print 12 in u

print 3 in i
print 7 in i
print 12 in i

Бег дает вам:

True
True
True
False
True
False

Answer 2

Вы пытаетесь создать набор, содержащий все целочисленные значения в диапазоне от 0 до 4 294 967 295. Байт составляет 8 бит, что дает вам 255. 99,9999940628% ваших значений имеют размер более одного байта. Общий минимальный размер вашего набора, даже если вы можете преодолеть синтаксические проблемы, составляет 4 миллиарда байт или 4 ГБ.

Вы никогда не сможете хранить экземпляр этого набора менее чем в ГБ памяти. Даже со сжатием, это, вероятно, будет жестким сжатием. Вы должны быть намного умнее со своей математикой. Вы можете воспользоваться некоторыми свойствами набора. В конце концов, это очень особенный набор. Что вы пытаетесь сделать?

Answer 3

Я бы не стал создавать подклассы set, поскольку очевидно, что вы не сможете использовать повторно ни одну часть реализации set. Я бы даже не стал создавать подклассы collections.Set, поскольку последний требует от вас предоставить __len__ - функциональность, которая, как вам кажется, не нужна в противном случае, и просто не может быть эффективно выполнена в общем случае (это будет O(N), с, размер которого вы говорите, слишком медленный). Вам вряд ли удастся найти какую-либо существующую реализацию, которая достаточно хорошо соответствует вашему варианту использования, чтобы ее можно было использовать повторно, потому что ваши требования очень специфичны и даже своеобразны - например, концепция «случайной итерации и случайного дублирования в порядке» действительно необычный.

Если ваши спецификации завершены (вам нужны только объединение, пересечение и случайная итерация, а также случайные добавления и удаления отдельных элементов), реализация класса специального назначения, который заполняет эти спецификации, не является сумасшедшей задачей. Если у вас есть больше спецификаций, которые вы явно не упомянули, это будет сложнее, но трудно угадать, не услышав все спецификации. Так, например, что-то вроде:

import random

class AbSet(object):
  def __init__(self, predicate, maxitem=1<<32):
    # set of all ints, >=0 and <maxitem, satisfying the predicate
    self.maxitem = maxitem
    self.predicate = predicate
    self.added = set()
    self.removed = set()

  def copy(self):
    x = type(self)(self.predicate, self.maxitem)
    x.added = set(self.added)
    x.removed = set(self.removed)
    return x

  def __contains__(self, item):
    if item in self.removed: return False
    if item in self.added: return True
    return (0 <= item < self.maxitem) and self.predicate(item)

  def __iter__(self):
    # random endless iteration
    while True:
      x = random.randrange(self.maxitem)
      if x in self: yield x

  def add(self, item):
    if item<0 or item>=self.maxitem: raise ValueError
    if item not in self:
      self.removed.discard(item)
      self.added.add(item)

  def discard(self, item):
    if item<0 or item>=self.maxitem: raise ValueError
    if item in self:
      self.removed.add(item)
      self.added.discard(item)

  def union(self, o):
    pred = lambda v: self.predicate(v) or o.predicate(v),
    x = type(self)(pred, max(self.maxitem, o.maxitem))
    toadd = [v for v in (self.added|o.added) if not pred(v)]
    torem = [v for v in (self.removed|o.removed) if pred(v)]
    x.added = set(toadd)
    x.removed = set(torem)

  def intersection(self, o):
    pred = lambda v: self.predicate(v) and o.predicate(v),
    x = type(self)(pred, min(self.maxitem, o.maxitem))
    toadd = [v for v in (self.added&o.added) if not pred(v)]
    torem = [v for v in (self.removed&o.removed) if pred(v)]
    x.added = set(toadd)
    x.removed = set(torem)

Я не совсем уверен в логике определения, добавляемой и удаляемой при объединении и пересечении, но я надеюсь, что это хорошая база для работы с вами.

Answer 4

Похоже, что это может перекрываться с линейным программированием. В линейном программировании вы пытаетесь найти какой-то оптимальный случай, когда вы добавляете ограничения к набору значений (обычно целых), которые изначально могут быть очень большими. Существуют различные библиотеки, перечисленные в http://wiki.python.org/moin/NumericAndScientific/Libraries, в которых упоминается целочисленное и линейное программирование, но ничто не выдается за то, что вы явно хотите.

Answer 5

Если вы используете python 3.0, вы можете создавать коллекции подклассов. Установите