Квази-случайных последовательностей: как улучшить стиль и тестов?


Требования для этого были (первоначально так вопрос):

  • Генерировать случайные-ишь последовательность элементов.
  • Последовательность должна быть у каждого элемента N раз.
  • Последовательность не должна иметь серийный работает дольше, чем заданное число (длинной ниже).

Решение на самом деле был разработан другой пользователь, это моя реализация (под влиянием случайных.перетасовать).

from random import random
from itertools import groupby # For testing the result
try: xrange
except: xrange = range

def generate_quasirandom(values, n, longest=3, debug=False):
  # Sanity check
  if len(values) < 2 or longest < 1:
    raise ValueError

  # Create a list with n * [val]
  source = []
  sourcelen = len(values) * n
  for val in values:
    source += [val] * n

  # For breaking runs
  serial = 0
  latest = None

  for i in xrange(sourcelen):
    # Pick something from source[:i]
    j = int(random() * (sourcelen - i)) + i
    if source[j] == latest:
      serial += 1
      if serial >= longest:
        serial = 0
        guard = 0
        # We got a serial run, break it
        while source[j] == latest:
          j = int(random() * (sourcelen - i)) + i
          guard += 1
          # We just hit an infinit loop: there is no way to avoid a serial run
          if guard > 10:
            print("Unable to avoid serial run, disabling asserts.")
            debug = False
            break
    else:
      serial = 0
    latest = source[j]
    # Move the picked value to source[i:]
    source[i], source[j] = source[j], source[i]

  # More sanity checks
  check_quasirandom(source, values, n, longest, debug)

  return source


def check_quasirandom(shuffled, values, n, longest, debug):
  counts = []
  # We skip the last entries because breaking runs in them get too hairy
  for val, count in groupby(shuffled):
    counts.append(len(list(count)))
  highest = max(counts)
  print('Longest run: %d\nMax run lenght:%d' % (highest, longest))

  # Invariants
  assert len(shuffled) == len(values) * n
  for val in values:
    assert shuffled.count(val) == n

  if debug:
    # Only checked if we were able to avoid a sequential run >= longest
    assert highest <= longest

for x in xrange(10, 1000):
  generate_quasirandom((0, 1, 2, 3), 1000, x//10, debug=True)

Я хочу получать ввод у вас на улучшить этот код, в комментарии к тесты и что-нибудь еще вы можете думать.



864
13
задан 25 января 2011 в 11:01 Источник Поделиться
Комментарии
1 ответ

Две возможные улучшения кода, которые я заметил:

sourcelen = len(values) * n

Это кажется излишне сложным для меня. Я имею в виду, после второго мышления читателя этой линии будет понимать, что лен(значения) * Н - это действительно длина источника, но это еще один шаг мышления больше, чем потребовалось бы, если бы ты сделал sourcelen = лен(источник) (после заполнения источника конечно).

Это, как говорится, я не понимаю, почему нужно сохранять длину источника в переменную вообще. Делаешь для меня в xrange(лен(источник)): не менее читаемым и менее эффективно, чем делает для меня в xrange(sourcelen):, так что я бы просто избавиться от переменной в целом.


source = []
for val in values:
source += [val] * n

Это может быть написано как постижение список такой:

source = [x for val in values for x in [val]*n]

Используя списочные включения обычно считаются более идиоматические питона, чем создание списка итерационно. Это также часто более эффективным.

Как Фред Nurk указывает, постижение список также может быть записан как

source = [val for val in values for _ in xrange(n)]

что позволяет избежать создания временного списка и, возможно, немного более читаемым.


j = int(random() * (sourcelen - i)) + i

Чтобы получить случайное целое число между х (включительно) и г (эксклюзив), вы можете использовать случайный.randrange(Х,Y), так что выше может быть записан как:

j = randrange(i, len(source) - i)

(Вы также должны импортировать randrange , а не случайно от случайных модуля). Это делает его более сразу очевидно, что J не является случайным числом между я и лен(источник) - я и требует меньше места для ошибок.

3
ответ дан 26 января 2011 в 11:01 Источник Поделиться