Ruby
algorithm
Web
scraping
NOOBS

対象の数字が分からない時に少ないwhileの回数で目標の数字に辿り着くrubyプログラム

More than 1 year has passed since last update.

qiitaとruby初心者で情報処理科未修です!!アルゴリズム?新しい音楽ジャンルか?

元々何がしたかったかというと、例えばurlでpage=724とか入っていてpage=1から開いて、最後のページ(page=725)になったらfalse返してそれまでのurlをarrayにpushするプログラムを書きたいとする。というか書いて動かした。
そうすると、サーバー側からアタックと判断されて、リクエストを弾かれるようになる。
つまり、スクレイピングできなくなる。
今回の場合qiitaのrubyタグのページの中から「いいね」を多く貰った順にソートして記事のURLを拾うため、とりあえず汎用性考えてページ数を数えるプログラムから作ろうとしてた。
が、2回目動かしたらqiitaのサーバーから拒否されてしまった(当然だ。一瞬で700回以上サーバーにリクエストしたことになる。そもそもスクレイピングやめろとか言われると困ってしまうけど)
当然、qiita以外でも発生する問題になる。サーバー側にも負荷がかかるし、自分も拾いたい情報を拾えないから面白くない。

前置き長くなりすぎた。

それでこのプログラムは変数iが不明の場合、そのiに対してなるべく少ないアクセス回数でページがあるか判断するプログラム、を作るためのプロトタイプです。
変数iが不明の場合、なるべく少ない変数iへのアクセス回数で、変数iを求めるプログラム。

冒頭の問題のプログラムがこれ。(1..3).timesの部分は元々(1..100).timesだった。これはだいぶ良くない。
これはrubyでURL先が本当に存在するか確認する方法を参考にして書いた。

page_counter.rb
#page_counter.rb

require 'net/http'
require 'pp'

urls = []
(1..3).each do |page|
    urls << "http://qiita.com/tags/Ruby/likes?page=#{page}"
end

page_num = 0
urls.each_with_index do |url, page_num|
    response = Net::HTTP.get_response(URI.parse(url))
    if response == Net::HTTPSuccess
        puts "#{page_num+1}ページある"
    elsif response == Net::HTTPRedirection
        puts "ページない"
        break
    else
        puts "なんかエラー"
        break
    end
end

で、表題の、プログラムがこれ。
これは作りかけだけどなんとか対処ができそうな気がする。
できなかったらまた別の方法考える。

smaller_number_of_loop.rb
#smaller_number_of_loop.rb

i = 30
n = 1
counter = 1

p n if i == n

while i >= n
  counter += 1
  p "a"
  n *= 2
  if i == n
    counter += 1
    p "b"
    p counter
    exit
  end 
  if i <= n
    while i <= n
       counter += 1
       p "c"
       n -= 1
      if i == n
        counter += 1
        p "d"
        p counter
        p n
        exit
      end
    end
  end
end

もっと綺麗に書けると思うけど、これ動いたところで力尽きた...
nを2倍していってiを超えたら1ずつ減らす。
問題は、iが1024を超えた場合とか。
例えば、1200ページあると、2の10乗の1024、の次、2の11乗の2048から848回デクリメントしないと辿り着かないことになる。
もちろんデクリメントの数も2乗していけばいいんだけど、
(デクリメントしすぎたら今度は1ずつインクリメントする。なんかアホらしい気もするけど...)
プログラミングスキル不足、というか書いてて頭使いすぎた。
4時間くらいこの実装に時間かかった。理論としては良いけど、実装する能力が低すぎる。
こういうのを書くコツ教えてください。

これの手本になったのは、rubyのメモリ確保が=はその都度メモリ確保だけど、<<なら足りなかった場合倍のメモリ確保するっていう仕組みから。あれはちょっと感動した。

多分、こういう処理するためのもっと適したアルゴリズムとか実装って既にあると思うんだけど、知らなかったので頭使って書いた。

あと、みなさんコメント本当に嬉しいです。ありがとうございます。