みま

満員電車つらい

GormでDB(MySQL)を操作してみた

Gormとは

gorm.io
Golang用のORMライブラリで、DBの操作を簡単に行うことが出来る。

環境

macOS 10.14.5
Golang ver 1.13.5 darwin/amd64
mysql ver 8.0.19

事前準備

$ cd $GOPATH/src
$ mkdir gorm-test
$ cd gorm-test
$ touch gorm.go

gormパッケージをインストール

go get github.com/jinzhu/gorm

実装

gorm.goを何かしらのエディタで開き、以下のように記述

package main

import (
	"fmt"

	"github.com/jinzhu/gorm"
	_ "github.com/jinzhu/gorm/dialects/mysql"
)

type ImplDB struct {
	DB *gorm.DB
}

type User struct {
	UserID   uint   `gorm:"primary_key;auto_increment:false"`
	UserName string `gorm:"size:255"`
}

func (i *ImplDB) initDB() {
	var err error
	// USER、PASS、DBNMEなどは各自設定してある値を記述
	DBMS := "mysql"
	USER := "root"
	PASS := "password"
	PROTOCOL := "tcp(localhost:3306)"
	DBNAME := "sample"

	CONNECT := USER + ":" + PASS + "@" + PROTOCOL + "/" + DBNAME + "?charset=utf8&parseTime=True&loc=Local"
	i.DB, err = gorm.Open(DBMS, CONNECT)

	if err != nil {
		panic("DBへの接続に失敗しました")
	}
}

// スキーマのマイグレーション
func (i *ImplDB) initMigration() {
	i.DB.AutoMigrate(&User{})
}

func main() {
	i := &ImplDB{}

	// DBに接続
	i.initDB()

	// main関数が終わる際にDBの接続を切る
	defer i.DB.Close()

	// スキーマのマイグレーション
	i.initMigration()

	insertUser := User{}
	user := User{}
	user2 := User{}

	insertUser.UserID = 1
	insertUser.UserName = "hoge"

	// 作成
	// INSERT INTO users(user_id,user_name) VALUES(1,'hoge');
	i.DB.Create(&insertUser)

	// 取得
	// SELECT * FROM users WHERE user_id = 1;
	i.DB.Find(&user, "user_id = ?", 1)

	fmt.Println("取得したuserの値は", user)

	// 更新
	// UPDATE users SET user_name = 'fuga' WHERE user_id = 1 and user_name = 'hoge';
	i.DB.Model(&user).Update("user_name", "fuga")

	fmt.Println("更新後のuser:", user)

	// 削除
	// DELETE FROM users WHERE user_id = 1 and user_name = 'hoge';
	i.DB.Delete(&user)

	if err := i.DB.Find(&user2, "user_id = ?", 1).Error; err != nil {
		// エラーハンドリング
		fmt.Println("存在しませんでした")
	} else {
		fmt.Println("取得したuserの値は", user2)
	}
}
// スキーマのマイグレーション
func (i *ImplDB) initMigration() {
	i.DB.AutoMigrate(&User{})
}

ここではUserの構造体とDBのスキーマを比較して、不足しているカラムなどを追加。
またusersテーブルがない場合はusersテーブルを作成。
AutoMigrate()メソッドの引数にはアドレスを渡す。他のメソッド( Create()やFirst() など )も値ではなくアドレスを渡すのでそこは注意したい。

そして実行

$ go run hello.go
取得したuserの値は {1 hoge}
更新後のuser: {1 fuga}
存在しませんでした

で簡単にDB操作を行うことが出来た。
ちなみに上記の操作を一個の処理単位として行いたい場合はTransactionというものを使えば良いらしい。
gorm.io
以上、Gormの紹介でした。

EchoでWebサーバを立てる

Echoとは

echo.labstack.com
EchoはGolangの軽量Webフレームワークです。
REST API向けに最適化されたフレームワークであり、拡張性が高く、カスタマイズが容易という特徴があります。
今回、EchoでWebサーバをEchoを立てていきます。

事前準備

Golangの環境設定は省略

$ cd $GOPATH/src
$ mkdir hello
$ cd hello
$ touch hello.go

echoパッケージをインストール

$ go get -u github.com/labstack/echo/…

実装

hello.goを何かしらのエディタで開き、以下のように記述

package main

import (
    "net/http"

    "github.com/labstack/echo"
)

func main() {
    // ルーティングのためのインスタンスを生成
    e := echo.New()

    // ルーティング
    e.GET("/", func(c echo.Context) error {
        return c.String(http.StatusOK, "Hello World")
    })

    // ポート番号を指定して、サーバ起動
    e.Logger.Fatal(e.Start(":1323"))
}

サーバを起動

$ go run hello.go
別タブのターミナル上でリクエストを投げる
$ curl -s -X GET \
  --url 'localhost:1323'
Hello World

これでHello Worldという文字列が返ってきました。

次にJSON形式のものを返すようにします。
先程のmainの上に構造体のコードを記述。

// Userの構造体
type User struct {
  UserID       uint   `json:"user_id"`
  FirstName string `json:"first_name"`
  LastName  string `json:"last_name"`
}

そしてmain関数の中に以下を記述

// JSON形式でUser情報を返す
e.GET("/json", func(c echo.Context) error {
	jsonUser := User{
		UserID:        1,
		FirstName: "hoge",
		LastName:  "fuga",
	}
	return c.JSON(http.StatusOK, jsonUser)
})

最終的にhello.go全体の内容は以下のようになります。

package main

import (
	"net/http"

	"github.com/labstack/echo"
)

 // Userの構造体
type User struct {
  UserID        uint   `json:"user_id"`
  FirstName string `json:"first_name"`
  LastName  string `json:"last_name"`
}

func main() {
	// ルーティングのためのインスタンスを生成
	e := echo.New()

	// ルーティング
	e.GET("/", func(c echo.Context) error {
		return c.String(http.StatusOK, "Hello World")
	})

        // JSON形式でUser情報を返す
	e.GET("/json", func(c echo.Context) error {
		jsonUser := User{
			UserID:        1,
			FirstName: "hoge",
			LastName:  "fuga",
		}
	     return c.JSON(http.StatusOK, jsonUser)
	})

	 // ポート番号を指定して、サーバ起動
	e.Logger.Fatal(e.Start(":1323"))
}

そして起動

$ go run hello.go
別タブのターミナル上でリクエストを投げる
$ curl -s -X GET \
  --url 'localhost:1323/json'
{"user_id":1,"first_name":"hoge","last_name":"fuga"}

これでUser情報がJSON形式で返ってきました。
ただ、これだと1行でズラーっと表示されるので、より見栄えの良い表示をしてくれるjqコマンドというものを使ってJSON形式のものを整形して表示します。
stedolan.github.io

$ curl -s -X GET \
  --url 'localhost:1323/json' | jq
{
  "user_id": 1,
  "first_name": "hoge",
  "last_name": "fuga"
}

これで見栄えの良いJSONが返ってきました。

最後に

Echoで簡単にWebサーバを立てることが出来ました。
Echo以外にもGinやirisといった軽量Webフレームワーク、RevelやBeegoといったフルスタックWebフレームワークなどがあるので、そっちもやっていきたい。

ラズパイで自宅サーバを構築した

自宅サーバとは?

以下のサイトに丁寧に説明されてた。
自宅サーバーとは?
 今回はファイルサーバ機能とキャッシング機能を実装する事に。
 ファイルサーバ機能では同一ネットワーク上のあらゆるデバイスでファイル共有が可能なストレージを設ける事が出来る。
 キャッシング機能では通信量の軽減と高速化を図る事が出来る。

事前準備

ラズパイにsshログインが可能
以上

ファイルサーバ「Samba」の設定

最新パッケージの取得
$ sudo apt-get update
Sambaをインストール
$ sudo apt-get install samba
編集前にバックアップ
$ sudo cp /etc/samba/smb.conf /etc/samba/smb_tmp.conf
Sambaの設定ファイルを編集
$ sudo vi /etc/samba/smb.conf

以下を追加

#interfaces = 127.0.0.0/8 eth0 を
interfaces = [ラズパイのIP] 127.0.0.0/8 eth0 #に変更
security = user #を追加
#[]内に任意の名前
[raspi]
#共有の概要
comment = File Share
#共有するディレクトリのパス
path = home/tanaka/share
#パスワード認証なしで接続を許可
guest ok = Yes
#書き込みを許可
read only = no
#パーミッションの設定
create mask = 755

ufwファイアウォールの設定

fromの後はラズパイのプレフィックス表記
$ sudo ufw allow from 192.168.100.0/24 to any port 445
ファイアウォールを再読み込み
$ sudo /etc/init.d/ufw restart
Sambaを再読み込み
$ sudo /etc/init.d/samba restart

PC(Mac)から接続

Finderを開きCommand-Kを押すと「サーバへ接続」と出るのでそこにsmb://[ラズパイのIP]を入力する
f:id:mimaken:20171025195823p:plain
ゲストを選択して接続
f:id:mimaken:20171025200815p:plain
OKを選択
f:id:mimaken:20171025200823p:plain
これでMacから接続できるようになる

携帯(iPhone)から接続

iphoneからのアクセスには無料版のこのアプリを使用した
FileExplorer: File Manager

FileExplorer: File Manager

  • Skyjos Co., Ltd.
  • 仕事効率化
  • 無料
最初の画面で+を押し、上から3番目のLinux/Unixを押す
その後ホスト名/IPアドレス、ポート番号、ユーザー名とパスワードを入力し保存
f:id:mimaken:20171025201706p:plain:w300
接続で登録したIPアドレスを押す
f:id:mimaken:20171025204412p:plain:w300
f:id:mimaken:20171025201637p:plain:w300
これでiphoneからも接続できるようになった

キャッシングの設定

以下の記事を参考にした。
qiita.com
squidのインストール
$ sudo qpt-get install squid
編集前にバックアップ
$ sudo cp /etc/squid/squid.conf /etc/squid/squid_tmp.conf
設定ファイルを編集
$ sudo vi /etc/squid/squid.conf

# 最下行に追加
# デフォルトのポート8080を変更。
http_port 49492

acl myacl src [ラズパイのIP]/[ラズパイのサブネットマスク]
http_access allow myacl
http_access deny all

# プロキシサーバーを使用している端末のローカルIPアドレスを隠蔽化
# 相手のWebサーバにIPアドレスを知らせない
forwarded_for off

# プロキシ経由でアクセスしていることをアクセス先に知られないようにする
# クライアント及びプロキシ情報を隠蔽する
header_access X-Forwarded-For deny all
header_access Via deny all
header_access Cache-Control deny all

# ログフォーマットの設定
# access_log /var/log/squid/access.log squid
logformat combined %>a %03>Hs %rm %mt %ru
access_log /var/log/squid/access.log combined

ufwファイアウォールの設定

#fromの後はラズパイのプレフィックス表記
$ sudo ufw allow from 192.168.100.0/24 to any port 49492
ファイアウォールを再読み込み
$ sudo /etc/init.d/ufw restart
squidを再読み込み
$ sudo /etc/init.d/squid restart

締め

 ラズパイは様々な用途に使えるので是非とも一度は使ってみた方がいいと思う。またラズパイで電子工作をやってみるのも全然ありだし個人的には監視カメラとかが面白そう。
 いつか時間ある時にWebサーバやハニーポットとかもやってみない。そしてそれを機にWeb技術やネットワークまわりの知識もつけたいと思う(思うだけ)

ラズパイでセキュアを意識したSSH接続の設定をした

 久々の投稿。今回はみんな大好きラズベリーパイでセキュアを意識したssh接続の設定をやってみた。
 ラズパイとは関係ないが昨日WPA2の脆弱性が発表された。Wi-Fiで最も安全性が高いと言われていた認証方式なだけにネット上でも衝撃が走っていた。
 通称KRACKs(key reinstallation attacks : 鍵再インストール攻撃)と呼ばれAESなどの暗号解読によってパスワードが読み取られるという訳ではなく暗号化された通信の内容を覗かれたり、攻撃コードを埋め込んだり、不正サイトに誘導されるらしい。怖い話です。

ラズパイ側の設定

さて本題に
まずIPアドレスを固定
ルーターDHCPサーバ機能によってIPアドレスを動的に振り分けるため、ラズパイ側のIPアドレスは何度も変わってしまうため、IPアドレスを固定。
$ sudo vi /etc/network/interfaces

# interfaces(5) file used by ifup(8) and ifdown(8)
# Include files from /etc/network/interfaces.d:
 source-directory /etc/network/interfaces.d
 
   # The loopback network interface
   auto lo
   iface lo inet loopback
  
  auto wlan0
  iface wlan0 inet static   // "dhcp""static"に変更
  address 192.168.100.40   // 設定したいラズパイの固定IPアドレス
  netmask 255.255.255.0   // サブネットマスク
  gateway 192.168.100.1    // ルータのIPアドレス
  dns-nameservers 192.168.100.1  // ルータのアドレス

と書いたら
$ sudo /etc/ini.d/networking start
でネットワークサービスを起動
ちなみに編集して再起動したいときは
$ sudo /etc/init.d/networking restart
止めたいときは
$ sudo /etc/init.d/networking stop
OpenSSHをラズパイ側で利用するためのパッケージをインストール
$ sudo apt-get install openssh-server

続いて
$ sudo vi /etc/ssh/sshd_config

//もともと書いてある
Port 22
//を22番以外の数字に変更
//49513~65535の間が基本的に無難
Port 615625

rootログインを非許可にする
PermitRootLogin no //yesをnoに
// ラズパイのUbuntu MATEで
// 最初から記述してある
// PermitRootLogin widhout-password
// だとなぜかエラーが出た

// パスワード認証によるログインを非許可
PasswordAuthentication  no //yesをnoに

$ sudo /etc/init.d/ssh start
サービスを起動

クライアント(mac)側の設定

OpenSSHをクライアントで利用するためのパッケージをインストール
$ brew install openssh-client
鍵ファイルの作成
$ ssh-keygen -t rsa
$ cd .ssh
$ vi config

Host [ラズパイ側のエイリアス名前(何でも良い)]
    HostName 192.168.100.40 // ラズパイのIPアドレス
    User [クライアント側のユーザ名]
    Port 615625
    IdentityFile ~/.ssh/id_rsa
#以下の場合180秒ごとにサーバ(ラズパイ)にメッセージを送り、ServerAliveCountMax のデフォルト回数である 3回応答しなくなったらタイムアウトする
ServerAliveInterval 180

$ chmod 700 ~/.ssh
$ chmod 600 ~/.ssh/[鍵ファイルの作成でつけた名前].pub
$ chmod 600 ~/.ssh/[鍵ファイルの作成でつけた名前]

公開鍵をラズパイに転送
$ rsync -e "ssh -p 615625" -avz ~/.ssh/id_rsa.pub [ラズパイ側のユーザ名]@192.168.100.40:~/.ssh

ラズパイ側の設定

$ mv ~/.ssh/[鍵ファイルの作成でつけた名前].pub ~/.ssh/authorized_keys
$ chmod 600 ~/.ssh/authorized_keys
$ sudo /etc/init.d/ssh start

2このようにすれば本来
$ ssh ユーザ名@ホスト名 -p ポート番号
と打ち込むのを
$ ssh ユーザ名
でパスワードを入力せずにパスワード認証方式より安全な公開鍵暗号方式ssh接続できるようになる

最後に

ufwファイアウォールの設定を行う
ufwをインストール
$ sudo apt install ufw

同一ネットワーク内からのみのfromで指定したアドレスからtoで指定したアドレスかつポートへの通信を受信する
$ sudo ufw allow from 192.168.100.0/24 to any port 615625

ufwの設定を読み込み
$ sudo ufw enable
$ sudo /etc/init.d/ufw start

これで完成

最近VimでEscキーが遠いと感じた話

 最近まで僕はVimを使ってる時、他のエディタを使う時の様なキーボードとマウスを使う煩わしさが拮抗することなく使えてる事に感動していた。しかしキーボードだけで使っている時「Escキーが遠い。。」と感じてきた。
 基本的に両手はホームポジションにあるため手のひらの手根?の場所はCommandキーや十字キーの下に配置している。普通に文字など入力している時は手を固定して入力できるのだがVimでモードを変更する際(Visualモード、もしくはInsertモードからNormalモードに切り替える時)Escキーを押さないといけないのだが、左手を固定したままだとEscキーまでやや届かない。最初は特に気にも留めなかったが使っているうちにだんだん面倒だと感じてきた。なので.vimrcにEscキーのキーマッピングを割り当てたコードを追加した。

""""""""""""""""追加""""""""""""""""""
inoremap <C-z> <Esc>
vnoremap <C-z> <Esc>

ついでに連打でハイライト解除の箇所にも追加した

" Esc連打でハイライト解除
nmap <Esc><Esc> :nohlsearch<CR><Esc>
""""""""""""""""追加""""""""""""""""""
"C-z連打でも解除するよう追加
nmap <C-z><C-z> :nohlsearch<CR><Esc>

 本来C-zはシェルのジョブコントロール機能で、一時的に、ターミナルを使うために処理を中断させるもの。僕はC-zを使わないので両手をホームポジションに固定したままC-zでEsc処理を行えるようになった。

 ただそれだけの話でした。

ソートアルゴリズムの速度比較

ソートアルゴリズムについて

 大小関係が定められたたくさんのデータを、小さい順(昇順)あるいは大きい順(降順)に並べ替える作業をソート(整列)と言い、それを行うアルゴリズムをソートアルゴリズムと言います。 この処理は、さまざまなプログラムの中で頻繁に使われ、それ故、古くからいろいろなアルゴリズムが考案されてきました。

参考文献:いろいろなソートアルゴリズム

動機

 ソートの勉強を調べていたらソートアルゴリズムがたくさんあることに少しだけ疑問があった。
 なぜなら数字などを順番に並び変えるのにソートアルゴリズムなんて一つで十分ではないのか?と思ったという素朴な疑問。
 一つ一つ調べると、どのソートが効率が良く、どのソートが効率が悪いなど色々あることが分かったのですが、どれが良くてどれが悪いかを知るだけじゃいまいち物足りない気のするので実装してみようと思いつきました。
 その中で代表的なものの中の5つのソートアルゴリズムの速度を比較したいと思います。(ちなみに昇順に並べるコード)

測定するアルゴリズム

  • まず1つ目はソートと聞いて自分がパッと思いついた"バブルソート"です。これは比較的短いコードで書け、簡単なアルゴリズムですがソートアルゴリズムの中でもかなり効率の悪いアルゴリズムで、計算量はO(n^2)。
  • 2つ目は先ほどのバブルソートの改良版の"シェーカーソート"というもので、計算量はO(n^2)。
  • 3つ目はシェーカーソートよりは速いがクイックソートよりは遅い"挿入ソート"で、計算量はO(n^2)。
  • 4つ目はソートの中でも高速とされる"クイックソート"で、計算量はO(nlogn)。
  • 5つ目はC++のライブラリである"標準ソートです"。

測定コード

#include<iostream>
#include<vector>
#include<algorithm>
#include<stdlib.h>
#include<time.h>
#include<iomanip>

//  バブルソート関数
void Buble_Sort(int x[], int n);
//  シェーカーソート関数
void Shaker_Sort(int x[], int n);
//  挿入ソート関数
void Insertion_Sort(int [], int );
//  クイックソート関数
void Quick_Sort(int list[], int left, int right);

using namespace std;

int main(void){

  int i;
  // 異なる乱数の入った配列を保持する一時的に作った配列
  int *Temporary_Array;
  // それぞれのソート用のポインタ配列
  int *Buble_Array,*Shaker_Array,*Insertion_Array,*Quick_Array;
  int Array_Size;

  // 標準ソートで使う動的配列クラス
  vector<int> v;

  cout << "データサイズを入力してください : ";
  cin >> Array_Size;
  // それぞれの配列のメモリの動的確保
  Temporary_Array = new int[Array_Size];
  Buble_Array = new int[Array_Size];
  Shaker_Array = new int[Array_Size];
  Insertion_Array = new int[Array_Size];
  Quick_Array = new int[Array_Size];

  // 異なる乱数の生成
  srand((unsigned)time(NULL));
  for(i = 0;i < Array_Size;i++){  
    Temporary_Array[i] = rand();
    v.push_back(rand());
  }

  /* 異なる乱数の入った配列をバブルソートを行う配列に代入 */
  for(i = 0;i < Array_Size;i++)
    Buble_Array[i] = Temporary_Array[i];

  /* 異なる乱数の入った配列をシェーカーソートを行う配列に代入 */
  for(i = 0;i < Array_Size;i++)
    Shaker_Array[i] = Temporary_Array[i];

  /* 異なる乱数の入った配列を挿入ソートを行う配列に代入 */
  for(i = 0;i < Array_Size;i++)
    Insertion_Array[i] = Temporary_Array[i];

  /* 異なる乱数の入った配列をクイックソートを行う配列に代入 */
  for(i = 0;i < Array_Size;i++)
    Quick_Array[i] = Temporary_Array[i];
//  メモリを解放
  delete[] Temporary_Array;

  /* バブルソート計測開始 */
  clock_t Start_Buble_Sort = clock();
  Buble_Sort(Buble_Array,Array_Size);
  /* バブルソート計測終了 */
  clock_t End_Buble_Sort = clock();
  delete[] Buble_Array;

  /* シェーカーソート計測開始 */
  clock_t Start_Shaker_Sort = clock();
  Shaker_Sort(Shaker_Array,Array_Size);
  /* シェーカーソート計測終了 */
  clock_t End_Shaker_Sort = clock();
  delete[] Shaker_Array;

  /* 挿入ソート計測開始 */
  clock_t Start_Insertion_Sort = clock();
  Insertion_Sort(Insertion_Array,Array_Size);
  /* 挿入ソート計測終了 */
  clock_t End_Insertion_Sort = clock();
  delete[] Insertion_Array;

  /* クイックソート計測開始 */
  clock_t Start_Quick_Sort = clock();
  Quick_Sort(Quick_Array, 0, Array_Size-1);
  /* クイックソート計測終了 */
  clock_t End_Quick_Sort = clock();
  delete[] Quick_Array;

  // 標準ソート計測開始
  clock_t Standard_Start = clock();
  sort(v.begin(),v.end());
  // 標準ソート計測終了
  clock_t Standard_End = clock();

  cout << "・バブルソートによる実装時間は     " << fixed <<  setprecision(7) <<  (double)(End_Buble_Sort - Start_Buble_Sort)  / CLOCKS_PER_SEC << "秒" << endl;
  cout << "・シェーカーソートによる実装時間は " << fixed <<  setprecision(7) <<  (double)(End_Shaker_Sort - Start_Shaker_Sort)  / CLOCKS_PER_SEC << "秒" << endl;
  cout << "・挿入ソートによる実装時間は       " << fixed <<  setprecision(7) <<  (double)(End_Insertion_Sort - Start_Insertion_Sort)  / CLOCKS_PER_SEC << "秒" << endl;
  cout << "・クイックソートによる実装時間は   " << fixed <<  setprecision(7) <<  (double)(End_Quick_Sort - Start_Quick_Sort)  / CLOCKS_PER_SEC << "秒" << endl;
  cout << "・標準ソートによる実装時間は       " << fixed <<  setprecision(7) <<  (double)(Standard_End - Standard_Start)  / CLOCKS_PER_SEC << "秒" << endl;

  return 0;
}

/*  バブルソート */
void Buble_Sort(int x[], int n)
{
  int i, j, tmp;
  for (i = 0; i < n - 1; i++) {
    for (j = n - 1; j > i; j--) {
      if (x[j - 1] > x[j]) {  
        tmp = x[j];        
        x[j] = x[j - 1];
        x[j - 1]= tmp;
      }
    }	
  }
}

/*  挿入ソート */
void Insertion_Sort(int x[], int N){
  int i,j,v;
  for(i = 1;i < N;i++){
    v = x[i];
    j = i - 1;
    while(j >= 0 && x[j] > v){
      x[j + 1] = x[j];
      j--;
    }
    x[j + 1] = v;
  }
}

/*  シェーカーソート */
void Shaker_Sort(int x[], int N){
  int right, left, work, shift;
  int i, j;
  right = N - 1; left = 0;
  while(right > left){
    for(i = left; i < right; i++){
      if(x[i] > x[i + 1]){
        work = x[i];
        x[i] = x[i + 1];
        x[i + 1] = work;
        shift = i;
      }
    }
    right = shift;
    for(i = right; i > left; i--){
      if(x[i] < x[i - 1] ){
        work = x[i];
        x[i] = x[i - 1];
        x[i - 1] = work;
        shift = i;
      }
    }
    left = shift;
  }
}

/*  クイックソート */
void Quick_Sort(int list[], int left, int right){
  int i, last;
  int tmp;

  if (left >= right)
    return;
  last = left;
  for (i = left + 1; i <= right;i++){
    if (list[i] < list[left]){
      last++;
      tmp = list[last];
      list[last] = list[i];
      list[i] = tmp;
    }
  }
  tmp = list[left];
  list[left] = list[last];
  list[last] = tmp;

  Quick_Sort(list,left,last-1);
  Quick_Sort(list,last+1,right);
}

ちょっと雑な感じになってしまいましたがとりあえずこんな感じに書きました。

言語は先ほどちらっと言った、標準ライブラリのvectorを使うためC++です。C++は去年の学校の授業で触って以来全くやっていなかったので書くのに多少苦労もあった。。

ちなみにソートアルゴリズムは主にこちらの本を参考にした。

実装

f:id:mimaken:20170716103623p:plain

コンパイルを行いsortという実行ファイルを生成

f:id:mimaken:20170716103631p:plain

./sortで実行するとデータ数を入力するよう促される。試しに12345といったデータサイズの値を入力。そうすると各ソートの実装時間が表示される。
データサイズを1から10億をそれぞれ10回測定しそれらの平均の時間を調べた。

結果

結果は以下の表にまとめた。
f:id:mimaken:20170611015329p:plain
 空白の箇所はあまりにも時間がかかるため断念したところです。
 データサイズが少ないと一般的に速いとされているクイックソートや標準ライブラリによるソートが他のより若干遅いことがわかりました。
 ただデータサイズが大きくなるにつれやはり高速と呼ばれるクイックソートと標準ソートは100万まではデータサイズが小さい時とあまり変わらない速度でソートしてます。
 10億といった値だとなんと標準ソートの速度がクイックソートの半分といった結果でやはりライブラリは強い(確信)
 要するに

  • 高速なソートはデータ数が少ないとO(n^2)より遅い。
  • データサイズによってソートを使い分けるのは大事。

  • まさしくこのbotの言う通りである()

    どっち派?target=”_blank” or ”target=_new"

    タブの仕組み

     サイトにあるリンクなどをクリックすると同じタブに置き換わって表示されたり新しいタブが出てそこに表示されたりと色々な表示の仕方がある。それはaタグの中のtarget="何か"で制御されます。
     今回は新しいタブに表示される2通り仕組みを紹介します。

    blankとnewの説明

    f:id:mimaken:20170622150303p:plain
  • target="_blank"について
     target="_blank"は何枠でも出てきます
     例えばリンクを10回クリックすれば10つの新しいタブが出てきます。

  • target="_new"について
     target="_new"はblankとは違いリンクを何度クリックしても新しいタブは一つしか出てきません。そこに置き換わって表示されていきます。
     自分の知ってるサイトで有名なサイトですとyahoo画像なんかはtarget="_new"になっています。
     個人的にyahoo画像のサイトでその仕様ですと正直不便な気もしますが。。

    検証

  • target="_blank"の場合

  • Google & Yahoo

  • target="_new"の場合

  • Google & Yahoo


     ちなみに僕はtarget="_blank"派です。
     僕は新しいタブを開くことに対してあまり抵抗はなくいつもそのようにしてネットサーフィンを楽しんでます。
    要するに「_blank」の方に慣れているからです。大した理由はないです。。

    最後に

     皆さんはどちら派でしたか。
     ちなみに毎回別のタブを開くのことは「戻る」ボタンが使えなくなるので、前の画面に戻れなくなったり、さらにタスクバーがごちゃごちゃになるという混乱を招いてしまうことがあり、それらによって別のタブで開くことは極力避けた方が良いという意見が多々あるようです。
     またChrome拡張機能で、別タブで開く「_blank」を無効化して無視するのがあるらしくそれほど「_blank」は嫌われてる?
     こう言った意見を考慮すると「_new」の方が良いのかなと思ったり思わなかったり。