Scalaの勉強はじめました 2 〜文字列検索と深さ優先探索〜
はじめに
N予備校の「Scala基礎」を受講しています。
検索
索引型検索
文章の中からあらかじめ単語の文字列を抜き出して、単語ごとに索引を作っておく検索方法
あらかじめインデックスを作るイメージ
非索引型検索
与えられた文字の情報のみを用いて検索を行う
文章を全て走査するので時間がかかる
val text = "ネコネコネコネコイヌイヌイヌイヌネコネコワンコイヌイヌネコネコワンコ".toSeq
val pattern = "ワンコ".toSeq
val matchIndexes = search(text, pattern)
def search(text: Seq[Char], pattern: Seq[Char]): Seq[Int] = {
// 型を明示する
var matchIndexes = Seq[Int]()
// 文字列を検索
for (i <- 0 to text.length - 1){
// i文字目から3文字取り出す
val partText = text.slice(i, i + pattern.length)
if (isMatch(partText, pattern)) {
matchIndexes = matchIndexes :+ i
}
println(partText)
}
matchIndexes
}
isMatch
は検索に引っ掛かればtrue
を返すようにする。
正規表現を使う
val matchIndexes = pattern.r.findAllIn(text).matchData.map(_.start).toList
String
のr
メソッド
文字列を正規表現のRegex型に変換する
findAllIn
Regex
型のメソッドで、与えられた正規表現にマッチするIterator
を取得し、MatchIterator
型を返す
matchData
MatchIterator
のmatchData
フィールド
マッチした文字列に対するさまざまな情報を含む、Iterator[Match]
型を返す
Iterator
イテレータという何らかの要素の集合を巡回しながらアクセスできる型。 巡回可能なコレクションのような振る舞いを提供する。
_.start
Match
型を start: Int というマッチした時の出現箇所のインデックスに変換。_
を使うことで、map
関数を適用しようとしているコレクションの要素のメソッドも呼び出すことができる
深さ優先探索
1 回の呼び出しの中で、数列の 1 番目の要素を「足す場合」と「足さない場合」の 2 つの 再帰呼び出しをすることで、 最終的に全てのパターンを網羅する実装方法
部分和問題
val a = Seq(3, 6, -5, 7)
val n = a.length
val k = 9
def isMatchAndResult(index: Int, partial: Seq[Int]): (Boolean, Seq[Int]) = {
println(s"index: ${index}, partial: ${partial}")
if (index == n){
return if (partial.sum == k)(true, partial) else (false, Seq())
}
val (isMatchNotAdd, resultNotAdd) = isMatchAndResult(index + 1, partial)
if(isMatchNotAdd) return (isMatchNotAdd, resultNotAdd)
isMatchAndResult(index + 1, partial :+ a(index))
}
val (isMatch, result) = isMatchAndResult(0, Seq())
正直これ見てもちょっとわからなかったです。
絵を見てようやく理解できた感じ。
まとめ
再帰呼び出しはそもそも何を実現しようとしているのかを把握しないと、自力で変数の中を追うにも限界があるなと。
Author And Source
この問題について(Scalaの勉強はじめました 2 〜文字列検索と深さ優先探索〜), 我々は、より多くの情報をここで見つけました https://qiita.com/mybrother_jake/items/71449246d27719b1a7e9著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .