- 投稿日:2019-02-28T20:47:23+09:00
【Java初心者】for文と拡張for文の比較
はじめに
普通のfor文より拡張for文の方がIterator使ってるから早いんだぜ!と誰かに教えられたので調べもせずにそのままにしていました。この際ちゃんと調べようと思いました。普通のfor文の方が良いという話になったらどうしようか…
時代はstreamだと思いますが、私の現場はJava6なので後輩にもJava6で書ける書き方を教えなければならないのです。けっしてstreamが書けないからではないのです。検証環境
- OS Windows10
- Java 11.0.1
- Pleiades All in One Eclipse (2018-12)
書いてみた
検証コード
10万くらいでやったら値が小さすぎて比較できなかったので、1000万回ループさせてみました。
Main.javaimport java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { List<Integer> list = new ArrayList<>(); for (int i = 0; i < 10000000; i++) { list.add(i); } //開始 long start = System.currentTimeMillis(); //1000万ループ for (int i = 0; i < list.size(); i++) { int tmp = list.get(i); } //終了 long end = System.currentTimeMillis(); System.out.println("for文: " + (end - start) + " ms"); //開始 start = System.currentTimeMillis(); //1000万ループ for (Integer i : list) { int tmp = i; } //終了 end = System.currentTimeMillis(); System.out.println("拡張for文: " + (end - start) + " ms"); } }検証結果
そんなばかな…
何回か試したのですが拡張for文が早くなることはなかったです。for文: 24 ms 拡張for文: 29 ms検証②
このままじゃ終われないと思い調べたところこんなサイトさんがありました。
拡張for文を使う理由 - [Seasar]soichirooooo5の日記
リンク先を見てもらえればこの記事の書きたかった答えが書いてありますが、
せっかくなので最後までやります。
検証をArrayListでしかやっていませんので、配列とLinkedListでも検証してみます。検証コード(配列)
Main.javapublic class Main { public static void main(String[] args) { int[] array = new int[10000000]; for (int i = 0; i < 10000000; i++) { array[i] = i; } //開始 long start = System.currentTimeMillis(); //1000万ループ for (int i = 0; i < array.length; i++) { int tmp = array[i]; } //終了 long end = System.currentTimeMillis(); System.out.println("for文: " + (end - start) + " ms"); //開始 start = System.currentTimeMillis(); //1000万ループ for (Integer i : array) { int tmp = i; } //終了 end = System.currentTimeMillis(); System.out.println("拡張for文: " + (end - start) + " ms"); } }結果
for文高速すぎるwww
for文: 3 ms 拡張for文: 16 ms検証(LinkedList)
Main.javapackage qiita; import java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { List<Integer> list = new LinkedList<>(); for (int i = 0; i < 10000000; i++) { list.add(i); } //開始 long start = System.currentTimeMillis(); //1000万ループ for (int i = 0; i < list.size(); i++) { int tmp = list.get(i); } //終了 long end = System.currentTimeMillis(); System.out.println("for文: " + (end - start) + " ms"); //開始 start = System.currentTimeMillis(); //1000万ループ for (Integer i : list) { int tmp = i; } //終了 end = System.currentTimeMillis(); System.out.println("拡張for文: " + (end - start) + " ms"); } }検証結果
なんか5分くらい応答が返ってこないんですが。
※10分待っても終わらないので中止。検証(LinkedList)②
終わらないので10万ループにして再検証
Main.javaimport java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { List<Integer> list = new LinkedList<>(); for (int i = 0; i < 100000; i++) { list.add(i); } //開始 long start = System.currentTimeMillis(); //1000万ループ for (int i = 0; i < list.size(); i++) { int tmp = list.get(i); } //終了 long end = System.currentTimeMillis(); System.out.println("for文: " + (end - start) + " ms"); //開始 start = System.currentTimeMillis(); //1000万ループ for (Integer i : list) { int tmp = i; } //終了 end = System.currentTimeMillis(); System.out.println("拡張for文: " + (end - start) + " ms"); } }検証結果②
これはすごい!!
for文: 5695 ms 拡張for文: 36 ms最後に
ArrayListや配列のように前から順番に操作するものは普通のfor文の方が早いことがわかった。
しかし、LinkedListでは圧倒的に差が出てしまった。
Listインターフェースをループさせるときに実体を気にするのはおかしいので、拡張for文でよいという結論に持って行けたと思う。以下は参考サイトから引用です。
拡張for文を使っていれば、for文に渡されるオブジェクトがArrayListかLinkedListか分からない場合でも、「99%以上パフォーマンスが下がる」という心配をしなくて済みます。
また、拡張for文は、Listインタフェースの実装型をイテレータを使ったコードに変換し、配列の場合にはインデックスアクセスするコードに変換してくれます。
このコンパイラの翻訳によって、for文に渡すリスト又は配列に適したコードが生成されることが分かります。つまり、拡張forさえ使えば何も考えなくていい、何も心配しなくていいということです。まずいことがあればAPIの裏でなんとかしてくれる、ということです。
つまり何も考えずに拡張for文でよいということですね。
stream勉強しよう。
- 投稿日:2019-02-28T20:47:23+09:00
for文と拡張for文の速度を比較してみる。
はじめに
普通のfor文より拡張for文の方がIterator使ってるから早いんだぜ!と誰かに教えられたので調べもせずにそのままにしていました。この際ちゃんと調べようと思いました。普通のfor文の方が良いという話になったらどうしようか…
時代はstreamだと思いますが、私の現場はJava6なので後輩にもJava6で書ける書き方を教えなければならないのです。けっしてstreamが書けないからではないのです。検証環境
- OS Windows10
- Java 11.0.1
- Pleiades All in One Eclipse (2018-12)
書いてみた
検証コード
10万くらいでやったら値が小さすぎて比較できなかったので、1000万回ループさせてみました。
Main.javaimport java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) { List<Integer> list = new ArrayList<>(); for (int i = 0; i < 10000000; i++) { list.add(i); } //開始 long start = System.currentTimeMillis(); //1000万ループ for (int i = 0; i < list.size(); i++) { int tmp = list.get(i); } //終了 long end = System.currentTimeMillis(); System.out.println("for文: " + (end - start) + " ms"); //開始 start = System.currentTimeMillis(); //1000万ループ for (Integer i : list) { int tmp = i; } //終了 end = System.currentTimeMillis(); System.out.println("拡張for文: " + (end - start) + " ms"); } }検証結果
そんなばかな…
何回か試したのですが拡張for文が早くなることはなかったです。for文: 24 ms 拡張for文: 29 ms検証②
このままじゃ終われないと思い調べたところこんなサイトさんがありました。
拡張for文を使う理由 - [Seasar]soichirooooo5の日記
リンク先を見てもらえればこの記事の書きたかった答えが書いてありますが、
せっかくなので最後までやります。
検証をArrayListでしかやっていませんので、配列とLinkedListでも検証してみます。検証コード(配列)
Main.javapublic class Main { public static void main(String[] args) { int[] array = new int[10000000]; for (int i = 0; i < 10000000; i++) { array[i] = i; } //開始 long start = System.currentTimeMillis(); //1000万ループ for (int i = 0; i < array.length; i++) { int tmp = array[i]; } //終了 long end = System.currentTimeMillis(); System.out.println("for文: " + (end - start) + " ms"); //開始 start = System.currentTimeMillis(); //1000万ループ for (int i : array) { int tmp = i; } //終了 end = System.currentTimeMillis(); System.out.println("拡張for文: " + (end - start) + " ms"); } }結果
for文高速すぎるwww
拡張for文でオートボクシングが行われていたため、
正確に計測できていませんでした。
結果は変わらず。
※@swordone さんご指摘ありがとうございます。for文: 3 ms 拡張for文: 3 ms検証(LinkedList)
Main.javapackage qiita; import java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { List<Integer> list = new LinkedList<>(); for (int i = 0; i < 10000000; i++) { list.add(i); } //開始 long start = System.currentTimeMillis(); //1000万ループ for (int i = 0; i < list.size(); i++) { int tmp = list.get(i); } //終了 long end = System.currentTimeMillis(); System.out.println("for文: " + (end - start) + " ms"); //開始 start = System.currentTimeMillis(); //1000万ループ for (Integer i : list) { int tmp = i; } //終了 end = System.currentTimeMillis(); System.out.println("拡張for文: " + (end - start) + " ms"); } }検証結果
なんか5分くらい応答が返ってこないんですが。
※10分待っても終わらないので中止。検証(LinkedList)②
終わらないので10万ループにして再検証
Main.javaimport java.util.LinkedList; import java.util.List; public class Main { public static void main(String[] args) { List<Integer> list = new LinkedList<>(); for (int i = 0; i < 100000; i++) { list.add(i); } //開始 long start = System.currentTimeMillis(); //1000万ループ for (int i = 0; i < list.size(); i++) { int tmp = list.get(i); } //終了 long end = System.currentTimeMillis(); System.out.println("for文: " + (end - start) + " ms"); //開始 start = System.currentTimeMillis(); //1000万ループ for (Integer i : list) { int tmp = i; } //終了 end = System.currentTimeMillis(); System.out.println("拡張for文: " + (end - start) + " ms"); } }検証結果②
これはすごい!!
for文: 5695 ms 拡張for文: 36 ms最後に
ArrayListや配列のように前から順番に操作するものは普通のfor文の方が早いことがわかった。
しかし、LinkedListでは圧倒的に差が出てしまった。
Listインターフェースをループさせるときに実体を気にするのはおかしいので、拡張for文でよいという結論に持って行けたと思う。以下は参考サイトから引用です。
拡張for文を使っていれば、for文に渡されるオブジェクトがArrayListかLinkedListか分からない場合でも、「99%以上パフォーマンスが下がる」という心配をしなくて済みます。
また、拡張for文は、Listインタフェースの実装型をイテレータを使ったコードに変換し、配列の場合にはインデックスアクセスするコードに変換してくれます。
このコンパイラの翻訳によって、for文に渡すリスト又は配列に適したコードが生成されることが分かります。つまり、拡張forさえ使えば何も考えなくていい、何も心配しなくていいということです。まずいことがあればAPIの裏でなんとかしてくれる、ということです。
つまり何も考えずに拡張for文でよいということですね。
stream勉強しよう。
- 投稿日:2019-02-28T19:40:52+09:00
Debian, Ubuntuへapt(-get)でAdoptOpenJDKをインストールする方法
はじめに
Oracle JDK 8のサポート終了や、Oracle JDK 8の有償化に伴い、AdoptOpenJDKが注目を浴びています。例えば、豪Atlassian社のJiraやConfluence等は、AdoptOpenJDKをサポートしています。
AdoptOpenJDKのインストールは、AdoptOpenJDKのサイトからtar+gz形式のアーカイブファイルをダウンロードして展開し、適当なディレクトリへ配置し、パスを通すというのが標準的な方法になりますが、せっかくUbuntuやDebianを使っているのであれば、どうせならapt(-get)で管理したくなります。
ということで、apt(-get)からのAdoptOpenJDKのインストール方法になります。
手順
OpenJDK 8 をインストールする場合
(内容は、後述の参考情報と同じです)Ubuntu
sudo add-apt-repository --yes ppa:rpardini/adoptopenjdk sudo apt-get update sudo apt-get install adoptopenjdk-8-installerDebian
[[ ! -f /usr/lib/apt/methods/https ]] && sudo apt-get update && sudo apt-get install apt-transport-https sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys A66C5D02 echo 'deb https://rpardini.github.io/adoptopenjdk-deb-installer stable main' > /etc/apt/sources.list.d/rpardini-aoj.list sudo apt-get update sudo apt-get install adoptopenjdk-8-installer参考情報
- Debian/Ubuntu installer packages for AdoptOpenJDK
- AdoptOpenJDK
- 投稿日:2019-02-28T16:06:10+09:00
デザインパターン ~Builder~
1. はじめに
GoFのデザインパターンにおける、Builderパターンについてまとめます。
2. Builderパターンとは
- Buildという英単語は、構造を持っている大きなものを構築したりすることの意味になります。
- 複雑な構造をもったものを作り上げるとき、一気に完成させるのは困難です。まず全体を構築している各部分を作り、段階を踏んで組み上げていくことになります。
- Builderパターンは、構造を持ったインスタンスを組み上げていく方式です。
- GoFのデザインパターンでは、生成に関するデザインパターンに分類されます。
3. サンプルクラス図
4. サンプルコード
4-1. Builderクラス
文書を構成するためのメソッドを定義した抽象クラスです。
Builder.javapublic abstract class Builder { public abstract void makeTitle(String title); public abstract void makeString(String str); public abstract void makeItems(String[] items); public abstract void close(); }4-2. Guideクラス
1つの文書を作成するクラスです。
Guide.javapublic class Guide { private Builder builder; public Guide(Builder builder) { this.builder = builder; } public void construct() { builder.makeTitle("バーベキューについて"); builder.makeString("日時"); builder.makeItems(new String[]{ "2019/2/28 (木)", "11:00~", }); builder.makeString("場所"); builder.makeItems(new String[]{ "xxx市 xxxバーベキュー場", }); builder.makeString("持ち物"); builder.makeItems(new String[]{ "タオル", "肉", "飲み物", "(略)", }); builder.close(); } }4-3. TextBuilderクラス
プレーンテキストで文書を作成するクラスです。
TextBuilder.javapublic class TextBuilder extends Builder { private StringBuffer buffer = new StringBuffer(); public void makeTitle(String title) { buffer.append("==============================\n"); buffer.append("『" + title + "』\n"); buffer.append("\n"); } public void makeString(String str) { buffer.append('■' + str + "\n"); buffer.append("\n"); } public void makeItems(String[] items) { for (int i = 0; i < items.length; i++) { buffer.append(" ・" + items[i] + "\n"); } buffer.append("\n"); } public void close() { buffer.append("==============================\n"); } public String getResult() { return buffer.toString(); } }4-3. HTMLBuilderクラス
HTMLファイルで文書を作成するクラスです。
HTMLBuilder.javaimport java.io.FileWriter; import java.io.IOException; import java.io.PrintWriter; public class HTMLBuilder extends Builder { private String filename; private PrintWriter writer; public void makeTitle(String title) { filename = title + ".html"; try { writer = new PrintWriter(new FileWriter(filename)); } catch (IOException e) { e.printStackTrace(); } writer.println("<html><head><title>" + title + "</title></head><body>"); writer.println("<h1>" + title + "</h1>"); } public void makeString(String str) { writer.println("<p>" + str + "</p>"); } public void makeItems(String[] items) { writer.println("<ul>"); for (int i = 0; i < items.length; i++) { writer.println("<li>" + items[i] + "</li>"); } writer.println("</ul>"); } public void close() { writer.println("</body></html>"); writer.close(); } public String getResult() { return filename; } }4-5. Mainクラス
メイン処理を行うクラスです。
Main.javapublic class Main { public static void main(String[] args) { if (args.length != 1) { System.exit(0); } if (args[0].equals("plain")) { TextBuilder textbuilder = new TextBuilder(); Guide guide = new Guide(textbuilder); guide.construct(); String result = textbuilder.getResult(); System.out.println(result); } else if (args[0].equals("html")) { HTMLBuilder htmlbuilder = new HTMLBuilder(); Guide guide = new Guide(htmlbuilder); guide.construct(); String filename = htmlbuilder.getResult(); System.out.println(filename + "が作成されました。"); } else { System.exit(0); } } }4-6. 実行結果
4-6-1. テキスト
============================== 『バーベキューについて』 ■日時 ・2019/2/28 (木) ・11:00~ ■場所 ・xxx市 xxxバーベキュー場 ■持ち物 ・タオル ・肉 ・飲み物 ・(略) ==============================4-6-2. HTML
5. メリット
サンプルプログラムを見てみると、Mainクラスは文書の構築方法(Builderクラスのメソッド)を知りません。MainクラスはGuideクラスのconstructメソッドを呼び出すだけで、文章を構築できます。
また、GuideクラスはBuilderクラスを使って文書を構築しますが、Guideクラスは自分が実際に利用しているクラスが何なのか(TextBuilderなのかHTMLBuilderなのか)を知りません。
TextBuilderのインスタンスをGuideに与えても、HTMLBuilderのインスタンスをGuideに与えても正しく機能するのは、GuideクラスがBuilderクラスの具体的なクラスを知らないからになります。
知らないからこそ、入れ替えができる、入れ替えられるからこそ、部品としての価値が高まります。6. 参考
- 投稿日:2019-02-28T15:10:37+09:00
個人メモ Eclipseプラグインのインストール
Eclipse Checkstyleプラグインのインストールと使い方
https://itsakura.com/eclipse-checkstyle
- 投稿日:2019-02-28T14:24:45+09:00
JavaでXMLをフォーマットする
やりたいこと
<tag><tag>test</tag></tag>のような文字列を
<tag> <tag>test</tag> </tag>のように変換したい。
方法
やり方は諸説あるようですが、いくつかを組み合わせて以下のようにしました。
static public String formatXml(String xml) { try { InputStream bais = new ByteArrayInputStream(xml.getBytes("utf-8")); DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance(); DocumentBuilder builder = factory.newDocumentBuilder(); Document doc = builder.parse(bais); doc.setXmlStandalone(true); Transformer transformer = TransformerFactory.newInstance().newTransformer(); transformer.setOutputProperty(OutputKeys.INDENT, "yes"); transformer.setOutputProperty(OutputKeys.OMIT_XML_DECLARATION, "yes"); transformer.setOutputProperty("{http://xml.apache.org/xslt}indent-amount", "2"); StreamResult result = new StreamResult(new StringWriter()); DOMSource source = new DOMSource(doc); transformer.transform(source, result); String xmlString = result.getWriter().toString(); String header = "<?xml version=\"1.0\" encoding=\"UTF-8\"?>"; return header + "\n" + xmlString; } catch (Exception e) { e.printStackTrace(); } return xml; }
- 投稿日:2019-02-28T12:31:54+09:00
TestNG使ってみた
Java6サポート切れ対応で火を吹いていた時期にちょうど休職しており、難を逃れました。JUnit3というかdjUnitのテストクラスとかどうしたんだろう(一応動くには動くらしい)。
というわけで、超今さらながらTestNG使ってみました。
準備
Mavenであれば以下の依存性を追加すれば準備完了です。
pom.xml(コピペ厳禁)<dependency> <groupId>org.testng</groupId> <artifactId>testng</artifactId> <version>6.14.3</version> <scope>test</scope> </dependency>Maven自体ほとんど使ったことがなかったのですが、pom.xmlの記述をコピペして書き換えたりすると高確率で事故ります。実際、コピペしたらscope間違えていて、動くには動くけどデプロイするアーカイブにtestng-6.14.3.jarが入ってしまうというおかしなことになりました。必ずIDEの自動補完を使ってください。
使ったことはあるけどpom.xmlの書き方はわからないって人は結構多いかもしれませんね。
テストケースを作る
JUnitで言うところのテストクラスです。結構似ています。
JUnit4を使ったことがあれば戸惑うこともありません。LogoutBeanTest.javapublic class LogoutBeanTest { /** テスト対象クラス */ private LogoutBean logoutBean; @Test public void logout() throws Exception { String result = logoutBean.logout(); // 結果の検証 assertEquals(logoutBean.getMessage(), "ログアウトしました"); assertEquals(result, "/logout/logout.jsf"); } @BeforeMethod public void setUpMethod() throws Exception { logoutBean = new LogoutBean(); } }
assertEquals()
の引数の順番がJUnitと逆なのがちょっと気になりましたね。JUnitだと想定結果(expected)が先ですが、TestNGでは実際の結果(actual)が先になります。JUnitでも逆に書いている人結構いましたけどね……テストスイートを作る
複数のテストクラスをXMLで管理することができます。
コマンドラインでTestNGを実行する場合は複数のテストクラスをまとめて呼べるようになって便利なのですが、IDEではその利点を見出せず。testng.xml<!DOCTYPE suite SYSTEM "http://testng.org/testng-1.0.dtd" > <suite name="cc.cress.sample"> <test name="Login"> <classes> <class name="cc.cress.sample.login.LoginBeanTest"/> <class name="cc.cress.sample.util.PasswordEncrypterTest"/> </classes> </test> <test name="Logout"> <classes> <class name="cc.cress.sample.logout.LogoutBeanTest"/> </classes> </test> </suite>このあとPowerMockito(モックオブジェクト)とかJacoco(カバレッジ取得)とかも導入しているのですが、かなりボリューミーになってしまったので一旦ここまで。
- 投稿日:2019-02-28T09:33:56+09:00
デザインパターン ~Prototype~
1. はじめに
GoFのデザインパターンにおける、Prototypeパターンについてまとめます。
2. Prototypeパターンとは
- Prototypeという英単語は、原型や模範という意味になります。
- Prototypeパターンは、new xxx()でクラスからインスタンスを生成するのではなく、インスタンスから別のインスタンスを作り出す方式です。
- 複製を作る操作をcloneと呼びます。
- GoFのデザインパターンでは、生成に関するデザインパターンに分類されます。
3. サンプルクラス図
4. サンプルコード
4-1. Productインターフェース
複製メソッドを定義するインターフェースです。javaのCloneableインターフェースを継承しています。
Product.javapackage framework; import java.lang.Cloneable; public interface Product extends Cloneable { public abstract void use(String s); public abstract Product createClone(); }4-2. Managerクラス
Productの作成指示や管理を行うクラスです。
Manager.javapackage framework; import java.util.HashMap; public class Manager { private HashMap showcase = new HashMap(); public void register(String name, Product proto) { showcase.put(name, proto); } public Product create(String protoname) { Product p = (Product)showcase.get(protoname); return p.createClone(); } }4-3. UnderlinePenクラス
Productインターフェースを実装するクラスです。当クラスは「文字に下線を引く」クラスになります。
UnderlinePen.javaimport framework.Product; public class UnderlinePen implements Product { private char ulchar; public UnderlinePen(char ulchar) { this.ulchar = ulchar; } public void use(String s) { int length = s.getBytes().length; System.out.println(s); for (int i = 0; i < length; i++) { System.out.print(ulchar); } System.out.println(""); } public Product createClone() { Product p = null; try { p = (Product)clone(); } catch (CloneNotSupportedException e) { // オブジェクトのクラスがCloneableインタフェースを実装していない場合にスローされる例外 e.printStackTrace(); } return p; } }4-4. MessageBoxクラス
Productインターフェースを実装するクラスです。当クラスは「文字を囲む」クラスになります。
MessageBox.javaimport framework.Product; public class MessageBox implements Product { private char decochar; public MessageBox(char decochar) { this.decochar = decochar; } public void use(String s) { int length = s.getBytes().length; for (int i = 0; i < length + 2; i++) { System.out.print(decochar); } System.out.println(""); System.out.println(decochar + s + decochar); for (int i = 0; i < length + 2; i++) { System.out.print(decochar); } System.out.println(""); } public Product createClone() { Product p = null; try { p = (Product)clone(); } catch (CloneNotSupportedException e) { // オブジェクトのクラスがCloneableインタフェースを実装していない場合にスローされる例外 e.printStackTrace(); } return p; } }4-5. Mainクラス
メイン処理を行うクラスです。
Main.javaimport framework.Manager; import framework.Product; public class Main { public static void main(String[] args) { Manager manager = new Manager(); UnderlinePen upen = new UnderlinePen('~'); MessageBox mbox = new MessageBox('*'); MessageBox pbox = new MessageBox('+'); manager.register("strong message", upen); manager.register("warning box", mbox); manager.register("slash box", pbox); Product p1 = manager.create("strong message"); p1.use("Hello world"); Product p2 = manager.create("warning box"); p2.use("Hello world"); Product p3 = manager.create("slash box"); p3.use("Hello world"); } }4-6. 実行結果
Hello World =========== ************* *Hello World* ************* +++++++++++++ +Hello World+ +++++++++++++5. メリット
サンプルプログラムでは比較的シンプルなケースでしたが、インスタンスを生成するにあたり、複雑な処理が必要だったり、時間がかかる処理が必要だったりする場合があります。インスタンスを生成する度にnew xxx()としていては、とても非効率になります。
Prototype(雛形)を作っておいてコピーするだけで、簡単にインスタンスを生成することができます。6. 参考
- 投稿日:2019-02-28T06:25:42+09:00
探索の基礎とJava実装・計測
TL;DR
- 初心者向け
- 適切な探索方法を選んで、実行時間を短くする方法を学びましょう
- 単純な処理でも20億回実行したら0.5秒ぐらいかかります
- (なおDB接続を繰り返すと桁外れに時間がかかります)
主要な探索の種類とイメージ
- 線形探索
- 二分探索
- ハッシュ探索
mail_addressを指定してcustomerを検索する例を考えてみましょう
線形探索
- 対象データを順番に参照して、検索キーmail_addressが一致しているか調べます
計算量
1024件のデータがあれば1024回参照します。愚直。
O(n)二分探索
- mail_addressで全体をソートします
- 真ん中辺りのデータを参照して、一致しているか調べます
- 一致していなければ半分を捨てて、残りの半分の真ん中を参照します
- 一種の分割統治法
計算量
1024件 = 2^10件 = 2*2*2*2*2*2*2*2*2*2件を半分ずつ捨てながら見るので、
最大でも10個のデータを参照すれば見つかります。賢い。O(\log n)※計算機科学で言うlogの底は2です。
2^(log n) = n
ですハッシュ法
- 対象データ全てのmail_addressをハッシュ関数に渡して一定のルールで変換し、ハッシュ値を得ます
- 検索キーのmail_addressも同じハッシュ関数に渡して、同じルールで変換し、ハッシュ値を得ます
- ハッシュ値の一致するデータを参照します
- 対象データのハッシュ値の塊から指定したハッシュ値xxxを見つける際に、追加の処理は必要ありません(実装例:ハッシュテーブル)
計算量
1024件でもハッシュ関数を1度経由すれば、対象データを直接参照できます
O(1)欠点
一般的に、アルゴリズムは実行時間短縮とメモリ消費低減のトレードオフです
両方が悪い実装は存在しますし、作れますが、
それぞれで同時に最高のパフォーマンスを出すアルゴリズムは存在しないでしょう
ハッシュ法もご多分に漏れず、メモリを食いますデータベースで使われているのは?
PostgreSQL 実行計画(explain, explain analyze)
- Seq Scan: 線形探索
- Index Scan: 二分探索っぽいもの
- Hash ~: ハッシュ法
PostgreSQL Index Only Scan 奮闘記 その3 | TECHSCORE BLOG
【SQL】ゼロ知識から実行計画を読み解きパフォーマンス改善 - Qiita
EXPLAIN - PostgreSQL 10.5文書Java実装・計測
探索の実装前に
単純な処理分岐でも20億回実行したら0.61秒かかります
ベースにするソースコード
100000人のcustomerを用意して、メールアドレスを1000回検索してみましょう。
https://ideone.com/w0hDzg検索処理を入れる場所(TODO)が未実装の状態で0.9秒です。
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) throws java.lang.Exception { // n人分のデータを作り int n = 100000; Random rand = new Random(); String[][] customer = new String[n][2]; for (int i = 0; i < n; i++) customer[i][0] = String.valueOf((char) (rand.nextInt(26)+'a')) + i + "@ab.com"; for (int i = 0; i < n; i++) customer[i][1] = i + "さん"; // メールアドレスでソートします Arrays.sort(customer, (c1, c2) -> c1[0].compareTo(c2[0])); // キーをメールアドレス、値を名前としたハッシュマップも作ります Map<String, String> hashmap = new HashMap<>(n); for (String[] c : customer) hashmap.put(c[0], c[1]); // 同じcustomer(101番目)の名前が取れる System.out.println(customer[101][0] + "の名前は" + customer[101][1]); // ハッシュマップからメールアドレスで取ることもできる System.out.println(customer[101][0] + "の名前は" + hashmap.get(customer[101][0])); System.out.println("確認終わり"); // では、m人分のメールアドレスを適当に選んで int m = 1000; String[] keys = new String[m]; for (int j = 0; j < m; j++) keys[j] = customer[rand.nextInt(n)][0]; // 1人ずつ for (int j = 0; j < m; j++){ String key = keys[j]; // 検索してみましょう // TODO String found = null; if (j % 100 == 0) { System.out.println(key + "の名前は" + Objects.toString(found, "不明")); } } } }線形探索
3.9秒です。遅い!
https://ideone.com/GIle7V// TODOだった場所 String found = null; for (int i = 0; i < n; i++) { if (Objects.equals(key, customer[i][0])) { found = customer[i][1]; } }二分探索
1秒です。そもそもデータ用意が0.9秒だったので、検索自体にほとんど時間がかかっていません
https://ideone.com/eF7Txv// TODOだった場所 String found = null; keyCustomer[0] = key; int index = Arrays.binarySearch(customer, keyCustomer, (c1, c2) -> c1[0].compareTo(c2[0])); found = customer[index][1];ハッシュ法
0.93秒です。ほぼ全く時間がかかりません
https://ideone.com/67PzQP// TODOだった場所 String found = null; found = hashmap.get(key);二分探索(1024倍)
二分探索とハッシュ法の差が誤差レベルだったので、
検索回数(m)を1024倍にして比較してみましょう。
二分探索は1.69秒です。
https://ideone.com/ppG31dハッシュ法(1024倍)
ハッシュ法の検索回数(m)も1024倍にしてみましょう。
1.16秒です。
https://ideone.com/ppG31d
二分探索よりも、検索キーの増加に対して実行時間の伸びが緩やか。計算量の差です探索って実際に開発で使うの?
初学者が意識する機会は少ないでしょうが、利用しています。
データベースで注文履歴一覧を検索する状況を考えてみましょう。SQLでcustomer顧客テーブル(1万件超)にorder注文テーブル(1万件超)とorder_detail注文明細テーブル(1万件超)を結合して明細を取得して、さらにproduct商品テーブル(1万件超)を結合して商品名を取得します。
あなたがこのSQLを実行して現実的な時間で終了するのであれば、DB管理者が適切な主キー制約/一意制約/インデックスなどを設定して、DBがそれに基づいて二分探索(っぽいもの)に使う木構造データやハッシュ法に使うハッシュ表を事前に用意して、SQL実行時に利用されているのでしょう。
なお現場では、DB定義が抜けているために処理が遅い/SQLのテーブル結合条件が複雑なため線形探索しかできず、遅い/本番環境で動かすまでそれらの問題に気づかない/改善余地はあるが放置される、といった不幸な状況が多く発生します。
あなたの担当の外にも疑わしい箇所がある、ということは知っておいてください。Hope this helps.
その他、参考
線形探索(リニアサーチ)とは - IT用語辞典 e-Words
二分探索(2分探索)とは - IT用語辞典 e-Words
ハッシュ法(ハッシュ探索)とは - IT用語辞典 e-Words
線型探索 - Wikipedia
二分探索 - Wikipedia