Набор Python со способностью вызывать случайный элемент

Мне нужен объект Python (2.7), который функционирует как набор (быстрая вставка, удаление и проверка принадлежности), но имеет возможность вернуть случайное значение. Предыдущие вопросы, заданные в stackoverflow, имеют следующие ответы:

import random
random.sample(mySet, 1)

Но это довольно медленно для больших множеств (он работает в O (n) времени).

Другие решения не являются достаточно случайными (они зависят от внутреннего представления наборов python, что приводит к очень неслучайным результатам):

for e in mySet:
    break
# e is now an element from mySet

Я закодировал свой собственный рудиментарный класс, который имеет постоянный поиск, удаление и случайные значения времени.

class randomSet:
    def __init__(self):
        self.dict = {}
        self.list = []

    def add(self, item):
        if item not in self.dict:
            self.dict[item] = len(self.list)
            self.list.append(item)

    def addIterable(self, item):
        for a in item:
            self.add(a)

    def delete(self, item):
        if item in self.dict:
            index = self.dict[item]
            if index == len(self.list)-1:
                del self.dict[self.list[index]]
                del self.list[index]
            else:
                self.list[index] = self.list.pop()
                self.dict[self.list[index]] = index
                del self.dict[item]

    def getRandom(self):
        if self.list:
            return self.list[random.randomint(0,len(self.list)-1)]

    def popRandom(self):
        if self.list:
            index = random.randint(0,len(self.list)-1)
            if index == len(self.list)-1:
                del self.dict[self.list[index]]
                return self.list.pop()
            returnValue = self.list[index]
            self.list[index] = self.list.pop()
            self.dict[self.list[index]] = index
            del self.dict[returnValue]
            return returnValue

Есть ли какие-либо улучшения для этого или какие-либо большие улучшения в этом коде?

Ответы

Ответ 1

Я думаю, что лучший способ сделать это - использовать MutableSet абстрактный базовый класс в collections. Наследовать от MutableSet, а затем определить add, discard, __len__, __iter__ и __contains__; также перепишите __init__, чтобы, возможно, принять последовательность, как это делает конструктор set. MutableSet предоставляет встроенные определения всех других методов set, основанных на этих методах. Таким образом, вы получите полный set интерфейс дешево. (И если вы это сделаете, addIterable определяется для вас под именем extend.)

discard в стандартном интерфейсе set представляется тем, что вы назвали delete здесь. Поэтому переименуем delete в discard. Кроме того, вместо отдельного метода popRandom вы можете просто определить popRandom следующим образом:

def popRandom(self):
    item = self.getRandom()
    self.discard(item)
    return item

Таким образом, вам не нужно поддерживать два метода удаления отдельных элементов.

Наконец, в методе удаления элемента (delete теперь discard в соответствии со стандартным интерфейсом набора) вам не нужен оператор if. Вместо того, чтобы тестировать index == len(self.list) - 1, просто поменяйте конечный элемент в списке на элемент в индексе списка, который нужно выставить, и внесите необходимые изменения в словарь обратного индексирования. Затем вытащите последний элемент из списка и удалите его из словаря. Это работает независимо от того, index == len(self.list) - 1 или нет:

def discard(self, item):
    if item in self.dict:
        index = self.dict[item]
        self.list[index], self.list[-1] = self.list[-1], self.list[index]
        self.dict[self.list[index]] = index
        del self.list[-1]                    # or in one line:
        del self.dict[item]                  # del self.dict[self.list.pop()]

Ответ 2

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

Затем вы можете использовать pop для выбора случайного элемента, и если он не относится к типу соли, повторно вставьте и верните его, но если он имеет тип соли, вставьте новый, случайно генерируемый объект соли ( и поп, чтобы выбрать новый объект).

Это приведет к изменению порядка выбора объектов. В среднем количество попыток будет зависеть от доли солевых элементов, т.е. Амортизированной производительности O (k).

Ответ 3

Нельзя ли реализовать новый класс, наследующий от set, с некоторыми (хакерскими) модификациями, которые позволяют нам извлекать случайный элемент из списка с O (1) временем поиска? Btw, на Python 2.x вы должны наследовать от object, т.е. Использовать class randomSet(object). Также PEP8 - это что-то для вас: -)

Изменить: Для получения некоторых идей о том, какие хакерские решения могут быть способны, этот поток стоит прочитать: http://python.6.n6.nabble.com/Get-item-from-set-td1530758.html

Ответ 4

Да, я бы выполнил "упорядоченный набор" почти так же, как и вы, и использовал список как внутреннюю структуру данных.

Однако я бы наследовал прямо из "набора" и просто отслеживал добавленные элементы в внутренний список (как и вы) - и оставьте методы, которые я не использую в одиночку.

Возможно, добавьте метод "sync" для обновления внутреннего списка всякий раз, когда набор обновляется с помощью специальных операций, таких как методы * _update.

Что, если использование "заказанного дикта" не распространяется на ваши варианты использования. (Я просто обнаружил, что попытка отличить ключи ordered_dict к регулярному набору не оптимизирована, поэтому, если вам нужны заданные операции над вашими данными, которые не являются опцией)

Ответ 5

Если вы не возражаете только поддерживать сопоставимые элементы, вы можете использовать blist.sortedset.

Ответ 6

Вот решение с нуля, которое добавляет и появляется в постоянное время. Я также включил некоторые дополнительные функции набора для демонстрационных целей.

from random import randint


class RandomSet(object):
  """
  Implements a set in which elements can be
  added and drawn uniformly and randomly in
  constant time.
  """

  def __init__(self, seq=None):
    self.dict = {}
    self.list = []
    if seq is not None:
      for x in seq:
        self.add(x)

  def add(self, x):
    if x not in self.dict:
      self.dict[x] = len(self.list)
      self.list.append(x)

  def pop(self, x=None):
    if x is None:
      i = randint(0,len(self.list)-1)
      x = self.list[i]
    else:
      i = self.dict[x]
    self.list[i] = self.list[-1]
    self.dict[self.list[-1]] = i
    self.list.pop()
    self.dict.pop(x)
    return x

  def __contains__(self, x):
    return x in self.dict

  def __iter__(self):
    return iter(self.list)

  def __repr__(self):
    return "{" + ", ".join(str(x) for x in self.list) + "}"

  def __len__(self):
    return len(self.list)