ノイズとアートの間にはどんな関係があるのか

目次

はじめに

 こんにちは、アンです。

 最近、私の博士前期の研究テーマやタイトルについて悩んでいます。社会や他者からの「ノイズ(騒音)」が私たち人間に及ばす影響に興味があります。その影響に対する人間の脳の反応に着目し、ジェネラティブアートの制作を研究したいです。そこで、ノイズとアートに関連性がある概念や事例を調べました。

ノイズとは

 ノイズの概念は、分野によって違います。情報処理の分野では、ノイズは処理対象となる情報以外の不要な情報のことです。一方、日常生活のノイズは、日本騒音制御工学会によると、ノイズあるいは騒音、雑音とは、身の周りの様々な音のうち、人に好ましくない影響を及ぼす音、不必要な音、邪魔な音を指します[1]。しかし、ノイズ(騒音)は主観的な概念として定義されています。つまり、音の印象は聞く人とその人の状態によって大きく左右されます。ある人にとっては、快い音楽であっても、別の人には騒音になりかねません。たとえば、電車やバスのなかで隣の人のヘッドフォンから漏れた音などがそうです。さらに、ノイズ(騒音)は聞く人にとっての個人的問題であるばかりでなく、聞く人が属する社会や文化にも関わっています[2]。つまり、ある音がノイズかどうかを判断する基準は、主観的な基準であり、同時に、社会的あるいは文化的な基準でもあります。

ノイズとアート

 ノイズは、それぞれの分野で定義が違います。しかし、必ず不要、邪魔、余計などの意味を含んだ定義がされています。つまり、どんな分野においても、ノイズは良くないものです。

 一方、アートまたは芸術とは、作品の創作と鑑賞によって精神の充実体験を追求する文化活動を指します。精神の充実体験として、アートは人間に良い影響を与えるといえます。

 このように意義が対立している二つの概念には、密な関係があります。音楽、ジェネラティブアートの二つの分野で、ノイズとアートの関連性を検討します。

  • ノイズと音楽(ノイズ・ミュージック)

 もともと、音楽美学の分野では、音楽にふさわしい音、ふさわしくない音の区別を研究されていました。たとえば、ジゼール・ブルレは、「楽音」と「騒音」を対比させて以下のように論じます。「騒音は私たちを世界へとつなぎとめるが、音楽は私たちを世界から解放してくる。騒音は動揺を引き起こすのに対して、楽音は安らぎを与える」[2]。しかし、イタリア未来派ルイージルッソロがノイズに美的な価値を見出しました[3]。そのさい『騒音の芸術(The Art of Noises)』という宣言を発表しました。自動車のエンジン音など日常生活のなかでのノイズ(騒音)は抽象的な素材となり、音楽の作品が作られます。ルッソロはノイズを用いた表現と電子音楽の先駆者と考えられています。

  • ノイズとジェネラティブアート

    3D Noise_colorful(https://openprocessing.org/sketch/1609947)
     ジェネラティブアートとは何かを前回のブログで紹介しました。私の場合は、p5.js、processing、glslなどのプログラミング言語を使ってジェネラティブアートの表現を研究しています。これから、p5.jsを使用して作れた例を挙げながら、ジェネラティブアートでのノイズを紹介します。

     p5.jsでのnoise関数とperlin noise 

     p5.jsのnoise関数の説明によれば、noise()関数は指定された座標での パーリンノイズ(Perlin noise)値、あるいはランダムの値を返します。random() 関数と比較すると、より自然な順序で調和のとれた一連の数値を生成するランダムシーケンスジェネレータです。パーリンノイズは、1980年代にKen Perlinによって発明され、手続き型のテクスチャ、自然な動き、形状、地形などを生成するためにグラフィカルアプリケーションで使用されています。

     パーリンノイズは、無限のn次元空間で定義されます。p5.jsには、指定された座標の数に応じて、1D、2D、および3Dノイズを計算できます。結果の値は常に0.0 から 1.0 の間になります[4]。

     p5.jsで、一次元のnoise(x)、二次元のnoise(x, y)と三次元のnoise(x, y, z)それぞれを使って1D、2D、3Dの例(下の図)を作りました。

    noise関数の例(左から右までは1D2D3Dの表現)

    池田亮司と《test pattern》

     池田亮司は、日本の電子音楽実験音楽のミュージシャン、現代美術作家として知られています[5]。超音波、周波数、そして音そのものの持つ本質的な特性の細部に徹底してこだわる池田の作品は、音の物理的特性や人間の知覚との因果関係、音楽としての数学的類推、時間、空間を活用する[6]といわれています。2008年から、代表的なシリーズ制作の《test pattern》が始まりました。《test pattern》は、あらゆる種類のデータ(テキスト、サウンド、写真、映画)を2つの形式「バーコード」と「0/1バイナリー」に変換するシステムです。下の写真は、2017年の「test pattern [nº13]」です。

    「test pattern [nº13]」(photo: Martin Argyroglo)[7]
     私の感想

     シリーズ作品の《test pattern》は、私にとってはじめて理解できた池田の作品であり、また一番印象的な作品でもあると思います。《test pattern》では、ノイズのような実験的な音楽と、白黒のパターンが長年試行錯誤されています。音の持つ本質的な特性を細部まで検討、音だけではなく画像や映像のノイズに活用していることを池田の作品から学びました。

さいごに

 今回はノイズの定義、音楽とジェネラティブアートの分野でのノイズについての概念を簡潔に紹介しました。同時に、池田亮司の代表作とそれに対する私の感想を書きました。私のこれからの研究と制作に参考にしたいと思います。

参考文献

ISUCON12に参加します!

はじめに

こんにちは,光岡です.2本目の記事になります.

前回はGo言語を使ったソートアルゴリズムに関して書き,今回も当初はアルゴリズム関連の予定でした.しかし2本目にして早速路線変更することにしました.(綺麗なシリーズ化はできそうにないので,アルゴリズムを学んで,また書きたくなったら書こうと思います..)

今月何があったかな..と振り返った時に思い出したのが,

"無事に"ISUCON12の参加登録ができた!

ってことですかね.

ISUCONとは?については後述しますが,3回あった申し込みのうち,1回目は2分44秒で220枠が埋まってしまい,2回目で無事に参加登録できました.ちなみに2回目は1分10秒で予約215枠が埋まったそうです💦

まるで,有名なアーティストのライブチケットの争奪戦のようでした...

ということで,今回はISUCONについて,その中でも先日の事前講習座学&ハンズオンにも参加してきたので,座学で学んだことについて書いていこうと思います.

ISUCONとは

ISUCONとは,お題となるWebサービスを決められたレギュレーション内で,高速化を行いその点数を競う大会になります. ISUCONの名称は,Iikanjini(いい感じに)SpeedUp Contest から取られています.この名称の由来を聞いたら緩そうな大会に感じるかもしれませんが,中身はガチな大会となっています.

年一回で行われており,1チーム3人まで,最近は約600チームが参加しています.有名企業がスポンサーを務め,予選大会で上位30チームまで絞られ,本戦で優勝したチームには賞金100万円です!前述しましたが,今年のISUCONはまず参加するのが一苦労でした. つまり,Webエンジニアにとってはロマンあふれる大会ということですね!

私は去年初めて参加しましたが,正直な感想は難しすぎて何が何だか分からないっていうのが本音でした.結局SQLの最適化・インデックスを貼ったぐらいで全然戦力になりませんでした. ということで,今年もチャレンジです!

事前講習座学編の学び

事前講習座学編の資料に関しては,既に公開されているため,気になる方は下記を見てみてください!

isucon.net

今回の記事では,本当に一部を抜粋して書いています.

「やっていいこと」は明言されていない

ISUCONはレギュレーションに禁止事項がしっかりと書かれており,開始直後にまずそのルールを確認することがとても大事です.反対にやっていいことに関しては,特に制限がありません.挙動が変わらず,禁止事項に触れていなければ基本的には何をやっても大丈夫です.3台のサーバーが渡されますが,役割も自由です.ある年ではサーバー2台をDBにあてることで良いパフォーマンスが出ることもあったそうで,その時々のお題のサービスの特徴を掴んで対応する力が必要になります.

ISUCONではクライアント以降全てが対象領域

ISUCONでは,対象となる技術領域がとにかく広いです.サーバーもEC2が渡されるため,OS等の知識がもちろん必要です.最近はECSばかり触れていた自分は楽をしていたなという気持ちにさせられます笑.そしてnginxからアプリケーションコード,RDB,KVS,Cacheなどてんこ盛りです.その分学びもたくさんあり楽しいですが..

デプロイに1分以上かけない

改善した内容を反映するデプロイは,脳死でできるように準備しておきましょう.改善して負荷試験をしてログを見て次の改善ポイントを探す一連の流れが制限時間内で何回行えるかが大事になります.そのため繰り返し行う手順はとにかく素早く行えるように準備しておこうとのことでした.

ISUCONから学べること:世界中にクライアントが増えていく

座学も面白かったのですが,個人的にその後の,「世界中にクライアントが増えていく」というお話がとても興味深かったです. IoT化が進み,いつか日本世帯全ての炊飯器が通信すると5000万台がサーバーに,「ご飯が炊けましたよ」の時代が来るかもねというお話でした.この大量の通知でサーバーが死ぬかもしれません.こういった時代が来るのであれば,性能改善の重要性はますます高まります.危機的なお話ですが,ワクワクしながら聞いてました!将来そういった部分も担当したいなと思ったり..

さいごに

だいぶかいつまんで書いてしまいましたが,ISUCONの雰囲気が少し分かる感じならいいかなと思います.まだまだ2回目のISUCON初心者なので,予選までに練習を重ね,色々知見を深めたいなと思います.

Bluetoothの活用法を調べてみた

はじめに

はじめまして、及川です。今回は、Bluetoothのさまざまな使用例についてまとめたいと思います。Bluetoothと聞くと、イヤホンやマウス、キーボードの無線接続が思い浮かびますが、他にどのような使用方法があるのか気になったので調べてみました。今回は、普段目にしないところまで手を伸ばして、Bluetoothの使用例を見ていきたいと思います。

そもそもBluetoothとは

Bluetoothとは

毎日使っているBluetoothについて、基本情報を確認してみます。デジタル大辞泉によると、Bluetoothは以下のようにまとめられています。

スマートホン、パソコンの周辺装置などの無線接続に用いられる通信規格。ケーブルを使わずにデータの送受信や機器の連携が可能となる。

Bluetoothとは何? わかりやすく解説 Weblio辞書

ぼんやりと持っていたイメージと同じでした。 無線接続と聞くと一番に思い浮かぶのはWi-Fiですが、Bluetoothならではの特徴はどのようなものがあるのでしょうか。

Bluetoothの特徴

Bluetoothの特徴
・省電力
・近距離(~10m程度)
・そこそこ速い通信速度
・音楽系に強い
・パーソナルユースの機器に強い

【サルでもわかるBLE入門】(1) BLEの基礎 - 株式会社ムセンコネクト

Bluetoothは、Wi-Fiよりもはるかに消費電力が小さいことが最大の特徴です。
通信距離も通信速度もWi-Fiより小さいのですが、消費電力が小さい点を最大限に活用した使用用途が多いようです。

Bluetoothで何ができるのか

では、実際にBluetoothを使用してどのようなことができるようになったのでしょうか。

イヤホン・ヘッドフォンをワイヤレス接続

イヤホン・ヘッドフォンに関しては特に意外ではありませんね。多くの方が普段から使用しています。

バイス間でのデータ共有

バイス間のデータ共有とは、AppleユーザにはおなじみのAirDropなどが該当します。パソコンとスマートフォン間でデータを簡単に移動できたり、友人同士で簡単に写真の共有ができたりして、データの共有が簡単に行えます。

テザリング

スマートフォンルーター化して他の端末でインターネットを使用するテザリングにもBluetoothが使われています。筆者もカフェで作業する際などにもっぱら活用しています。

ここまでは、日常生活に溶け込んでいるBluetoothの活用法でした。
次項目からは、別の視点の活用方法や研究を見ていきましょう。

健康管理

ヘルスケアで有名なタニタは、Bluetoothを活用した体重計が発売されています。
これは、体組成計で取得したデータをBluetoothを通してスマートフォンに送信し、専用のアプリケーションを活用することで健康を管理しやすくしています。 自身で記録を取るのと比べると、労力が減るのはもちろん、いつでもどこでも確認することができます。
また、データがあれば、見やすいグラフなどへの転換が容易に行え、視覚的に健康を管理できます。

接触確認アプリCOCOA

Covid-19が流行しはじめてから注目されたのが接触確認アプリCOCOAです。
このアプリもBluetoothを活用しています。 ユーザのスマートフォンから電波を発信し、周囲の人のスマートホンと互いにデータを保存することで接触確認を行なっています。
消費電力が少ないことを最大限に活用しています。

AED設置場所への屋内誘導アプリ

AED設置場所への屋内誘導アプリでは、Bluetoothを活用することで、スマートフォン操作者とAEDとの距離や方向を計算し、AED設置場所へ誘導してくれます。
普段行き慣れていない場所で、もしもの時に役に立つアプリケーションです。
(野口ら 2020)

屋内避難におけるスマートフォンへの画面通知

屋内避難におけるスマートフォンへの画面通知は、先ほどのAEDの例と少々似ていますが、逆の使い方をしています。
Bluetoothを活用し、災害時に立ち入りが危険な場所に近づくと通知がくるという仕組みです。
災害が多い日本において、このような活用が是非広がってほしいと思います。
(濱田ら 2018)

認知症高齢者見守りのための徘徊履歴可視化

認知症高齢者見守りのための徘徊履歴可視化に関する研究は、認知症の高齢者の方にBluetooth発信機を持ち歩いてもらい、固定型受信機を街中に設置することで徘徊している方を素早く見つけようという試みです。発信機はお守りの形をした袋に入っており、抵抗なく持ち歩けます。
高齢化が進んでいる日本では、こうしたBluetoothの活用も鍵になりそうです。
(荒川ら 2018)

おわりに

よく知っているような活用法から、研究途中の活用法までまとめてみました。
普段の生活に溶け込みすぎるあまり、目を向ける機会の少ないBluetoothですが、多岐にわたる分野で活躍していることがわかりました。今後の活用方法にも目を向けていきたいと思います。

参考記事・参考文献

Bluetoothとは何? わかりやすく解説 Weblio辞書

【サルでもわかるBLE入門】(1) BLEの基礎 - 株式会社ムセンコネクト

Bluetooth機能でできること7つ!音楽・アプリ・カーナビ | iPhone格安SIM通信

接触確認アプリ利用者向けQ&A|厚生労働省

野口裕之介,田中寿弥,森澤勝明,皆月昭則,2020,「BLE Beaconを用いたAED設置場所への屋内誘導におけるスマートフォンアプリケーションの開発」 第81回全国大会講演論文集,1巻,341-342

濱田大祐,大段一真,中道上,渡辺恵太,小滝泰弘,2019,「屋内避難におけるスマートフォンへの画面通知タイミングによる誘導効果」 第81回全国大会講演論文集,1巻,53-39

荒川智哉,白松俊,岩田彰,マウリシオクグレ,2018,「認知症高齢者見守りのための徘徊履歴可視化機構の開発 」第80回全国大会講演論文集,1巻,679-680

ジェネラティブアートとは

はじめに

 こんにちは、アンです。
 現在、聞いたことがない⼈がいないほど、世界中でNFTブームが起きています。私が注⽬しているジェネラティブアートの分野でもたくさんの作品が NFT 化しています。2021年、タイラー・ホッブス(Tyler Hobbs)のシリーズ作品《Fidenza》が販売されました。現時点で(2022年5月9日)、オープンシー(OpenSea)で販売されている合計999点の作品の総価値が45.9K ETH(約14,670,642,000円)になっています。NFTとNFTアートのブームのおかげで、私も含めてジェネラティブアートの作者が増えています。しかし、ジェネラティブアートとはいったい何なのでしょうか。今回、ジェネラティブアートの歴史を紹介します。

ジェネラティブアートとは

NoisePlanet_Echo_V4 - Samuel YAN, 2022 (https://openprocessing.org/sketch/1548117)

 簡潔に説明すると、ジェネラティブアートとは、ある程度の自律性を備えたシステムによって作成された作品、または人の介入がほとんどなくても機能できる作品を指します。言語ルール、マシン、アルゴリズムなどを使用して作者がシステムを設計します。設計したシステムに従って、作品が生成されます。これらのシステムは、デジタル、または化学、建築、詩、文学、アニメーション、視覚芸術など、さまざまな分野で実践されています。
 私の場合は、p5.js、processing、pythonなどのプログラミング言語を使って、ジェネラティブアート作品を制作しています。

ジェネラティブアートの歴史

萌芽

 19 世紀末に、ジェネラティブアートの芽が出始めました。キュビズムの原則の基礎を築いたポール・セザンヌのような芸術家たちは、彼らの作品の中で幾何学図形や、矛盾した視点などを使いはじめました。そこから、未来派構成主義がテクノロジーと機械を⽤いて 作品の魅⼒を広めます。その後、ダダイズムシュルレアリスム、抽象表現主義などの芸術運動が続きます。それぞれ、芸術を再定義しようとチャレンジしました。こうした芸術運動は、ジェネラティブアートの中心的な構成要素につながっています。

発展

 ビジネス用のコンピューターが登場した1960年代と1970年代に、ジェネラティブアーティストは、一つの部屋のような大きなサイズの計算機を使って、実験を行い、芸術とコンピューターサイエンスの関係を研究し始めました。1965 年にドイツのシュトゥットガルトで、初めての精選されたジェネラティブアートの展覧会が開催され、ゲオルク・ニース(Georg Nees)の作品が注目されました。その後、パイオニアであるニースとフリーダー・ナーケ(Frieder Nake)は、別の展覧会で彼らの作品を一緒に展示しました。その展覧会(Computer-Grafik (Nake & Nees))では、プログラムされ、コンピュータで制御されたドローイングマシンが制作した作品が特集されています(Generative Art: Origins, Artists, and Exemplary Works - Invaluable)。

Polygon of 23 Vertices (23-Ecke) — Georg Nees, 1964
13/9/65 Nr. 2 ("Hommage à Paul Klee") - Frieder Nake, 1965

 その間、⼥性の作家もジェネラティブアートの分野で活躍しました。たとえば、ジェネラティブ・アーティストで研究者のリリアン・シュワルツ(Lillian Schwartz)は、1968年から34年以上にわたってベル研究所のアーティスト・イン・レジデンスをつとめました。彼女は、MoMAが買い上げたはじめてのジェネラティブ・アートの作家としてよく名前があがります(Why Love Generative Art? — Artnome)。

Pixillation, photographic film stills - Lillian Schwartz, 1970

現状と展望

 コンピュータの普及で、アーティストたちがアルゴリズムを使用し始めました。数⼗年にわたって、芸術をコード化することができるコンピュータ・プログラムは、1990年代後半に開発されました。これらの革新があるため、コンピュータさえあれば、誰でもジェネラティブアートを作ることができます。2014年から、人工知能の飛躍的な発展により、AIが生み出すジェネラティブアート(AIアート)は開花しました。人間の脳のように考えるアルゴリズムが設計されており、ジェネラティブアートを制作することに成功しています。

ジェネラティブアートの種類

 今まで紹介したのは、最も一般的なタイプのジェネラティブアートであるビジュアルアート(視覚芸術)の分野の作品です。世界中のアーティストは、さまざまな⾃律的なシステムを⽤いて、有機的な⾃然界のものから⼈⼯的なものまで、さまざまな作品を制作してきました。コンピュータが利⽤しやすくなったので、コンピュータをベースとしたジェネラティブアートが増加しています。⽂学、⾳楽、建築、詩など、他のさまざまな分野でも実践されています。

ジェネラティブアートの魅力

 他のジャンルの芸術と⽐べ、私にとってジェネラティブアートの魅⼒がいくつかあります。これから、p5.jsを使用した自身の作品例を挙げながら紹介します。

ランダム性

 ランダム性は、ジェネラティブアートの⼀番魅⼒があるところだと思います。random関数を使って、色、位置、線の太さなどにランダム性を与えると作品に変化が生まれます。ランダムな値のおかげで、コードを実⾏するたびに異なる画像を⽣成し、さまざまな出⼒が⽣まれます。
 たとえば、次の画像では、色、線の太さ、幅の広さなどをrandom関数で設定しました。

MetalWave_3.0 - Samuel YAN, 2022 (https://openprocessing.org/sketch/1559761)

対象の可変性

 アルゴリズムやシステムを作った上で、「対象(object)」を変換すれば、生み出される結果(画像などの出⼒)が変わります。ここでの「対象」は、円、四角形、三⾓形、線などの基本的な幾何学的図形だけではなく、複数のシンプルな図形を組み合わせて作った複雑なパターンや模様も含まれます。
 たとえば、次のシリーズ作品の《urbanME》で、「対象」に異なる要素を入れることで結果が変わりました。

urbanME series - Samuel YAN, 2021~ (https://openprocessing.org/curation/73130#)

双方向性(インタラクティブ

 インタラクティブとは、相互に作⽤する、対話的な、双⽅向の、相乗効果の、などの意味を持つ英単語で、メディアコンテンツでは、 内容を利⽤者に⼀⽅的に与えるのではなく、利⽤者の働きかけにより刻々と内容が変化することをインタラクティブであるといいます(IT用語辞典e-Words)。アートの場合は、インタラクティブアートというジャンルや分野が存在します。ジェネラティブアートでも双⽅向性(インタラクティブ)がある作品が作れます。
 たとえば、次の作品では、外部の⾳源の⾳量によって、画⾯の中の点が移動しています。

Pulse Wave_1.2.2 with Music - Samuel YAN, 2022 (https://openprocessing.org/sketch/1546845)

さいごに

 ジェネラティブアートの歴史を遡って、歴史的な作家や作品を紹介しました。最後に私にとってのジェネラティブアートの魅力にも触れました。今回、たくさんの文章を読んだことで、ジェネラティブアートの分野でパイオニアたちが試行錯誤したことや考え方を知ることができました。この調査を、今後の私の研究と制作に役立てていきたいと思います。

Go言語で基本のソートアルゴリズムを実装してみた

はじめに

こんにちは,光岡です. このブログはとある大学院の研究室メンバーによるブログです! 3人体制で各々が月に1回ずつ,研究分野問わず自分が興味を持っていることについて発信していきます. そして今回は第一回目の投稿になります!

私はWebサービス開発を勉強していることもあり,今Go言語に興味があります. また,本研究室は情報系の学域ではないため(デザインよりの学域です),最近は個人的にアルゴリズムを学んでいます.アルゴリズムとデータ構造の勉強をする際はC言語Pythonが主流だと思いますが,今回は私が興味を持っている2つを掛け合わせて,Go言語のソートアルゴリズムに関して書いていきたいと思います.

Go言語とは

Go言語とは,Googleによって設計されたプログラミング言語です. Go言語の主な特徴は以下になります.

個人的にはこれまで動的型付け言語を触ってきていたので,最初の型定義が少し面倒だなと感じていましたが,今では型がないと、このメソッドの引数・返り値の型はなんだろう..とたまになってしまうので,型が欲しいなと思うようになりました.

また,最初Go言語で書かれたコードを読んだ時,:=記法を理解していなかったのですが,こちらはvarを省略した記法になります.

// 型を宣言
var n int // n = 0 (Go言語の変数は必ず初期化され,ゼロ値が入ります)

// 型推論
var n = 1

// varを省略
n := 1

実装

今回は,選択ソート,挿入ソート,シェルソートクイックソートの4種を実装してみました.

選択ソート

ソートのアルゴリズムの一つ。 配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える。 最悪時間計算量は O(n2) と遅いため、一般にはクイックソートなどのより高速な方法が利用される。


選択ソートは以下の手順で行う:

  1. 1 番目の要素から最後尾の要素までで最も値の小さいものを探し、それを 1 番目の要素と交換する(1番目の要素までソート済みとなる)

  2. 以降同様に、未ソート部分の最小要素を探索し、未ソート部分の先頭要素と交換する

  3. すべての要素がソート済みになったら処理を終了する

選択ソート - Wikipedia

for文で最も小さい値のインデックスをmin_idxに代入していき,最終的に格納されていたインデックスを使用して,スライスの要素を順に昇順に並び替えました.

スライスとは
他の言語では,配列を使用しますが,Go言語ではスライスを使用するほうが一般的です. 配列とスライスの違いは,配列はサイズが固定長,スライスが可変長です.

package main

import "fmt"

func SelectionSort(nums []int) []int {
    for i := range nums {
        min_idx := i

        for j := i; j < len(nums); j++ {
            if nums[min_idx] > nums[j] {
                min_idx = j
            }
        }
        nums[i], nums[min_idx] = nums[min_idx], nums[i]
    }
    return nums
}

func main() {
    nums := []int{2, 4, 3, 1, 5, 7, 6}
    fmt.Println(SelectionSort(nums)) // [1 2 3 4 5 6 7]
}

挿入ソート

数値の列を先頭から小さい順(昇順)に並べる場合を考える。まず、先頭から2つの値を比較して小さい方を先頭に、大きい方を2番目に置く。次に3番目の値を取り出し、先頭・2番目と順に比較し、適切な位置に挿入する。

4番目以降も同様にして、n番目の値を取り出して先頭からn-1番目までと順番に比較し、適切な位置に挿入する操作を繰り返す。

挿入ソート(基本挿入法 / インサーションソート)とは - IT用語辞典 e-Words

未整列の要素が逆順に近い並びの場合は,計算時間が多くかかってしまい,それを緩和したアルゴリズムシェルソート(後述)になります.

下記コードでは,tempに格納した値を,条件が当てはまる限り適切な位置まで移動させるのがポイントになります.

最初の状態[4, 3, 1, ...]において,i = 1 の時に並び替えると,[3, 4, 1, ...]となります.
次に i = 2 の時,temp = nums[2] = 1が入ります.この時 4 > temp(=1) により,nums[2] に 4 を移動させた後 j をデクリメントして,3 と temp(=1)を比較します. 3 > temp(=1) により,同様に nums[1] に 3 を移動させ,1 が nums[0] に移動し,[1, 3, 4, ...]となります.

このように,比較対象になった値は,適切な位置まで移動し切ってから次の要素を並び替えます.

package main

import "fmt"

func InsertionSort(nums []int) []int {
    for i := 1; i < len(nums); i++ {
        if nums[i-1] > nums[i] {
            j := i
            temp := nums[i]
            for 0 < j && nums[j-1] > temp {
                nums[j] = nums[j-1]
                j--
            }
            nums[j] = temp
        }
    }
    return nums
}

func main() {
    nums := []int{4, 3, 1, 5, 7, 6, 2}
    fmt.Println(InsertionSort(nums)) // [1 2 3 4 5 6 7]
}

シェルソート

挿入ソートの一般化であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。


主な手順は以下の通りです.

  1. 適当な間隔 h を決める

  2. 間隔 h をあけて取り出したデータ列に挿入ソートを適用する

  3. 間隔 h を狭めて、2.を適用する操作を繰り返す

  4. h = 1 になったら、最後に挿入ソートを適用して終了

シェルソート - Wikipedia

間隔の決め方については,様々な方法がありますが,今回は,まずスライスの要素数 / 2 で始め,都度2で割って間隔を狭めていく方法をとって実装してみました.

今回は数値を2で割る際に,ビット演算子の右シフトを使用してみました.

// example

num := 50
fmt.Printf("Result: %06b ( = %d )\n", num, num)          // 110010 ( = 50 )
fmt.Printf("Result: %06b ( = %d )\n", num>>1, num>>1)    // 011001 ( = 25 )
fmt.Printf("Result: %06b ( = %d )\n", num>>2, num>>2)    // 001100 ( = 12 )
package main

import "fmt"

func ShellSort(nums []int) []int {
    n := len(nums)
    h := n >> 1

    for h > 0 {
        for i := h; i < n; i++ {
            for j := i; j >= h; j -= h {
                if nums[j-h] > nums[j] {
                    nums[j], nums[j-h] = nums[j-h], nums[j]
                }
            }
        }
        h >>= 1
    }
    return nums
}

func main() {
    nums := []int{4, 3, 1, 5, 7, 6, 2}
    fmt.Println(ShellSort(nums)) // [1 2 3 4 5 6 7]
}

クイックソート

クイックソートとは分割統治法の1つです. 主な手順は以下の通りです.

  1. ピボットの選択:適当な値(ピボット(英語版)という)を境界値として選択する
  2. 配列の分割:ピボット未満の要素を配列の先頭側に集め、ピボット未満の要素のみを含む区間とそれ以外に分割する
  3. 再帰:分割された区間に対し、再びピボットの選択と分割を行う
  4. ソート終了:分割区間が整列済みなら再帰を打ち切る

クイックソート - Wikipedia

文章のみの説明だとイメージしづらいと思います.個人的には クイックソートとは | 分かりやすく図解で解説の図解がとてもわかりやすかったので,是非確認してみてください!

他のソートアルゴリズムに比べ,高速だと言われていますが,手順1のピボットの位置やデータの並びによっては計算量が多くなることもあります.

今回のピボットは,スライスの最後の要素を使用して実装してみました. また,partitionメソッドの返り値i + 1は pivot に指定していた値の最終的な位置を返しており,その pivot よりインデックスが小さいスライスと大きいスライスの2つに分け,再帰的に同じ処理を行い並び替えを行っています.

package main

import (
    "fmt"
)

func partition(nums []int, low int, high int) int {
    i := low - 1
    pivot := nums[high]
    for j := low; j < high; j++ {
        if nums[j] <= pivot {
            i++
            nums[i], nums[j] = nums[j], nums[i]
        }
    }
    nums[i+1], nums[high] = nums[high], nums[i+1]
    return i + 1
}

func QuickSort(nums []int, low int, high int) []int {
    if low < high {
        partition_idx := partition(nums, low, high)
        QuickSort(nums, low, partition_idx-1)
        QuickSort(nums, partition_idx+1, high)
    }
    return nums
}

func main() {
    nums := []int{2, 4, 3, 1, 5, 7, 6}
    low := 0
    high := len(nums) - 1
    fmt.Println(QuickSort(nums, low, high)) // [1 2 3 4 5 6 7]
}

さいごに

今回は基本のソートアルゴリズム4種をGo言語で実装してみました.これまでアルゴリズムをしっかり学んだことがなかったのですが,楽しみながら学ぶことができました.まだ次回内容は決めていませんが,他のアルゴリズムも取り上げてみたいと思います.

参考記事