2021-08-09

[Python] 座標圧縮ってなんだ！ -AtCoder学習日記 #1

概要

今回からAtCoderのコンテストに参加して解けなかった問題の復習を書いておこうと思います。
AtCoderは基本Pythonで参加しています。今回はABC213-Cです。

ACできないコード

import numpy
from sys import stdin

_, _, n = map(int, input().split())
low = numpy.empty(n, dtype=int)
col = numpy.empty(n, dtype=int)
for i in range(n):
  a, b = map(int, stdin.readline().split())
  low[i] = a
  col[i] = b

for i in range(n):
  print(numpy.count_nonzero(low <= low[i]), numpy.count_nonzero(col <= col[i]))

基本TLEで一部WAでした。

解説の解説

解説によると今回の問題は「座標圧縮」の問題とのことです。

そもそも「座標圧縮」とは？

座標圧縮はいらない部分を切り落とすことです。
主に情報のない部分が多いときに探索等を行う場合に使用するようです。
無駄な部分を無くすことで探索を高速化するんですね。TLEばかりの僕にピッタリダァ

座標圧縮のアルゴリズム

ある数列Aを座標圧縮することを考えます。

Aをソートした数列をBとする
Bの重複した値を消す
Aの全要素についてBの何番目かを調べる

これで座標圧縮できます。トッテモカンタン！

このアルゴリズムを愚直に使ってコードを書いてみます。

import numpy
from sys import stdin

_, _, n = map(int, input().split())
low = numpy.empty(n, dtype=int)
col = numpy.empty(n, dtype=int)
for i in range(n):
  a, b = map(int, stdin.readline().split())
  low[i] = a
  col[i] = b
  
low_sorted = numpy.sort(numpy.unique(low))
col_sorted = numpy.sort(numpy.unique(col))

for i in range(n):
  print(numpy.where(low_sorted==low[i])[0][0]+1, numpy.where(col_sorted==col[i])[0][0]+1)

これでTLEだけになりました。ACではないです。
最後のlow_sorted、col_sortedの探索に時間がかかってると思われます。

模範回答コード

H,W,N=map(int,input().split())
X,Y=[],[]
for i in range(N):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)

Xdict = {x:i+1 for i,x in enumerate(sorted(list(set(X))))}
Ydict = {y:i+1 for i,y in enumerate(sorted(list(set(Y))))}

for i in range(N):
  print(Xdict[X[i]], Ydict[Y[i]])

解説にある模範回答コードです。ソート後の数列の探索を辞書を使うことでほぼ無くすようにしています。
そんな解決方法があったのか…。まだまだ精進が足りないようです。

まとめ

次元圧縮は無駄な情報を削ぎ落とすこと
インデックスの探索には辞書が使えることも

2020-11-07

[Swift]RealmSwiftでデータベースを使いたい<実践編>

Swift Realm Swift Realm SwiftUI プログラミング

概要

Swiftでデータベースを使いたい。<準備編>, <基本編>の続き。

環境

Xcode: 12.1
Swift: 5.3
Realm: 10.1.1
RealmSwift: 10.1.1

今回(と前回)で作るアプリ

入力した文字列をリストに追加していくアプリを作ってみる

f:id:yuyuyu_331:20201105131223p:plain — RealmSwiftTestApp

実際に組み込んでみる

前回の<基本編>で書いたRealmSwiftのコードを実際にアプリケーションの中に組み込んでみます。

SwiftUIを使って組み込みます。

SwiftUIの説明はがっつり省きます。後日まとめると思います多分。

前提となるレコードの型や関数

前回の説明に出てきた方々です。

class ListComponent: Object {
    @objc dynamic var word = ""
}

func addRecord (component: String) {
    let realm = try! Realm()
    let record = ListComponent()
    record.word = component
    try? realm.write {
        realm.add(record)
    }
}

func delRecord (record: ListComponent) {
    let realm = try! Realm()
    try? realm.write {
        realm.delete(record)
    }
}

レコードのリスト表示

レコードを全件取得してそれをリスト表示します。

基本的にはレコードを取得した後、それをForEachで回すイメージです。

List {
    ForEach(realm.objects(ListComponent.self), id: \.self) { record in
        Text(record.word)
    }
}

これでOKです。

データベースの更新をリストに反映

データベースの監視

今回のアプリでは、入力された文字列をリストに追加していくため、データベースにレコードが追加された時にまたレコードを取得し、リストを更新する必要があります

そのためにレコードの変化を監視するobserveメソッドを使います。

データベースのレコードを取得するモデルを作成し、その中で監視するといった方法をとります。

class ListComponentViewModel: ObservableObject {
    private var token: NotificationToken?
    private var componentResults = try? Realm().objects(ListComponent.self)
    @Published var components: [ListComponent] = []
    init() {
        token = componentResults?.observe { [weak self] (changes: RealmCollectionChange) in
            switch changes {
            case .initial:
                self?.components = self?.componentResults?.map { $0 } ?? []
            case .update(let record, deletions: let deletion, insertions: let insertion, modifications: _):
                if deletion != [] {
                    for index in deletion {
                        self?.components.remove(at: index)
                    }
                }
                if insertion != [] {
                    for index in insertion {
                        self?.components.append(record[index])
                    }
                }
            case .error(_):
                print("error")
            }
        }
    }
    deinit {
        token?.invalidate()
    }
}

うわぁ。。。なんだこのコード読む気すらおきない。。。

と思ったそこのあなた。間違い無いです。ごめんなさい

一個ずつ説明していきます。

NotificationTokenというクラスで、コレクション(レコードの集まり)を監視するようです。NotificationTokenはコレクションのobserveメソッドで得ることができます。

observeメソッド中でコレクションの変化毎に行うことを書きます。ちなみに、observeメソッドは、オブジェクト(レコード)、コレクション、Realm全体それぞれにあるらしく(ここに書いてあります)、コレクションだと、「コレクションへの挿入(insertion)」「コレクションからの削除(deletion)」「コレクションないの変更(modification)」の三種類を監視しているみたいです。

その三種類の内どれかが行われた時にobserveメソッドが呼び出されるようになってるみたいです。呼び出された種類によって.update内の引数に指定された変数の中に変更があった部分のインデックスがArrayで格納されます。

8番目に挿入されたならinsertionsに指定された変数(今回はinsertion)に[8]が格納されます。

6番目のレコードが削除されたならdeletionsに指定された変数(今回はdeletion)に[6]が格納されます。

また.updateの最初の引数には変更後のコレクションそのものが格納されます。

.initialは最初に取得した時に実行されるみたいです。(正直ここはよくわかってません)今回では、コレクションを配列として扱いたいのでコレクションを取得して配列に変換してます。

.errorは多分エラーが出た時に実行されます。(ここはほんとにわかんないです。勘)

リスト表示

レコードの受け取り方を変えたのでリスト表示の方も少しだけ変えます。

@ObservedObject var model = ListComponentViewModel()
List {
    ForEach(model.components, id: \.self) { record in
        Text(record.word)
    }
}

ついでにリストからの削除も実装しておきます。

List {
    ForEach(model.components, id: \.self) { record in
        Text(record.word)
    }
    .onDelete{ indexSet in
        if let index = indexSet.first {
            delRecord(record: self.model.components[index])
        }
    }
}

入力部分

ここはもうほとんどSwiftUIの基礎そのままみたいな感じですかね。

TextFieldで文字入力を受け付けて、Buttonでそれをデータベースに追加するといった感じです。

@State private var word = ""

HStack {
    TextField("", text: $word)
        .textFieldStyle(RoundedBorderTextFieldStyle())
        .padding(10)
    Button(action: {
        if word != "" {
            addRecord(component: word)
            word = ""
        }
    }, label: {
        Text("ADD")
    })
    .padding(10)
}

ここまでをまとめる

ここまで出てきたものを全部まとめて形を整えるとこんな感じになります。

import SwiftUI
import RealmSwift

class ListComponent: Object {
    @objc dynamic var word = ""
}

class ListComponentViewModel: ObservableObject {
    private var token: NotificationToken?
    private var componentResults = try? Realm().objects(ListComponent.self)
    @Published var components: [ListComponent] = []
    init() {
        token = componentResults?.observe { [weak self] (changes: RealmCollectionChange) in
            switch changes {
            case .initial:
                self?.components = self?.componentResults?.map { $0 } ?? []
            case .update(let record, deletions: let deletion, insertions: let insertion, modifications: _):
                if deletion != [] {
                    for index in deletion {
                        self?.components.remove(at: index)
                    }
                }
                if insertion != [] {
                    for index in insertion {
                        self?.components.append(record[index])
                    }
                }
            case .error(_):
                print("error")
            }
        }
    }
    deinit {
        token?.invalidate()
    }
}

func addRecord (component: String) {
    let realm = try! Realm()
    let record = ListComponent()
    record.word = component
    try? realm.write {
        realm.add(record)
    }
    print("add")
}

func delRecord (record: ListComponent) {
    let realm = try! Realm()
    try? realm.write {
        realm.delete(record)
    }
}

func changeRecord (record: ListComponent, component: String) {
    let realm = try! Realm()
    try? realm.write {
        record.word = component
    }
}

struct ContentView: View {
    @State private var word = ""
    @ObservedObject var model = ListComponentViewModel()
    let realm = try! Realm()
    var body: some View {
        VStack {
            HStack {
                TextField("", text: $word)
                    .textFieldStyle(RoundedBorderTextFieldStyle())
                    .padding(10)
                Button(action: {
                    if word != "" {
                        addRecord(component: word)
                        word = ""
                    }
                }, label: {
                    Text("ADD")
                })
                .padding(10)
            }
            List {
                ForEach(model.components, id: \.self) { record in
                    Text(record.word)
                }
                .onDelete{ indexSet in
                    if let index = indexSet.first {
                        delRecord(record: self.model.components[index])
                    }
                }
            }
        }
    }
}

struct ContentView_Previews: PreviewProvider {
    static var previews: some View {
        ContentView()
    }
}

やったことだけじゃなくてテンプレートとかその他もろもろがくっついてきてるんですけどね。

これで目的のアプリケーションの関西です。お疲れ様でした。

まとめ

RealmSwiftについての文書が少なすぎる。全然わからんかった。よく頑張った私。

参考にさせていただいた記事

2020-11-06

[Swift]RealmSwiftでデータベースを使いたい<基本編>

Swift Realm Swift Realm プログラミング

概要

Swiftでデータベースを使いたい。<準備編>の続きです。

環境

Xcode: 12.1
Swift: 5.3
Realm: 10.1.1
RealmSwift: 10.1.1

今回(と次回)で作るアプリ

入力した文字列をリストに追加していくアプリを作ってみる

基本的な使い方

もちろん

import RealmSwift

でRealmSwiftを使えるようにしておいてください

クラス(レコード)の定義

データベースに保存するデータ(レコード)の形はRealmSwiftのObjectを継承したクラスで定義します。

class ListComponent: Object {
    @objc dynamic var word = ""
}

今回は文字列しか使わないので、プロパティは一つだけですが、複数あっても大丈夫です。

"@objc"とか"dynamic"って何？？？？ってなると思うんですけど、Objective-Cというプログラミング言語(昔のiOSAppの開発に使われていました)の機能を使うのに必要みたいです。

レコードの追加方法

レコードの追加は、Realmインスタンスを生成して、writeメソッドの中で、addメソッドで追加します。

func addRecord (component: String) {
    let realm = try! Realm()
    let record = ListComponent()
    record.word = component
    try? realm.write {
        realm.add(record)
    }
}

ここで出てきたtry!とtry?ですが、どちらもエラーを無視できるといったものです。try!はエラーの際にクラッシュ、try?は単純にエラーを無視します。ほんとはあんまり使わない方がいいらしいです。。。

ちなみに追加した後に以下のようなコードを書くとエラーになります。

record.word = "hoge"

レコードの変更方法は下に書いているのでそっちを使いましょう。

レコードの削除方法

レコードの削除もRealmインスタンスを生成、writeメソッドの中で、deleteメソッドで削除します。

func delRecord (record: ListComponent) {
    let realm = try! Realm()
    try? realm.write {
        realm.delete(record)
    }
}

レコードの変更方法

レコードを変更する場合も、Realmインスタンスを生成、writeメソッドの中で変更してください。

func changeRecord (record: ListComponent, component: String) {
    let realm = try! Realm()
    try? realm.write {
        record.word = component
    }
}

レコードの読み込み方法

レコードの読み込みをする場合はobjectsメソッドで読み込めます。返り値はRealmSwiftのResultです。

条件に合うレコードを探す場合はfilterメソッドを使います。

全件取得

let realm = try! Realm()
let result = realm.objects(ListComponent.self)

特定の文字列を含むレコードを取得

let realm = try! Realm()
let result = realm.objects(ListComponent.self).filter("word contains 'Yuyu'")

特定の文字列と一致するレコードを取得

let realm = try! Realm()
let result = realm.objects(ListComponent.self).filter("word like 'Yuyuyu'")

数値が一定以下のレコードを取得

文字列以外の条件検索の方法はあったりします。

class TestRecord: Object {
    @objc dynamic var word = ""
    @objc dynamic var number = ""
}

let test1 = TestRecord()
test1.word = "hoge"
test1.number = 20

let test2 = TestRecord()
test1.word = "fizz"
test1.number = 3

let realm = try! Realm()
try? realm.write {
    realm.add(test1)
    realm.add(test2)
}

let realm = try! Realm()
let result = realm.objects(TestRecord.self).filter("number <= 10")

まとめ

今回は、こんなところですかね、、、多分次回(たぶん実践編)でRealmSwiftをつかったアプリを作っていくと思います。多分。

2020-11-05

[Swift]RealmSwiftでデータベースを使いたい<準備編>

Swift Realm Realm Swift プログラミング

概要

Swiftでデータベースを使いたい。Realmが早くていいらしい。とりあえずやってみっか！

環境

Xcode: 12.1
Swift: 5.3
Realm: 10.1.1
RealmSwift: 10.1.1

準備

CocoaPodsに苦戦

実はRealmはXcodeに初めから入ってるライブラリではないらしい。ので外部から自分で入れてあげないといけないみたい。

とりあえずCocoaPodsっていうのを使うらしいですよ。っていうのでやってみたら無理でした。
こんな感じのエラーが出てうまくいかないんですよね。。。

[!] /bin/bash -c 
set -e
sh build.sh cocoapods-setup

Downloading dependency: sync 10.0.0 from https://static.realm.io/downloads/sync/realm-sync-xcframework-10.0.0.tar.xz
ld: building for iOS Simulator, but linking in .tbd built for macOS/Mac Catalyst, file '/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX.sdk/usr/lib/libz.tbd' for architecture x86_64
clang-4.0: error: linker command failed with exit code 1 (use -v to see invocation)

たすけてえらいひと

Swift PMで再戦

まぁここで諦めてたらいけないんで、他の方法を探してみると、公式サイトに他の方法も乗っていました。

とりあえず、簡単そうなSwiftPMでやってみることにしました。

File > Swift Packages > Add Package Dependency を開くと"Enter package repository URL"っ書いてあるURLを入れるところがあるので"https://github.com/realm/realm-cocoa"を入力します。

サクサク進んで

RealmとRealmSwiftを選択してFinishです。

これでプロジェクトにRealmSwiftが入りました。

まとめ

これでやっと(?)RealmSwiftが入りました。

中身を触って理解したら<基本編>を書くと思います多分。

2020-10-28

[Python]waveファイルを重ね合わせたい

Python Numpy LibROSA 音プログラミング

概要

あるwaveファイルの一部にノイズ(waveファイル)を重ねたいんだ！！！

どうやるの

LibROSAとNumpyでなんとかなりそう。

準備

まずは準備。LibROSAとNumpyのインストールから。
たぶんAnaconda使ってる人はNumpyは最初から入ってるかもです。

pip install librosa

pip install numpy

で行けるはず。

やってみた

今回は、自宅で録音したこの10秒間の音に、(音量小さいので注意！)

このガラスの割れる音をランダムな位置に混ぜます。(音量大きいので注意！)

ちなみにこのガラスの割れる音はここ→ 生活[1]｜効果音ラボ← からダウンロードしてます。ガラスが割れる音2ってやつです。

import librosa #LibROSAをつかうよ！
import librosa.output #LibROSAで書き出しするよ！
import random #ランダムな数を使うよ！
import numpy as np #numpyはよくnpって略されるらしい。

y, sr = librosa.load('/Users/yuta/Documents/work/python/HomeSaver/dev_data/test/sample_2020-10-27T03:13:44.793815.wav', sr=None, mono=False)
# 家の音の読み込み
ay, asr = librosa.load('/Users/yuta/Documents/work/python/HomeSaver/Anomaly/glass-break3.wav', sr=sr, mono=True)
# ガラスの割れる音の読み込み

nokori = y.shape[0] - ay.shape[0] # ガラスの割れる音の始まるところの範囲

ran = random.randrange(nokori) # ガラスの割れる音をどこから始めるか

y[ran:ran+ano_shape[0]] += ay / 15 # 家の音とガラスの割れる音を足してる。
# ガラスの割れる音が大きすぎるので1/15にしてる。

librosa.output.write_wav('./sample.wav', y, sr)
# 書き出したお

そしてできたのがこんな音です。

もう一回回してみるとこんな感じ

ちゃんと違う位置にガラスの割れる音が入ってます。

まとめ

LibROSAとNumpyを使ってwaveファイルにwaveファイルを重ねたよ。結構いい感じにできた。

2020-10-28

[Python]Pythonで録音したい

Python PyAudio 音プログラミング

概要

機械学習の訓練用データの収集のためにPythonで録音したい。できればリアルタイムで録音しながら細切れに保存していきたい。

どーやるの

PyAudioっていうライブラリを使うのです。

準備

PyAudioをインストールすれば使えます。

$ pip install pyaudio

で、済めばよかったです。しっかりとERRORが出ます。
なので調べてみたらここ→https://python5.com/q/lmnhhjsd←で書かれてる

$ conda insatall -c anaconda pyaudio

でうまく行きました。よかった。

とりあえずPyAudioを動かしてみる

とりあえずPyAudioで5秒間録音してその波形を表示するプログラムを作ってみる。

import pyaudio  #pyaudioをインポート
import wave     #データ保存用にwaveを使う

device = 0 #マイクの選択
chunk = 1024 
format = pyaudio.paInt16 #フォーマットは16bit
channel = 1 #モノラルで録音
rate = 48000 #サンプリングレート
time = 5 #5秒間録音する
output_path = './fiveseconds.wav' #保存先の名前

p = pyaudio.PyAudio() #録音するんやで

stream = p.open(format = format, 
                channels = channel,
                rate = rate,
                input = True,
                input_device_index = device,
                frames_per_buffer = chunk) #ストリームを開いて録音開始!

print("now recoding...")

frames = [] #録音したデータをしまうList
for i in range(0, int(rate / chunk * time)): 
  data = stream.read(chunk)
  frames.append(data)

print('done.') #録音終わったよ！

stream.stop_stream() #用済みどもの始末
stream.close()
p.terminate()

wf = wave.open(output_path, 'wb') # ファイルに保存するよ
wf.setnchannels(channel)
wf.setsampwidth(p.get_sample_size(format))
wf.setframerate(rate)
wf.writeframes(b''.join(frames))
wf.close() #ファイルを保存したよ

作ると行ったけども実際はここ→ pyaudioを使ってpython上で録音・再生してみよう！ - もろみ先輩の日常← のコードを参考にしまくりました。

どうやらストリームを閉じるまでは録音してくれる模様

PyAudioでリアルタイム録音＆細切れ保存

ここからは試行錯誤しました。頑張った私。細切れに褒めるの大事。

import pyaudio  #pyaudioをインポート
import wave     #データ保存用にwaveを使う
import datetime

device = 0 #マイクの選択
chunk = 1024
format = pyaudio.paInt16 #フォーマットは16bit
channel = 1 #モノラルで録音
rate = 48000 #サンプリングレート
time = 10 #10秒間ずつ録音する
rec_hour = 18 # 録音する時間
output_path = './fiveseconds.wav' #保存先の名前

p = pyaudio.PyAudio() #録音するんやで

stream = p.open(format = format,
                channels = channel,
                rate = rate,
                input = True,
                input_device_index = device,
                frames_per_buffer = chunk) #ストリームを開いて録音開始!

start = datetime.datetime.now() #録音開始時間
end = start + datetime.timedelta(hours=rec_hour) #録音終了時間
print("now is " + start.isoformat())
print("this recording will end on " + end.isoformat())
print("now recoding...")

while True:
    frames = [] #録音したデータをしまうList
    for i in range(0, int(rate / chunk * time)):
      data = stream.read(chunk)
      frames.append(data)
    now_dt = datetime.datetime.now() #今の時間を取得
    output_path = './data/sample_' + now_dt.isoformat() + '.wav' #録音を保存するパスを設定
    wf = wave.open(output_path, 'wb')
    wf.setnchannels(channel)
    wf.setsampwidth(p.get_sample_size(format))
    wf.setframerate(rate)
    wf.writeframes(b''.join(frames))
    wf.close()
    if now_dt > end: #録音終了時間をすぎてたら終わるよ
        break

print('done.') #録音終わったよ！

stream.stop_stream() #用済みどもの始末
stream.close()
p.terminate()

こんな感じでかいてみたのですが、長時間録音してると、

Traceback (most recent call last):
  File "rec.py", line 32, in <module>
    data = stream.read(chunk)
  File "/Users/yuta/opt/anaconda3/lib/python3.7/site-packages/pyaudio.py", line 608, in read
    return pa.read_stream(self._stream, num_frames, exception_on_overflow)
OSError: [Errno -9981] Input overflowed

オーバーフローしてしまうみたいです。

現在解決策模索中です。。。

まとめ

Pythonで録音したよ。録音することよりもPyAudio入れる方に時間がかかった。。。

2020-10-27

使っている環境について

概要

現在(2020/10/27)使っている環境です。もしこのブログを参考にしてる人がいたらここの環境を参考にしてください。たまに更新し忘れると思います。どこまで書けばいいかわかんない。

相棒

ノートPC

MacBook Pro (13-inch, 2020, Four Thunderbolt 3 ports)
CPU : 2.3Ghz クアッドコア Intel Corei7
メモリ : 32GB 3733MHz LPDDR4X
GPU : Intel Iris Plus Graphics 1536MB
OS : macOS Catalina ver.10.15.7

大体いつもこの子で作業をしてます。
macを使うのはこの子が初めてだったりします。
この前に使っていたノートPCがsurfaceだったので大裏切りをかましました。

開発環境

Python

python 3.7
conda 4.9.0
pip 20.0.2
...こんなところ...?

C++

gcc 9.2.1
C++においてはAtCoderについてるコードテストとかだけだったり