Yabu.log

ITなどの雑記

ubuntu18.04で英字キーボード(101)キーボードを使う備忘録(主に日本語/英語切り替え)

日本語版ubuntuの英字キーボードのデフォルト設定に不満があったためカスタマイズしたかったが設定がわからりずらすぎて消耗したのでメモ

1.pkg-reconfigureでキーボードレイアウト設定

sudo dpkg-reconfigure keyboard-configurationで該当するキーボードを選択。

102を勧めているqiitaがあったけど、

qiita.com

Shiftとzキーの間になにかキーがあればそれは102キーボードだけど、多分そのキーがない101キーボードのほうが日本では一般的なのでそちらを選択する可能性のほうが高い。(手元のキーボードの配列を調べてあってるものを選んでください。)

2.言語設定からmozc(日本語)以外をすべて削除

設定>Region & Language のinput SourcesからEnglishを削除して「日本語(Mozc)」のみの状態にする

f:id:yuyubu:20190704172454p:plain
mozcいがい全部消す

3.mozcのツール>プロパティ>キー設定で「入力キー」hankaku/zenkakuのを切り替えに使いたいキーに入れ替える

キー設定の選択[MS-IME]は多分プリセットなので適当に自分が慣れているものを選びましょう。設定後は「カスタム」に変わるはずです。

f:id:yuyubu:20190704172939p:plain
プリセットは自分が好みのものを選ぼう

f:id:yuyubu:20190704172907p:plain
中段の4つを全部ctrol + spaceとかに入れ替える

f:id:yuyubu:20190704172535p:plain
mozcの設定の入り口は画面右上の方にある

上記手順完了のち、ログインし直して設定は完了。設定したキーで日本語英語切り替えできるようになっているはず。

Amazonで新品の本を注文したら表紙が一部破損しているものが届いた

ちょうどブログのネタになるかなと思ったので半年ほど前にあったことを書き残しておきます。

経緯

買った本はWeikum本ことトランザクションの本です。

kindle版を持っていたが、この本は「ここで以前説明したtheorem 5.4によると...」という感じでページを行ったり来たりするので紙の本もあると良いなと思って購入した。

ちなみにこの本のKindle版は固定PDFのような形になっておりフォントサイズが変えられないため、iPadだと読めるがパソコンだと文字が小さくてかなり読みづらい。

ですので一応紙の本も買ってみる事にした。

ちなみに現在電子版を買うならDRM FREEのPDFが変えるのでそっちがおすすめ*1

で、本が届くと表紙にヒビが入っていた。

f:id:yuyubu:20190130132748j:plain
表紙にヒビがはいってる

対処

この本はその重すぎる自重故に、持ち運んでいるとそのうちバラバラになってくるらしいが、そもそも最初から破れてるのはおかしいんじゃない?とのアドバイスをもらったので、一応クレームを出してみる事にした。

表紙がひび割れた状態で到着しました。新品のものを買った認識ですが、この件に関するサポートは受けられますか?

破損している商品の写真を求められたのでそちらをメールで送付した。輸送中の破損は仕方ないと思うので、売り手、買手で五分五分で手を打つのが筋なんじゃないないかと個人的に考えています。50%返金とかになるかな?

交渉

とりあえず、20%の返金で良いか?という提案がきた。なぜ20%?何を基準に?少し調べてみると、Amazonにはマーケットプレイス保証というものがある。

Amazon.co.jpのウェブサイトで出品者から商品を購入するお客様は、配送料を含めた購入総額のうち、最高300,000円まで保証されます。

www.amazon.co.jp

「返品ポリシー」に合致して返品を却下された場合、Amazonが30万円まで保証してくれるらしい。

調べる過程で見つけましたが、amazonのseller向けフォーラムというものの存在を知り、軽く巡回してみたが以下のことがわかった

https://sellercentral-japan.amazon.com/forums/

  • 返品に関しては購入者が有利になっている。

一応新品を買って破損していたので、返品に応じなければマーケットプレイス保証が使えるはず。 と言っても、返品は流石に可愛そうなので50%返金 or 交換の選択肢で交渉に挑んでみた。

20%は安すぎませんか。

ここは新品と交換が筋だと思いますが、時間がどれぐらいかかりますか?(また在庫的に可能でしょうか?)

交換が難しい場合は、50%返金でどうでしょうか。

結果

  • 再送(返品不要)

という事になった。50%返金 or 交換の選択肢でなぜ再送という判断になるんだろうか。 向こうの負担的には50%返金が一番ダメージ少ない気がするけど。 tx本の在庫処分に困っていたのだろうか。

なぜか我が家にはweikum本が3冊(normal + 破損 + kindle)あるという自体に... とりあえず会社と自宅に置いておく事にした

Transactionのinterpretation(herbrand semantics)について

herbrand semanticsのメモです。主にFSRを理解するための準備です。このエントリはChristos Papadimitrioupapa:Theory of Database Concurrency Control(通称papa本)の5~9ページのまとめです。

データベースの世界にはherbrand semanticsというConflictやSerializabilityを考える時に使う便利な道具があります。いつからherbrand semanticsと呼ばれるようになったのかはわかりませんが、papa本ではinterpretationという名前で扱われています。 近年ではトランザクションの教科書にもherbrand semanticsと書かれていることもありますので、本エントリではpapa本からの引用以外はこちらの名前を使います。

weikum本寄りの解説はぱとさんがあげているので、今回はpapa本寄りのメモを書きたいと思います。

taityo-diary.hatenablog.jp

Theory of Database Concurrency Control

Theory of Database Concurrency Control

transactionとreadとwrite

まずはトランザクションの定義から。トランザクションは任意のentityに対するreadとwriteの有限集合。

Difinition 1.1 A transaction A is a finite sequence fo steps A = a_1,a_2...a_n. The steps are assumed to be distinct symbols, and two differencttransactions cannot have steps in common. With each step a_j of A we associate an action ACTION(a_j) ∈ {W,R}, and an entity ENTITY(a_j) ∈ E.

read:対象entityの現在の値をプログラム中の変数へ割当てることを意味する。

If some step a_j reads entity x. This means that a particular program variable t_j in the underlying program is assigned the current value of x in the database: t_j := x.

write:対象entityに対するプログラムで計算した値の割り当てを意味する。

If ACTION(a_j) = W and ENTITY(a_j) = x , then the step write x. By this we mean that x is assigned a value computed by the program, which is potentially a function of all previously read(by the same program) values of entities: x := fj(t_i1,ti_2,...t_ik),where the ip's are all indices smaller than j for which ACTION(a_ip) = R

なおこのwriteで書く値の計算はwrite step以前のすべてのreadを引数にとる関数fとして定義することができる。この関数の厳密な定義がherbrand semanticsになる。

interpretation

条件分岐や繰り返しなどの制御構文を含むアプリ(プログラム)から発行されたdatabaseに対するread/writeのdatabase stepの意味をdatabase側から解釈する。プログラムが発行したdatabase stepのまとまりはtransactionになる。transactionは制御構文を持たないので、アプリとは別の解釈が必要となる。

A transaction, as defined above, is a purely syntactic object, subject to different interpretations. Intuitively, specifying an interpretation of a transaction means fixing a particular application program from which the transaction has originated, disregarding of course any control structure the program may have.

トランザクションの実行はある状態からある状態への写像と解釈する。

An interpretation of A(注:このAは任意のtransactionを指している) is a pair I = (D,F), where D = {D_x,D_y,...} is a set of domains, onefor each entity in E; each domain is a set of values for the corresponding entity. F = {f_a:a is a step of A and Action(a)=W} is a set of functions, one for each write step of A. For each such step a, f_a is a mapping

f_a: \prod_{x \in B(a)} D_x \to D_{ENTITY(a)}

  • writeのオペレーションはそれまでに読んだ値のドメインの直積からwrite対象のentityのドメインへの写像になる。
  • B(a)はa以前に読んだ全てのentityの集合。

B(a_j) = {x \in E : {\bf For \, some }\, i  \le j \, ACTION(a_i) = {\bf R \, and \, }ENTITY(a_i) = x}

具体例として1トランザクション前提(1並列)で以下の送金プログラムで説明されている。

program transfer(amt:integer);
    entities x,y: integer;
    variables temp1,temp2:integer;
    begin
    temp1 := x;
    if temp1 ≧ amt then
        begin
        x := tmp1 -amt; 
        temp2 := y;
        y := temp2 + amt
        end
    end.

ローカル変数へのentity代入をread,entityへの値の書き込みをwriteのデータベースステップと考えると上記のプログラムは以下のschedule(Action)を作る。

A = R(x)W(x)R(y)W(y)

この時、各database stepのherbrand semanticsは以下のようになる。

t1:=x
x:=f2(t1)
t3:=y
y:=f4(t1,t3)

f4の関数の内容はf4(t1,t3)=t3+50で、t1は一切使わないが、このt1はherbrand semanticsでは必要とする。 どのパラメータが実際に使われているかという情報はアプリ(DBMSを読み書きするプログラム)の完全な情報がないと分からない。そしてconncurency controlを考える時にアプリのコード全体が把握できるケースは極めて稀*1であるため、writeの前に発行されたreadは全てwriteを表す関数の引数として扱う。

Situations such as this of Example 1.2, in which we have complete information about the program and the value of their parameters, are rare in concurrency control

同じentityへの各database stepは1回まで

オペレーションごとにherbrand semanticsを考えることができそうだが、correctなスケジュールなら1つのentityへの複数回のread,writeは冗長なので、herbrand semanticsを考えるときは同じトランザクション内では

  • read/writeは1つのentityに対して1回まで
  • writeしたentityの値をreadしない

という前提を置く

It is quite natural-and, it turns out, simplifying-to make the following assumptions about the structure of the transactions.

(a)In a transaction an entity is read at most once, and is written at most once.

(b)In a transaction, no entity is read after it is written.

後述しますが、本来ならあるトランザクションの何番目のステップのfというような表記になるところを上記の前提を置くことで 、あるトランザクションのあるentityに対する操作(f)、またはあるトランザクションの何番目の操作(f)というシンタックスで表現できる。ちなみに、weikum本では前者のシンタックスを採用し、papa本では後者を採用している。*2

Hs(wi(x)) := fix(Hs(ri(y1)),...,Hs(ri(ym))), where the ri(yj), 1 ≤ j ≤ m, represent all read operations of ti that occur in s before wi(x)

weikum本より引用。f_{ix}のiをトランザクションの添え字、xをentityとするシンタックスにしている

Interpretationとshcedule

If s is a schedule involving the transactions A_1,...,A_k, then an interpretation I of s is a k-tuple of interpretations I_j = (D,F_j), all with the same choice D of domains for the entities.

scheduleにinterpretationを適応すると、schedule中の任意のdatabase stepをa_s(I,X)で表現することができる。

Suppose that s is a schedule, I an interpretation, and X an initial state, that is a value for each entity. We say that every database step a of s computes a value a_s(I,X).

また、スケジュールの実行結果、つまり最終状態をs(I,X)という特別なシンタックスで表現する

The final state resulting from the execution of s, denoted s(I,X)

まとめ

  • 各entityがとりうる値(domain)の集合をDとしている
  • writeの関数fのすべての集合をFとしている。
  • 上記二つのペアをinterpretation(herbrand semantics)としている。
    • interpretationと初期値Xを使うことでtransaction中の任意のstepを関数で表現できる

*1:ストアドは例外

*2:上記のプログラムのread/writeへのherbrand semanticsの適当を見ると、最初のwriteは2回目のオペレーションなのでf2となっている

Effecitve SQLを読書会で読み終わりました

全16回でした。毎度木村@meijikさんの博識ぶりには驚かされる勉強会でした。

Effective SQL

Effective SQL

プログラマSQLと比べると、中身が優しかったり、即効性がある情報が多いので、今すぐ役立つSQLテクニックを知りたい人にオススメです。逆にプログラマのためのSQLに出てきたような、長時間みんなで悩みながら「このクエリは何をやっているんだろう...」という難解なSQLは少ない傾向があったので、そういうのが好きな人には向かないかもしれません。

いかに個人的に面白いと思った本書の内容をまとめました。

CROSS JOIN

本書は1章丸ごとCROSS JOINに割いています。(第8章 直積)直積をまる一章説明している本は珍しいのではないでしょうか。気になった人はこの章だけでも通読をおすすめします。

「項目31 GROUP BYは短く保つ」

最近はgroup byに書いていないカラムもselect句に書いても良い 昔のMySQLの話ではない(ややこしい)

一部のDBMSでは、集約に使用されない列をGROUP BYに追加しなければならない。ただい、現在のSQL企画では、そうする必要はなくなっている

SQL/99以降では関数従属性が認識されている。したがって、現在のSQL木各区に準拠するには、実際には~のクエリで十分である

SELECT c.CustomerID, c.CustFirstName, c.CustLastName, c.CustState,
  MAX(o.OrderDate) AS LastOrderDate, COUNT(o.OrderNumber) AS OrderCount,
  SUM(o.OrderTotal) AS TotalAmount
FROM Customers AS c
LEFT JOIN Orders AS o
  ON c.CustomerID = o.CustomerID
GROUP BY c.CustomerID, c.CustFirstName, c.CustLastName, c.CustState;

以下のSQLではCustomersテーブルの主キーCustomerIDで集約しているため、CustomerテーブルのカラムはGroup byに書かなくてもSELECT句に書くことができます。

SELECT c.CustomerID, c.CustFirstName, c.CustLastName, c.CustState,
  MAX(o.OrderDate) AS LastOrderDate, COUNT(o.OrderNumber) AS OrderCount,
  SUM(o.OrderTotal) AS TotalAmount
FROM Customers AS c
LEFT JOIN Orders AS o
  ON c.CustomerID = o.CustomerID
GROUP BY c.CustomerID;

これがSQL99で標準化されているというのはちょっとした驚きでした。がこの本のクエリが全体的にこのGroup byの中を小さく保つ書き方がされていなかったのは少し気になりました。

あまり聞かない単語

挫折結合

LEFT JOINの適用後に右側のテーブルの主キーにnullをwhere句で指定すると、右側のテーブルに対応するデータがない左側のエンティティを絞り込むことができます。

SELECT P.ProductNumber, P.ProductName
FROM Products AS P LEFT JOIN Order_Details AS OD
  ON P.ProductNumber = OD.ProductNumber
WHERE OD.ProductNumber IS NULL;

これを挫折結合(frustrated join)というそうです。この単語はこの本で初めてみました。

sargable

出自はIBMのマニュアルのようです。意味としてはWhere句の中がB-tree indexを利用できるような述語になっているか、という意味になります。(そして本書にはSQLをsargableにするテクニックが多数紹介されています)

一般的でない誤字

order by 述語という誤字がよく出てきました。こちらは木村さんが原著を確認したところorder by predicateとなっていた(多分)ので誤訳ではなく、原著からの誤字だと思います。よくwhere文やcase文という間違い(SQLでは正しくはwhere句,case式)は結構みますが、order by述語という言い間違いは初めて見ました。わざわざ「述語」なんて言い方する人は、ある程度語句の使い方には注意しているのではないでしょうか。2019年6月時点で検索してみたら、SQLの文脈だと(order by述語)の使用例はこの本くらいでした。

参考

昔に背伸びして書いた記事です

qiita.com

次回

次回は曽根壮大さんの「失敗から学ぶRDBの正しい歩き方」を読むそうです。

失敗から学ぶRDBの正しい歩き方 (Software Design plus)

失敗から学ぶRDBの正しい歩き方 (Software Design plus)

同時並行で以下のものを読む計画があるそうです。

達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ (CodeZine BOOKS)

達人に学ぶSQL徹底指南書 第2版 初級者で終わりたくないあなたへ (CodeZine BOOKS)

SQLパフォーマンス詳解

SQLパフォーマンス詳解

  • A Critique of ANSI SQL Isolation Levels

okachimachiorz.hatenablog.com

tombo2.hatenablog.com

developer.hatenastaff.com

ギター初日感想

20台後半で初めてのギターです。rock smith 2014というギターを繋げて遊ぶ音ゲーが面白そうだったので、ギターと一緒に買ったところゲームの同梱品が不足したため、遊べなかったので色々調べて家で一人で練習していました。

ギターについて

  • 1万くらいのストラトというモデルのものをamazonで買った
  • メーカーとかモデルとかはまだよくわかっていない。
  • 本当はサイレントギターが欲しかった(形がかっこいいので)

ヤマハ YAMAHA サイレントギター ナチュラル SLG200S NT

ヤマハ YAMAHA サイレントギター ナチュラル SLG200S NT

  • とりあえず音はなる
  • 意外と重い
    • ストラップ的なのは買ってよかった。(重さが肩に分散する)
  • アンプとかは買わなくても部屋が静かならある程度音が出るので大丈夫そう?
    • ヘッドホンに繋げられるアンプは近所の店には置いてなかった
  • ギタースタンドが欲しい(床直置きで起こす時結構重いので)

チューニング

チューナーは実店舗でアマゾン(1600円)より安く変えました(1500円)

細い方から1弦,2弦...6弦まである

引く前に各弦の開放弦(何も抑えていない状態)の音程をチューナーを使って以下のものに合わせる

f:id:yuyubu:20190624192214j:plain
ノーマルチューニング
-

コード

同時に弦を抑えてハーモニー的なのを出すやつ

◯は開放弦の状態で鳴らす

f:id:yuyubu:20190624195823j:plain
C

f:id:yuyubu:20190624194035j:plain
Am

f:id:yuyubu:20190624201949j:plain
G

f:id:yuyubu:20190624201118j:plain
D

G⇨D⇨Cで曲っぽいものが弾ける

  • 基本的に弦は腹ではなく指先で押さえる
  • 結構握力がいる

形は覚えたが、押さえる指が関係ない弦に当たってうまく音が出ないのがほとんど。他の弦に触れずに一本だけ触るのは慣れもあるらしいので毎日ちょっとずつ頑張ります。

  • Fというのが鬼門らしいと聞く

基本的なコード(初心者が覚える順、押す場所、押す指、開放弦)がまとまってる本が欲しい...

NP問題における決定問題とはなにか

アルゴリズムの話をする際に良く出てくるPやNP、NP完全というものを一度きちんと勉強しておきたいと思いブログを書いていましたが、長くなりすぎたため4部作にしました(本記事はpart1)。本記事では下準備としてNP問題であるための条件「決定問題」というものの解説をします。学習には以下の本を使っています。

組合せ最適化 第2版 (理論とアルゴリズム)

組合せ最適化 第2版 (理論とアルゴリズム)

まずは決定問題が扱う「言語」という概念から説明します。

言語

計算量理論は大部分が決定問題に基づいている。実際、任意の言語L⊆{0,1}*は、決定問題,すなわち,与えられた0-1文字列がLに属するか(どうかを)決定する問題,と解釈できるからである。(p419)

言語とあるが、これは一般的な自然言語でもプログラミング言語の意味でもない。何らかのデータを符号化したものと考えられる。言語{0,1}*は何らかの011001011...と続く01の羅列、即ちバイナリであることを前提としている。 決定問題は上記の文通り、あるバイナリが言語Lに属するかどうかを決定する問題のこと。

決定問題の定義

決定問題(decision problem)は多項式時間で決定できる言語Xとその部分集合Y⊆Xの対P=(X,Y)として定義される。

注意)このP=(X,Y)のPは複雑性クラスのP,NPのPではありません。本中では斜体にして区別している。

ここで{0,1}* ⊇ X ⊇ Yという言語間の包含関係が成り立つ集合X,Yを定義。なお任意のバイナリが{0,1}* ⊇ Xであるかはどうかは多項式時間で決定できる必要がある*1。この事を組合せ最適化の本ではハミルトン閉路問題を例に説明している

全ての2新文字列がハミルトン閉路問題のインスタンスというわけではなく、無効グラフを表すものだけがそのインスタンスである。本書で扱うほとんどの興味深い決定問題において、インスタンスは0-1文字列集合の真部分集合である。任意の文字列が正しいインスタンスであるかどうかを多項式時間で決定できることが必要である。(p420)

インスタンス

言語Xの任意の元をインスタンスと呼ぶ。

Xの要素をPのインスタンスという

インスタンスは以下の2つのものに分類できる

Yの要素がyes-インスタンス

X/Yの要素がNo-インスタンス(p420)

補足:X/Yは集合XからYを引いた差集合のこと。

決定問題(X,Y)に対するアルゴリズム

x∈Yならばf(x)=1, x∈ X/Y ならばf(x)=0となる関数f:X→{0,1}を計算する(p420)

Xの任意の元がYに属しているかを判定するアルゴリズムのこと。

を変えてして問題の任意のインスタンスを判定できる必要がある。

証明検証アルゴリズム

P=(X,Y)に対してP'=(X',Y')という多項式時間で処理できる決定問題(証明検証アルゴリズム)を定義する。X'とY'は以下のように示される

X':={x#c: x∈X, c∈{0,1}[p(size(x))]}

Y = {y∈X:y#c∈Y'であるようなc∈{0,1}[p(size(y))]が存在する}

シンボル#,文字列cをこの順に連結した文字列を表す。(p421)

[p(size(x))]というシンタックスはxのサイズにしたがって多項式サイズで増えるという意味。[value]は床関数のシンタックスです

ja.wikipedia.org

決定アルゴリズムに対して、証明検証アルゴリズムは扱える問題のインスタンスはyes-インスタンスの処理のみで十分でありNo-インスタンスの検証を要求されないが、処理速度は多項式時間を要求される。決定アルゴリズムの時点で速度が十分ある(任意の問題を多項式時間で決定できる)場合は決定アルゴリズムをそのまま証明検証アルゴリズムに流用することができる。決定アルゴリズムを使った検証では#cが不要になる。

決定問題P=(X,Y)とPの証明検証問題P'=(X',Y')には以下の関係がある

  • X'は言語Xのインスタンスに何らかの文字列#cを追加したものを元にする集合
  • XとX'は濃度は一致するが、集合間には特に部分集合であるとかそういう関係はない。(YとY'間も同様)
  • Xの任意の元はX'の部分文字列になっている。x'=x + "#c" ただし(x'∈X,x∈X)
  • 証明検証アルゴリズムでxが、連結されている#cによってYに属しているかどうかを判定する。
  • cは証明(certificate)と呼ばれる

y#c∈Y'となるような文字列cは、(cによってy∈Yであることが証明されるので)yに対する証明(certificate)とも呼ばれる

  • 証明検証アルゴリズムではX'がY'に含まれるかを計算する。この時の計算量が多項式時間で表せるものがクラスNPに属する(詳細は別エントリで)

決定問題まとめ

で、上記適当に箇条書きにしたものを整理すると、以下のことがわかる。

  • 問題、とは日曜に使う数学の問題という意味ではなく、バイナリの集合と部分集合のペア(P=(X,Y))が定義できれば問題となる
  • 部分集合のペアと言語の閉包関係は以下のようになる。{0,1}* ⊇ X ⊇ Y
  • 決定問題では任意のバイナリが問題のインスタンスであるかは多項式時間で決定できる必要がある。
  • 言語Xとその部分集合Yを定義する。アルゴリズム(関数)を使ってXの元がYに属するかの判定を{1,0}への写像で表現する。
  • 言語の包含関係{0,1}* ⊇ X ⊇ Yで後半のX ⊇ Yの決定に必要な計算量でP,NPの分類を行う。

続く。

*1:なぜ言語がXの適切な元かどうかを多項式時間で決定できる必要があるのかは自分が当たった本には書かれていおらず、私自身も理解できていないのでもし知っていれば教えてください

別パーティションのWindowsで使ってぃるディスクをubuntuにmount

ubuntuwindowsパーティションを分けたディスクで運用しているのでその知見でも書きたいと思います。

ubuntuからwindows側のパーティションにあるファイルを見たい場合はdiskをマウントして閲覧することができます。

f:id:yuyubu:20190614150234p:plain
windowsubuntuが乘っているnvme

windowsが完全に終了していないからマウント出来ない?というエラーが出ましたが、これでとりあえず閲覧(read-only)できるようになりました。

まずはマウントポイントを作ります。

$ sudo mkdir /media/winf

mountコマンドでマウントします。

$ sudo mount -t ntfs-3g /dev/nvme0n1p4 /media/winf

以下の警告が出ました。

Windows is hibernated, refused to mount.
Falling back to read-only mount because the NTFS partition is in an
unsafe state. Please resume and shutdown Windows fully (no hibernation
or fast restarting.)

f:id:yuyubu:20190614151333p:plain
エクスプローラで認識できるようになった

参考

dacelo.space

本記事方法でマントした情報はrebootすると消えますので、半永久的にOSに認識させたい場合は以下の記事を参照して/etc/fstabを編集してください。

pocke.hatenablog.com