組み込みdictとOrderedDictの比較 (Python 3.8)
この記事は、マイナビ Advent Calendar 2020 19日目の記事となります。
概要
- Pythonの組み込みdictクラスが、3.7から挿入順序を記憶するようになりました。
- もともとあったOrderedDictとの違いや、3.7以降でのOrderedDictの使いどころが気になったので、調べてみました。
公式ドキュメントの記述 (Python 3.8)
辞書は挿入順序を保存するようになりました。 キーの更新は順序には影響が無いことに注意してください。 いったん削除されてから再度追加されたキーは末尾に挿入されます。 (中略) バージョン 3.7 で変更: 辞書の順序が挿入順序であることが保証されるようになりました。この振る舞いは CPython 3.6 の実装詳細でした。
- collections > OrderedDict
- 「いまだ残っている dict との差分」から、気になった箇所を抜粋
- 「効率的に」が実行速度のことなのかコード量のことなのかが、この記述だけだと不明だが、とりあえずこの記事の下の方ではコード量を比較
OrderedDict に対する等価演算は突き合わせ順序もチェックします。 OrderedDict には、 効率的に要素を末尾に置き直す move_to_end() メソッドがあります。
等価演算の比較
- OrderedDict
from collections import OrderedDict d1 = OrderedDict({'one': 1, 'two': 2, 'three': 3}) d2 = OrderedDict({'one': 1, 'two': 2, 'three': 3}) d3 = OrderedDict({'one': 1, 'three': 3, 'two': 2}) d4 = OrderedDict({'one': 1, 'two': 2, 'three': 3, 'four': 4}) print(d1 == d2) # True print(d1 == d3) # False (順序もチェックする) print(d1 == d4) # False
- dict
d1 = {'one': 1, 'two': 2, 'three': 3} d2 = {'one': 1, 'two': 2, 'three': 3} d3 = {'one': 1, 'three': 3, 'two': 2} d4 = {'one': 1, 'two': 2, 'three': 3, 'four': 4} print(d1 == d2) # True print(d1 == d3) # True (順序はチェックしない) print(d1 == d4) # False
move_to_end
末尾に移動
- OrderedDict
from collections import OrderedDict d = OrderedDict({'one': 1, 'two': 2, 'three': 3}) d.move_to_end('two') print(list(d.keys())) # ['one', 'three', 'two']
- 同一の処理をdictで行う場合
- move_to_end相当の処理のために3行分書く必要あり。
d = {'one': 1, 'two': 2, 'three': 3} tmp = d['two'] del d['two'] d['two'] = tmp print(list(d.keys())) # ['one', 'three', 'two']
先頭に移動
- OrderedDict
from collections import OrderedDict d = OrderedDict({'one': 1, 'two': 2, 'three': 3}) d.move_to_end('two', last=False) print(list(d.keys())) # ['two', 'one', 'three']
- 同一の処理をdictで行う場合
- move_to_end相当の処理のために5行分書く必要あり。
d = {'one': 1, 'two': 2, 'three': 3} d_tmp = {'two': d['two']} del d['two'] for k, v in d.items(): d_tmp[k] = v d = d_tmp print(list(d.keys())) # ['two', 'one', 'three']
AtCoderのGo言語で構造体をソートする時の注意点
この記事は、マイナビ Advent Calendar 2019 17日目の記事となります。
概要
AtCoderのGo言語ジャッジシステムで、構造体のスライスをソートする時の注意点をまとめました。
2通りの方法
- 競技プログラミングでは、ソートをよく使います。
- Go言語にはPackage sortがあります。
- int、float64、string型は、それぞれ以下の関数で簡単にソートできます。
- sort.Ints
- sort.Float64s
- sort.Strings
- しかし上記3つの以外の型をソートする場合は、一工夫必要です。
sort.Slice (バージョン1.8で追加)
package main import ( "fmt" "sort" ) type Person struct { Name string Age int } func (p Person) String() string { return fmt.Sprintf("%s: %d", p.Name, p.Age) } func main() { people := []Person{ {"Bob", 31}, {"John", 42}, {"Michael", 17}, {"Jenny", 26}, } fmt.Println(people) sort.Slice(people, func(i, j int) bool { return people[i].Age > people[j].Age }) fmt.Println(people) }
sort.Sort (バージョン1.7以前でも使用可能)
package main import ( "fmt" "sort" ) type Person struct { Name string Age int } func (p Person) String() string { return fmt.Sprintf("%s: %d", p.Name, p.Age) } type ByAge []Person func (a ByAge) Len() int { return len(a) } func (a ByAge) Swap(i, j int) { a[i], a[j] = a[j], a[i] } func (a ByAge) Less(i, j int) bool { return a[i].Age < a[j].Age } func main() { people := []Person{ {"Bob", 31}, {"John", 42}, {"Michael", 17}, {"Jenny", 26}, } fmt.Println(people) sort.Sort(ByAge(people)) fmt.Println(people) }
※Package sortのExampleから抜粋
バージョン1.6ではsort.Sliceが使用できない
競技プログラミングでGo言語を使い始めた時につまづいたこと
この記事は、マイナビ Advent Calendar 2019 9日目の記事となります。
概要
AtCoderでGo言語を使い始めた時に、つまづいたことについてまとめました。
バージョン1.6がmacOSで使用できない
2019年12月8日時点のジャッジシステムにおいて、Go言語の処理系はバージョン1.6です。
https://atcoder.jp/contests/abc147/rules
新しいバージョンだと、使用できる標準モジュールが異なるため、AtCoder用に1.6の環境も用意しようとしました。
※macOS Mojave(バージョン10.14)で検証
動作確認用のコード(Hello World)
package main import ( "fmt" ) func main() { fmt.Println("Hello World") }
バージョン1.11では正常に動作します。
$ goenv global 1.11.4 $ go version go version go1.11.4 darwin/amd64 $ go run hello.go Hello World
しかし以下のように、バージョン1.6では「Segmentation fault」になります。
$ goenv install 1.6.4 $ goenv global 1.6.4 $ go run hello.go Segmentation fault: 11
公式のリポジトリで同じ問題に遭遇しているissueがありました。
cmd/go: segmentation fault on macOS 10.13.4 #24679
そしてこんなコメントが。
macOS Sierra(バージョン10.12)以降では、goの1.10.1以前のバージョンが動かないとのこと。
Please make sure you upgrade to go 1.10.1. Earlier versions of Go are incompatible with changes to the kernel interface in Sierra and later.
1.6で動作確認したい場合は、コンテストページのコードテストから実施するしかない模様
https://atcoder.jp/contests/abc147/custom_test
補足
ジャッジサーバの処理系がアップデートされたら、上記問題は解決しそうです。