11月 « 2023 « shell-mag

香川大学SLPからお届け！（Vol.87掲載）

投稿日：2023.11.25　｜　カテゴリー：　コード

著者：大村空良

プログラミングにおいて重要な要素の一つが、プログラムの実行速度です。プログラムの実行速度は、より良いアルゴリズムを選択することで大きく改善できます。今回は、巡回セールスマン問題を解くC++プログラムを、アルゴリズムを変更して高速化した例を紹介します。

シェルスクリプトマガジン Vol.87は以下のリンク先でご購入できます。

図2　図1の巡回セールスマン問題を解くC++コード「sample1.cpp」

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n = 4, ans = 1e9-1, sum;
  int a[4][4] = {
    {0, 3, 7, 8},
    {3, 0, 4, 4},
    {7, 4, 0, 3},
    {8, 4, 3, 0}
  };
  vector<int> v_ans, v = {0, 1, 2, 3};
  do {
    //初期化
    sum = 0;
    //距離を足す
    for (int i = 1; i < n; i++) {
      sum += a[v[i-1]][v[i]];
    }
    sum += a[v[n-1]][v[0]];
    //比較
    if (ans > sum) {
      ans = sum;
      v_ans = v;
    }
  } while (next_permutation(v.begin(), v.end()));
//結果表示
  for_each(v_ans.begin(), v_ans.end(),
         [](int& item) { item++; });
  copy(v_ans.begin(), v_ans.end(),
       ostream_iterator<int>(cout, "→"));
  cout << v_ans[0] << endl;
  cout << ans << endl;
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

int main() {

int n = 4, ans = 1e9-1, sum;

int a[4][4] = {

{0, 3, 7, 8},

{3, 0, 4, 4},

{7, 4, 0, 3},

{8, 4, 3, 0}

};

vector<int> v_ans, v = {0, 1, 2, 3};

do {

//初期化

sum = 0;

//距離を足す

for (int i = 1; i < n; i++) {

sum += a[v[i-1]][v[i]];

}

sum += a[v[n-1]][v[0]];

//比較

if (ans > sum) {

ans = sum;

v_ans = v;

}

} while (next_permutation(v.begin(), v.end()));

//結果表示

for_each(v_ans.begin(), v_ans.end(),

[](int& item) { item++; });

copy(v_ans.begin(), v_ans.end(),

ostream_iterator<int>(cout, "→"));

cout << v_ans[0] << endl;

cout << ans << endl;

return 0;

}

図3　都市数を変えられるように図2のコードを拡張した「sample2.cpp」

#include <bits/stdc++.h>
#include "sales.h"
using namespace std;
int main() {
  int ans = 1e9-1, sum;
  vector<int> v_ans;
  do {
    sum = 0;
    for (int i = 1; i < n; i++) {
      sum += a[v[i-1]][v[i]];
    }
    sum += a[v[n-1]][v[0]];
    if (ans > sum) {
      ans = sum;
      v_ans = v;
    }
  } while (next_permutation(v.begin(), v.end()));
  for_each(v_ans.begin(), v_ans.end(),
           [](int& item) { item++; });
  copy(v_ans.begin(), v_ans.end(),
       ostream_iterator<int>(cout, "→"));
  cout << v_ans[0] << endl;
  cout << ans << endl;
  return 0;
}

#include <bits/stdc++.h>

#include "sales.h"

using namespace std;

int main() {

int ans = 1e9-1, sum;

vector<int> v_ans;

do {

sum = 0;

for (int i = 1; i < n; i++) {

sum += a[v[i-1]][v[i]];

}

sum += a[v[n-1]][v[0]];

if (ans > sum) {

ans = sum;

v_ans = v;

}

} while (next_permutation(v.begin(), v.end()));

for_each(v_ans.begin(), v_ans.end(),

[](int& item) { item++; });

copy(v_ans.begin(), v_ans.end(),

ostream_iterator<int>(cout, "→"));

cout << v_ans[0] << endl;

cout << ans << endl;

return 0;

}

図4　ヘッダーファイル生成用のPythonスクリプト「make_header.py」

import random
import sys

text = "dummy"
while not text.isdecimal():
  print("整数値を入力してください: ",
        file=sys.stderr, end='')
  text = input()
num = int(text)
if num > 15 or num < 1:
  sys.exit(1)
array = [[0] * num for i in range(num)]
random.seed()
for i in range(num):
  for j in range(num):
    if i != j:
      if array[j][i] != 0:
        array[i][j] = array[j][i]
      else:
        array[i][j] = random.randint(1, 9)
print('#include <vector>')
print('using namespace std;')
print(f'int n = {num};')
print(f'int a[{num}][{num}] = {{')
for i in range(num):
  line = str(array[i])[1:-1]
  print('{' + line + '},')
print('};')
line = list(range(0, num))
line = str(line)[1:-1]
print(f'vector<int> v = {{{line}}};')

import random

import sys

text = "dummy"

while not text.isdecimal():

print("整数値を入力してください: ",

file=sys.stderr, end='')

text = input()

num = int(text)

if num > 15 or num < 1:

sys.exit(1)

array = [[0] * num for i in range(num)]

random.seed()

for i in range(num):

for j in range(num):

if i != j:

if array[j][i] != 0:

array[i][j] = array[j][i]

else:

array[i][j] = random.randint(1, 9)

print('#include <vector>')

print('using namespace std;')

print(f'int n = {num};')

print(f'int a[{num}][{num}] = {{')

for i in range(num):

line = str(array[i])[1:-1]

print('{' + line + '},')

print('};')

line = list(range(0, num))

line = str(line)[1:-1]

print(f'vector<int> v = {{{line}}};')

図5　フィボナッチ数を求めるC++コード「sample3.cpp」

#include <bits/stdc++.h>
using namespace std;
unsigned long long fib(char n) {
  if ((n <= 0) || (n > 93)) return 0;
  if (n == 1) return 1;
  return fib(n - 1) + fib(n - 2);
}
int main() {
  char n = 5;
  cout << fib(n) << endl;
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

unsigned long long fib(char n) {

if ((n <= 0) || (n > 93)) return 0;

if (n == 1) return 1;

return fib(n - 1) + fib(n - 2);

}

int main() {

char n = 5;

cout << fib(n) << endl;

return 0;

}

図7　動的計画法を用いて改良したコード「sample4.cpp」

#include <bits/stdc++.h>
using namespace std;
unsigned long long fib(char n) {
  if ((n <= 0) || (n > 93)) return 0;
  if (n == 1) return 1;
  unsigned long long f[128];
  f[0] = 0;
  f[1] = 1;
  for (char i = 2; i <= n; i++) {
    f[i] = f[i - 1] + f[i - 2];
  }
  return f[n];
}
int main() {
  char n = 5;
  cout << fib(n) << endl;
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

unsigned long long fib(char n) {

if ((n <= 0) || (n > 93)) return 0;

if (n == 1) return 1;

unsigned long long f[128];

f[0] = 0;

f[1] = 1;

for (char i = 2; i <= n; i++) {

f[i] = f[i - 1] + f[i - 2];

}

return f[n];

}

int main() {

char n = 5;

cout << fib(n) << endl;

return 0;

}

図10　動的計画法を用いて改良したコード「sample5.cpp」

#include <bits/stdc++.h>
#include "sales.h"
using namespace std;
int main() {
  int dp[(1<<n)][n];
  for (int i = 0; i < (1<<n); i++) {
    for (int j = 0; j < n; j++) {
      dp[i][j] = 1e9-1;
    }
  }
  dp[0][0] = 0;
  for (int i = 0; i < (1<<n); i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        if (i==0 || !(i & (1<<k)) && (i & (1<<j))) {
          if( j != k ) {
            dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k],
                                    dp[i][j] + a[j][k]);
          }
        }
      }
    }
  }
  cout << dp[(1<<n) - 1][0] << endl;
  return 0;
}

#include <bits/stdc++.h>

#include "sales.h"

using namespace std;

int main() {

int dp[(1<<n)][n];

for (int i = 0; i < (1<<n); i++) {

for (int j = 0; j < n; j++) {

dp[i][j] = 1e9-1;

}

dp[0][0] = 0;

for (int i = 0; i < (1<<n); i++) {

for (int j = 0; j < n; j++) {

for (int k = 0; k < n; k++) {

if (i==0 || !(i & (1<<k)) && (i & (1<<j))) {

if( j != k ) {

dp[i | (1<<k)][k] = min(dp[i | (1<<k)][k],

dp[i][j] + a[j][k]);

}

cout << dp[(1<<n) - 1][0] << endl;

return 0;

}

Pythonあれこれ（Vol.87掲載）

投稿日：2023.11.25　｜　カテゴリー：　コード

著者：飯尾淳

本連載では「Pythonを昔から使っているものの、それほど使いこなしてはいない」という筆者が、いろいろな日常業務をPythonで処理することで、立派な「蛇使い」に育つことを目指します。その過程を温かく見守ってください。皆さんと共に勉強していきましょう。第17回では、データを記録して残す「永続化」の手法の続編として、O/Rマッパーを使ってデータベースにアクセスする方法について解説します。

シェルスクリプトマガジン Vol.87は以下のリンク先でご購入できます。

図3　宣言的マッピングをするコード

from typing import List
from typing import Optional
from sqlalchemy import ForeignKey
from sqlalchemy import String
from sqlalchemy.orm import DeclarativeBase
from sqlalchemy.orm import Mapped
from sqlalchemy.orm import mapped_column
from sqlalchemy.orm import relationship

class Base(DeclarativeBase):
  pass

class User(Base):
  __tablename__ = "user_account"
  id: Mapped[int] = mapped_column(primary_key=True)
  name: Mapped[str] = mapped_column(String(30))
  fullname: Mapped[Optional[str]]
  addresses: Mapped[List["Address"]] = relationship(
    back_populates="user", cascade="all, delete-orphan"
  )
  def __repr__(self) -> str:
    return f"User(id={self.id!r},\
name={self.name!r}, fullname={self.fullname!r})"

class Address(Base):
  __tablename__ = "address"
  id: Mapped[int] = mapped_column(primary_key=True)
  email_address: Mapped[str]
  user_id: Mapped[int] = mapped_column(ForeignKey("user_account.id"))
  user: Mapped["User"] = relationship(back_populates="addresses")
  def __repr__(self) -> str:
    return f"Address(id={self.id!r},\
email_address={self.email_address!r})"

from typing import List

from typing import Optional

from sqlalchemy import ForeignKey

from sqlalchemy import String

from sqlalchemy.orm import DeclarativeBase

from sqlalchemy.orm import Mapped

from sqlalchemy.orm import mapped_column

from sqlalchemy.orm import relationship

class Base(DeclarativeBase):

pass

class User(Base):

__tablename__ = "user_account"

id: Mapped[int] = mapped_column(primary_key=True)

name: Mapped[str] = mapped_column(String(30))

fullname: Mapped[Optional[str]]

addresses: Mapped[List["Address"]] = relationship(

back_populates="user", cascade="all, delete-orphan"

)

def __repr__(self) -> str:

return f"User(id={self.id!r},\

name={self.name!r}, fullname={self.fullname!r})"

class Address(Base):

__tablename__ = "address"

id: Mapped[int] = mapped_column(primary_key=True)

email_address: Mapped[str]

user_id: Mapped[int] = mapped_column(ForeignKey("user_account.id"))

user: Mapped["User"] = relationship(back_populates="addresses")

def __repr__(self) -> str:

return f"Address(id={self.id!r},\

email_address={self.email_address!r})"

図4　データベースエンジンとなるオブジェクトを作成するコード

from sqlalchemy import create_engine
engine = create_engine("sqlite:///a_db.sqlite3", echo=True)

1 2	from sqlalchemy import create_engine engine = create_engine("sqlite:///a_db.sqlite3", echo=True)

図5　発行されるSQL

CREATE TABLE user_account (
	id INTEGER NOT NULL, 
	name VARCHAR(30) NOT NULL, 
	fullname VARCHAR, 
	PRIMARY KEY (id)
)
CREATE TABLE address (
	id INTEGER NOT NULL, 
	email_address VARCHAR NOT NULL, 
	user_id INTEGER NOT NULL, 
	PRIMARY KEY (id), 
	FOREIGN KEY(user_id) REFERENCES user_account (id)
)

CREATE TABLE user_account (

id INTEGER NOT NULL,

name VARCHAR(30) NOT NULL,

fullname VARCHAR,

PRIMARY KEY (id)

)

CREATE TABLE address (

id INTEGER NOT NULL,

email_address VARCHAR NOT NULL,

user_id INTEGER NOT NULL,

PRIMARY KEY (id),

FOREIGN KEY(user_id) REFERENCES user_account (id)

)

図6　データ操作用オブジェクトを作成するコード

from sqlalchemy.orm import Session

with Session(engine) as session:
  spongebob = User(
    name="spongebob",
    fullname="Spongebob Squarepants",
    addresses=[Address(email_address="spongebob@sqlalchemy.org")],
  )
  sandy = User(
    name="sandy",
    fullname="Sandy Cheeks",
    addresses=[
      Address(email_address="sandy@sqlalchemy.org"),
      Address(email_address="sandy@squirrelpower.org"),
    ],
  )
  patrick = User(name="patrick", fullname="Patrick Star")
  session.add_all([spongebob, sandy, patrick])
  session.commit()

from sqlalchemy.orm import Session

with Session(engine) as session:

spongebob = User(

name="spongebob",

fullname="Spongebob Squarepants",

addresses=[Address(email_address="spongebob@sqlalchemy.org")],

)

sandy = User(

name="sandy",

fullname="Sandy Cheeks",

addresses=[

Address(email_address="sandy@sqlalchemy.org"),

Address(email_address="sandy@squirrelpower.org"),

)

patrick = User(name="patrick", fullname="Patrick Star")

session.add_all([spongebob, sandy, patrick])

session.commit()

図7　図6のコードを実行した際の画面出力（抜粋）

BEGIN (implicit)
INSERT INTO user_account (name, fullname) VALUES (?, ?) RETURNING id
（略）('spongebob', 'Spongebob Squarepants')
INSERT INTO user_account (name, fullname) VALUES (?, ?) RETURNING id
（略）('sandy', 'Sandy Cheeks')
INSERT INTO user_account (name, fullname) VALUES (?, ?) RETURNING id
（略）('patrick', 'Patrick Star')
INSERT INTO address (email_address, user_id) VALUES (?, ?) RETURNING id
（略）('spongebob@sqlalchemy.org', 1)
INSERT INTO address (email_address, user_id) VALUES (?, ?) RETURNING id
（略）('sandy@sqlalchemy.org', 2)
INSERT INTO address (email_address, user_id) VALUES (?, ?) RETURNING id
（略）('sandy@squirrelpower.org', 2)
COMMIT

BEGIN (implicit)

INSERT INTO user_account (name, fullname) VALUES (?, ?) RETURNING id

（略）('spongebob', 'Spongebob Squarepants')

INSERT INTO user_account (name, fullname) VALUES (?, ?) RETURNING id

（略）('sandy', 'Sandy Cheeks')

INSERT INTO user_account (name, fullname) VALUES (?, ?) RETURNING id

（略）('patrick', 'Patrick Star')

INSERT INTO address (email_address, user_id) VALUES (?, ?) RETURNING id

（略）('spongebob@sqlalchemy.org', 1)

INSERT INTO address (email_address, user_id) VALUES (?, ?) RETURNING id

（略）('sandy@sqlalchemy.org', 2)

INSERT INTO address (email_address, user_id) VALUES (?, ?) RETURNING id

（略）('sandy@squirrelpower.org', 2)

COMMIT

図8　簡単な検索をするコード

from sqlalchemy.orm import Session
from sqlalchemy import select

session = Session(engine)
stmt = select(User).where(User.name.in_(["spongebob", "sandy"]))
for user in session.scalars(stmt):
  print(user)

from sqlalchemy.orm import Session

from sqlalchemy import select

session = Session(engine)

stmt = select(User).where(User.name.in_(["spongebob", "sandy"]))

for user in session.scalars(stmt):

print(user)

図9　図8のコードを実行した際に発行されるSQL

BEGIN (implicit)
SELECT user_account.id, user_account.name, user_account.fullname
FROM user_account
WHERE user_account.name IN (?, ?)
（略） ('spongebob', 'sandy')

BEGIN (implicit)

SELECT user_account.id, user_account.name, user_account.fullname

FROM user_account

WHERE user_account.name IN (?, ?)

（略） ('spongebob', 'sandy')

図10　図8のコードを実行した際に表示される検索結果

User(id=1, name='spongebob', fullname='Spongebob Squarepants')
User(id=2, name='sandy', fullname='Sandy Cheeks')

1 2	User(id=1, name='spongebob', fullname='Spongebob Squarepants') User(id=2, name='sandy', fullname='Sandy Cheeks')

図11　少し複雑な検索をするコード

stmt = (
  select(Address)
  .join(Address.user)
  .where(User.name == "sandy")
  .where(Address.email_address == "sandy@sqlalchemy.org")
)
sandy_address = session.scalars(stmt).one()

stmt = (

select(Address)

.join(Address.user)

.where(User.name == "sandy")

.where(Address.email_address == "sandy@sqlalchemy.org")

)

sandy_address = session.scalars(stmt).one()

図12　図11のコードを実行した際に発行されるSQL

SELECT address.id, address.email_address, address.user_id
FROM address JOIN user_account ON user_account.id = address.user_id
WHERE user_account.name = ? AND address.email_address = ?
（略） ('sandy', 'sandy@sqlalchemy.org')

SELECT address.id, address.email_address, address.user_id

FROM address JOIN user_account ON user_account.id = address.user_id

WHERE user_account.name = ? AND address.email_address = ?

（略） ('sandy', 'sandy@sqlalchemy.org')

図13　データ変更のシンプルなコード例

sandy_address.email_address = "sandy_cheeks@sqlalchemy.org"
session.commit()

1 2	sandy_address.email_address = "sandy_cheeks@sqlalchemy.org" session.commit()

図14　図13のコードを実行した際に発行されるSQL

UPDATE address SET email_address=? WHERE address.id = ?
（略）('sandy_cheeks@sqlalchemy.org', 2)
COMMIT

UPDATE address SET email_address=? WHERE address.id = ?

（略）('sandy_cheeks@sqlalchemy.org', 2)

COMMIT

図15　データ変更の少し複雑なコード例

stmt = select(User).where(User.name == "patrick")
patrick = session.scalars(stmt).one()
patrick.addresses \
.append(Address(email_address="patrickstar@sqlalchemy.org"))
session.commit()

stmt = select(User).where(User.name == "patrick")

patrick = session.scalars(stmt).one()

patrick.addresses \

.append(Address(email_address="patrickstar@sqlalchemy.org"))

session.commit()

図16　図15のコードを実行した際に発行されるSQL


SELECT user_account.id, user_account.name, user_account.fullname
FROM user_account
WHERE user_account.name = ?
（略）('patrick',) 
　
SELECT address.id AS address_id, address.email_address
  AS address_email_address, address.user_id AS address_user_id 
FROM address 
WHERE ? = address.user_id
（略）(3,)
　
INSERT INTO address (email_address, user_id) VALUES (?, ?)
（略）('patrickstar@sqlalchemy.org', 3)
COMMIT

SELECT user_account.id, user_account.name, user_account.fullname

FROM user_account

WHERE user_account.name = ?

（略）('patrick',)

SELECT address.id AS address_id, address.email_address

AS address_email_address, address.user_id AS address_user_id

FROM address

WHERE ? = address.user_id

（略）(3,)

INSERT INTO address (email_address, user_id) VALUES (?, ?)

（略）('patrickstar@sqlalchemy.org', 3)

COMMIT

004　レポート　Raspberry Pi 5が登場
005　レポート　キーボード「HHKB Studio」が発売
006　製品レビュー　小型パソコン「X68000 Z PRODUCT EDITION BLACK MODEL」
007　NEWS FLASH
008　特集1　ゆっくりMovieMaker4で映像制作編集作業編/ふる（FuruyamD）
014　特集2　電子帳簿保存法を知る/永禮啓大
021　Hello Nogyo!
022　特別企画　アプリバで業務システム開発/前佛雅人
032　Raspberry Pi Pico W/WHで始める電子工作/米田聡
035　行動経済学と心理学で円滑に業務を遂行/請園正敏
038　Pythonあれこれ/飯尾淳　コード掲載
044　法林浩之のFIGHTING TALKS/法林浩之
046　中小企業手作りIT化奮戦記/菅雄一　コード掲載
052　エコシステム/桑原滝弥、イケヤシロウ
054　香川大学SLPからお届け！/大村空良
060　タイ語から分かる現地生活/つじみき
066　ユニケージ通信/ぱぺぽ
070　Linux定番エディタ入門/大津真
076　Techパズル/gori.sh
077　コラム「ユニケージが実現・目指しているところ」/シェル魔人

Vol.87

投稿日：2023.11.25　｜　カテゴリー：　バックナンバー

　特集1は、動画投稿・共有サイト「YouTube」で人気の「ゆっくり実況」「ゆっくり解説」を作成できる無料動画編集ソフト「ゆっくりMovieMaker4」の第2弾です。今回は、以前の特集で設定したキャラクタや、字幕が動く動画の編集作業を紹介します。
　特集2は、2023年12月末に宥恕（ゆうじょ）措置が廃止となる電子帳簿保存法（電帳法）です。2023年10月から開始されたインボイス制度を含めて、企業が対応しなければならない法制度が増えています。電帳法への対応は今からでも間に合います。本特集を読んで2024年1月からの義務化を乗り越えてください。
　特別企画では、さくらインターネットが提供する、ノーコードによるモバイルアプリ開発および配備環境のクラウドサービス「アプリバ」を紹介します。サイボウスの「kintone」（キントーン）など、プログラミングの知識がない人でも業務アプリを開発できるノーコード開発が注目されています。アプリバは1カ月無料で試せるので、本企画を読んでノーコード開発を体験してみましょう。
　このほか、レポートではコンパクトキーボードの新版「HHKB Studio」、製品レビューではパソコン「X68000」を復刻した小型パソコン「X68000 Z PRODUCT EDITION BLACK MODEL」といった話題の新製品を紹介しています。
　今回も読み応え十分のシェルスクリプトマガジン Vol.87。お見逃しなく!

※記事掲載のコードはこちら。記事の補足情報はこちら

※読者アンケートはこちら

Vol.87 補足情報

投稿日：2023.11.25　｜　カテゴリー：　コード

訂正・補足情報はありません。
情報は随時更新致します。

shell-mag ブログの 2023年11月のアーカイブを表示しています。

-->

シェルスクリプトマガジン

香川大学SLPからお届け！（Vol.87掲載）

Pythonあれこれ（Vol.87掲載）

シェルスクリプトマガジンvol.87 Web掲載記事まとめ

Vol.87

Vol.87 補足情報

固定ページ

アーカイブ

カテゴリー