Most common dictionary in an array of dictionaries
I need to find the most common dictionary in an array of swift dictionaries. I tried using the following:
func frequencies
<S: SequenceType where S.Generator.Element: Hashable>
(source: S) -> [(S.Generator.Element,Int)] {
var frequency: [S.Generator.Element:Int] = [:]
for x in source {
frequency[x] = (frequency[x] ?? 0) + 1
}
return sorted(frequency) { $0.1 > $1.1 }
}
But I cannot call "frequencies" with a type argument list [[String:String]]()
. How can I edit the above function to take an array of dictionaries or use a different method entirely?
source to share
You can use NSCountedSet
which provides functionality like this:
let arr = [
[
"foo": "bar"
],
[
"foo": "bar"
],
[
"foo": "baz"
],
]
let countedSet = NSCountedSet(array: arr)
for dict in countedSet {
println(countedSet.countForObject(dict))
println(dict)
}
prints
2
["foo": "bar"]
1
["foo": "baz"]
If you are having trouble with the wrong initializer use:
let countedSet = NSCountedSet()
countedSet.addObjectsFromArray(arr)
instead
let countedSet = NSCountedSet(array: arr)
I haven't tested with Swift 2, but the usage should be more or less the same.
source to share
As noted in the comments, the problem is that the type is [String:String]
not Hashable
.
A (much) less efficient solution when your types are not hashable is to fallback to Comparable
(can sort and generate running totals) Equatable
or, in the worst case, require the caller to supply a isEquivalent
closure. Then you go hunting through your frequencies looking for an equivalent element (and if you don't find one, insert it at frequency 1).
Here's an implementation that does it in Swift 2.0:
extension SequenceType {
func frequencies(@noescape isEquivalent: (Generator.Element,Generator.Element) -> Bool) -> [(Generator.Element,Int)] {
var frequency: [(Generator.Element,Int)] = []
for x in self {
// find the index of the equivalent entry
if let idx = frequency.indexOf({ isEquivalent($0.0, x)}) {
// and bump the frequency
frequency[idx].1 += 1
}
else {
// add a new entry
frequency.append(x,1)
}
}
return frequency.sort { $0.1 > $1.1 }
}
}
Since there is an implementation ==
that compares two dictionaries, if those dictionaries contain equivalent values, you can call them like this:
let dicts = [
["name": "David", "number": "1"],
["name": "John", "number": "2"],
["name": "David", "number": "1"],
]
// you can use `==` in two dictionaries that contain an equatable value,
// such as String here:
dicts[0] == dicts[1] // false
dicts[0] == dicts[2] // true
// so you can call frequencies like so:
dicts.frequencies(==)
which returns:
[(["number": "1", "name": "David"], 2),
(["number": "2", "name": "John"], 1)]
edit: here is Swift 1.2 version unfortunately tricky due to the lack of a version find
in 1.2 (renamed indexOf
2.0) which takes a predicate. This should work, but I don't have a working copy of 1.2 on this machine, so you may need to fix any syntax errors:
extension Array {
// add missing indexOf to Array as 1.2 doesn't have an equivalent
func indexOf(@noescape predicate: T->Bool) -> Int? {
for idx in indices(self) {
if predicate(self[idx]) { return idx }
}
return nil
}
}
func frequencies<S: SequenceType>
(source: S, @noescape isEquivalent: (S.Generator.Element,S.Generator.Element) -> Bool) -> [(S.Generator.Element,Int)] {
var frequency: [(S.Generator.Element,Int)] = []
for x in source {
// find the index of the equivalent entry
if let idx = frequency.indexOf({ isEquivalent($0.0, x)}) {
// and bump the frequency
frequency[idx].1 += 1
}
else {
// add a new entry
frequency.append(x,1)
}
}
return sorted(frequency) { $0.1 > $1.1 }
}
frequencies(dicts, ==)
source to share
(I don't know if this works with Swift 1.2)
You can also use a global function:
func frequencies<K, V where K : Hashable, V: Equatable>(dicts: [[K : V]]) -> [(dict: [K : V], count: Int)] {
var counts = [(dict: [K : V], count: Int)]()
for dict in dicts {
if let index = counts.indexOf({ $0.dict == dict }) {
counts[index].1++
} else {
counts.append(dict: dict, count: 1)
}
}
return counts.sort { $0.1 > $1.1 }
}
Use it like
let dicts = [
["name": "David", "number": "1"],
["name": "John" , "number": "2"],
["name": "David", "number": "1"],
]
print(frequencies(dicts))
outputs
[(["number": "1", "name": "David"], 2),
(["number": "2", "name": "John" ], 1)]
source to share