LoginSignup
0
1

More than 5 years have passed since last update.

@kazokmr(kazo)

経路探索プログラムをTDDで書いてリファクタリングしてみた

Posted at

TDDのスキルアップに、こちらのブログでまとめられていたお題のいくつかを試していて、経路探索を進めている途中で、個人的にスッキリするリファクタリングが出来たので、記録用にまとめておきます。

なお、課題は４までの実施で、ここでは３から４におけるリファクタリングを記述しています。

前準備

開発環境

Java

OpenJDK 11を利用。 macなのでhome brew cask javaでインストールしたもの

Maven

3.6.0を利用。こちらもhomebrewでインストールした

IDE

IntelliJ IDEA 2018.3を利用

プロジェクトの設定で、上記のOpenJDKやMavenで実行するように設定

プロジェクト設定

テストはJUnit5、アサーションにAsserJを使うようにPomを設定した

pom.xml
<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>myTest</groupId>
    <artifactId>myTest</artifactId>
    <version>1.0-SNAPSHOT</version>
    <packaging>jar</packaging>
    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <java.version>11</java.version>
    </properties>
    <build>
        <plugins>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <version>3.8.0</version>
                <configuration>
                    <source>${java.version}</source>
                    <target>${java.version}</target>
                </configuration>
            </plugin>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-surefire-plugin</artifactId>
                <version>2.22.1</version>
            </plugin>
        </plugins>
    </build>
    <dependencies>
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-api</artifactId>
            <version>5.3.2</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>org.junit.jupiter</groupId>
            <artifactId>junit-jupiter-engine</artifactId>
            <version>5.3.2</version>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>org.assertj</groupId>
            <artifactId>assertj-core</artifactId>
            <version>3.11.1</version>
            <scope>test</scope>
        </dependency>
    </dependencies>
</project>

テストコード

課題４までのテストコード

TrainPathTest.java
import static org.assertj.core.api.Assertions.assertThat;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

class TrainPathTest {

  private TrainPath trainPath;

  @BeforeEach
  void createTrainPath() {
    trainPath = new TrainPath();
  }

  @Test
  @DisplayName("横浜から大島は電車で行けない")
  void cannotFromYokohamaToOshima() {
    assertThat(trainPath.exist("横浜", "大島")).as("横浜から大島へは行けない").isFalse();
  }

  @Test
  @DisplayName("大島から横浜は電車で行けない")
  void cannotFromOshimaToYokohama() {
    assertThat(trainPath.exist("大島", "横浜")).as("大島から横浜へは行けない").isFalse();
  }

  @Test
  @DisplayName("横浜から東京は電車で行ける")
  void canGoFromYokohamaToTokyo() {
    assertThat(trainPath.exist("横浜", "東京")).as("横浜から東京へ行ける").isTrue();
  }

  @Test
  @DisplayName("東京から横浜は電車で行ける")
  void canGoFromTokyoToYokohama() {
    assertThat(trainPath.exist("東京", "横浜")).as("東京から横浜へ行ける").isTrue();
  }

  @Test
  @DisplayName("東京から大宮は電車で行ける")
  void canGoFromTokyoToOmiya() {
    assertThat(trainPath.exist("東京", "大宮")).as("東京から大宮へ行ける").isTrue();
  }

  @Test
  @DisplayName("大宮から東京は電車で行ける")
  void canGoFromOmiyaToTokyo() {
    assertThat(trainPath.exist("大宮", "東京")).as("大宮から東京へ行ける").isTrue();
  }

  @Test
  @DisplayName("大宮から横浜は電車で行ける")
  void canGoFromOmiyaToYokohama() {
    assertThat(trainPath.exist("大宮", "横浜")).as("大宮から横浜は行ける").isTrue();
  }

  @Test
  @DisplayName("横浜から大宮は電車で行ける")
  void canGoFromYokohamaToOmiya() {
    assertThat(trainPath.exist("横浜", "大宮")).as("横浜から大宮は行ける").isTrue();
  }

  @Test
  @DisplayName("川崎から赤羽は電車で行ける")
  void canGoFromKawasakiToAkabane() {
    assertThat(trainPath.exist("川崎", "赤羽")).as("川崎から赤羽は行ける").isTrue();
  }
}

プロダクションコード

クラスは２つ

  1. TrainPath.java 経路探索を実行する
  2. Section.java 経路を情報を持つ

課題３　横浜から大宮間は直接繋がっていなくても、東京で繋がっているのでたどり着く

悩んだポイント

  • 一つの経路では辿り着けないので、経由地を取りながら繰り返し探索したところ
  • 一度探索した経路は探索し直さないこと
TrainPath.java
import java.util.ArrayList;
import java.util.List;

class TrainPath {

  private final List<Section> sectionList;

  TrainPath() {
    sectionList = new ArrayList<>();
    sectionList.add(new Section("横浜", "東京"));
    sectionList.add(new Section("東京", "大宮"));
  }

  boolean exist(String departure, String destination) {

    List<String> stations = new ArrayList<>();
    stations.add(departure);

    while (true) {
      List<String> transitList = new ArrayList<>();

      for (String startStation : stations) {
        for (Section section : sectionList) {
          if (section.isSearched()) {
            continue;
          }
          if (section.exist(startStation, destination)) {
            return true;
          }
          String transit = section.getTargetStation(startStation);
          if (transit == null) {
            continue;
          }
          if (transitList.contains(transit)) {
            continue;
          }
          transitList.add(transit);
          section.setSearched();
        }
      }
      if (transitList.isEmpty()) {
        return false;
      }

      stations.clear();
      stations = new ArrayList<>(transitList);
    }
  }
}
Section.java
class Section {
  private String station1;
  private String station2;
  private boolean searched;

  Section(String station1, String station2) {
    this.station1 = station1;
    this.station2 = station2;
    this.searched = false;
  }

  boolean exist(String departure, String destination) {
    if (station1.equals(departure) && station2.equals(destination)) {
      return true;
    }
    return station2.equals(departure) && station1.equals(destination);
  }

  String getTargetStation(String station) {
    if (station.equals(this.station1)) {
      return this.station2;
    } else if (station.equals(this.station2)) {
      return this.station1;
    }
    return null;
  }

  boolean isSearched() {
    return searched;
  }

  void setSearched() {
    this.searched = true;
  }
}

課題３のリファクタリング

TrainPathのWhile文の処理をメソッド分割

  • for文のネストの内側をexistSectionメソッドに分ける
  • さらに経由地の取得処理もexistTransitメソッドに分ける

メソッドを分割したことで、分かり易くなったと思う。

TrainPath.java
import java.util.ArrayList;
import java.util.List;

class TrainPath {

  private final List<Section> sectionList;
  private List<String> transitList;

  TrainPath() {
    sectionList = new ArrayList<>();
    initializeSection();
  }

  boolean exist(String departure, String destination) {

    List<String> stations = new ArrayList<>();
    stations.add(departure);

    while (true) {
      transitList = new ArrayList<>();
      for (String station : stations) {
        if (existSection(station, destination)) return true;
      }
      if (transitList.isEmpty()) return false;
      stations = new ArrayList<>(transitList);
    }
  }

  // 出発地から目的地への直通経路があるか検索する
  // 直通経路が無ければ経由地があるか検索する
  private boolean existSection(String departure, String destination) {
    for (Section section : sectionList) {
      if (section.isSearched()) continue;
      if (section.exist(departure, destination)) return true;
      existTransit(departure, section);
    }
    return false;
  }
  // 経路から経由地を検索する
  private void existTransit(String departure, Section section) {
    String transit = section.getTargetStation(departure);
    if (transit == null) return;
    if (transitList.contains(transit)) return;
    transitList.add(transit);
    section.setSearched();
  }

  private void initializeSection() {
    sectionList.add(new Section("横浜", "東京"));
    sectionList.add(new Section("東京", "大宮"));
  }
}

課題４　色々な場所に行けることを確認する

課題３の時点で、実現が出来ていたので、経路リストを追加することでテストもパスできた

TrainPath.java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class TrainPath {

  private final List<Section> sectionList = new ArrayList<>();
  private List<String> transitList;

  TrainPath() {
    initializeSection();
  }

  boolean exist(String departure, String destination) {

    List<String> stations = Collections.singletonList(departure);

    while (true) {
      transitList = new ArrayList<>();
      for (String station : stations) {
        if (existSection(station, destination)) return true;
      }
      if (transitList.isEmpty()) return false;
      stations = new ArrayList<>(transitList);
    }
  }

  // 出発地から目的地への直通経路があるか検索する
  // 直通経路が無ければ経由地があるか検索する
  private boolean existSection(String departure, String destination) {
    for (Section section : sectionList) {
      if (section.isSearched()) continue;
      if (section.exist(departure, destination)) return true;
      existTransit(departure, section);
    }
    return false;
  }
  // 経路から経由地を検索する
  private void existTransit(String departure, Section section) {
    String transit = section.getTargetStation(departure);
    if (transit == null) return;
    if (transitList.contains(transit)) return;
    transitList.add(transit);
    section.setSearched();
  }

  private void initializeSection() {
    sectionList.add(new Section("横浜", "武蔵小杉"));
    sectionList.add(new Section("横浜", "川崎"));
    sectionList.add(new Section("武蔵小杉", "西国分寺"));
    sectionList.add(new Section("武蔵小杉", "渋谷"));
    sectionList.add(new Section("武蔵小杉", "川崎"));
    sectionList.add(new Section("川崎", "東京"));
    sectionList.add(new Section("西国分寺", "南浦和"));
    sectionList.add(new Section("西国分寺", "新宿"));
    sectionList.add(new Section("渋谷", "新宿"));
    sectionList.add(new Section("渋谷", "東京"));
    sectionList.add(new Section("東京", "お茶の水"));
    sectionList.add(new Section("東京", "秋葉原"));
    sectionList.add(new Section("新宿", "池袋"));
    sectionList.add(new Section("新宿", "お茶ノ水"));
    sectionList.add(new Section("お茶の水", "秋葉原"));
    sectionList.add(new Section("秋葉原", "田端"));
    sectionList.add(new Section("池袋", "赤羽"));
    sectionList.add(new Section("池袋", "田端"));
    sectionList.add(new Section("田端", "赤羽"));
    sectionList.add(new Section("赤羽", "南浦和"));
    sectionList.add(new Section("南浦和", "大宮"));
  }
}

課題４のリファクタリング (コードの現在の状態)

メソッドを分割はしたものの、強引な感じが否めず、メソッドの責務がハッキリしないなと感じていた。

調べていく中で、コードの再帰呼び出しを知り、これを利用すれば経由値リストが要らなくなるのでは？と思いリファクタリングしてみた。

ポイント

  • 再帰呼び出して、経由地リストを使ったループ処理(while文と外側のfor文)が要らなくなった。
  • 経路検索のロジックを見直し、StreamAPIを使って、for文の前に不要な経路を除外したリストを作成するようにした。

随分スッキリ書けた。
StreamAPIを使って予め探索不要な経路を除外しておくことで、探索処理のfor文内のロジックを判定処理だけに減らすことができた。

StreamAPIのところは、CollectionのremoveIfにすることも検討したが、経由地が変わったときに必要な経路を削除してしまうため、この形にした。

TrainPath.java
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

class TrainPath {

  private final List<Section> sectionList = new ArrayList<>();

  TrainPath() {
    initializeSection();
  }

  boolean exist(String departure, String destination) {
    // 検索しない経路を除外する
    List<Section> filteredSectionList = sectionList.stream()
        .filter(section -> section.isNeedSearch(departure))
        .collect(Collectors.toList());

    for (Section section : filteredSectionList) {
      if (section.exist(departure, destination)) return true;
      sectionList.remove(section);

      // 経路の目的地を経由する経路で再検索する
      String transit = section.getDestination(departure);
      if (exist(transit, destination)) return true;
    }
    return false;
  }

  private void initializeSection() {
   // 省略
  }
}

Section.javaでは、TrainPathのStreamAPIのfilter処理の判定ロジックを追加した。

Section.java
class Section {
  private String station1;
  private String station2;

  Section(String station1, String station2) {
    this.station1 = station1;
    this.station2 = station2;
  }

  boolean exist(String departure, String destination) {
    if (station1.equals(departure) && station2.equals(destination)) {
      return true;
    }
    return station2.equals(departure) && station1.equals(destination);
  }

  String getDestination(String departure) {
    if (departure.equals(this.station1)) {
      return this.station2;
    } else if (departure.equals(this.station2)) {
      return this.station1;
    }
    return null;
  }

  boolean isNeedSearch(String departure) {
    return departure.equals(this.station1) || departure.equals(this.station2);
  }
}

まとめ

テストコードを書いておくと安心してリファクタリングできる。
今回、booleanを返すメソッドでロジックを逆に書いてしまったが、テストがfailになることで容易に間違いを発見できた。
今までだと実際に動かしてみたり、デバッグモードでチェックすることで検査していたので時間掛かるし、テストの漏れも多かった。
また、テストコードをデバッグモードで実行してチェックするのも、従来のデバッグモードでの検査よりも問題を検査するポイントが絞れるので修正しやすかった。

親子など関係のあるパラメータを変えながら同じメソッドで処理する場合に、メソッドの再帰呼び出しを使うとコードがシンプルになるので見やすくなる。その反面、慣れないと呼び出し元に返す戻り値がどうなるのか混乱してしまう。

for文の中で行なっていた前処理などを、事前にStreamAPIを使って加工することで、前処理を分岐することができるし、for文でやることがシンプルになるので分かりやすくなる。
本当はfor文の処理を全てStreamAPIにできると良いが、無理せず出来ることだけをStreamAPIに分割するだけでも非常に有効だと感じた。

今回は色々試行錯誤しながらリファクタリングしてみたが、もっと良い書き方はあるような気がする。ただそれに気づくにはまだ未熟だと思うし、コードをもっともっと書いて色々知らないといけないと感じました。

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1