Листать производительности монет


Это подбрасыванием монеты проблему на CodeChef:

Есть \$N монет\$ оставить на столе, пронумерованных от \$0\ долларов \$П - 1\$. Изначально, каждая монета хранится решкой вверх. Вам придется выполнять два типа операций:

  1. Перевернуть все монеты пронумерованы между \долларов\$ и $\\ Б$ включительно. Это представляла команда "0 б"

  2. Ответ, как много монет, пронумерованных от \долларов\$ и $\Ъ\$ включительно головы. Это представляет команда "1 Б".

Вход:

Первая строка содержит два целых числа, \Н $\$ и $\Щ\$. Каждая следующая \$Щ\$ линии либо в форме "0 Б" или "1 Б", как указано выше.

Выход:

Выход 1 строку для каждого из запросов вида "1 Б", содержащий необходимый ответ на соответствующий запрос.

Из всех представленных материалов в Python 3.5, никто из них не смог решить ее в указанный срок (возможно 0.3 С, он не указан точно). Как я могу оптимизировать мой код?

n,q = map(int,input().split())
c = [0]*n
for i in range(q):
    j,k,l = list(map(int,input().split()))
    co = 0 
    if j == 1:
        #do Something
        for m in range(k,l+1):
            if c[m] == 1:
                co += 1
        print(co)
    if j == 0:
        #do something
        for m in range(k,l+1):
            if c[m] == 1:
                c[m] = 0
            else:
                c[m] = 1


Комментарии
5 ответов

Код, который вы выложили является прямолинейным и достаточно простым. Из-за этого, я собираюсь предположить, что вы не супер-опытный в Python. Я буду делать некоторые прямые предложения, чтобы перейти от вашего текущего кода для более быстрой версии вашего кода, но я не ожидаю, что вы будете в состоянии сделать ограничение по времени с этой структурой. См. @ВНП ответ, как это сделать.

Вы написали:

n,q = map(int,input().split())
c = [0]*n
for i in range(q):
j,k,l = list(map(int,input().split()))
co = 0
if j == 1:
#do Something
for m in range(k,l+1):
if c[m] == 1:
co += 1
print(co)
if j == 0:
#do something
for m in range(k,l+1):
if c[m] == 1:
c[m] = 0
else:
c[m] = 1

Когда я прочитал задание, вот что я увидел:


Есть N монет оставить на столе, пронумерованных от 0 до N - 1.
Изначально, каждая монета хранится решкой вверх. Вам придется выполнять два типа
операций:

1) переворачивать все монеты пронумерованы между A и B включительно. Это
представлял команду "0 б" ...

Тем не менее, когда я смотрю на ваш код, я вижу это:

for i in range(q):
j,k,l = list(map(int,input().split()))

Вы не отображение проблема пространства в коде. Это делает его более трудным для вас - и мне, и всем остальным, что видит он - рассуждать о коде.

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

N, num_opns = list(map(int, input().split()))

for i in range(num_opns):
operation, A, B = list(map(int, input().split()))

Видите разницу? Н. н. есть операции , которые могут быть 0 или 1. Думаю, что это операция? И есть параметры a и B, четко обозначены. Я не изменилась, как она функционирует, но тому, кто читает код может теперь обратиться к инструкции и посмотреть, что к чему.

При Добавлении Быстрее

Далее, Давайте посмотрим на ваши две операции. Вот ваш первый, считая 1 значений:

for m in range(k,l+1):
if c[m] == 1:
co += 1

Ваш код выглядит на все значения, а если 1, добавляет 1 к графу, и если это не 1, ничего не добавляет к графу.

Теперь, думаю, как программист! Спросите: "как я могу избавиться от этого кода?" В этом случае, что происходит, когда c[m] это не равна 1? Почему, тогда, она равна 0. И что происходит, когда вы добавляете 0 на любое число? Ничего - количество не меняется. Так что вы могли бы изменить код, чтобы:

for m in range(k,l+1):
co += c[m]

И получите тот же результат!

Идем дальше, оказывается, что в Python есть встроенный sum что добавляет последовательности значений! Вы можете перейти от добавления этих чисел в Python, чтобы иметь интерпретатор Python добавить цифры в с., Что должно ускорить процесс красиво:

co = sum(c[k:l+1])

Есть две вещи, происходит. Первое, c[k:l+1] называется нарезка выражение. Он создает "суб-список" c список, с просто значения вопрос. Второе-это использование sum() встроенный.

Переключения Быстрее

Ваша вторая операция просто меняет значения:

for m in range(k,l+1):
if c[m] == 1:
c[m] = 0
else:
c[m] = 1

Есть несколько способов, чтобы ускорить этот процесс, и все они связаны делаешь какую-то одну операцию вместо if заявление. Например, можно выполнить побитовое исключающее ИЛИ значения с 1. Побитовое исключающее ИЛИ побитовое тоже (не брать) вычитание по модулю 2, так что, когда вы гаммирования вещи 0 становится 1, а 1 становится 0.

for m in range(k,l+1):
c[m] ^= 1

Кроме того, вы можете хранить значения в кортеже и карта старое значение на новое значение:

new_values = (1, 0)
for m in range(k,l+1):
c[m] = new_values[c[m]]

Наконец, я укажу вам на timeit модуль, который является стандартный Python способ измерения скорости. Если вы пытаетесь побить лимит времени в любой вызов, убедитесь, что вы используете timeit так что вы можете отслеживать, какое влияние каждого изменения вы делаете на производительность.

14
ответ дан 25 января 2018 в 09:01 Источник Поделиться

Не грубой силой.


  • Нет никаких причин, чтобы сохранить весь список государств монета, гораздо меньше, чтобы проанализировать фактическое сальто. Государство легко извлекаемые из последовательности 0 операций.

  • Основное наблюдение состоит в том, что 0 a b операция на самом деле пара операций: флип монеты a в конце концов, и флип монеты b + 1 до конца. Это приводит к решение:


    • Отвязать 0 a b работа в a и b+1

    • Сохранить список флип очки, и держать его заказал

    • Для выполнения 1 операции, найти самый большой флип точку перед A. Если его индекс в Flip список даже, A монета лежит решкой вверх, в противном случае он возглавляет. Затем, пройти перевернуть список, пока B добавление длины каждого интервала.


Сложность пространства \$О(Г)\$; время сложность \$О(Г\журнал Щ)\$.

11
ответ дан 25 января 2018 в 09:01 Источник Поделиться

Я думаю, что авторы задачи может быть предназначена для людей, чтобы использовать структуру данных, которая позволяет для быстрых запросов и обновлений. Вы можете запустить его в \и$Q\журнал(N)\$ время с помощью древовидной структуры.

Во-первых, обратите внимание, что играть в орлянку в интервале \$[л,р)\$ такая же, как листать \$[0,р)\$ и $\[0,л)\$, поэтому мы вынуждены листать \$[0,р)\$. Идея не в том, чтобы вообще перевернуть все что угодно, но использовать двоичное дерево, в котором записывается число, \$П{Я,J}\$ глав интервалов форме \$призраки{я,J}=2^я[дж,дж+1)\$. Дети \$призраки{я,J}\ долларов \$призраки{я-1,2 Дж}\$ и $\призраки{я-1,2 в J+1}\$.

Каждым обновлением вызвана листать \$[0,р)\$ могут быть разбиты на последовательность переворачивается интервалов \$призраки{я,p_i}\$, где$p_i=\sum_{J В>Я}2^{J не-я}r_j\$ являются производными от двоичной расширения \$\sum_{J в\ge0}2^jr_j\ долларов \$Р\$. Чтобы перевернуть \$[0,р)\$ вы (я) флип \$призраки{я,p_i}\ долл \$r_i=1\$, Что означает, что изменение \$п{я,p_i}\ долларов \$2^я-п{я,p_i}\$, (II) и исправить предок узлов форма \$призраки{я+1,p_i/2}\$, (III) в запишите на флип в узле \$(я,p_i)\$ в отдельном массиве, так что все узлы-потомки могут быть отменены, когда они запрашиваются.

(III) не спасает от неприятностей сделать заказ \ФП\$ объем работы ремонт узлов ребенка, за счет причинения запросов дополнительную \\$log_2(Н)\$ работа проверка всех предков для сальто. На самом деле это не очень много дополнительной работы, поскольку запрос уже взял \$\log_2(Н)\$ времени.

Есть пример реализации ниже. (К сожалению, это не красиво.)

Правка, чтобы добавить: я старался представить это в Codechef и его сдали в категории содержатся и Python 2 (быстрый бег времени и действует только запись соответственно), но тайм-аут в Python 3. Вероятно, это только лишь достаточно быстро, как Python 2, и только совсем уж медленно, как в Python 3.

Редактировать, чтобы добавить более подробное объяснение:

Инвариант, который сохраняется в том, что количество глав в диапазоне \$потому{я,J}=[Дж\$<<\$я,(к+1)\$<<\$я)\$ равна Сум\$[я][Дж]\$ и \$2^я-\$суммы\$[я][Дж]\$ в зависимости от того, \$\sum_{г>0} \$сальто\$[я+д][Дж\$>>\$д]\$ четным или нечетным соответственно.

Это звучит нелепо, но это просто бинарное дерево, а точнее, два одинаково проиндексированных бинарных деревьев, соответствующих сумм[][] (целых чисел) и одно сальто[][] (булевых переменных).

Узлы индексируются \$(я,J)\ долларов \$0\ЛЭ Джей<2^{N-я}\$, где \N $\$ равна \$\log_2(Н)\$ округляется до ближайшего целого числа. Узел на \$(Я,J)\$ представляет собой интервал \$[2^я.Дж,2^я(к+1))\$. Для \$Я>0\$, дети \$(Я,J)\ долларов \$(я-1,2 Дж)\$ и $\(я-1,2 в J+1)\ долларов, что на два интервала, которые вместе образуют головной интервал, а \$(0,к)\$ узлах находятся листья.

Например, предположим, что \$П=32\$, \$П=5\ долларов, и мы желаем, чтобы перевернуть интервал \$[0,23)\$. ("Листать этот интервал" является сокращением для уточнения суммы деревья[][] и перевороты[][] сохранение инварианта, а если монеты в позиции \$0,\лдоц 22\$ были перевернуты.)

Сначала пишите \$23\$ в двоичном виде \$23=16+4+2+1\$, затем отдельно флип интервалы \$[0,16)\$, \$[16,20)\$, \$[20,22)\$, \$[22,23)\$.

Например, что мы должны сделать, чтобы перевернуть интервал \$[16,20) = призраки{2,4}\$?

В первую очередь надо изменить суммы\$[2][4]\$ для \$4-\$суммы\$[2][4]\$. Что исправляет запросы \$потому{2,4}\ само$. (Это соответствует цикл в коде начинаться с комментария "флип монеты [(Р-М)&-М, Р&-М)".)

Затем нам нужно исправить графу для родительского интервал \$[16,24) = призраки{3,2}\$. Это можно сделать, установив количество голов в \$[16,24)\$ равен наш новый номер для \$[16,20)\$ плюс, что в \$[20,24)\$. Тогда интервал прародителя, \$[16,32)\$ должна быть скорректирована путем переписывания ее голову считать, что \$[16,24)\$ плюс, что \$[24,32)\$. (Это соответствует цикл в коде начинаться с комментария "исправить предков измененных узлов". Хотя на самом деле эти операции объединяются для всех \$[0,16)\$, \$[16,20)\$, \$[20,22)\$, \$[22,23)\$.)

Тогда нам нужно исправить количество запросов всех потомком интервалов: \$[16,18)\$, \$[18,20)\$, \$[16,17)\$, \$[17,18)\$, \$[18,19)\$, \$[19,20)\$. В целом там может быть довольно много, и если мы что-то сделали вручную для всех из них, это разрушило бы наш заказ сложности. Поэтому мы отложить эту операцию для запроса времени (т. е. ОП=1, где мы ищем число) и сразу отмечу, что нам нужно вести себя так, будто все эти интервалы должны были быть отражено в их совокупности. Это осуществляется путем перестановки логического сальто\$[2][4]\$, соответствующий интервал \$[16,20)\$. Это отсроченная оценка налагает на время выполнения запроса для проверки флип статус всех родительских узлов, инвертирующий численности, если количество предка флип переключатели странно. (Переменная ФЛ в csum().)

Примечание: приведенный ниже код \$О(Н+м\журнал(N))\ расхода \$О(Г\журнал(N))\$. Дополнительные \ФП\$ исходит из выделения массивов sums и flips. Этот термин мог быть удален с помощью словарей, заменив инициализации sums и flips по

from collections import defaultdict
sums=[defaultdict(int) for i in range(n+1)]
flips=[defaultdict(bool) for i in range(n+1)]

но я оставил его как массивы здесь, потому что он работает быстрее, для типичных значений мы используем здесь, примерно \$П=М=100000\$.

from sys import stdin

def getline(): return map(int,stdin.readline().split())
N, Q = getline()
n=1
while (1<<n)<N: n+=1

sums=[[0]*((N>>i)+2) for i in range(n+1)]
flips=[[False]*((N>>i)+1) for i in range(n+1)]

# We keep information about the dice over "standard intervals" I_{i,j}=[j<<i,(j+1)<<i).
#
# These form a binary tree where the children of I_{i,j} are I_{i-1,2j} and I_{i-1,2j+1},
# and the parent of I_{i,j} is I_{i+1,j>>1}.
#
# The parent interval I_{i,j} is the disjoint union of its two children.
# For example if i=3, j=5, then I_{3,5}=[40,48) is the union of
# I_{2,10}=[40,44) and I_{2,11}=[44,48).
#
# The interval [0,R) decomposes into a disjoint union of standard intervals
# I_{i,j} according to the binary expansion of R:
# If R = r_n r_{n-1} ... r_0 in binary (r_i=0 or 1), then
# [0,R) is the disjoint union of I_{i,(R>>i)-1} over i such that r_i=1.
#
# The collection of all ancestor nodes of all standard intervals in the decomposition
# of [0,R) is I_{i,R>>i} over all i>0 (whether or not r_i = 0 or 1).
#
# We maintain the invariant:
# Number of heads over the range I_{i,j} = sums[i][j] modified by flips[i'][j']
# as (i',j') ranges over the ancestors of (i,j) in the tree.

def flip(R):# flip coins [0,R)
m=0;M=1
while M<=R:
if R&M:# flip coins [(R-M)&-M, R&-M)
t=(R-M)>>m
sums[m][t]=M-sums[m][t]
flips[m][t]=not flips[m][t]# invert flip status to make descendants work
m+=1;M<<=1
# Fix ancestors of changed nodes
m=1;M=2
while M<=N:
R2=R>>m
sums[m][R2]=sums[m-1][2*R2]+sums[m-1][2*R2+1]
if flips[m][R2]: sums[m][R2]=M-sums[m][R2]
m+=1;M<<=1

def csum(R):# Sum over [0,R)
s=0
fl=False
for m in range(n,-1,-1):
M=1<<m
if R&M:
t=sums[m][(R-M)>>m]
if fl: t=M-t
s+=t
fl=(fl!=flips[m][R>>m])# exclusive or
return s

out=[]
for i in range(Q):
op, A, B = getline()# operation, start, end (inclusive)
B+=1
if op==0: flip(A);flip(B)
else: out.append(str(csum(B)-csum(A)))
print("\n".join(out))

11
ответ дан 26 января 2018 в 09:01 Источник Поделиться

Поскольку Codechef, кажется, поддерживает numpyЯ бы предложил такое решение:

import numpy as np

n, q = map(int, input().split())
coins = np.zeros(n, dtype=bool)

for _ in range(q):
command, start, end = map(int, input().split())
end += 1 # end is inclusive
if command == 0:
coins[start:end] = ~coins[start:end]
elif command == 1:
print(coins[start:end].sum())

Это использует трюк , упомянутых здесь , чтобы перевернуть (суб)массив, используя унарный оператор отрицания ~. Это также гарантирует, что второе сравнение работает только после первой неудачной (так как только одна из двух команд может быть запущен).

Я также дал имена немного понятнее, не нужно быть немногословным здесь (50 КБ это предел исходный код, а это меньше, чем 500).

Я также добавил некоторые пробелы, по словам питона официальный стиль-руководство, PEP8.

Это также превышает срок, хотя. На моей машине это занимает около 3.1 S с входной файл, созданный с ниже код, который использует верхнюю границы для \n $\$ и $\Щ\$. Для сравнения, код операции занимает почти 10 минут (580s), так это уже значительную скорость, но тут еще такой фактор 10 не хватает до высшей время-предел (0,3 с).

import random

n, q = 100000, 100000
data = "\n".join("{} {} {}".format(random.choice([0, 1]),
*sorted([random.randrange(n),
random.randrange(n)]))
for _ in range(q))

with open("flipping_coins_input.dat", "w") as f:
f.write("{} {}\n".format(n, q))
f.write(data)


Приведенный выше код может быть немного быстрее-на затягивание вывода после цикла, что снижает количество приливов:

import numpy as np

n, q = map(int, input().split())
c = np.zeros(n, dtype=bool)

out = []
for _ in range(q):
command, start, end = map(int, input().split())
if command == 0:
c[start:end + 1] = ~c[start:end + 1]
elif command == 1:
# print(c[start:end + 1].sum())
out.append(str(c[start:end + 1].sum()))

print("\n".join(out))

Это сбривает около 10% (так она занимает 2.7 с).

6
ответ дан 25 января 2018 в 04:01 Источник Поделиться

Похоже, некоторые операции и NumPy дают очень большой постоянной скоростью фактором благо, как Graipher продемонстрировал в своем ответе. Решение Graipher является \$о(семо)\$, но вполне могут конкурировать с \$О(Г\журнал(N))\$ древовидное чисто решение на Python (подробно описано в моей другой ответ).

Я подумал, если это было возможно, чтобы адаптировать решение Graipher так, чтобы он проходил под порог времени Codechef с помощью Python 3.5. Попытка ниже делит растрового изображения на блоки по 64, кэширования итогов каждого блока. В языке Python 3, это немного быстрее, чем \$о(г\журнал(N))\$ решение и пройти порог времени Codechef. Они принимают решение, которое принимает 0.84 s (по их времени), несмотря на то, что говорят другие о 0,3 с порогом. Возможно, питон решений могут выполняться медленнее.

Это таблица таймингов

Время в секундах, используя мой компьютер (обычный рабочий стол) на случайной вопросами и ответами С \$П=М=100000\$.


В Python 2 на Python 3 в PyPy
Программа 1 2.48 2.65 н/д
Программа 2 1.58 2.16 0.29
Программа 3 1.70 1.85 н/д

from sys import stdin
import numpy as np

def getline(): return map(int,stdin.readline().split())

N, Q = getline()

# c0[] = bitmap of heads, divided into blocks of size 64
N1=N//64+1
c0 = np.zeros(N1, dtype=np.int64)

# c1[] = number of set bits for each block
c1 = np.full(N1, 0, dtype=int)

# Number of set bits in 16 bit range
btc16=[0]
for i in range(1,65536): btc16.append(btc16[i>>1]+(i&1))

# Number of set bits in 64 bit range
def btc64(x):
return btc16[x&0xffff]+btc16[x>>16&0xffff]+btc16[x>>32&0xffff]+btc16[x>>48&0xffff]

out = []
for _ in range(Q):
command, start, end = getline()
end+=1
# Decompose start into block number, s1, and bit number within block, s0
s1=start>>6; s0=start&63
# Same for end
e1=end>>6; e0=end&63
if command == 0:
if s1<e1:
c0[s1+1:e1]=~c0[s1+1:e1]; c1[s1+1:e1]=64-c1[s1+1:e1]
c0[s1]^=-(1<<s0); c1[s1]=btc64(c0[s1])
c0[e1]^=(1<<e0)-1; c1[e1]=btc64(c0[e1])
else:
c0[s1]^=(1<<e0)-(1<<s0); c1[s1]=btc64(c0[s1])
elif command == 1:
if s1<e1:
t=btc64(c0[s1]&(-(1<<s0)))+c1[s1+1:e1].sum()+btc64(c0[e1]&((1<<e0)-1))
else:
t=btc64(c0[s1]&((1<<e0)-(1<<s0)))
out.append(str(t))

print("\n".join(out))

6
ответ дан 27 января 2018 в 06:01 Источник Поделиться