Ускоренные петли Python2 с XOR

Question

The answer вопрос, который отмечен дубликат неправильный и не удовлетворяет моим потребностям.

Мой код предназначен для вычисления хэша из серии чисел.

Проще понять структуру в виде матрицы. Если у меня есть 16 номера начиная с 29 структура будет: (пуск = 29, длина = 4)

29, 30, 31, 32,
33, 34, 35, 36,
37, 38, 39, 40,
41, 42, 43, 44

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

29, 30, 31, 32,//,
33, 34, 35, //, 36,
37, 38, //, 39, 40,
41, //, 42, 43, 44

Хеш = 29^30^31^32^33^34^35^37^38^39 = 54

---

Мой код является:

def answer(start, length): 
    val=0 
    c=0 
    for i in range(length): 
     for j in range(length): 
      if j < length-i: 
       val^=start+c 
      c+=1 
    return val 

Время, необходимое для вычисления больших значений, таких как answer(2000000000,10**4) - это слишком много.

---

Ограничения:

• Py2.7.6
• только стандартные библиотеки для BZ2, за исключением, крипта, Fcntl, ММАП, PWD, pyexpat, выберите сигнал, termios, нить, время, unicodedata, zipimport, zlib.
• Ограниченное время для вычисления.

В настоящее время вычисление параметров теста (неизвестно мне) дает мне ошибку тайм-аута.

---

Как можно улучшить скорость моего кода для больших значений?

Answer 1

Там это ошибка в принятом ответе на Python fast XOR over range algorithm: декрементирование l необходимо сделать, прежде чем Расчетным XOR. Вот исправленная версия, а также тест assert, чтобы убедиться, что он дает тот же результат, что и наивный алгоритм.

def f(a): 
    return (a, 1, a + 1, 0)[a % 4] 

def getXor(a, b): 
    return f(b)^f(a-1) 

def gen_nums(start, length): 
    l = length 
    ans = 0 
    while l > 0: 
     l = l - 1 
     ans ^= getXor(start, start + l) 
     start += length 
    return ans 

def answer(start, length): 
    c = val = 0 
    for i in xrange(length): 
     for j in xrange(length - i): 
      n = start + c + j 
      #print '%d,' % n, 
      val ^= n 
     #print 
     c += length 
    return val 

for start in xrange(50): 
    for length in xrange(100): 
     a = answer(start, length) 
     b = gen_nums(start, length) 
     assert a == b, (start, length, a, b) 

Над этими диапазонами start и length, gen_nums примерно в 5 раз быстрее, чем answer, но мы можем сделать это примерно в два раза быстрее снова (т.е. примерно 10 раз быстрее, чем answer) за счет устранения этих вызовов функций :

def gen_nums(start, length): 
    ans = 0 
    for l in xrange(length - 1, -1, -1): 
     b = start + l 
     ans ^= (b, 1, b + 1, 0)[b % 4]^(0, start - 1, 1, start, 0)[start % 4] 
     start += length 
    return ans 

---

Как Мирек Opoka упоминает в комментариях, % 4 эквивалентно & 3, и это быстрее, потому что побитовое ар ithmetic быстрее, чем выполнение целочисленного деления и отбрасывание частного. Таким образом, мы можем заменить основной шаг

ans ^= (b, 1, b + 1, 0)[b & 3]^(0, start - 1, 1, start, 0)[start & 3] 

Answer 2

Похоже, вы можете заменить внутреннюю петлю, и если с:

for j in range(length - i) val^=start+c c+=1 c+=i Это должно сэкономить некоторое время, когда я становлюсь больше

Я боюсь, что я не могу проверить это прямо сейчас, извините !

Answer 3

Я боюсь, что с вашим вводом answer(2000000000,10**4) вы никогда не закончите «вовремя».

Вы можете получить довольно большую скорость вверх за счет улучшения внутреннего цикла, не обновляя c переменной каждый раз, и используя xrange вместо range, как это:

def answer(start, length): 
    val=0 
    c=0 
    for i in range(length): 
     for j in range(length): 
      if j < length-i: 
       val^=start+c 
      c+=1 
    return val 


def answer_fast(start, length): 
    val = 0 
    c = 0 
    for i in xrange(length): 
     for j in xrange(length - i): 
      if j < length - i: 
       val ^= start + c + j 
     c += length 
    return val 


# print answer(10, 20000) 
print answer_fast(10, 20000) 

профайлере показывает, что answer_fast примерно в два раза так быстро:

> python -m cProfile script.py 
366359392 
     20004 function calls in 46.696 seconds 

Ordered by: standard name 

ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 46.696 46.696 script.py:1(<module>) 
     1 44.357 44.357 46.696 46.696 script.py:1(answer) 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
    20001 2.339 0.000 2.339 0.000 {range} 

> python -m cProfile script.py 
366359392 
     3 function calls in 26.274 seconds 

Ordered by: standard name 

ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 26.274 26.274 script.py:1(<module>) 
     1 26.274 26.274 26.274 26.274 script.py:12(answer_fast) 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 

Но если вы хотите, основной скорость окна (заказы magnitute) вы должны рассмотреть переписывать функцию в Cython.

Вот «cythonized» версия этого:

def answer(int start, int length): 
    cdef int val = 0, c = 0, i, j 
    for i in xrange(length): 
     for j in xrange(length - i): 
      if j < length - i: 
       val ^= start + c + j 
     c += length 
    return val 

При тех же исходных параметрах, что и выше, она занимает менее 200 мс InstEd 20 + секунд, что является 100x ускорение.

> ipython 

In [1]: import pyximport; pyximport.install() 
Out[1]: (None, <pyximport.pyximport.PyxImporter at 0x7f3fed983150>) 

In [2]: import script2 

In [3]: timeit script2.answer(10, 20000) 
10 loops, best of 3: 188 ms per loop 

С вашими входными параметрами, он принимает 58ms:

In [5]: timeit script2.answer(2000000000,10**4) 
10 loops, best of 3: 58.2 ms per loop