Edit :

So I let the code run for 70 hours and it did not return. Thus I stick to my point, it does get stuck on something, fails silently and let the bash hanging. From the time increase compared to the relatively small jump between N1 and N2, it's not something a O(N) -> O(N²) can explain.

(input going from N to 2N implies an execution time going from N² to 4N², so it should only take 4 time more. Not returning after hours for 2N while finishing in 15 minutes max for N means something fails)

Accepted solution works very well until it reaches (instantly) a very clean memory overflow.

$ py so_mysan.py 400000000 Traceback (most recent call last): File
"so_mysan.py", line 36, in
sys.exit(main(sys.argv[1:])) File "so_mysan.py", line 8, in main
ordering = list(range(N)) MemoryError

Thank you for your time.

/edit

Stack Overflow advised me to post here my issue. Although an alternative has been proposed, I would like to know why my few lines of code kind of stop working.

The script takes an empty array N and fills it randomly respecting
only one rule : a slot can be filled only if previous, current and
following slots are empty.

We want to know the filling rate for N -> infinity (obviously between
0.333 and 0.5).

My script might not be the best way to do that but it does not matter for my question is: why does it returns in ~2 minutes for N = 3.10^6 and still has not return for N = 3.5.10^6 and beyond?

To compare, it takes roughly the same order of magnitude of time going from 10^6 to 2.10^6 to 3.10^6 (a few minutes).

I understand it's the del operation but what is happening that makes it suddenly so slow?

The whole script is below, anyone can run it with 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:]))

As described in this answer, your presented algorithm has time complexity $O(N^2)$, i.e., the runtime will increase quadratically in number of elements. This will make an increase in $N$ have a big impact on the run time. It is possible to implement the algortihm in $O(N)$, i.e., a linear runtime increase in elements, e.g. as the solution I presented as a response to your Stack Overflow quesiton.

I have run the two algorithms for different sizes of $N$ below. In addition to the run times for the different solutions I have put reference lines for $O(N)$ and $O(N^2)$. The interesting part is the slope, rather than exact values.

As can be seen, for low $N$ values your algorithm is having a linear runtime increase. I don't know why that is, but it could be due to some under-the-hood Python optimizations. When $N$ increases, though, the complexity seems to approach $N^2$ as expected. Also, from this, it is quite clear that when going to larger $N$ values the time complexity will be increase dramatically. In comparison, the solution I presented, continue to increase linearly, also for larger N values, which is a much nicer behavior.

But, as I stated above, why your algortihm seems to be linear for small $N$ values I don't know. It would be interesting to find out, though.

emptySlot is used to contain free slots. When a slot is taken their neighboring slots are also taken (so no 2 houses can be next to each other). However removing an element from the middle of a list takes $O(n)$ time. So the total time of your algorithm is $O(n^2)$.

It's better to check the neighbouring slots if it is taken and if so skip inserting a house at that point. That way you don't need to mess with the extra array.

As stated in PEP8

Python coders from non-English speaking countries: please write your comments in English, unless you are 120% sure that the code will never be read by people who don't speak your language.

Clearly, sharing the code here without thinking about readability by non-french reviewer is just throwing some garbage into your code and hopping people will easily ignore it.

Anyway, PEP8 as a whole should be applied here as you have a few violations:

• add spacing, especially around operators;


• remove superfluous parenthesis (in if and while conditions, for instance);


• improve your variable names and stick to naming conventions (lowercase_with_underscore for variable names, for instance).

This will help make your Python code look like Python to other readers.