propyonの日記

情報科学を学ぶ黄色いネズミ

あなたがものを渡すときに考慮しなければならない3つの渡し方

tags: 情報

どうも.コンピュータサイエンスを極める前にRuby on Railsを極めないとインターン先でやばい,ピカチュウです

今回はプログラミングにおける渡し方を整理したいと思います

題名は中身がない記事にありそうな雰囲気を意識しました.想像通り中身はないのでご安心ください

プログラミングにおける渡し方

プログラミングにおける変数の渡し方は以下の3つがあります

  • 値渡し
  • ポインタ(アドレス)渡し
  • 参照渡し

(渡し方なんてどうでもいいと思った人は,好きな人にプレゼントを着払いで渡せばいいと思います)

渡し方というのはコンピュータのメモリを理解すればすんなり理解できるので,サンプルコードと表をセットで説明したいと思います

その前に...メモリとは?

コンピュータには主記憶装置,通称メモリ(memory)というものがあります

このメモリにはそれぞれアドレスというのが割り振られています

そして,そのアドレス上で値を保持するのがプログラミングにおける変数の役割です

そのメモリをどう扱うかが渡し方によって異なるわけです

値渡し

サンプルコードはC言語です

int x = 1; # xのアドレスを確保し,そのアドレスの指す値に1を入れている
int y = x; # yのアドレスを確保し,そのアドレスの指す値にxのアドレスが指す値,1を入れている
変数名 アドレス
x m1 1
y m2 1

値渡しは上のように変数(y)のあるアドレスに指す値に,他の変数(x)の値を代入する際に渡すことです

ここではアドレスのやり取りはなく,値のやり取りのみが行われます

ポインタ(アドレス)渡し

C言語において,ポインタとして宣言されるとアドレス,値どちらの値も示すことができます

一方,単に整数として宣言された場合はそのアドレスの指す値を示します

ポインタの宣言,ポインタ以外アドレスを指す方法,アドレスの指す値を指す方法です

int* x; # 宣言
&x; # アドレス
*y; # 値

サンプルコードはC言語です

int x = 1; # xのアドレスを確保し,そのアドレスの値に1を入れている
int* y; # ポインタ型であるyのアドレスを確保している
y = &a; # yのアドレスにxのアドレスを入れている(xとyのアドレスを同じにした)
*y = 2 # yのアドレスの値に2を代入している
変数名 アドレス
x m1 1
y m2 m1

ここでは,ポインタとして宣言されたyの値に

参照渡し

サンプルコードはRubyです

x = 1
y = x
変数名 アドレス
x m1 1
y m1 1

参照渡しはアドレスをコピーして渡すやり方です

この渡し方でバグを生んだことしかないのです

次にその一例を載せておきます

Rubyでソート関数を書いたときの話

このなんたら渡しというのは別に変数に変数を代入するときだけでなく,関数に代入するときも関係します(仮引数に変数を代入していると考えるといいと思います)

Rubyの場合,配列,ハッシュを引数とする関数へは参照渡しが行われます

以下のようなバブルソートを用意します

引数にa(配列)とn(配列の要素数)を受け取ります

def bubble_sort(arr, n)
  flag = true
  while flag
    flag = false
    (1..n - 1).reverse_each do |i|
      next unless arr[i] < arr[i - 1]

      arr[i], arr[i - 1] = arr[i - 1], arr[i]
      flag = true
    end
  end
  arr
end

この関数でソートしてみると以下のような結果になります

arr = [*(1..10)].reverse!
# => [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
sorted_arr = bubble_sort(arr)
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
puts sorted_arr
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

そうです,引数の配列もひっくり返ってしまっています

このように意図しない副作用が起きてしまうので注意が必要です

ちなみに

sorted_arr = bubble_sort(arr.dup)

のように引数に複製した配列を与えると配列を意図しない形でソートせずに返すことが可能です

まとめ

プレゼントを渡す時は渡し方にも拘ろう

RemacsをUbuntuにインストール

tags: 情報

Remacsとは

Remacsのリンク

EmacsをRustで書き換えようというOSSです

Emacsの拡張性は非常に高く僕もよく使うエディタですが,それをRustで改良しようというコンセプトが面白いですね

Remacsのインストール

Rustをインストールしていない場合

UNIX系の場合は下のコマンドでrustupをインストールします1

$ curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

インストールはインストーラーの指示にしたかってください

Rustのインストールが済んでいる場合

Cコンパイラや周辺環境をインストールします

$ sudo apt install build-essential automake clang libclang-dev
$ sudo  apt install texinfo libjpeg-dev libtiff-dev \
   libgif-dev libxpm-dev libgtk-3-dev libgnutls28-dev \
   libncurses5-dev libxml2-dev libxt-dev

これが終わったら本体のインストールです

$ git clone https://github.com/remacs/remacs.git

remacsディレクトリに移りビルドします

$ ./autogen.sh
$ ./configure --enable-rust-debug
$ make

ところが

$ ./autogen.sh

を実行しようとすると以下のエラーが発生する

Checking Rust toolchain install ...
Remacs requires the rustup command to be installed in order to build. Please see https://www.rustup.rs/; Aborting.

rustuprustもインストールしたはずなのになんで...?

どうやらrustupをダウロードするときに

$ source $HOME/.cargo/env

というコマンドを打たないといけなかったらしいです

Remacsの実行

RUST_BACKTRACE=1 src/remacs

上のように実行します

RUST_BACKTRACE=1はとりあえず付けたほうがよいらしいです

-qというオプションをsrc/remacsのあとに付けることも可能です.emacs.dを無視してくれるオプションらしいです

使った感想

-qオプションを付けないで起動すると下のようなエラーメッセージが

Warning (package): Unnecessary call to ‘package-initialize’ in init file

Remacsではパッケージをinitializeしなくてもいいのかな?

とりあえずコーディングや拡張に関してEmacsと変わらないように感じました

使ってみて困った点があったらIssueに上げてみようと思います

人間関係をReset-Set型と人生Delay型

tags: 情報

人生の7割はフリップフロップで説明できる

はい.学科の人が7/31で期末試験が終わるところ,まだ米国に3週間滞在するピカチュウです

今回は実は遷移を理解していないけど,まあそういうもんだよなとされがちなフリップフロップの遷移を丁寧に追っていこうと思います

なにせ,

A flip-flop accounts for 70 % of life

チューリング賞受賞者が言うほどです...1

こんな大事なものをなんとなく真理値表だけ見てわかった気にっている人は科学技術の恩恵に与ろうだなんて思う資格はありません!

即刻家に帰ってハードオフに電子機器を売って,電子炊飯器を使わずにご飯を炊いて,まずい飯を食いながら育ててくれた人と電子機器に感謝しなさい!

そもそもフリップフロップとは

フリップフロップ (flip-flop) は、二進法の基本である1ビットの情報を一時的に"0"または"1"の状態として保持する(記憶する)ことができる論理回路で、順序回路の基本要素である。 2

"ある"と"なし"という2つの状態を保持することができる論理回路のことですね!

これによって,レジスタ,メモリ,キャッシュなどが構成されているので考案してくれた先人に感謝!

突然LINEを消すやつ

質問です!

あなたは突然SNSのアカウントを消したことはありますか?

僕ですか?もちろんYES!

僕と似たようなフリップフロップRS型(Reset-Set型)フリップフロップです(SR型とも呼ばれます)

こいつは突然今まで保持していた値を消してしまうタイプのやべーやつ

もしこういう人と長く友達でいられる人間は将来どこかで損をしそうですが強く生きてほしいです

Delayのある俺の人生はもうおしまい

浪人(留年)で2年も人よりDelayしている?

引きこもって10年目?もう社会には復帰できないDelay?

僕ですか?もちろん浪人してます!Delayバンザイ!

そんな人よりも遅れちゃっていると感じちゃいがちなあなたにはD型(Delayed/Data型)フリップフロップ!

こいつは直前の信号を出力する心の優しいフリップフロップです

こんなに優しいフリップフロップばかりじゃないってことを社会に出て知ることになるのはまた別の話...

遷移

御託が長い

では具体的に遷移を眺めてみましょう

RS型

真理値表は次のとおりです

ちなみにS,Rは"Set","Reset"を表しています

Qはよくわかりませんがなんかそうなっています(誰か知っている人教えてください><)

S=1, R=1のときは動作が保証されていないので注意してください

S R Q_next
0 0 hold Q_old
0 1 0
1 0 1
1 1 prohibited

RS型フリップフロップ自体

どちらも0だと値が保持される

片方が0でもう片方が1のときは次のS(Set)の値になる

D型

真理値表は次の通りです

D,Cはそれぞれ"Data","Clock"を表しています

また,Cの"↑”,”↓”はそれぞれ1, 0のことです

D C Q_next
0 0
1 0
x hold Q_old

D型フリップフロップ自体

C=1(Clockが立ち上っているとき)

C=0(Clockが立ち下がっているとき)

こう見ると,D型フリップフロップは最終的にはSR型フリップフロップと同じ形になっていることがわかります

同じ働きをしているので当たり前(?)

まとめ

フリップフロップと同じ動きをする人間と関わらないと人生の7割,得をすることができます

ちなみにこの記事を書いたのは一応電気系なので電気系っぽいことも書こうかなという動機からでした

ではまた

難しく考えたら負けかなと思っている

難しく考えたら負けかなと思っている

tags: 情報

再帰関数難しく考えていないですか?

皆さんこんにちは.留学先でもピカチュウのTシャツを着て目立っていますピカチュウです(\not=不協和音)

どちらかと言ったらエキセントリック

東京は涼しいと聞いていますが,サンフランシスコの夏も一日の寒暖差が激しく上着が手放せません1 まぁそんなことはどうでもいいんですけど,今回は再帰関数に関して記事を書こうと思います

というのも,現地で再帰関数がよくわからない!というプログラミングを始めたての方がいるからです

教える前に記事にして一回まとめておこうというわけです

ゆるゆるに再帰関数の

  1. 再帰的定義(再帰関数は再帰関数で定義されている)
  2. 停止性(簡単になっているか,有限回で処理が終わるか)

を説明して,そこまで再帰関数が難しくないんじゃないかなと思ってもらえるような記事にしたいと思います

再帰的定義

再帰関数という名前の通り,再帰的定義を考えてみましょう

以下のPythonで書かれたコードを見てください

def fib(n)
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

ここで出てくるfibという関数は以下のように定義されたフィボナッチ数列の第n項を取り出すものです

$$ fib(n) = \begin{cases} 0 & (n=0) \\ 1 & (n=1) \\ fib(n-1) \cdot fib(n-2) & (otherwise) \end{cases} $$

fibという関数はfibという関数によって定義されていますね

これが再帰的定義で,自身で自身を定義していることが再帰関数の特徴です

そして,この再帰的定義は見てわかるように,最初の引数nを小さくしたn-1n-2が使われています

後で,このことを考えるので頭の片隅においておいてください

停止性

???「お前のものは俺のもの.俺のものも俺のもの」

これはおそらく日本で一番有名なトートロジー2が使われた文章ですね(論理学の文脈で使っているわけではないので悪しからず) 「これも再帰関数?」と考えられそうな気もしますが違います

そもそも関数じゃないというのもありますが,その最も大きな差は停止性の有無です

またPythonのコードを見てみましょう

def fib(n)
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

ここではif < 2という部分でしっかりと関数が終了する条件が書かれています.

再帰的定義によってfibの引数であるnが小さくなり,最終的にn < 2で終了する, つまり有限回でこの関数が終了するように定義されています

一方&ャイ%ンのセリフでは「お前のもの」が「俺のもの」にはなりますが,「俺のもの」の定義が「俺のもの」なので一生に定義が完了しません

再帰関数がどんな感じなのかわかってくれましたか?

原作を見たら意味が全く違っていた...

分割統治法

問題を分割し,解決することを分割統治法と言います

再帰関数は分割統治法を使った関数です(もちろん有限回でおわらないのも再帰関数ですが,ある問題を解く再帰関数は必ずこのようになっている必要があります)

実際に関数が再帰的に使え,停止性がはっきりしているような問題に対してに使ってましょう

文字列をひっくり返して実感

文字を反転させる...

いろいろやり方はあると思いますが,

def inv(str):
    if str == "":
        return ""
    else:
        return str[-1] + inv(str[:-1])

ここでは以下のように考えることで実装しています

  1. 再帰的定義:答えとなる文字列は<すでに反転された文字列> + <反転される文字列の最後の文字>と考えることができます
  2. 停止性:反転させる文字列は徐々に小さくなり,反転させる文字列がなくなったときにこの関数は終わります

このように考えると上のようなコードを簡単に書くことが可能です

(Pythonではstr[::-1]で文字列を反転することができます.あくまで例のためです)

実際に問題を解く

「具体例が少なすぎてわかりません!」と言う人,すみません!

そんな方におすすめなサイトにLeetCodeというものがあります

データ構造とアルゴリズムを勉強・実践するのにはぴったりなサイトでこのページ再帰関数に関する情報,問題がまとまっているので実際に手を動かして身につけたいという人は是非楽しんでください

再帰関数が簡単だと思えるようになってくれたら嬉しいです

再帰関数を難しく考えたら負けだと思っている

AtCoderテスト自動化スクリプト

tags: 情報

競プロのテストめんどくさいなぁ

以前makeを使った方法を書きましたがこれでもすべてのテストを調べるのは面倒

と思ったので調べたら次のような良いツールが有りました(AtCoder専用ですが)

競技プログラミングのための補助ツールを作った

AtCoderのテストができるツールを$ sudo pip3 install online-judge-toolsでインストールできるますよということが書いてあります

これをこのまま使うのも面倒なので,シェルスクリプトを探したところこの記事に当たりました

ただ,エイリアスの説明がなかったのと,このままだと自分の環境に使えなかったので次のようにエイリアスを設定し,書き換えたという話です

コード

.
|--abc
|   |- 133a.cpp
|
|--arc
|   |-001a.cpp
|
|--agc
    |-001a.cpp

ABCの際は次のように書いています

#!/bin/bash
problemname=$1
contest="abc"
oj dl "https://${contest}${problemname:0:3}.contest.atcoder.jp/tasks/${contest}${problemname:0:3}_${problemname:3}"
g++ -Wall -std=c++14 ./$1.cpp
oj test
rm -f a.out
rm -rf test

エイリアス~/.bashsrc

alias cptest="./cptest"

と書くだけ

実際に使ってみる

まずはcptest.shに権限を与えます

$ chmod 777 ./cptest.sh

実際のテストは次のように行います.非常に簡単です

$ cptest 133a

出力結果です

[x] GET: https://pypi.org/pypi/online-judge-tools/json
[x] 200 OK
[!] update available: 6.2.1 -> 6.5.0
[*] run: $ pip3 install -U online-judge-tools
[*] see: https://github.com/kmyk/online-judge-tools/blob/master/CHANGELOG.md
[x] problem recognized: AtCoderProblem.from_url('https://atcoder.jp/contests/abc133/tasks/abc133_a'): https://abc133.contest.atcoder.jp/tasks/abc133_a
[x] GET: https://atcoder.jp/contests/abc133/tasks/abc133_a
[x] 200 OK
[*] skipped due to language: current one is lang-ja, not lang-en: Sample Input 1 
[*] skipped due to language: current one is lang-ja, not lang-en: Sample Output 1 
[*] skipped due to language: current one is lang-ja, not lang-en: Sample Input 2 
[*] skipped due to language: current one is lang-ja, not lang-en: Sample Output 2 
[*] skipped due to language: current one is lang-ja, not lang-en: Sample Input 3 
[*] skipped due to language: current one is lang-ja, not lang-en: Sample Output 3 
[x] save cookie to: /Users/diohabara/Library/Application Support/online-judge-tools/cookie.jar
[x] append history to: /Users/diohabara/Library/Caches/online-judge-tools/download-history.jsonl

[*] sample 0
[x] input: sample-1
4 2 9

[+] saved to: test/sample-1.in
[x] output: sample-1
8

[+] saved to: test/sample-1.out

[*] sample 1
[x] input: sample-2
4 2 7

[+] saved to: test/sample-2.in
[x] output: sample-2
7

[+] saved to: test/sample-2.out

[*] sample 2
[x] input: sample-3
4 2 8

[+] saved to: test/sample-3.in
[x] output: sample-3
8

[+] saved to: test/sample-3.out
[!] update available: 6.2.1 -> 6.5.0
[*] run: $ pip3 install -U online-judge-tools
[*] see: https://github.com/kmyk/online-judge-tools/blob/master/CHANGELOG.md
[*] 3 cases found

[*] sample-1
[x] time: 0.009526 sec
[+] AC

[*] sample-2
[x] time: 0.008854 sec
[+] AC

[*] sample-3
[x] time: 0.008949 sec
[+] AC

[x] slowest: 0.009526 sec  (for sample-1)
[+] test success: 3 cases

ちなみに

同じ寮の人間が東大のミスターコンテストに出ているので是非投票してあげてください

"ENTRY 03 赤尾将希"と書いてある人です

https://mrcolle.com/tokyo2019/vote