Простой скрипт на Python, кажется, чтобы остановить, когда N >> 1


Редактировать :

Так что я пусть код будет работать на 70 часов и не вернулся. Таким образом, я придерживаюсь моей точки зрения, это не застрять на что-то, молча не удается, и пусть Баш висит. С увеличением времени по сравнению с относительно небольшой прыжок между N1 и N2, это не то, что О(П) -> О(Н2) могу объяснить.

(входной сигнал идет от N до 2n подразумевает выполнение перейдя от N2 к 4N2, поэтому он должен принимать только 4 больше времени. Не возвращаясь после часа на 2 ночи во время окончания в 15 минут максимум для N означает что-то не удается)

Принял решение работает очень хорошо, пока не достигнет (мгновенно) очень чистый переполнения памяти.

$ пы so_mysan.py 400000000 обратная трассировка (самый недавний призыв последнего): файл "so_mysan.py", строка 36, в Сыс.выход(основной(представление sys.аргумент argv[1:])) файл "so_mysan.py", линия 8, в основной заказ = список(диапазон(Н)) MemoryError

Спасибо за ваше время.

/редактировать

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

Скрипт принимает пустой массив N и заполняет его случайным уважения только одно правило : слот может быть заполнен только если предыдущие, текущие и следующие слоты пусты.

Мы хотим знать скорость наполнения при n -> бесконечности (очевидно, между 0.333 и 0.5).

Мой скрипт может не быть лучший способ сделать это, но это не важно на мой вопрос: почему он возвращается в ~2 минуты для n = 3.10^6 и до сих пор не возвращают при n = 3.5.10^6 и далее?

Для сравнения, это примерно тот же порядок величины, что время идет от 10^6 до 2.10^6 до 3,10^6 (несколько минут).

Я понимаю это del но что происходит, что делает его вдруг так медленно?

Весь скрипт ниже, каждый может запустить его с py script.py N

import sys
import numpy as np 
from random import randint

def main(arguments):
    N = int(sys.argv[1])
    # definissons notre ligne de maison : 
    houses = [0]*N
    emptySlot = list(range(0,N)) 
    # counter = 1 
    while (len(emptySlot)>0):
        # on prend une maison vide possiblement habitable par un mysanthrope, au hasard. 
        empt = randint(0, len(emptySlot)-1)
        houses[emptySlot[empt]] = 1
        # on enlève cette maison de notre liste de possibilité 
        # et éventuellement les maisons adjacentes si elles y étaient
        temp = emptySlot[empt]
        del emptySlot[empt]
        # on essaye d'enlever les autres si existes plus efficacement : 
        if (0<=empt and empt<len(emptySlot) and emptySlot[empt] == temp+1):
            del emptySlot[empt] # comme on a viré l'index empt, ça décale.
        if (empt-1 >= 0 and emptySlot[empt-1] == temp-1):
            del emptySlot[empt-1] # pour l'inférieur, cela ne change rien

    occupancyRate = sum(houses) / N
    print(occupancyRate)

if __name__ == '__main__':
    sys.exit(main(sys.argv[1:]))


238
-3
задан 6 февраля 2018 в 12:02 Источник Поделиться
Комментарии
3 ответа

Как описано в этот ответ, ваш представленный алгоритм имеет сложность времени \$o(П^2)\$, т. е. во время выполнения возрастет квадратично по числу элементов. Это позволит сделать увеличение \Н $\$ иметь большое влияние на время выполнения. Это можно реализовать algortihm в \$О(П)\$, т. е. линейное время выполнения увеличение элементов, например, решение, которое я представил в качестве ответа на ваш переполнение стека вопрос.

Я запустил два алгоритма для разных размеров \Н $\$ ниже. В дополнение к времени выполнения для различных решений я поставил опорные линии для \$О(П)\$ и $\o(П^2)\$. Самая интересная часть-это склон, а не точные значения.

time complexity

Как видно, для низких \ФП\$ значения ваш алгоритм имеет линейный рост времени выполнения. Я не знаю, почему это так, но это может быть из-за некоторых под капотом оптимизации в Python. Когда \ФП\$ растет, хотя, сложность, кажется, подход \$П^2\$, как ожидалось. Кроме того, из этого, вполне понятно, что когда собирается больше \ФП\$ значения сложность времени будет резко увеличиваться. Для сравнения, решение, которое я представил, продолжают расти линейно, и для больших значений N, что гораздо приятнее поведения.

Но, как я уже говорил выше, почему ваш algortihm вроде бы линейный для малых \ФП\$ значения я не знаю. Было бы интересно узнать, хотя.

4
ответ дан 7 февраля 2018 в 08:02 Источник Поделиться

emptySlot используется для хранения свободных слотов. При приеме слот соседних слотах также принимаются (так что не 2 дома могут быть рядом друг с другом). Однако удаление элемента из середины списка принимает \$О(П)\$ времени. Таким образом, общее время ваш алгоритм \$o(п^2)\$.

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

3
ответ дан 6 февраля 2018 в 02:02 Источник Поделиться

Как говорится в PEP8


Питон кодеров из неанглоязычных стран: пожалуйста, пишите свои комментарии на английском, если вы на 120% уверены, что код никогда не будут читать люди, которые не говорят на вашем языке.

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

В любом случае, PEP8 в целом должны быть применены, как у вас есть несколько нарушений:


  • добавлять интервалы, особенно вокруг операторов;

  • удалить лишние скобки (в if и while условия, например);

  • улучшить ваши имена переменных и придерживаться соглашения об именовании (lowercase_with_underscore для имен переменных, например).

Это поможет сделать ваш код Python выглядеть Python для других читателей.

3
ответ дан 7 февраля 2018 в 09:02 Источник Поделиться