python - 提高Python中列表集迭代的效率

Question

我有一个列表列表，其中元素 0 中包含项目，元素 1 中包含与其关联的值。每个项目可能出现多次。我想创建一个唯一项目列表，其中每个项目都有最大值。我的代码实现了这一点，但似乎效率很低。另外，这是一个简化的示例。 mylist 可能有 100,000 行。有什么提高效率的建议吗？

mylist = [['Item 1', 12],['Item 1', 10], ['Item 3', 12],['Item 4', 10], ['Item 3', 14]]

# get unique items
my_unique_items = list(set(x[0] for x in mylist))

# make it a list of list
my_unique_items = [[x] for x in my_unique_items]

# iterate over list items
for item in my_unique_items:

    # do list comp to get max value and append
    item.append(max([x[1] for x in mylist if x[0] == item[0]]))

print my_unique_items

Answer 1

仅循环 mylist 一次会更有效。如果您只关心每个项目键的最大值，只需保留项目及其最大值的映射，并在浏览列表时比较它们。

最坏情况的复杂度为 O(n)，而您原来的最坏情况的复杂度为 O(n^2)。

item_maxes = {}
for item in mylist:
    max_value = item_maxes.setdefault(item[0], None)
    if max_value is None or item[1] > max_value:
        item_maxes[item[0]] = item[1]

编辑:我认为ShadowRanger's此方法的版本看起来更清晰:

max_vals = {}
for item, value in mylist:
    max_vals[item] = max(max_vals.get(item, value), value)