python - 如何实现 "group_by"功能

Question

在 Python、Ruby 或 SQL 等许多函数式语言中，我们可以使用预定义的“group_by”函数或方法。如果我想使用 Java、C 或其他没有默认实现“group_by”的东西来实现它，最好的方法是什么？

输入:[键，值]

{ [ 'A', 1 ], [ 'B', 3 ], [ 'C', 1 ], [ 'A', 2 ], [ 'A', 6 ], [ 'B', 7 ] ... }

输出:

{ [ 'A', [ 1, 2, 6 ] ], [ 'B', [ 3, 7 ] ], [ 'C' [ 1 ] ], ... }

示例代码:

for element in "input": 
        for temp in "input":
            if ( temp.key == element.key )
                Output . getKey( element.key ) . addValue( temp.value );
            end if
        end for
end for

这段代码似乎是处理它的常用方法，但有没有人有比这更好的想法？

我假设数组没有排序，尽管这很容易。而且，有时需要NOT修改输入，那么我们该怎么办？复制整个输入数据似乎是一种解决方案，但它会消耗大量内存。

哈希表可以解决这个问题，我相信这是最常见的解决方法，空间复杂度为 O(n)，运行时间复杂度为 O(n)。

Answer 1

在 Python 中你可以使用字典:

input = [('A', 1), ('B', 3), ('C', 1), ('A', 2), ('A', 6), ('B', 7)]

output = {}
for key, value in input:
    if not key in output:
        output[key] = []
    output[key].append(value)