0

Я решал задачку «Покупка футболок», но оказалось, что она работает очень медленно. Причин я не могу понять, так как не слишком хорошо знаю питон. Но одно я понимаю точно, что это странно, так как оно имеет хорошую ассимптотику и не должно долго работать.

n = int(raw_input())
price = [int(value) for value in raw_input().split(' ')]
front = [1 << (int(value) - 1) for value in raw_input().split(' ')]
back = [1 << (3 + int(value) - 1) for value in raw_input().split(' ')]
result = {}
for index in range(0, n):
    if not(front[index] + back[index] in result):
        result[front[index] + back[index]] = [price[index]]
    else:
        result[front[index] + back[index]].append(price[index])
for item in result:
    result[item] = sorted(result[item])
cust = int(raw_input())
fav = [1 << (int(value) - 1) for value in raw_input().split(' ')]

index = 0
for itemCust in fav:
    minValue = 2000000000
    minItem = -1
    for item in result:
        priceValue = result[item]
        if (item & itemCust != 0 or item & (itemCust << 3) != 0) and len(priceValue) > 0 and priceValue[0] < minValue:
            minValue = priceValue[0]
            minItem = item
    if minItem != -1:
        result[minItem] = result[minItem][1:]
        print minValue
    else:
        print -1

Комментарий по задаче. У нас есть пары чиселок от 1 до 3 (футболки). Есть запросы (покупатели) в виде одной чиселки от 1 до 3, которым важно, чтобы среди пар чиселок (футболок) была хотя бы одна такая же, как и у них.

Для решения мы кидаем все футболки в мапу, кодируя их следующим образом. Каждая футболка -- это бит-число из 2х единиц. Первые 3 единицы отвечают первой чиселке из пары. Вторые 3 единицы отвечают второй чиселке из пары.

1 1 --> 100100 (т.е. 1ый бит и (1 + 3)ый бит)

1 2 --> 100010 (т.е. 1ый бит и (2 + 3)ый бит)

3 2 --> 001010 (т.е. 3ий бит и (2 + 3)ый бит)

и т.д.

Собственно, для каждого бинарного кода заведём мапу и будем хранить список цен, отсортированных в порядке убывания. После чего переберём всех покупателей поочереди и будем выбирать за 6 шагов самую подходящую футболку.

4
  • А вопрос в чем? Вы можете посмотреть на узкие места в вашем коде, используя профилировщики: vmprof, kernprof
    – m9_psy
    12 мая 2017 в 10:44
  • @m9_psy Вопрос в том, где могут быть узкие места в коде. Окей, погляжу. 12 мая 2017 в 13:13
  • вам эти инструменты покажут все узкие места лучше любого ответа - они покажут сколько времени (сколько раз) выполняется та или иная строчка в вашем скрипте (не как cProfile - тот сразу в потроха лезет) - отсюда можно и оценивать асимптотику (сколько раз вызывается та или иная функция в зависимости от входных данных) и насколько тяжела та или иная операция и чем ее можно заменить.
    – m9_psy
    12 мая 2017 в 13:26
  • @m9_psy, это, конечно, всё прекрасно, но ассимптотика и так понятна, ровно как и примерное число операций. Непонятность во времени добавления и извеления данных из структуры dict и сортировках. 12 мая 2017 в 13:45

1 ответ 1

1

вот решение в лоб за 2,2 сек

import time
import random

# исходные данные
shirts_count = 200000
shirts_prices = [random.randrange(1, 1000000000) for _ in range(shirts_count)]
shirts_colors_front = [random.randrange(1, 3) for _ in range(shirts_count)]
shirts_colors_back = [random.randrange(1, 3) for _ in range(shirts_count)]

shoppers_count = shirts_count - 1
shoppers_colors = [random.randrange(1, 3) for _ in range(shoppers_count)]

# {цвета: [цены]}
Shirts = {}
for c, p in zip(zip(shirts_colors_front, shirts_colors_back), sorted(shirts_prices)):
    try: Shirts[c].append(p)
    except: Shirts[c] = [p]

def buy_color_shirt(color: int):
    '''купить'''
    for c in Shirts:
        if color in c:
            prices = Shirts[c]
            if prices:
                return prices.pop(0)
    return -1


if __name__ == '__main__':
    t = time.time()
    # покупка
    for color in shoppers_colors:
        buy_color_shirt(color)
    print(round(time.time() - t, 1), 'сек')

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.