100 боевиков в кругу убивают следующего человека

Я очень рад, потому что решил эту проблему с очень маленьким кодом:

"""

    100 people are standing in a circle with gun in their hands.
    1 kills 2, 3 kills 4, 5 kills 6 and so on till we are
    left with only one person. Who will be the last person alive?
    Write code to implement this ##efficiently.## <-[ Python is not efficient]

"""

persons = list(range(1,101)) # The question asks 1-indexing

while len(persons) > 1:
    for index, person in enumerate(persons):
        del persons[(index + 1) % len(persons)]

print(persons)
29 голосов | спросил Caridorc 6 PMpMon, 06 Apr 2015 16:15:42 +030015Monday 2015, 16:15:42

1 ответ


68

1. Инкапсуляция

Написание кода на верхнем уровне модуля затрудняет проверку кода и затрудняет измерение его производительности. Лучше всего инкапсулировать код в функцию. Соответственно, я бы написал:

def survivor(n):
    """Return the survivor of a circular firing squad of n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        for index, _ in enumerate(persons):
            del persons[(index + 1) % len(persons)]
    return persons[0]

(переменная person не используется в теле цикла for; для таких переменных она является условной для записи _, и это что я здесь сделал.)

2. Значение эффективности

Теперь, этот код «эффективен», как задает вопрос? Обычно в вычислениях мы используем «эффективный», чтобы ссылаться на алгоритмическую эффективность : то есть на скорость, с которой ресурсы, используемые программа вырастает как функция ввода, обычно выражаемая в обозначении большого О> .

В соответствии с этим взглядом на эффективность язык программирования не имеет значения: эффективность - это свойство алгоритма, а не языка, на котором он реализован. Но вы написали «Python неэффективен», что говорит о том, что у вас есть другое понимание этого слова. Может быть, вы могли бы обновить свой пост, чтобы объяснить, что вы подразумеваете под этим? В оставшейся части этого ответа я собираюсь предположить, что этот вопрос предполагает обычный смысл.

3. Это случайно квадратично

Какова продолжительность выполнения функции survivor, выраженная как функция \ $ n \ $? Итак, посмотрев страницу с временной сложностью на Python Wiki, мы можем видеть, что del операция в списке принимает \ $ O (n) \ $, где \ $ n \ $ - длина списка, и это выполняется один раз для каждого убитого человека, в результате чего общая продолжительность выполнения \ $ O (n ^ 2) \ $.

Можно проверить это экспериментально:

>>> t = 1
>>> for i in range(8, 17):
...     t, u = timeit(lambda:survivor(2**i), number=1), t
...     print('{:6d} {:.6f} {:.2f}'.format(2**i, t, t / u))
... 
   256 0.000138 0.00
   512 0.000318 2.31
  1024 0.000560 1.76
  2048 0.001363 2.43
  4096 0.006631 4.87
  8192 0.030330 4.57
 16384 0.132857 4.38
 32768 0.534205 4.02
 65536 2.134860 4.00

Вы можете видеть, что для каждого удвоения n время выполнения увеличивается примерно в четыре раза, что мы и ожидаем для алгоритма \ $ O (n ^ 2) \ $.

Строка log-log n против времени выполнения в секундах

4. Сделаем его линейным

Как мы можем ускорить это? Ну, мы могли бы избежать дорогостоящей операции del, сделав список оставшихся в живых, а не удалив умершего. Рассмотрим одну поездку вокруг кругового отряда. Если есть четное число людей, оставшихся, люди с индексами 0, 2, 4 и т. Д. Выживут. Но если число людей остается нечетным, то последний выживший снимает человека с индексом 0, поэтому выжившие люди с индексами 2, 4 и т. Д. Введем это в форму кода:

def survivor2(n):
    """Return the survivor of a circular firing squad of n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        if len(persons) % 2 == 0:
            persons = persons[::2]
        else:
            persons = persons[2::2]
    return persons[0]

(Вы могли бы сократить это, если хотите, используя выражение типа persons[(len(persons) % 2) * 2::2], но я не думаю, что небольшое сокращение в длине кода стоит потеря ясности.)

Давайте проверим, что это правильно, сравнивая результаты с исходной реализацией:

>>> all(survivor(i) == survivor2(i) for i in range(1, 1000))
True

Обратите внимание, насколько полезно для тестирования, что у нас есть код, организованный в функции.

Теперь, какова продолжительность выполнения survivor2? Опять же, глядя на страницу времени сложности на Python Wiki, мы видим, что операция «получить срез» занимает время \ $ O (k) \ $ где \ $ k \ $ - количество элементов в срезе. В этом случае каждый фрагмент составляет половину длины persons, поэтому среда выполнения $$ O \ big ({n \ over 2} \ big) + O \ big ({n \ over 4} \ big) + O \ big ({n \ over 8} \ big) + \ dots $$, который является \ $ O (n) \ $. Опять же, мы можем проверить это экспериментально:

>>> t = 1
>>> for i in range(8, 25):
...     t, u = timeit(lambda:survivor2(2**i), number=1), t
...     print('{:8d} {:8.6f} {:.2f}'.format(2**i, t, t / u))
... 
     256 0.000034 0.00
     512 0.000048 1.40
    1024 0.000087 1.79
    2048 0.000142 1.63
    4096 0.000300 2.12
    8192 0.000573 1.91
   16384 0.001227 2.14
   32768 0.002628 2.14
   65536 0.006003 2.28
  131072 0.017954 2.99
  262144 0.043873 2.44
  524288 0.094669 2.16
 1048576 0.180889 1.91
 2097152 0.364302 2.01
 4194304 0.743028 2.04
 8388608 1.497255 2.02
16777216 3.094121 2.07

Теперь, для каждого удвоения n, время выполнения увеличивается примерно в два раза, что мы и ожидаем для алгоритма \ $ O (n) \ $.

Строка log-log n против времени выполнения в секундах

5. Сделать это (поли) логарифмическим

Можем ли мы сделать еще лучше, чем это? Давайте посмотрим, кто из выживших на самом деле после каждой поездки вокруг отряда стрельбы:

from pprint import pprint

def survivors(n):
    """Print survivors after each round of circular firing squad with n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        if len(persons) % 2 == 0:
            persons = persons[::2]
        else:
            persons = persons[2::2]
        pprint(persons, compact=True)

>>> survivors(100)
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41,
 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81,
 83, 85, 87, 89, 91, 93, 95, 97, 99]
[1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77,
 81, 85, 89, 93, 97]
[9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97]
[9, 25, 41, 57, 73, 89]
[9, 41, 73]
[73]

После каждого раунда разрыв между оставшимися в живых удваивается. Итак, после одного раунда, оставшиеся в живых - каждый второй человек; после двух раундов, каждый четвертый человек, после трех раундов, каждый восьмой человек и так далее. Когда есть четное число людей, первый человек остается первым оставшимся в живых в следующем раунде. Но когда есть нечетное число людей, третий человек становится первым оставшимся в живых в следующем раунде.

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

def survivor3(n):
    """Return the survivor of a circular firing squad of n people."""
    first = 1
    gap = 1
    while n > 1:
        if n % 2: first += 2 * gap
        gap *= 2
        n //= 2
    return first

Еще раз, мы должны проверить, что это правильно:

>>> all(survivor(i) == survivor3(i) for i in range(1, 1000))
True

Как быстро это? Здесь каждый раз по циклу мы просто имеем некоторые арифметические операции над числами размером не более \ $ n \ $, беря \ $ O (\ log n) \ $, и каждый раз вокруг цикла мы делим количество оставшихся в живых на два, поэтому цикл выполняет \ $ O (\ log n) \ $ раз, для общей среды выполнения \ $ O ((\ log n) ^ 2) \ $.

>>> t = 0
>>> for i in range(8, 60, 4):
...     t, u = timeit(lambda:survivor3(2**i), number=1), t
...     print('{:20d} {:8.6f} {:.6f}'.format(2**i, t, t - u))
... 
                 256 0.000014 0.000014
                4096 0.000012 -0.000001
               65536 0.000013 0.000001
             1048576 0.000015 0.000002
            16777216 0.000016 0.000002
           268435456 0.000018 0.000002
          4294967296 0.000022 0.000003
         68719476736 0.000030 0.000008
       1099511627776 0.000026 -0.000003
      17592186044416 0.000027 0.000001
     281474976710656 0.000031 0.000003
    4503599627370496 0.000032 0.000001
   72057594037927936 0.000035 0.000003

Вы можете видеть, что для каждого увеличения n в 16 раз время выполнения увеличивается примерно на примерно сумму, что мы и ожидаем для полилогарифмического алгоритма.

Полу-лог-график n против времени выполнения в секундах

Обратите внимание, что график показывает масштабирование во времени пропорционально \ $ \ log n \ $, а не \ $ (\ log n) ^ 2 \ $. Это потому, что значения \ $ n \ $ малы (меньше \ $ 2 ^ {64} \ $), и поэтому в этом диапазоне арифметические операции эффективны \ $ O (1) \ $. Нам нужно использовать гораздо большие значения \ $ n \ $, чтобы показать асимптотическое поведение.

Является ли survivor3 максимально эффективным? Ну, мы могли бы выжать один из факторов \ $ O (\ log n) \ $, будучи умнее о том, как мы манипулируем значениями в цикле (каждая операция в first влияет только на один бит результат), делая алгоритм \ $ O (\ log n) \ $. Мы не можем сделать это быстрее, чем это, потому что для вывода ответа требуется \ $ Î © (\ log n) \ $.

6. Дальнейшее чтение

Эта проблема (простой случай) представляет собой известную проблему Иосифа Флавия .

ответил Gareth Rees 6 PMpMon, 06 Apr 2015 20:22:45 +030022Monday 2015, 20:22:45

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132