python - 挑选卡片(卡片更少，成本更低)- 性能问题

Question

n - 手牌数量例如:n = 4

collection - 根据 n 收集卡片，例如:collection =[1,3,4,7]

d 表示卡片总数，例如:10 [1,2,3,4,5,6,7,8,9,10]

卡片 1 - 费用 1 ;卡片 5-费用 5

场景:需要挑选不在收藏列表中的卡片，卡片成本低于(d)并且需要显示最多可能的卡片

eg: sum of (2+5) <10 so we need to show (fewer cards ,cost less) accepted
eg: sum of (2+6) < 10 rejected (fewer cards ,cost more) 
eg: sum of (2+5+6) < 10 rejected (more cards ,cost more,count more than d) 
eg: sum of  (2+8) < 10 rejected (cost more)

它适用于小数据获取性能问题:

场景 1:

start = time. time()
n=4
collection=[1,3,4,7]
d=10
lis=[]
list1=[]
[lis.append(x+1) for x in range(0,d)]
[lis.remove(x) for x in collection]  
#print(lis)
#for L in range(0, len(lis)+1):
for subset in itertools.combinations(lis, d%n):
    if sum(subset)<=d:
        #print(subset)
        list1.append(subset)
k = list(map(lambda x: len(x),list1))
s = list(filter (lambda x: len(x)==max(k),list1))
m = list(filter(lambda x: sum(x) == min(list(map(lambda x: sum(x),s))),s))
print(*m[0],sep='\n')
end = time. time()
print(end - start)

结果:2 5时间0.0

场景 2:n=8 collection=[1,3,4,7,20,25,50,60] d=100

结果2个5个6个8

时间:762.9762706756592

Answer 1

如果我正确理解你的问题，我认为这会像你想要的那样:

def pick_cards(collection, d):
    collection_set = set(collection)
    # The ordered sequence of cards not in collection
    pickable = (i for i in range(1, d + 1) if i not in collection_set)
    # Sum of picked cards
    s = 0
    # Picked cards
    picked = []
    for pick in pickable:
        # If the card does not go over the limit
        if s + pick < d:
            # Add card
            picked.append(pick)
            s += pick
        else:
            # Otherwise finish
            break
    return picked

# Examples
print(pick_cards([1, 3, 4, 7], 10))
# [2, 5]
print(pick_cards([1, 3, 4, 7, 20, 25, 50, 60], 100))
# [2, 5, 6, 8, 9, 10, 11, 12, 13, 14]