なんとな~くしあわせ?の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

Seleniumにおける待ち合わせの概念

Selenium

  • このページの重要な点を翻訳

stackoverflow.com

Implicit Wait(暗黙的待ち合わせ)

  • 暗黙的待ち合わせはウェブドライバーのインスタンスにHTML DOMの要素を見つけたり、要素のグループやコレクションを見つけたりする時に即時利用可能でない場合の待ち合わせの設定をする方法です(※CSSセレクタXpathを実行した際に、要素が出るまで待ってくれる)
  • W3Cの規定によればデフォルト値は0
  • 必要に応じてプログラムのどこからでも設定値を変えられる
  • その設定値はWebdriverのインスタンスの生成から廃棄までの間有効

Explicit Wait(明示的待ち合わせ)

  • 明示的待ち合わせは、コードを実行する前に特定の状態になるまでWebdriverのインスタンスのために設定、実装されるコードのこと
  • WebDriverWaitとExpectedConditionで定義される特定のメソッドと状態は明示的待ち合わせを実装するための一つの手法です

要は

  • この話に従えば、暗黙的待ち合わせさえ設定していれば明示的に待ち合わせる必要ないように見える。しかし実際にはAjaxリクエストを待つときに明示的待ち合わせを書く必要があったりするので例外はあると言える。
  • ちなみにSelenideはデフォルトで4秒の暗黙的待ち合わせになっている

Selenide - Concise UI Tests in Java

プロジェクトオイラーProblem 12を解いてみた

今回はほとんど自力では解けてないので、翻訳実装しただけです。

問題

   三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は:
    
   1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
   となる.
    
   最初の7項について, その約数を列挙すると, 以下のとおり.
    
    1: 1
    3: 1,3
    6: 1,2,3,6
   10: 1,2,5,10
   15: 1,3,5,15
   21: 1,3,7,21
   28: 1,2,4,7,14,28
    
   これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.
    
   では, 500個より多く約数をもつ最初の三角数はいくつか.

解答

五角数を求めるのも、その約数を求めるのも至極簡単なのですが500を超える約数を愚直に求めるとプログラムの実行が終わりません。
結局私はそこの工夫の仕方が思いつかなかったので他者の回答を読むことにしました。

参考にした解答

解答の方法はリンク先の方々に任せるとして、ポイントを載せる。

問題のポイント

アルゴリズム上の工夫:
  • 一度計算した約数の個数は、保存しておいて再利用する
  • もし、nや(n+1)/2等の数が、再び m(m+1)のかたちで表せるなら、前出の式が再び適用できる(このパターンは意外に多い)
メモ
  • 約数F(n)F(m)は互いに素(!)なので、掛け算で求められる。
    • ここはマジで思いつかなかった、掛け算で求められるので約数自体を保存しておく必要はなく数だけ数えればよい。
  • nや(n+1)/2等の数が、再び m(m+1)のかたちで表せる
    • これを求める方法がわからなかったのだが、コードを見れば一目瞭然、nの平方根を求め+1で掛け算したときnになるか見ている

ソースコード

@fact = {1=>1,2=>2}

def num_factors(n)
  return @fact[n] if @fact.has_key?(n)

  r = Math.sqrt(n).to_i
  num = 0
  if r*(r+1)==n
    num = num_factors(r)*num_factors(r+1)
  else
    i=1
    while i<r
      if n % i==0
        num +=1
      end
      i+=1
    end
    num *= 2
    num += 1 if r*r==n
  end
  @fact[n] = num
  return num
end

n = 2
loop {
  if n.even?
    fn = num_factors(n/2) * num_factors(n+1)
  else
    fn = num_factors(n) * num_factors((n+1)/2)
  end

  if fn >= 500
    printf "%d = (%d * %d)/2, it has %d factors", n*(n+1)/2, n, n+1, fn
    break
  end

  @fact[n*(n+1)/2] = fn
  n+=1
}

AtCoder Beginner Contest 009 (辞書式順序ふたたび) を解いてみた

ABC 009 C問題に使われるアルゴリズム要素は貪欲法です。貪欲法自体は定型のアルゴリズムがあるわけではないので、知識ではなく地頭を問う問題です。

  • 問題文
    • 文字列Sとその長さN、そして入れ替えしていい文字数Kが与えられる
    • K文字だけ入れ替えて辞書順で最小になる文字列を求めよ

考え方

7 2
atcoder

の場合、2文字入れ替え可能。答えはactoderになる。文字列を前から順に見ていって、辞書順で最小になるようにすればよい。

疑似コード

  • 解説にある疑似コードをもう少し詳細に書き下してみた
(解説の疑似コード)
T""
for i in 0 to N-1
  for c in (使用可能な文字を辞書順で)
    if (T+cにして大丈夫なら)
      TT + c
      break

(書き下し)
def available(t)
    Sの文字列からtの文字列を除いてソートしたもの

T""
for i in 0 to N-1
  for c in available(t)
    TT + c  // T[i] = c

    k = i文字目まででの変更数
    switch_count, t_tmp = 残り文字列を埋めた時の変更数と文字列を返す

    if k + switch_count == K
        t_tmpを表示して終了
    elsif k + switch_count > K
        # 次の文字を試す
    else
        # 次のiを試す
        break
    end

考えるべきだったこと

  • 辞書順=貪欲法までは思いつくべき
  • 解いてみると意外と愚直なソースになる
  • Kと変更数の関係でバグらせまくった。これは単純に経験不足か…