LINUX.ORG.RU

Является ли такая реализация правильной?

 , , ,


0

2

Задача.

Имеются запросы в форме tuple of ints например

 
q=(1,5)  No1 query
q=(2,3)  No2 query
q=(3,1)  No3 query

q[0] может быть 1 или 2 или 3
q[1] - любое положительное число

Условия (по-англ. короче)
array=[ ]
if q[0]==1, insert q[1] to array
if q[0]==2, remove q[1] from array
if q[0]==3, check if there is integer whose frequency is q[1] in array

Количество запросов: 1<= queries <= 10**9

Является ли это правильным решением, если удалять запрошенные числа не по мере поступления запроса с q[0]=2, а сформировать сначала два независимых списка (один с числами для добавления, а другой с числами ждя удаления) и удалять, когда придет запрос с q[0]=3? И является ли решение с генераторами приемлемым или это странное решение?

def freqQuery(queries):
    from collections import Counter

    output=[]
    ad = Counter()
    de = Counter()
    for k,v in queries:
        if k==3:
            ad=ad-de
            if v in ad.values():
                output+=[1]
            else:
                output+=[0]
        elif k==2:
             de.update([v])
        else:
             ad.update([v])

    return output

def freqQuery(queries):
    from collections import Counter

    def helper(k, v, ad, de):

        if k==1:
            ad.update([v])   # add value as key & count its frequency only for No 1 queries
        elif k==2:
            de.update([v])   # add value as key & count its frequency only for No2 queries
        return ad-de         # remove all integers of No2 quaries from Counter related to No 1 queries


    a = Counter()
    d = Counter()

    #list of final arrays in the form of generator to analyze No 3 queries
    # such list includes Counters , tuples of Counter and int related to No 3 query
    gen=(helper(key, value, a, d) if key !=3 else (a, value) for key,value in queries)

    # list of tuples in the form of generator
    gen2=(item for item in gen if type(item) == tuple)

    #form final output
    gen3=(1 if item[1] in item[0].values() else 0 for item in gen2)

    return list(gen3)


Работать должно правильно, но что если запросы в основном будут типа 3? Не будет ли производительность убита постоянным ad=ad-de + v in ad.values()?

xaizek ★★★★★ ()

Оверинжениришь дофига. Вот решение проще:

def process_queries(queries):
    from collection import Counter
    array = Counter()

    total = 0
    for action, value in queries:

        if action == 0:
            array[value] += 1
            total += 1

        elif action == 1:
            array[value] -= 1
            total -= 1

        else:
            count = array[value]
            frequency = float(count) / float(total)

    return  # process_queries
anonymous ()
Ответ на: комментарий от xaizek

наверное, это неудачно

В этом варианте уже проще, но с ним тоже проблемы. Выполнение замедляется из-за v in c.values()?

def freqQuery(queries):
    from collections import Counter

    output=[]
    c=Counter()
    for k,v in queries:
        if k==1:
            c[v]+=1
        elif k==2 and v in c:
            c[v]-=1

        elif k==3:

            if v in c.values():
                output+=[1]
            else:
                output+=[0]
    return output

hibiscusM ()
Ответ на: комментарий от anonymous

я не понимаю что это

        else:
            count = array[value]
            frequency = float(count) / float(total)

в вашем коде value из запроса № 2 и № 3 - ключи в словаре array.

Вы берете запрос №3, в котором value не должно являться ключом в словаре. Оно должно быть значением одного из ключей.

hibiscusM ()
Ответ на: комментарий от hibiscusM

and v in c

Не думаю, что это надо проверять. Входные данные должны быть корректны.

Выполнение замедляется из-за v in c.values()?

Не больше чем должно, наверное. Если что, я не питонист.

Только дошло, что нужно там проверять. Думаю, можно сделать проверку быстрее с помощью дополнительного словаря.

output+=[1]

Мне кажется, что append может работать быстрее: output.append(1).

xaizek ★★★★★ ()
Последнее исправление: xaizek (всего исправлений: 2)
Ответ на: комментарий от xaizek

Мне кажется, что append может работать быстрее: output.append(1)

да с этим стало работать быстрее

and v in c

Не думаю, что это надо проверять. Входные данные должны быть корректны.

(1,2)
(2,3)

>>> ar=Counter()
>>> ar[2]=1
>>> ar
Counter({2: 1})
>>> ar[3]-=1
>>> ar
Counter({2: 1, 3: -1})
>>> 
hibiscusM ()