LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 18

Swift Advent Calendar 2025

@nak435

[Swift] defaultdict ライクな Dictionary

Posted at

動機

Swift の Dictionary には、デフォルトがありません。存在しないかもしれない key でアクセスする場合は、アンラップやオプショナルバインディングするか、毎回 default値 を与える必要があります。
このため、Python における defaultdict が使えると便利だなと思いながら、いつもコードを書いています。

そこで、defaultdict ライクな DefaultDictionary を簡単に実装してみました。

実装

たった 15行です。

struct DefaultDictionary<Key, Value> where Key: Hashable {
    let defaultValue: Value
    fileprivate var storage: [Key: Value]
    init(default defaultValue: @autoclosure @escaping () -> Value, dictionary: [Key: Value] = [:]) {
        self.defaultValue = defaultValue()
        self.storage = dictionary
    }
    subscript(key: Key) -> Value {
        get { storage[key, default: defaultValue] }
        set { storage[key] = newValue }
    }
    var keys: Dictionary<Key, Value>.Keys { storage.keys }
    var values: Dictionary<Key, Value>.Values { storage.values }
    mutating func callAsFunction(_ callback: (_ dict: inout Dictionary<Key, Value>) -> Void) { callback(&storage) }
}

本家Dictionaryは subscriptでデフォルトを指定します。一方、DefaultDictionaryは イニシャライザでデフォルトを指定することで、subscriptでのデフォルト指定を不要にする発想です。

Dictionary
init()
subscript(key: Key) -> Value? { get set }	//keyが存在しない場合は nil
subscript(
    key: Key,
    default defaultValue: @autoclosure () -> Value
) -> Value { get set }						//keyが存在しない場合は default値
DefaultDictionary
init(default defaultValue: @autoclosure () -> Value) //keyが存在しない場合の default値
subscript(key: Key) -> Value { get set }	//keyが存在しない場合は 常に default値

使い方

subscriptごとにデフォルトを変えたい場合や、オプショナルバインディングしたい場合には不向きですが、いつも同じデフォルトを使う場合であれば、タイピング数が減り可読性も向上します。

Dictionaryの場合
var dict = Dictionary<Int, Int>()
let range = 0 ..< 100
for _ in 1...10 {
    let r = Int.random(in: range)
    dict[r, default: 0] += 1
}
for r in range {
    print("\(r): \(dict[r, default: 0])")
}

通常のデフォルト値は、Valueの型で ほぼ一意だと思います。
たとえば、整数系なら0、浮動小数点系なら0.0、文字列系なら""（空）、配列やコレクションなら[]（空）と。

上のコードを DefaultDictionary を使って書き換えると、コードの見通しがよくなります。

DefaultDictionaryの場合
var dict = DefaultDictionary<Int, Int>(default: 0)
let range = 0 ..< 100
for _ in 1...10 {
    let r = Int.random(in: range)
    dict[r] += 1
}
for r in range {
    print("\(r): \(dict[r])")
}

Dictionary変数をアクセスする箇所が増えるほど、この違いを実感できます。

DefaultDictionary にも keys と values プロパティを用意したので、ほぼ不便は無いはず ですが、欠点としては、Dictionary型なら存在する多様なメソッド/プロパティ類を一切 定義（継承）していないことです。これを補うため、callAsFunction で Dictionary変数を ミュータブルで引き渡すことにより、直接参照/更新を可能にしてあります。

良い例が思い浮かびませんが、たとえば、以下のように使います。

内部Dictionary変数の直接更新
dict { d in
    d[100] = -100
    if let n = d[999] { print(n) } //オプショナルバインディングも可
}
print(dict[100])
//-100

面倒な方は、内部変数storageを直接アクセスしちゃってください。

使用例

アルファベットの出現を DefaultDictionary で管理する例を示します。

import Foundation

let text = """
    A dictionary is a type of hash table, providing fast access to the entries it contains. Each entry in the table is identified using its key, which is a hashable type such as a string or number. You use that key to retrieve the corresponding value, which can be any object. In other languages, similar data types are known as hashes or associated arrays.
    Create a new dictionary by using a dictionary literal. A dictionary literal is a comma-separated list of key-value pairs, in which a colon separates each key from its associated value, surrounded by square brackets. You can assign a dictionary literal to a variable or constant or pass it to a function that expects a dictionary.
    """
var dict = DefaultDictionary<Character, [Int]>(default: [])
for (offset, char) in text.enumerated() where char.isLetter {
    let uppercase = char.uppercased().first!
    dict[uppercase].append(offset)
}

let uppercaseLetters = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

//出現個数(アルファベット順)
for char in uppercaseLetters { 
    print("\(char) : \(dict[char].count)")
}

//出現位置(少ない順,小さい順)
let sortedLetters = uppercaseLetters.sorted { 
    dict[$0].count == dict[$1].count ?
        dict[$0].lexicographicallyPrecedes(dict[$1]) :
        dict[$0].count < dict[$1].count
    }
for char in sortedLetters {
    print("\(char) : \(dict[char])")
}

以前なら、ほぼすべての箇所に, default: xを書かなければ ならなかったと思うと、面倒くさいしゾッとします。
（下記、出力結果のZは、デフォルト値が使われている）

出力結果
//出現個数(アルファベット順)
A : 69
B : 10
C : 28
D : 16
E : 54
F : 6
G : 8
H : 21
I : 50
J : 1
K : 6
L : 17
M : 5
N : 35
O : 34
P : 10
Q : 1
R : 37
S : 45
T : 50
U : 15
V : 6
W : 5
X : 1
Y : 20
Z : 0
//出現位置(少ない順,小さい順)
Z : []
J : [267]
Q : [554]
X : [663]
W : [141, 248, 319, 365, 479]
M : [188, 295, 437, 438, 515]
F : [24, 48, 121, 457, 512, 648]
V : [41, 220, 241, 463, 532, 611]
K : [136, 207, 316, 459, 508, 564]
G : [46, 130, 181, 239, 285, 288, 385, 582]
P : [20, 38, 163, 233, 308, 443, 469, 495, 635, 664]
B : [33, 108, 157, 189, 258, 266, 378, 550, 560, 616]
U : [126, 167, 187, 196, 198, 244, 286, 381, 466, 535, 540, 544, 555, 572, 649]
D : [2, 43, 116, 124, 236, 301, 344, 367, 389, 411, 449, 530, 546, 548, 587, 672]
L : [34, 109, 158, 243, 282, 297, 400, 406, 422, 428, 451, 465, 489, 534, 598, 604, 617]
Y : [11, 19, 97, 138, 162, 194, 209, 263, 307, 350, 376, 379, 398, 420, 461, 510, 551, 570, 596, 681]
H : [26, 29, 64, 91, 103, 142, 145, 152, 155, 169, 203, 224, 249, 252, 278, 325, 328, 480, 483, 506, 658]
C : [4, 54, 55, 78, 90, 144, 168, 227, 251, 254, 269, 339, 354, 369, 391, 413, 435, 482, 487, 505, 525, 563, 574, 589, 623, 651, 666, 674]
O : [7, 23, 40, 61, 79, 183, 195, 212, 228, 234, 265, 276, 318, 332, 338, 372, 394, 416, 436, 456, 488, 490, 514, 524, 543, 571, 592, 607, 620, 624, 632, 644, 654, 677]
N : [8, 45, 68, 80, 84, 94, 100, 118, 129, 180, 186, 235, 238, 256, 262, 274, 284, 317, 320, 363, 373, 384, 395, 417, 477, 491, 545, 576, 583, 593, 625, 629, 650, 655, 678]
R : [10, 39, 70, 96, 178, 184, 191, 214, 217, 229, 230, 280, 299, 313, 333, 347, 348, 355, 375, 397, 404, 419, 426, 445, 472, 497, 513, 541, 542, 557, 561, 595, 602, 613, 621, 633, 680]
S : [14, 28, 50, 57, 58, 73, 85, 113, 127, 134, 148, 154, 166, 172, 176, 199, 232, 290, 293, 310, 323, 327, 330, 336, 337, 351, 382, 431, 441, 453, 473, 493, 501, 519, 522, 523, 539, 553, 567, 579, 580, 626, 637, 638, 668]
I : [3, 6, 13, 42, 44, 71, 75, 83, 99, 112, 115, 120, 122, 128, 132, 143, 147, 179, 218, 237, 250, 273, 294, 296, 340, 368, 371, 383, 390, 393, 401, 412, 415, 423, 430, 452, 471, 476, 481, 517, 526, 581, 588, 591, 599, 614, 640, 653, 673, 676]
T : [5, 18, 31, 51, 60, 63, 69, 76, 81, 95, 102, 106, 119, 133, 161, 177, 202, 205, 211, 216, 223, 270, 277, 303, 306, 342, 358, 370, 392, 402, 414, 424, 447, 454, 499, 518, 528, 566, 590, 600, 606, 627, 630, 641, 643, 652, 657, 660, 667, 675]
E : [21, 35, 56, 65, 67, 72, 88, 93, 104, 110, 117, 123, 137, 159, 164, 190, 200, 208, 215, 219, 221, 225, 231, 245, 259, 268, 279, 289, 309, 314, 329, 343, 356, 359, 364, 403, 425, 442, 448, 460, 467, 494, 500, 503, 509, 529, 536, 547, 558, 565, 601, 618, 662, 665]
A : [0, 9, 16, 27, 32, 49, 53, 82, 89, 107, 150, 153, 156, 171, 174, 204, 242, 255, 261, 283, 287, 298, 302, 304, 312, 322, 326, 335, 341, 346, 349, 357, 361, 374, 387, 396, 405, 409, 418, 427, 433, 439, 444, 446, 464, 470, 485, 496, 498, 504, 521, 527, 533, 556, 562, 575, 578, 585, 594, 603, 609, 612, 615, 628, 636, 646, 659, 670, 679]

一般には、Eの出現が最も多いそうだが、今回の短い文章では 2位だった。1位はA

最後に

これで、Dictionaryを使ったコードを書くのが、かなり楽になります。

上のコードは、AtCoder環境（Swift 6.2）でも問題なく動作することを 確認済み。

追伸

やはり、オプショナルバインディングしたいこともあるかなと考えて、optional 引数付きの subscript を追加しました。
また、少しでも性能に寄与するようにインライン展開のアトリビュートを付けました。

struct DefaultDictionary<Key, Value> where Key: Hashable {
    let defaultValue: Value
    fileprivate var storage: [Key: Value]
    init(default defaultValue: @autoclosure @escaping () -> Value, dictionary: [Key: Value] = [:]) {
        self.defaultValue = defaultValue()
        self.storage = dictionary
    }
+   @inline(__always)
    subscript(key: Key) -> Value {
+       @inline(__always)
        get { storage[key, default: defaultValue] }
+       @inline(__always)
        set { storage[key] = newValue }
    }
+   @inline(__always)
+   subscript(optional key: Key) -> Value? {
+       @inline(__always)
+       get { storage[key] }
+       @inline(__always)
+       set { storage[key] = newValue }
+   }
+   @inline(__always)
    var keys: Dictionary<Key, Value>.Keys { storage.keys }
+   @inline(__always)
    var values: Dictionary<Key, Value>.Values { storage.values }
+   @inline(__always)
    mutating func callAsFunction(_ callback: (_ dict: inout Dictionary<Key, Value>) -> Void) { callback(&storage) }
}
オプショナルバインディングしたいとき
var dict = DefaultDictionary<Int, Int>(default: 0)

if let n = dict[optional: 99] {

} 

if let n = dict.storage[99] {

}

お好みの書き方で どうぞ。


@inline(__always)を追加しましたが、
AtCoder環境での性能を比較すると、数倍〜数十倍 遅い結果が出ました。このため、アクセス数が多い場合はTLEになる可能性があります。この点をご注意ください。
もし使用される場合は自己責任でお願いします。

内部変数storageを直接アクセスすると 性能差が無いため、subscriptでのアクセスが遅いということです。


以上

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?