[SwiftUI] RealmSwiftのMigrationについて
概要
長い間見て見ぬ振りしてきたRealmSwiftのMigration処理について触れることになりました。
とてもとても長い道のりでした。
もっと早くにやっておけばよかったと後悔してます。
解決策
まずは解決策から
class AppDelegate: UIResponder, UIApplicationDelegate { func application(_ application: UIApplication, didFinishLaunchingWithOptions launchOptions: [UIApplication.LaunchOptionsKey : Any]? = nil) -> Bool { RealmMigrator.setDefaultConfiguration() return true } }
これを<アプリの名前>App.swiftに追記します。
次にRealmMigrator.swiftを作成して
import SwiftUI import RealmSwift enum RealmMigrator { static private func migrationBlock( migration: Migration, oldSchemaVersion: UInt64 ) { if oldSchemaVersion < 1 { // 変更点とか書くところ } } static func setDefaultConfiguration() { let config = Realm.Configuration( schemaVersion: 1, migrationBlock: migrationBlock) Realm.Configuration.defaultConfiguration = config } }
と書き込みます。以上です。
ここに辿り着くまでにほんとに時間かかった．．．
その他解説
執筆中．．．
関連記事
まとめ(?)
- Migrationは早めにやっておこう
- いつの間にか消えていたAppDelegate.swift
参考にしたサイト
[SwiftUI] Cannot assign to property: 'last' is a get-only property について
# 概要 今回はSwiftUIをいじっていた時に出てきた
Cannot assign to property: 'first' is a get-only property
というエラーについて分かったことと対応策です。
エラーが起きた状況
var a = [1, 2, 3, 4] a.last! = 3 // Cannot assign to property: 'first' is a get-only property
という配列の最後の要素をlastで取り出して変更しようとした時にエラーが起きました。
どういうやらこのエラー「'last'というpropertyはgetしかできません」という意味みたいです。
つまり、'last'というプロパティは値を取ってくるだけで、新しい値をセットすることはできないということみたいです。
そのため、「最後の要素を取ってきて」「新しい値をセットする」という二つの手順を踏みたい場合には'last'は使えないです。
解決策
この問題は単純に配列の要素をIndexで指定して取り出すことで解決できます。
var a = [1, 2, 3, 4] a[a.count - 1] = 3
'count'で配列の長さを取得して、-1で最後の要素を指定して値を取り出すという感じです。
まとめ
- 'last'は配列の最後の要素を取り出すことしかできない
- 取り出した要素を変更したい場合は直接Indexで指定する
- 'count-1'で最後の要素のIndexになる
補足
'first'でも同じエラーが起こるみたいです。この場合は
var a = [1, 2, 3, 4] a[0] = 3 // a.first! = 3から変更
で修正できます。
sortされたlistを維持したいならbisectをつかう！ -AtCoder学習日記 #6
概要
今回はABC217-Dについてです。TLEから抜け出せずに終わってしまいました．．．
なかなかTLEにならないコードを書くのは難しいですね。
今回はレートが下がりました悲しいです。
ACらないコード
l, q = map(int, input().split()) cut = [] for _ in range(q): c, x = map(int, input().split()) if c == 1: cut.append(x) else: cut_p = list(filter(lambda s: s <= x, cut)) cut_n = list(filter(lambda s: s > x, cut)) if len(cut_p) == 0: if len(cut_n) == 0: print(l) else: print(min(cut_n)) else: if len(cut_n) == 0: print(l - max(cut_p)) else: print(min(cut_n) - max(cut_p))
切断部分を記録しておいて、長さを取得する際は含まれていて欲しい部分より「大きい最小値」と「小さい最大値」の差を出力する。
と言った考え方です。
解説読んだ感じだと、考え方自体は間違っていなかったみたいですね．．．
解決策について
どうやら、解き方は間違っていない模様ですが、Listに挿入するときに少し工夫をすることでTLEを脱出できそうです。
今回はPythonのbisectを使ってみようと思います。
bisectライブラリとは
Pythonの二分探索を用いた標準ライブラリです。少ない計算量でListをソートされた状態を保つことができます。
詳しいことは参考文献に書いてあります。今回はbisect_leftを使うことになりそうです。
bisect_leftはソートされた状態を保ったまま挿入する場合のindexを返してくれるメソッドです。
ACれるコード
from bisect import bisect_left from array import array l, q = map(int, input().split()) cut = array('i', [0, l]) for _ in range(q): c, x = map(int, input().split()) index = bisect_left(cut, x) if c == 1: cut.insert(index, x) else: print(cut[index] - cut[index-1])
listではTLEのままだったので、arrayを使用してみたらうまくいきました。
もしかしてarrayの方が早い...?
まとめ
- 順序を保ったまま挿入したい場合はbisectを使おう！
- listよりもarrayを使った方が高速みたいです。
- 今回はレートが下がりました悲しいです。
参考文献
Dequeを使うといいのかも -AtCoder学習日記 #5
概要
今回はABC216-Dについてです。 今回はうまくいったと思ってたんですけどね．．．やはりTLEに悩まされます。
ACにならなかったコード
n, m = map(int, input().split()) nodes = [set() for _ in range(n+1)] for _ in range(m): k = int(input()) pipes = list(map(int, input().split())) for i in range(k): for j in range(i+1, k): nodes[pipes[i]].add(pipes[j]) if pipes[i] in nodes[pipes[j]]: print("No") exit() print("Yes")
筒の中で出てくる色の順番が異なる部分が出てきたらダメだと思って組んだんですけどTLEになってしまいました．．．
解説の解説
解説を私なりに要約すると「書いてあることをそのままやればいいよ。ただ計算量(実行時間)に気をつけてね」ということみたいです。
なので今回は前から気になっていたDeque型を使ってみたいと思います。
Dequeについて
Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。
ちなみに、Listでも同じことが可能です。しかし、Dequeを用いた方が圧倒的に早い模様です。それぞれの計算量は以下のようになってます。
ListとDequeで計算量が変わるところは赤くしています。
| 操作 | List | Deque |
|---|---|---|
| 先頭に追加 | O(n) | O(1) |
| 最後尾に追加 | O(1) | O(1) |
| 先頭を取り出す | O(n) | O(1) |
| 最後尾を取り出す | O(1) | O(1) |
先頭についての操作はDequeの方が上手みたいですね。
ACなコード
from collections import deque n, m = map(int, input().split()) pipes = [] for _ in range(m): k = input() pipes.append(deque(map(int, input().split()))) queue = deque([(q.popleft(), i) for i, q in enumerate(pipes)]) # queueに各筒の先頭の球を入れる。 balls = [-1] * (n + 1) # 入ってた筒と球が2つ出たかどうかの判定 while queue: a, i = queue.popleft() if balls[a] == -1: balls[a] = i # 1つ目の球なら球の入っていた筒の番号を保存 else: j = balls[a] balls[a] = -2 # 2つ目の球なら2つ出たことを記録して # jに1つ目の球が入っていた筒の番号 # iに2つ目の球が入っていた筒の番号を記録 if pipes[j]: queue.append((pipes[j].popleft(), j)) #もしj番目の筒に球があるならqueueに入れる if pipes[i]: queue.append((pipes[i].popleft(), i)) #もしi番目の筒に球があるならqueueに入れる if sum(balls) == -2 * n - 1: print('Yes') else: print('No')
今回からコードの説明をコメントで書き込んでみました。少しはわかりやすくなっている...はず...です。
まとめ
- 先頭と最後尾を扱う配列の場合はListよりもDequeの方が計算量が少ない！
- 問題によっては問題文通りに進めるのも良いこともある
参考文献
最長増加部分列ってどちら様？？？ -AtCoder学習日記 #4
概要
今回はARC125-Cについてです。
今回の問題に至っては問題文の理解から時間がかかりました。最長増加部分列(LIS)についての問題のようです。
私事：やっと茶色に乗ることができました！！！
最長増加部分列とは？
部分列
そもそも最長増加部分列を理解する前に、部分列について知る必要がありそうです。
部分列とは、「ある数列のうち、いくつかの項を取り出して順番を変えずに作れる数列」のことです。
例えば数列を考えると、
は部分列ですし、
も部分列です。
途中の項を飛ばしてもOKですが順番を変えるのはNGです。
そのため、は部分列ではありません。
増加部分列
次に増加部分列の説明です。
増加部分列は「となる部分列」のことです。
例えば数列を考えると、
は増加部分列ですし、
も増加部分列です。
すべての項において常に増加するため、は増加部分列ではありません。
最長増加部分列
最後に最長増加部分列についてです。
最長増加部分列は「増加部分列の内、最長のもの」です。
先程の例の数列だと
が最長増加数列です。
ACになるコード
n, k = map(int, input().split()) a_list = list(map(int, input().split())) ans = [] used = [0] * (n + 1) i = 1 for a in a_list[:-1]: ans.append(a) used[a] = 1 while i < a: if used[i] == 0: ans.append(i) used[i] = 1 i += 1 break i += 1 for j in range(n, i - 1, -1): if used[j] == 0: ans.append(j) print(" ".join(map(str, ans)))
指定された数列を入れつつ、入れられるところは小さい数字から入れていくって感じですね。
その後、余った数字は単調に減少するようにします。
まとめ
- 最長増加部分列は「増加部分列の内、最長のもの」
- 再帰的に考えてみるのもあり
- やっと茶コーダー！
参考文献
[Python] 数値誤差恐るべし。。。 -AtCoder学習日記 #3
概要
今回はABC215-Bについてです。
コード自体は簡単なのですが「誤差」でWAになってしまいました。
ACできないコード
import math n = int(input()) print(math.floor(math.log2(n)))
ほとんどACなのですが一部だけWAになってしまっています。
なぜ誤差が出るのか
そもそも誤差はなんで生まれるのかについてです。
整数を扱っている際には特に誤差は生じないのですが、問題は小数を扱っている時です。
通常コンピュータでは10進数を2進数に変換して計算します。
そのため2進数にすると循環小数になってしまうような10進数を扱うと、循環している部分が丸められてしまうため正確な値にならないのです。
誤差を起こさないための対策
10進数同士の和差積商であれば、pythonのdecimalモジュールとfractionsモジュールを用いることで解決できるようです。参考文献のサイトに例が載っているのでそちらを参照してみてください。しかし、
floatの計算→Decimalの計算→Fractionの計算、の順番に計算速度が遅くなります。
とのことですので、競プロにはあまり向かない気がします。
解説にもあるように
競技プログラミングにおいて、整数性のある問題に対して整数性を外して実数で処理することには危険が伴います。整数性のある問題はなるだけ整数型で処理することをおすすめしますが、どうしても実数型が必要な際は注意して取り扱いましょう。
を忠実に守るのが良さそうです。。。
ACできたコード
import numpy n = int(input()) n = numpy.array(n).astype('float128') s = numpy.log2(n) print(s.astype('int64'))
Numpyの型変換で4倍精度浮動小数点型(float128)を用いることでACになりました。
まとめ
- 小数の計算するときには誤差に気をつける。
- decimal, fractionsモジュールを使うことで誤差をなくせる
- そもそも整数を扱う問題を実数に落とし込むのは危険
参考文献
[Python] UnionFindって何！？ -AtCoder学習日記 #2
概要
今回はABC214-Dです。やっとD問題に手が出るようになりました。
問題文的にこの問題はグラフ理論の問題のように見えます。
解説文
今回詳しく書く部分(私がわからなかった部分)を赤くしています。
以下では、辺の重みは相異なると仮定します。制約にそのような条件はありませんが、添字の大小による tie-break などを行えばよいです。
各
について、
となる
の総数を数えることを考えます。
を結ぶパスに辺
が含まれ、かつそのパスに含まれる他の辺の重みが
より小さいことです。
重みが
と
は必ず連結成分に属します。これら二つの連結成分の一方に
、もう一方に
が属することが、
となるための条件です。
よって、辺の重みの小さい順にグラフに追加していき、Union-Findなどのデータ構造を用いて連結成分の大きさを取得することにより、この問題を得ことができます。
解説の解説
解説を読む限り、グラフ理論の用語をしっかり知っておく必要がありそうです。。。
森
我らがWikipedia先生によると
閉路を持たない (連結であるとは限らない) グラフを森 (もり、英: forest) という。
とのことです。
閉路は"始点と終点が同じ道"、つまりループ部分のことです。
連結であるは"ある2点間を結ぶ道が存在すること"です。
つまり、バラバラなところがあってもいいけど、ループ部分はないグラフですかね。
木は「連結な森」とのことです。
ここまではわかります。
連結成分
次は、連結成分についてです。
極大で連結な部分グラフは、連結成分 (connected component) という。
極大で連結な部分グラフ？？？
よくわからないので、少しずつ整理します。
連結は先ほどにも出てきた通り”ある2点間を結ぶ道が存在すること”で、部分グラフは”グラフの一部分のグラフ”です。
では、極大で連結とはどういうことなのでしょうか。
Google先生に聞いてみるとここで以下のような説明がありました。
G'がグラフGの極大で連結な部分グラフであるとは、G'を部分グラフに持つGの連結な部分グラフがG'以外にないことを言います。
つまり極大で連結な部分グラフもとい連結成分はバラバラになってない一塊のグラフってことですかね！
グラフの中に、連結でない部分があることをしっかり意識しないと理解するのも難しいです。。。
Union-Find
DSU( Disjoint Set Union, 素集合データ構造)とも言うみたいです。
ここに以下のように説明があります。とてもわかりやすいです。
Union-Find木とは，グループ分けを木構造で管理するデータ構造のこと．同じグループに属する＝同じ木に属するという木構造でグループ分けをする際，以下の二点を高速で行うことができるのがメリット．
要素xと要素yが同じグループに属するかどうかを判定したい
→要素xの根と要素yの根が同じならば同じグループ，要素xの根と要素yの根が同じでないならば異なるグループにあることが分かる．要素xと要素yが同じグループに属する場合，要素xの属するグループと要素yの属するグループの併合する．
このスライドが非常に分かりやすい．
そのスライドも本当にわかりやすいです。
ある集合内の要素を特定の条件に従って分けるときに効果を発揮するアルゴリズムってことみたいですね。
同じ条件のグループを同じ木でまとめて、要素同じグループかどうかは木の根が同じかどうかで判断します。
同じ条件かどうかを木の根のみで判断するため、結局どこの木の根にくっついているかのみに着目すれば良いことになります。
そのため、実際には木構造を構成するのではなく、リストで木の根がどの要素なのかのみを管理すれば良いです。
これらをPythonで実装するとこんな感じですかね。
class UnionFind: def __init__(self, n): self.n = n self.root_size = [-1] * n #木の根が誰かを格納するリスト(自分が木の根の場合は負の数) #グループのサイズを木の根のところに負の数で格納する # →木の根の部分には、自分が木の根であることとグループのサイズ # の2つの情報が入ることになる． def root(self, u): #木の根が誰かを返すメソッド if self.root_size[u] < 0: return u else: self.root_size[u] = self.root(self.root_size[u]) return self.root_size[u] def merge(self, u, v): #二つの要素をまとめるメソッド u_root = self.root(u) #木の根が誰かを求めて v_root = self.root(v) if u_root == v_root: #一致していれば、すでにまとめられている return True else: #一致していなければ、 self.root_size[v_root] += self.root_size[u_root] #片方のサイズをもう片方に足して、 self.root_size[u_root] = v_root #木の根を変更する return True def size(self, u): #ある要素のいるグループのサイズを返すメソッド #木の根が誰かを求めて、そのサイズをリストから求める． return -self.root_size[self.root(u)]
このように実装できるとおもいます。
ACになる解答
UnionFindのPythonでの実装はもう書いたのでそれ以外の部分です。
n = int(input()) edge = [] for _ in range(n-1): #一旦辺の情報を保存して u, v, w = map(int, input().split()) edge.append([u-1, v-1, w]) edge = sorted(edge, key=lambda x: x[2]) #重みが小さい順に分ける uf = UnionFind(n) ans = 0 for i in range(n-1): [u, v, w] = edge[i] ans += w * uf.size(u) * uf.size(v) #UnionFind木のそれぞれの要素が含まれるグループのサイズをかける # →f(u, v)がその重みになる個数がわかる。 # →uのグループに含まれる頂点からvのグループに含まれる頂点までを結ぶ道で # u-vの辺を通る場合の数 # *重みが少ない順に処理しているため、常に全てのグループは # 処理する時の重みよりも小さい重みの辺のみを持つ uf.merge(u, v) #uの入ったグループと, vの入ったグループを同じグループにまとめる。 print(ans)
と、このような感じです。これでしっかりとACが出るはずです。
重みが小さい順に処理することで、ある重みよりも小さい辺だけで繋がった連結成分だけを考えられるのは、なかなか出てこない発想な気がします。
いや．．．ただ勉強不足なだけか．．．？
