Ускорение этого кода на Python для большого ввода

Question

Я написал этот код Python для выполнения определенного вычисления в более крупном проекте и отлично работает для меньших значений N, но он не очень хорошо масштабируется для больших значений, и хотя я побежал в течение нескольких часов, чтобы собрать данные, мне было интересно, если есть способ, чтобы ускорить этот

import numpy as np 

def FillArray(arr): 
while(0 in arr): 
    ind1 = np.random.randint(0,N) 
    if(arr[ind1]==0): 
     if(ind1==0): 
      arr[ind1] = 1 
      arr[ind1+1] = 2 
     elif(ind1==len(arr)-1): 
      arr[ind1] = 1 
      arr[ind1-1] = 2 
     else: 
      arr[ind1] = 1 
      arr[ind1+1] = 2 
      arr[ind1-1] = 2 
    else: 
     continue 
return arr 

N=50000 

dist = [] 
for i in range(1000): 
    arr = [0 for x in range(N)] 
    dist.append(Fillarr(arr).count(2)) 

для N = 50,000, в настоящее время он занимает чуть больше минуты на моем компьютере, на одной итерации для заполнения массив. Поэтому, если я хочу имитировать это, скажем, 1000 раз, это занимает много часов. Есть ли что-то, что я могу сделать, чтобы ускорить это?

Редактировать 1: Я забыл упомянуть, что он на самом деле делает. У меня есть список длины N, и я инициализирую его, имея нули в каждой записи. Затем я выбираю случайное число между 0 и N, и если этот индекс списка имеет нуль, я заменяю его на 1 и его соседние индексы на 2, чтобы указать, что они не заполнены 1, но они не могут быть заполнены снова. Я продолжаю делать это, пока я не заполнил весь список 1 и 2, а затем подсчитаю, сколько записей содержит 2, что является результатом этого вычисления. Таким образом, я хочу узнать, если я случайно заполняю массив этим ограничением, сколько записей не будет заполнено.

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

Answer 1

Как заметил @SylvainLeroux в комментариях, подход к поиску нулевого значения, который вы собираетесь изменить, рисуя случайное местоположение и надеясь, что он будет равен нулю, замедлит работу, когда вы начнете заканчивать нули. Простое выбор из тех, которые вы знаете, будет равным нулю, значительно ускорит его. Что-то вроде

def faster(N): 
    # pad on each side 
    arr = np.zeros(N+2) 
    arr[0] = arr[-1] = -1 # ignore edges 
    while True: 
     # zeros left 
     zero_locations = np.where(arr == 0)[0] 
     if not len(zero_locations): 
      break # we're done 
     np.random.shuffle(zero_locations) 
     for zloc in zero_locations: 
      if arr[zloc] == 0: 
       arr[zloc-1:zloc+2] = [2, 1, 2] 
    return arr[1:-1] # remove edges 

будет намного быстрее (раз на мой старый ноутбук):

>>> %timeit faster(50000) 
10 loops, best of 3: 105 ms per loop 
>>> %time [(faster(50000) == 2).sum() for i in range(1000)] 
CPU times: user 1min 46s, sys: 4 ms, total: 1min 46s 
Wall time: 1min 46s 

Мы могли бы улучшить это путем векторизации больше вычислений, но в зависимости от ограничений, это может быть уже достаточно.

Answer 2

Во-первых, я переформулирую проблему с трехзначной до двукратной. То, что вы делаете, это расщепление вектора длины N на два меньших вектора в случайной точке k.

Предположим, что вы начинаете с вектора нулей, тогда вы ставите «1» в случайном порядке k и оттуда берете два меньших вектора нулей - [0..k-2] & [k + 2 .. N-1]. Нет необходимости в третьем состоянии. Вы повторяете процесс до исчерпания - когда вы остаетесь с векторами, содержащими только один элемент.

Использование recusion это достаточно быстро даже на моем iPad мини с Pythonista.

import numpy as np 
from random import randint 

def SplitArray(l, r): 
    while(l < r): 
     k = randint(l, r) 
     arr[k] = 1 
     return SplitArray(l, k-2) + [k] + SplitArray(k+2, r) 
    return [] 

N = 50000 
L = 1000 
dist=np.zeros(L) 
for i in xrange(L): 
    arr = [0 for x in xrange(N)] 
    SplitArray(0, N-1) 
    dist[i] = arr.count(0) 

print dist, np.mean(dist), np.std(dist) 

Однако, если вы хотите, чтобы сделать это очень быстро, то Двумерный проблема может быть закодирован очень эффективно и, естественно, в виде битовых массивов вместо хранения 1 и 0 в массивах целых или хуже поплавков в Numpy массивов. Бит-манипуляция должна быть быстрой, и в некоторых случаях вы легко можете приблизиться к скорости машинного уровня.

Что-то вдоль линии: (это идея не оптимальный код)

from bitarray import BitArray 
from random import randint 
import numpy as np 

def SplitArray(l, r): 
    while(l < r): 
     k = randint(l, r)   
     arr.set_bit(k) 
     return SplitArray(l, k-2) + [k] + SplitArray(k+2, r) 
    return [] 

def count0(ba): 
    i = 0 
    for n in xrange(1, N): 
     if ba.get_bit(n) == 0: 
      i += 1 
    return i 

N = 50000 
L = 1000 
dist = np.zeros(L) 
for i in xrange(L): 
    arr = BitArray(N, initialize = 0) 
    SplitArray(1, N)  
    dist[i] = count0(arr) 

print np.mean(dist), np.std(dist) 

использованием bitarray

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