Способ эффективного вычисления контрольной суммы XOR (^) на основе списка идентификаторов

Question

Когда информация о Google для получения информации о представлении списка Python мне предложили вызов google foobar, который я медленно работал в последние несколько дней для удовольствия. Последний вызов:

эффективно требует создания списка идентификаторов, игнорируя все большее число из каждой новой линии до тех пор, пока один ID слева. Затем вы должны XOR (^) идентификаторы для создания контрольной суммы. Я создал рабочую программу, которая выводит правильный ответ, однако недостаточно времени для прохождения всех тестовых случаев (пропусков 6/10) за выделенное время. Длина 50 000 должна давать результат менее чем за 20 секунд, но требуется 320.

Может ли кто-то направить меня в правильном направлении, но , пожалуйста, не делайте этого для меня, я с удовольствием подталкиваю себя с этой проблемой. Возможно, есть структура данных или алгоритм, который я могу реализовать, чтобы ускорить время вычисления?

Логика кода:

1. Во-первых, начиная идентификатор и длина берутся в

2. список идентификаторов генерируется, игнорируя все большее число идентификаторов из каждой новой линии, начиная с игнорируя 0 из первой строки.

3. операцию XOR всех чисел в списке IDS, используя для цикла

4. Ответ возвращается как INT

---

import timeit 
def answer(start,length): 
    x = start 
    lengthmodified = length 
    answerlist = [] 
    for i in range (0,lengthmodified): #Outter for loop runs an amount of times equal to the variable "length". 
     prestringresult = 0 
     templist = [] 
     for y in range (x,x + length): #Fills list with ids for new line 
      templist.append(y) 
     for d in range (0,lengthmodified): #Ignores an id from each line, increasing by one with each line, and starting with 0 for the first 
      answerlist.append(templist[d]) 
     lengthmodified -= 1 
     x += length  
     for n in answerlist: #XORs all of the numbers in the list via a loop and saves to prestringresult 
      prestringresult ^= n 
     stringresult = str(prestringresult) 
     answerlist = [] #Emptys list 
     answerlist.append(int(stringresult)) #Adds the result of XORing all of the numbers in the list to the answer list 
    #print(answerlist[0]) #Print statement allows value that's being returned to be checked, just uncomment it 
    return (answerlist[0]) #Returns Answer 



#start = timeit.default_timer() 
answer(17,4) 
#stop = timeit.default_timer() 
#print (stop - start) 

Answer 1

Возможно, вам понадобится другой подход, а не только незначительные улучшения, такие как Джон. Я просто написал решение, которое может сделать answer(0, 50000) примерно через 2 секунды на моем ПК. Я все еще делаю это по строкам, но вместо того, чтобы хсорировать все числа в диапазоне строк, я делаю это по частям. Сколько чисел в строке имеет 1-битный набор? ^[*] Нечетное количество номеров? Затем я переворачиваю 1-битный ответ. И тогда то же самое для 2-битного, 4-битного, 8-битного и т. Д., До 2 -bit. Таким образом, для каждой строки это всего лишь 31 небольшой расчет (вместо того, чтобы фактически клонировать десятки тысяч чисел).

[*] Может быть рассчитан быстро в постоянное время только от начала/остановки диапазона.

Редактировать: Поскольку вы попросили еще один намек, вот как вычислить, как часто 1 бит устанавливается в некотором диапазоне (a, b). Вычислите, как часто он устанавливается в диапазоне (0, a) и вычитает из того, как часто он устанавливается в диапазоне (0, b). Это легче, если диапазон начинается с нуля. Как часто устанавливается 1-бит в некотором диапазоне (0, c)? Легко: c//2 раз. Итак, как часто 1-битный набор в некотором диапазоне (a, b)? Просто b//2 - a//2 раз. Более высокие биты схожи, немного сложнее.

Редактировать 2: О, подождите, я просто вспомнил ... есть простой способ вычислить xor всех чисел в некотором диапазоне (a, b). Снова разделите работу на диапазон (0, a) и диапазон (0, b). Xor всех чисел в некотором диапазоне (0, c) легко, потому что есть хороший шаблон (вы увидите его, если вы сделаете это для всех c из 0, скажем, 30). Используя это, я теперь решаю answer(0, 50000) примерно в 0,04 секунды.

Answer 2

Ни templist, ни answerlist действительно необходимы , Давайте возьмем пару проходов в вашем коде, чтобы узнать, как их устранить.

1. Во-первых, давайте инициализации templist «s один вкладыш. Это:

   templist = [] 
   for y in range (x,x + length): 
       templist.append(y) 
   

   Становится это:

   templist = list(range(x, x + length)) 
   

2. Тогда давайте сделаем то же самое для answerlist. Это:

   for d in range (0,lengthmodified): 
       answerlist.append(templist[d]) 
   

   Становится это:

   answerlist.extend(templist[:lengthmodified]) 
   

3. Теперь давайте посмотрим, как они используются позже. Если мы будем игнорировать lengthmodified -= 1 и x += length на данный момент, мы имеем:

   templist = list(range(x, x + length)) 
   answerlist.extend(templist[:lengthmodified]) 
   
   for n in answerlist: 
       prestringresult ^= n 
   
   answerlist = [] 
   

   Вместо расширения answerlist, итерацию над ним, а затем очищая его, было бы быстрее, чтобы просто перебрать templist.

   templist = list(range(x, x + length)) 
   
   for n in templist[:lengthmodified]: 
       prestringresult ^= n 
   

   И теперь нет необходимости templist либо, так что давайте не компилировать его.

   for n in range(x, x + lengthmodified): 
       prestringresult ^= n 
   

   templist и answerlist ушли.

Единственный недостающий элемент здесь работает answerlist.append(int(stringresult)) обратно. Я оставлю это для вас, чтобы выяснить.

В целом, урок здесь состоит в том, чтобы избежать явных for циклов, когда вы можете. Написание много циклов for, которые перебирают контейнеры, - это способ мышления. В Python часто есть способы пережевывать коллекции сразу. Это позволяет вам использовать быстрые встроенные операции языка.

В качестве бонуса, идиоматический Python также легче читать.

Answer 3

Мне удалось немного улучшить, не используя список, но он по-прежнему будет терпеть неудачу на больших количествах. Вложенные циклы убивают скорость. Я думаю, вам нужно следовать логике Похмана, поскольку грубая сила редко является способом решения этих проблем.

Answer 4

Большинство людей получат лимит времени превышается в этом вопросе. Я сделал! Этот вопрос можно сделать следующим образом: «Найти XOR всех чисел, которые находятся между определенным диапазоном в постоянное время». Да, постоянное время!

Итак, из 3-6 ответ должен быть 3^4^5^6 = 4 в O (1) раз.

Решение: XOR являются ассоциативными по своей природе. Таким образом, A^B^C может быть записано как B^A^C. Кроме того, мы знаем, что XOR означает: «И, когда одни и те же биты приводятся к True, т.е. 1, а разные биты приводят к 2.

Из этих 2 природы мы можем написать: XOR между всеми числами от 3-6 можно записать в виде:

3^4^5^6 = (0^1^2)^(0^1^2)^(3^4^5^6) 
     = (0^1^2^3^4^5^6)^(0^1^2) (this comes from the associative nature of xor) 
     = XOR betn all the numbers from (0-6)^XOR betn all the numbers from (0-2)...eq(1) 

так вот, если мы сможем найти XOR всех чисел от 0 до некоторого целого числа в постоянное время, мы получит наш ответ.

К счастью, существует образец для нас:

Посмотреть это для примера:

(0-1): 0^1 = 1 (1) 
(0-2): 0^1^2 = 3 (2+1) 
(0-3): 0^1^2^3 = 0 (0) 
(0-4): 0^1^2^3^4 = 4 (4) 

(0-5): 0^1^2^3^4^5 = 1 (1) 
(0-6): 0^1^2^3^4^5^6 = 7 (6+1) 
(0-7): 0^1^2^3^4^5^6^7 = 0 (0) 
(0-8): 0^1^2^3^4^5^6^7^8 = 8 (8) 


So the pattern for finding the xor between all the integers between 0 to n is: 
if n%4 == 1 then, answer = 1 
if n%4 == 2 then, answer = n+1 
if n%4 == 3 then, answer = 0 
if n%4 == 0 then answer = n 

Therefore, XOR(0-6) becomes 7 (since 6%4 ==2) and XOR(0-2) becomes 3 (since 2%4 ==2) 

Therefore, the eq(1) now becomes: 
3^4^5^6 = 7^3 = 4 

Теперь вопрос довольно легко, большинство из нас застревают из-за времени ограничения превышены ошибку, потому что мы пытаемся использовать xor в каждом цикле, который был бы огромным, если число ввода/итерации увеличивается. Вот мой рабочий раствор в питоне, для которого всех тестовых случаи были приняты гуглом:

#Main Program 
def answer(start, length): 
    checkSum = 0 
    for l in range(length, 0, -1): 
     checkSum = checkSum^(getXor(start + l-1)^getXor(start-1)) 
     start = start + length 
    return checkSum 

def getXor(x): 
    result = [x, 1, x+1, 0] 
    return result[x % 4]