Python在字典中迭代

Question

我正在尝试遍历一个字典，但我不确定在遍历时如何更新

我想做的(Simulating LFU cache)： 收到请求后， 逐个遍历每个请求，并计算每个请求使用字典的频率

如果字典包含超过8个键，请删除频率最低的值，如果这些值的频率都相等，则删除字典中的最低键

因此，从当前8中删除最低的键，并将第9个键放入其中

然后继续这样做，直到剩下8个值

目前我有：

    requests=[1, 13, 15, 1, 3, 4, 2, 12, 10, 4, 1, 15, 15, 11, 14, 7, 10, 9, 14, 5]
    lst=[] #only holds 8 ints
    def leastFrequent():
        #user inputs requests manually
            print (requests)
            freq = {} #Dictionary
        
            for i in requests:
                if i in freq.keys():
                    #Increase frequency by 1
                    freq[i] += 1
                    print("Hit", i)
                else:
                    #If not set frequency to 1
                    freq[i] = 1
                    print("Miss", i)
            #I want to move my while loop inside this i think?? but i get errors with it being a dictionary

           freq = sorted(freq.items(), key=lambda k: k[0])#places dictionary into list of lists
           freq.sort(key=lambda x: x[1])#sort in order
           print("Converted frequency:",str(freq))
        
            while len(freq)>8:
                print("Size greater than 8..\n",str(freq[0]))
                del freq[0]#atm this just deletes the first value printed since it should be the lowest
                if len(freq)<=8:
                    break
        #i then move elements[0] into a final list to be printed
            lst=[item[0] for item in freq] 
            print ("\nPrinting final list")        
            print(lst)
            
    leastFrequent()

问题是它在逐个迭代时不会删除，而是先计算所有项，然后删除最低的项

这会导致不正确的输出：

 [11, 12, 13, 4, 10, 14, 1, 15]

预期产出：

[1, 13, 15, 4, 12, 11, 14, 5]

订单不重要，我想尝试在这方面不使用图书馆

抱歉，如果这听起来让人困惑，我是编程新手，我正在学习如何使用字典和列表

Answer 1

你的解释很混乱，但据我所知，我们有键：值对和变量的收入，它们被保存为字典（哈希映射），如果频率有相同的值，你希望保持最高频率或最高（键）。简而言之，我的建议是，你只想在每次更新字典时重新创建它。让我们看看您的代码：

# creates dictionary out of frequencies based on the input list
def simulating_list(req, req_list):
    req_list[req] = 1 if req not in req_list else req_list[req]+1

# 1.takes items of the list and sorts by frequency;
# 2.takes a slice of the list starting from 8th element from the end
# 3.reverses the list(just to look nice, dictionaries nowadays displyed ordered)
# 4.creates new dictionary out of list of lists


def filter_eight(req_list):
    return dict(sorted(req_list.items(), key=lambda x: x[1])[-8:][::-1])


# Your request lists
requests = [1, 13, 15, 1, 3, 4, 2, 12, 10,
            4, 1, 15, 15, 11, 14, 3, 4, 2, 1, 5, 3, 2, 4, 1, 2, 3, 4, 5, 12, 3, 4, 2, 34,  23, 1, 2, 3, 4, 12, 3, 12, 3, 4, 2, 3, 7, 10, 9, 14, 5]
# data base
req_data_base = {}
# generator inside the list will execute
[simulating_list(i, req_data_base) for i in requests]

print(filter_eight(req_data_base))
# Displays dictionary with key = request, value= frequency
# If you want to display it differently its up to you
# {3: 9, 4: 8, 2: 7, 1: 6, 12: 4, 5: 3, 15: 3, 14: 2}

Answer 2

def fun(requests):
    freq={}
    for i in requests:
        if i in freq:
            freq[i]+=1
            print("hit",i)
        else:
            freq[i]=1
            print("miss",i)
        if len(freq)>8:
            to_remove = min(freq,key=lambda k:(freq[k],k))
            print("to remove",to_remove,"from",freq)
            del freq[to_remove]
    return freq

这与Chris的类似，但没有将东西转换为字符串，另一件事是使用min的键函数获取要删除它的元素，我们使用元组是可排序的，并且它们的顺序由它们的值位置基给出，因此如果它们具有相同的值，则使用对（值，键）作为比较键（或本例中的频率）在第一个位置，检查其第二个位置，即我们的字典键（或给定的请求）

>>> requests=[1, 13, 15, 1, 3, 4, 2, 12, 10, 4, 1, 15, 15, 11, 14, 7, 10, 9, 14, 5]
>>> result=fun(requests)
miss 1
miss 13
miss 15
hit 1
miss 3
miss 4
miss 2
miss 12
miss 10
hit 4
hit 1
hit 15
hit 15
miss 11
to remove 2 from {1: 3, 13: 1, 15: 3, 3: 1, 4: 2, 2: 1, 12: 1, 10: 1, 11: 1}
miss 14
to remove 3 from {1: 3, 13: 1, 15: 3, 3: 1, 4: 2, 12: 1, 10: 1, 11: 1, 14: 1}
miss 7
to remove 7 from {1: 3, 13: 1, 15: 3, 4: 2, 12: 1, 10: 1, 11: 1, 14: 1, 7: 1}
hit 10
miss 9
to remove 9 from {1: 3, 13: 1, 15: 3, 4: 2, 12: 1, 10: 2, 11: 1, 14: 1, 9: 1}
hit 14
miss 5
to remove 5 from {1: 3, 13: 1, 15: 3, 4: 2, 12: 1, 10: 2, 11: 1, 14: 2, 5: 1}
>>> result
{1: 3, 13: 1, 15: 3, 4: 2, 12: 1, 10: 2, 11: 1, 14: 2}
>>> list(result)
[1, 13, 15, 4, 12, 10, 11, 14]
>>> 
        

（还请注意，字典对其键进行迭代是默认的，因此实际上不需要调用.keys）

Answer 3

也许我在你的描述中遗漏了什么，但是按照你的逻辑，我得到了相同的输出

我相信您的代码是错误的，在计数后循环-但在这种情况下，它可能奇怪地没有改变输出

requests=[1, 13, 15, 1, 3, 4, 2, 12, 10, 4, 1, 15, 15, 11, 14, 7, 10, 9, 14, 5]

freq = {}

for r in requests:
    r = str(r)
    if r in freq:
        freq[r]+=1
        print(f'Hit {r}')
    else:
        freq[r]=1
        print(f'Miss {r}')
    if len(freq.keys()) > 8:
        # Get list of keys that share the lowest frequency
        k = [int(k) for k, v in freq.items() if v == min(freq.values())]
        print(f'Requests sharing the lowest frequency of {min(freq.values())} -> {k}')
        print(f'Dropping lowest request value -> {min(k)}')
        del freq[str(min(k))]
        
print([int(x) for x in freq.keys()])

最终产量

[1, 13, 15, 4, 12, 10, 11, 14]