質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

1回答

371閲覧

sortが行われている様子が分かりません。どのように処理が流れているのでしょうか?

gyro16

総合スコア89

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2017/07/08 05:52

編集2017/07/08 08:22

###前提・実現したいこと

for(compLen =1; compLen < idx.size() * 2; compLen *= 2){ Collections.sort(idx, new strIndexComp());

ここで行われている処理が追えません。
変数compLenが1から流れていって、sortしている様子が分かりません。

compare()が使われている様子が分かりません。
compareが明示的に使われていないので、なおさら分かりにくいです。

このプログラムは文字列t に、q個の与えられる文字列が含まれているかを判定するもので、
含まれていれば 1、含まれていなければ 0を表示するものです。

###発生している問題・エラーメッセージ

エラーメッセージ

###該当のソースコード

java

1 2import java.util.*; 3 4public class Algo51{ 5 public static void main(String[] args){ 6 7 Scanner scan = new Scanner(System.in); 8 String t = scan.next(); 9 StringIndex si = new StringIndex(t, false); 10 11 int q = scan.nextInt(); 12 for(int i = 0; i < q; i++) 13 if(si.isExist(scan.next(), t)) 14 System.out.println("1"); 15 else 16 System.out.println("0"); 17 18 scan.close(); 19 System.exit(0); 20 } 21} 22 23class StringIndex{ 24 class StIdx{ 25 int pos; 26 char ch; 27 28 public StIdx(int i, char c){ 29 pos = i; 30 ch = c; 31 } 32 } 33 34 List<StIdx> idx = new ArrayList<StIdx>(); 35 int[] seq; 36 int compLen = 1; 37 boolean debug; 38 39 public StringIndex(String t, boolean d){ 40 debug = d; 41 42 seq = new int[t.length()]; 43 for(int i = 0; i < t.length(); i++) 44 idx.add(new StIdx(i, t.charAt(i))); 45 46 for(compLen =1; compLen < idx.size() * 2; compLen *= 2){ 47 Collections.sort(idx, new strIndexComp()); 48 49 int[] tmp = new int[seq.length]; 50 51 tmp[idx.get(0).pos] = 1; 52 for(int i = 1; i < tmp.length; i++) 53 if(idxComp(idx.get(i-1), idx.get(i)) == 0) 54 tmp[idx.get(i).pos] = tmp[idx.get(i-1).pos]; 55 else 56 tmp[idx.get(i).pos] = tmp[idx.get(i-1).pos] + 1; 57 58 for(int i = 0; i < seq.length; i++) 59 seq[i] = tmp[i]; 60 61 if(debug){ 62 System.out.println("------------"); 63 for(int i = 0; i < idx.size(); i++) 64 System.out.println(i + "\t" + seq[idx.get(i).pos] + "\t" + idx.get(i).pos + "\t" 65 + t.substring(idx.get(i).pos)); 66 } 67 } 68 } 69 70 class strIndexComp implements Comparator<StIdx>{ 71 72 @Override 73 public int compare(StIdx o1, StIdx o2){ 74 return idxComp(o1, o2); 75 } 76 } 77 78 private int idxComp(StIdx o1, StIdx o2){ 79 if(compLen == 1) 80 if(o1.ch > o2.ch) 81 return 1; 82 else if(o1.ch == o2.ch) 83 return 0; 84 else 85 return -1; 86 87 if(seq[o1.pos] > seq[o2.pos]) 88 return 1; 89 if(seq[o1.pos] == seq[o2.pos]){ 90 int npos1 = o1.pos + compLen / 2; 91 int npos2 = o2.pos + compLen / 2; 92 int nseq1 = 0, nseq2 = 0; 93 if(npos1 < seq.length) 94 nseq1 = seq[npos1]; 95 if(npos2 < seq.length) 96 nseq2 = seq[npos2]; 97 if(nseq1 > nseq2) 98 return 1; 99 else if(nseq1 == nseq2) 100 return 0; 101 else 102 return -1; 103 } 104 return -1; 105 } 106 107 public boolean isExist(String p, String t){ 108 int low = 0, hi = idx.size() - 1; 109 return (findBin(p, t, low, hi)); 110 } 111 112 private boolean findBin(String p, String t, int low, int hi){ 113 if(low > hi) 114 return false; 115 int i = low + (hi - low) / 2; 116 int len = p.length(); 117 if(len > t.length() - idx.get(i).pos) 118 len = t.length() - idx.get(i).pos; 119 120 int r = p.substring(0, len).compareTo(t.substring(idx.get(i).pos, idx.get(i).pos + len)); 121 if(r == 0) 122 if(len == p.length()) 123 return true; 124 else 125 return findBin(p, t, i+1, hi); 126 else if(r < 0) 127 return findBin(p, t, low, i-1); 128 else 129 return findBin(p, t, i+1, hi); 130 } 131}

###試したこと
課題に対してアプローチしたことを記載してください

###補足情報(言語/FW/ツール等のバージョンなど)
より詳細な情報

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

KSwordOfHaste

2017/07/08 06:08 編集

前半のコード(タグ```で囲まれていない部分)は後半のコードに含まれているようなので冗長ではないでしょうか?質問文にある不要な部分を整理した方がよいと思います。
KSwordOfHaste

2017/07/08 07:52

質問したいポイントがStringIndexクラスの機能の方なのであれば確かに難しい機能だと思います。しかしsortとComparatorの関係については比較的単純です。疑問点はStringIndexクラスの機能の方でしょうか?それともsortとComparatorの関係でしょうか?
gyro16

2017/07/08 08:19

Comparatorに従ってsortする感覚は分かりますが、Overrideされているcompareが明示的に使われていないのでどう回しているか分かりません。
guest

回答1

0

ベストアンサー

コード上にstrIndexComp#compareの呼び出しは出てきませんが、それはsortメソッドの実装内部から呼び出されます。List#sortは内部でなんらかのアルゴリズム(Oracle提供のJavaの標準ライブラリーではマージソートを用いているようです)に従って要素を並べ替えますが、どのようなアルゴリズムで並べ替えるにせよ、要素ごとの比較をしなければならない場面が出てきます。その際にsort内部からstrIndexComp#compareが呼び出されます。

実際の実装とは違いますが例えばList#sortが選択ソートアルゴリズムで実装されていたときのコードのイメージを示してみますと以下のようになります。つまり、ソートの途中で必要な回数だけcompareが呼び出されるわけです。

java

1public interface List<E> extends Collection<E> { 2 default void sort(Comparator<? super E> c) { 3 for (int i = 0; i < size() - 1; i++) { 4 E min = get(i); 5 int minIndex = i; 6 for (int j = size(); --j > i; ) { 7 E e = get(j); 8 if (c.compare(min, e) > 0) { // <= このように呼び出される 9 min = e; 10 minIndex = j; 11 } 12 } 13 if (minIndex != i) { 14 set(minIndex, get(i)); 15 set(i, min); 16 } 17 } 18 } 19}

投稿2017/07/08 08:43

KSwordOfHaste

総合スコア18392

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

gyro16

2017/07/11 08:13

ありがとうございました。チャートを追うことができました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問