>>> import random
>>> random.choice(list(open('/etc/dictionaries-common/words')))
'jaundiced\n'
Это эффективно с точки зрения человека и времени.
Кстати, ваша реализация совпадает с реализацией из stdlib random.py:
def choice(self, seq):
"""Choose a random element from a non-empty sequence."""
return seq[int(self.random() * len(seq))]
Измерение времени выполнения
Мне было интересно, какова относительная производительность представленных решений. linecache - очевидный фаворит. Насколько медленнее однострочный random.choice по сравнению с честным алгоритмом, реализованным в select_random_line()?
# nadia_known_num_lines 9.6e-06 seconds 1.00
# nadia 0.056 seconds 5843.51
# jfs 0.062 seconds 1.10
# dcrosta_no_strip 0.091 seconds 1.48
# dcrosta 0.13 seconds 1.41
# mark_ransom_no_strip 0.66 seconds 5.10
# mark_ransom_choose_from 0.67 seconds 1.02
# mark_ransom 0.69 seconds 1.04
(каждая функция вызывается 10 раз (производительность в кэше)).
Эти результаты показывают, что простое решение (dcrosta) в этом случае быстрее, чем более обдуманное (mark_ransom).
Код, который использовался для сравнения ( в качестве сущности ):
import linecache
import random
from timeit import default_timer
WORDS_FILENAME = "/etc/dictionaries-common/words"
def measure(func):
measure.func_to_measure.append(func)
return func
measure.func_to_measure = []
@measure
def dcrosta():
words = [line.strip() for line in open(WORDS_FILENAME)]
return random.choice(words)
@measure
def dcrosta_no_strip():
words = [line for line in open(WORDS_FILENAME)]
return random.choice(words)
def select_random_line(filename):
selection = None
count = 0
for line in file(filename, "r"):
if random.randint(0, count) == 0:
selection = line.strip()
count = count + 1
return selection
@measure
def mark_ransom():
return select_random_line(WORDS_FILENAME)
def select_random_line_no_strip(filename):
selection = None
count = 0
for line in file(filename, "r"):
if random.randint(0, count) == 0:
selection = line
count = count + 1
return selection
@measure
def mark_ransom_no_strip():
return select_random_line_no_strip(WORDS_FILENAME)
def choose_from(iterable):
"""Choose a random element from a finite `iterable`.
If `iterable` is a sequence then use `random.choice()` for efficiency.
Return tuple (random element, total number of elements)
"""
selection, i = None, None
for i, item in enumerate(iterable):
if random.randint(0, i) == 0:
selection = item
return selection, (i+1 if i is not None else 0)
@measure
def mark_ransom_choose_from():
return choose_from(open(WORDS_FILENAME))
@measure
def nadia():
global total_num_lines
total_num_lines = sum(1 for _ in open(WORDS_FILENAME))
line_number = random.randint(0, total_num_lines)
return linecache.getline(WORDS_FILENAME, line_number)
@measure
def nadia_known_num_lines():
line_number = random.randint(0, total_num_lines)
return linecache.getline(WORDS_FILENAME, line_number)
@measure
def jfs():
return random.choice(list(open(WORDS_FILENAME)))
def timef(func, number=1000, timer=default_timer):
"""Return number of seconds it takes to execute `func()`."""
start = timer()
for _ in range(number):
func()
return (timer() - start) / number
def main():
# measure time
times = dict((f.__name__, timef(f, number=10))
for f in measure.func_to_measure)
# print from fastest to slowest
maxname_len = max(map(len, times))
last = None
for name in sorted(times, key=times.__getitem__):
print "%s %4.2g seconds %.2f" % (name.ljust(maxname_len), times[name],
last and times[name] / last or 1)
last = times[name]
if __name__ == "__main__":
main()