如何合并两个字典，对相同键的值求和?

Question

我想要的是像merge(Dict1, Dict2, Merged)这样的东西，它的行为如下:

?- merge(counter{a: 1, b: 2}, counter{a: 3, c: 4, d: 5}, Merged).
Merged = counter{a: 4, b: 2, c: 4, d: 5}

我该怎么做才能做到这一点?我对逻辑编程完全陌生，所以我最终失败了，试图写一些看起来像其他语言的for循环的可怕端口。

Answer 1

dicts_merge_add(Dict1, Dict2, DictMerged) :-
% Convert to sorted key-value pairs
dict_pairs(Dict1, Tag, Pairs1),
dict_pairs(Dict2, Tag, Pairs2),
% Merge the pairs
pairs_merge_add(Pairs1, Pairs2, PairsMerged),
% Convert to dict
dict_pairs(DictMerged, Tag, PairsMerged).

% When reached end of 1 list, insert the remains of the other list
pairs_merge_add([], T, T) :- !.
pairs_merge_add(T, [], T) :- !.
pairs_merge_add([K-V1|T1], [K-V2|T2], L) :-
% Keys are same
!,
Sum is V1 + V2,
L = [K-Sum|Merg],
pairs_merge_add(T1, T2, Merg).
pairs_merge_add([K1-V1|T1], [K2-V2|T2], L) :-
K1 @< K2,
!,
L = [K1-V1|Merg],
pairs_merge_add(T1, [K2-V2|T2], Merg).
pairs_merge_add([K1-V1|T1], [K2-V2|T2], L) :-
K1 @> K2,
!,
L = [K2-V2|Merg],
pairs_merge_add([K1-V1|T1], T2, Merg).

结果swi-prolog:

?- D1 = counter{a: 1, b: 2, z:6},
D2 = counter{a: 3, c: 4, z:8, d: 5},
time(dicts_merge_add(D1, D2, Merg)).
% 17 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 389265 Lips)
D1 = counter{a:1,b:2,z:6},
D2 = counter{a:3,c:4,d:5,z:8},
Merg = counter{a:4,b:2,c:4,d:5,z:14}.

简单性能测试:

?- C = 30_000, numlist(1, C, L1N),
findall(N-N, member(N, L1N), L1),
dict_pairs(D1, v, L1), numlist(1, C, L2N),
findall(N-N, member(N, L2N), L2), dict_pairs(D2, v, L2),
time(merge(D1, D2, D3)), sleep(10).
% 180,005 inferences, 5.475 CPU in 5.486 seconds (100% CPU, 32877 Lips)
Vs mine: time(dicts_merge_add(D1, D2, D3))
% 60,005 inferences, 0.012 CPU in 0.012 seconds (100% CPU, 4987461 Lips)

这显示了使用排序列表所带来的巨大性能优势。

Answer 2

这种方法从A中获取条目，递归它们并将它们合并到B中:

merge(A, B, Merged) :-
dict_pairs(A, _, Pairs),     % Pairs are an ordered set
merge_(Pairs, B, Merged).

merge_([], Merged, Merged).       % No more pairs, merge finished.
merge_([K-V|Ps], B, Merged) :-    % Merge Key-Value from A.
(get_dict(K, B, Bval) ->     % Get the matching item from B.
Sum is V + Bval           % if success, sum their values.
; Sum is V),                % if not, just the value from A.
put_dict(K, B, Sum, B_),      % merge into B.
merge_(Ps, B_, Merged).       % merge remaining pairs into B.

在时髦的:

?- _D1 = counter{a: 1, b: 2, z:6},
_D2 = counter{a: 3, c: 4, z:8, d: 5},
time(merge(_D1, _D2, Merg)).
Merg = counter{a:4, b:2, c:4, d:5, z:14}
19 inferences, 0.000 CPU in 0.000 seconds (116% CPU, 827526 Lips)