Вопросы Теги

Взвешенный случайный выбор с и без замены

MySQL не устанавливает контрольные ограничения.

Это хорошо документированное отклонение от стандарта SQL. (Хотя это неожиданно для непосвященных.)

Если вам нужна база данных MySQL для обеспечения «контрольного ограничения», принудительное исполнение должно быть закодировано в триггер BEFORE INSERT и BEFORE UPDATE.

Эта заметка:

Предложение CHECK разобрано, но игнорируется всеми механизмами хранения.

blockquote>

похоронен в Справочное руководство по MySQL в синтаксисе CREATE TABLE.

Ссылка: https://dev.mysql.com/doc/refman/5.5/en/create-table.html

ПРЕДУПРЕЖДЕНИЕ О ENUM

ENUM не ограничивает «недействительные» значения от вставки; недопустимое значение переводится в строку нулевой длины, выдается предупреждение, но это не ошибка.

Демонстрация: 

CREATE TABLE foo (gen ENUM('M','F'))

INSERT INTO foo (gen) VALUES ('x')

-- Warning Code : 1265
-- Data truncated for column 'gen' at row 1

SELECT gen, CHAR_LENGTH(gen) FROM foo;

-- gen  CHAR_LENGTH(gen)  
-- ---  ----------------
--                     0

46
задан Nick Johnson 9 December 2008 в 17:06
поделиться

3 ответа

Одним из самых быстрых способов сделать многих с заменяющими образцами из неизменного списка является метод псевдонима. Базовая интуиция - то, что мы можем создать ряд мусорных ведер равного размера для взвешенного списка, который может быть индексирован очень эффективно посредством битовых операций, для предотвращения двоичного поиска. Окажется, что, сделанный правильно, мы должны будем только сохранить два объекта из исходного списка на мусорное ведро, и таким образом можем представить разделение с единственным процентом.

Позволяют нам нас, берут пример пяти одинаково взвешенных вариантов, (a:1, b:1, c:1, d:1, e:1)

Для создания поиска псевдонима:

  1. Нормализуют веса, таким образом, что они суммируют к 1.0. (a:0.2 b:0.2 c:0.2 d:0.2 e:0.2) Это - вероятность выбора каждого веса.

  2. Находят самое маленькое питание 2 больших, чем или равный количеству переменных и создают это количество разделов, |p|. Каждый раздел представляет вероятностную меру 1/|p|. В этом случае мы создаем 8 разделы, каждый, который в состоянии содержать 0.125.

  3. Берут переменную с наименее сохраняющим весом и место как можно больше, он - масса в пустом разделе. В этом примере мы видим что a заливки первый раздел. (p1{a|null,1.0},p2,p3,p4,p5,p6,p7,p8) с (a:0.075, b:0.2 c:0.2 d:0.2 e:0.2)

  4. , Если раздел не заполнен, возьмите переменную с большей частью веса и заполните раздел той переменной.

Повторные шаги 3 и 4, пока ни один из веса от исходного раздела не должен быть присвоенным списку.

, Например, если мы выполняем другое повторение 3 и 4, мы видим

(p1{a|null,1.0},p2{a|b,0.6},p3,p4,p5,p6,p7,p8) с [1 111] оставленный быть присвоенными

Во времени выполнения:

  1. Добирается U(0,1) случайное число, говорит двоичный файл 0.001100000

  2. сдвиг разряда это lg2(p), находя индексный раздел. Таким образом мы смещаем его на [1 115], уступая 001.1, или положение 1, и таким образом раздел 2.

  3. , Если раздел разделяется, используйте десятичную часть смещенного случайного числа для решения разделения. В этом случае значение 0.5, и 0.5 < 0.6, так возврат a.

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

32
ответ дан Regexident 8 November 2019 в 00:24
поделиться

Вот то, что я придумал для взвешенного выбора без замены: 

def WeightedSelectionWithoutReplacement(l, n):
  """Selects without replacement n random elements from a list of (weight, item) tuples."""
  l = sorted((random.random() * x[0], x[1]) for x in l)
  return l[-n:]

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

Вот то, что я придумал для взвешенного выбора с заменой: 

def WeightedSelectionWithReplacement(l, n):
  """Selects with replacement n random elements from a list of (weight, item) tuples."""
  cuml = []
  total_weight = 0.0
  for weight, item in l:
    total_weight += weight
    cuml.append((total_weight, item))
  return [cuml[bisect.bisect(cuml, random.random()*total_weight)] for x in range(n)]

Это - O (m + n, регистрируют m), где m является количеством объектов во входном списке, и n является количеством объектов, которые будут выбраны.

5
ответ дан Nick Johnson 8 November 2019 в 00:24
поделиться

Я рекомендовал бы запустить путем рассмотрения раздела 3.4.2 из Donald Knuth Получисловые Алгоритмы .

, Если Ваши массивы являются большими, существуют более эффективные алгоритмы в главе 3 Принципы Генерации случайных переменных John Dagpunar. Если Ваши массивы не являются ужасно большими, или Вы не обеспокоены отжиманием как можно большей эффективности, более простые алгоритмы в Knuth прекрасны, вероятно.

4
ответ дан John D. Cook 8 November 2019 в 00:24
поделиться