Hatena::ブログ(Diary)

papamitra RSSフィード

2008-12-12

[] ランダムソート 補足

前回sort_by{ rand }っていうのがでてきたけど間違えてsort_by{ rand n }とかやってしまうと台無しに。

irb(main):001:0> result = Hash.new(0)
=> {}
irb(main):002:0> 1.upto(7000) {result[[0,1,2,3,4,5,6].sort_by{rand 7}[0]] += 1}
=> 1
irb(main):003:0> Array(result).sort.each {|key,val| puts "%d %d" % [key, val]}
0 1535
1 600
2 795
3 1111
4 868
5 757
6 1334
=> [[0, 1535], [1, 600], [2, 795], [3, 1111], [4, 868], [5, 757], [6, 1334]]

容易に同じ数が出るようだと結果が偏ってしまう。

引数なしのrandなら0.0〜1.0のFloatが返るからまず実用上は問題なさげ。

2008-12-11

[]ランダムソート

誰が「ソートするときに比較関数に『ランダムに1か-1を返す関数』を与えたらシャッフルできる」って言い出したのかしらないけど、真に受ける方も真に受ける方だと思う。

ランダムソート(笑)とは

幸い使用したことはないけど、以前なにかの書籍で読んでそのまま鵜呑みにしたことがあるなぁ。。。

どの書籍で読んだのだろうと探してみてまず見つかったのが、『Rubyクックブック』p.53の例

module Enumerable
  def each_randomly
    (sort_by { rand }).each { |e| yield e}
  end
end

ぱっとみて「あ、これだ」と思ったけどsortじゃなくてsort_byなので大きく偏ることはなさそう。ただ厳密な意味でランダムかというと、たまたまrandが同じ数字を返したときとか微妙な気もする。

次に見つけたのが某Ruby書の監注にあった例

sort {.5 <=> rand }

うーん、ダメそう。

irb(main):001:0> result = Hash.new(0)
=> {}
irb(main):002:0> 1.upto(7000) {result[[0,1,2,3,4,5,6].sort{ 0.5 <=> rand}[0]] += 1}
=> 1
irb(main):003:0> Array(result).sort.each {|key, val| puts "%d %d" % [key, val]}
0 1114
1 958
2 1042
3 693
4 1172
5 967
6 1054
=> [[0, 1114], [1, 958], [2, 1042], [3, 693], [4, 1172], [5, 967], [6, 1054]]

先頭に3が全然こないよ。

もともと件の書籍ではランダム化の方法として

class Array
  def randomize!
    result = collect {slice! (rand length)}
    replace result
  end
end

というのが紹介されていて、本文に「もし読者がこれよりうまい方法を見つけたら、ぜひ私たちに教えてください。」とあり、それに対する監注として上の例が挙げられていたので、まんまと釣られてしまったというところなのだろうか。

2008-05-24

[] 抽象名前空間 - Rubyの場合

前回の続き。Rubyではどうやって抽象名前空間に接続するかという話。


RubyにはD-Busモジュールがあるので、てっきり普通に抽象名前空間で接続可能かとおもったら、

irb(main):002:0> require 'socket'
=> true
irb(main):003:0> socket = Socket.new(Socket::Constants::PF_UNIX, Socket::Constants::SOCK_STREAM, 0)
=> #<Socket:0xb7c8d3d8>
irb(main):004:0>  socket.connect(Socket.pack_sockaddr_un("\0/tmp/dbus-WIZUTq6875"))
ArgumentError: string contains null byte
    from (irb):4:in `pack_sockaddr_un'
    from (irb):4
    from /usr/bin/irb1.9:12:in `<main>'

見事に失敗。(前回とパス名が違うのはPC再起動したから)

じゃあD-Busモジュールはどうやって接続してるのかとソースを眺めてみたら、なんとsockaddr_unに対応する文字列を直に作成してconnectに渡していた。

つまりこういうこと。

irb(main):005:0> socket.connect("\x1\0\0/tmp/dbus-WIZUTq6875")
=> 0 #接続成功

先頭の"\x1\0"は(リトルエンディアンでの)AF_UNIXに対応している。

なるほど、そもそもpack_sockaddr_unも文字列を返すメソッドなのね。RubyすごいよRuby。。。

2006-06-25

[][] hw-howm.rb 0.1.0

微妙に修正。

はてダラファイルにhowmファイル名を"><!--hoge.howm--><"のように埋め込んでたけど、これがよろしくないらしい。RSSにしたとき"<"がゴミとして入ってきてしまう。

たぶんはてな側のバグだとおもうけど、よくよく考えるとpタグ停止記法を使う理由もないのでファイル名埋め込みには"<!-- -->"を使うことにする。


以下本体

#!/usr/bin/ruby -w
#
# hw-howm.rb -- howmメモをhw.plで扱える形式にする.
#
require "optparse"
require "fileutils"
require "find"
require "pathname"

begin
  opt = OptionParser.new
  OPTS = {}
  opt.banner= "usage: #$0 [options] src"
  opt.on_tail("-h", "--help", "show this message") {puts opt; exit 0}
  opt.on("-t", "--timestamp=FILE", "use FILE as timestamp (default: none)") {|v| OPTS[:t] = v} # touch file path
  opt.on("-g", "--group=GROUP", "assume group name"){|v| OPTS[:g] = v}
  opt.on("-o", "--outputdir=DIR", "output file in DIR (default: .)"){ |v| OPTS[:o] = v }
  opt.version = "0.1.0"
  opt.release = nil
  opt.parse!(ARGV)
rescue OptionParser::InvalidOption, OptionParser::MissingArgument
  puts $!
  puts opt
  exit 1
end

if ARGV.size == 0
  puts opt
  exit 1
end

updir = OPTS.key?(:o) ? OPTS[:o] : '.'
unless FileTest.directory? updir
  puts "invalid directory: #{dir}"
  puts opt
  exit 1
end

touch_file = ""
if OPTS.key?(:t) && FileTest.file?(OPTS[:t])
  touch_file = OPTS[:t]
end
TOUCH_MTIME = (touch_file == "") ? Time.at(0) : File.mtime(touch_file)

ARG_GROUP = OPTS.key?(:g) ? OPTS[:g] : ""

IN_NOOP = :IN_NOOP
IN_BODY = :IN_BODY
IN_DIARY = :IN_DIARY

# howmファイルの読み込み
def readhowm (path, def_date)

  status = IN_NOOP
  howm_content = Hash.new("")

  date = ""
  path.each_line do |line|    
    case status
    when IN_NOOP
      if line =~ /^= .*\{hw(:(.*))?(?=\})/
        date = def_date
        group = ""
        if !$2.nil? 
          $2.split(',').each do |str|
            str.strip!
            if str =~ /(\d{4}-\d{2}-\d{2})/
              date = $1
            elsif str =~ /g=(.*)/
              group = $1.strip
            end
          end
        end
        howm_content[date] += ""
        status = IN_BODY if ARG_GROUP == group
      end

    when IN_BODY
      if line =~ /^=( |$)/
        status = IN_NOOP
        redo
      end

      if line =~ /^%%%/
        status = IN_DIARY
        next
      end

    when IN_DIARY
      if line =~ /^=( |$)/
        status = IN_NOOP
        redo
      end

      # EOF対策。改行で終らせる。
      line += "\n" if line[-1] != ?\n
      howm_content[date] += line
    end
  end

  return howm_content
end

def scan_files(array, &block)
  array.each do |p|
    path = Pathname.new(p)
    path.find {|path| block.call(path)}
  end
end

# メインの処理
scan_files(ARGV) do |path|
  next unless path.readable?()

  # touchファイルより新しいか
  next if TOUCH_MTIME > path.mtime()

  # *.howmファイルのみ対象
  next unless /\.howm$/ =~ path.to_s

  filename = path.basename().to_s

  # ファイル名の先頭がYYYY-MM-DDならその日付を日記日付のデフォルトとして使用
  if /^(\d{4}-\d{2}-\d{2}).*\.howm$/ =~ filename
    def_date = $1
  else
    def_date = path.mtime().strftime("%Y-%m-%d")
  end

  # howmファイルの内容をハッシュに読みこみ
  howm_content = readhowm(path, def_date)

  howm_content.keys.each do |date|
    # はてダラファイル記事格納用ハッシュ
    hatena_content = Hash.new("")

    # はてダラファイルの先頭部分はhatena_content["0"]に格納
    key = "0"
    # はてダラファイルの内容をハッシュに格納
    uppath = "#{updir}/#{date}.txt"
    if FileTest.file?(uppath)
      File.foreach(uppath) do |line|
        if /^<!--(\d{4}-\d{2}-\d{2}.*\.howm)-->$/ =~ line
          key = $1
          next
        end
        hatena_content[key] += line
      end
    elsif FileTest.exist?(uppath)
      puts "#{uppath} is not file."
      next
    end

    # はてダラファイルもなく内容が空の場合はファイル出力しない
    next if !hatena_content.key?("0") and howm_content[date] == ""

    # はてダラファイルがなかったとき
    # とりあえずファイルの先頭は空行にしておく
    hatena_content["0"] = "\n" unless hatena_content.key?("0")

    if !hatena_content.key?(filename) or hatena_content[filename] != howm_content[date]
      hatena_content[filename] = howm_content[date]
      # はてダラファイルへ書き込み
      File.open(uppath, "w+") do |io|
        io << hatena_content["0"]
        hatena_content.keys.sort.each do |key|
          if key != "0" && hatena_content[key] != ""
            io << "<!--#{key}-->\n"
            io << hatena_content[key]
          end
        end
      end
    end
  end

end

# touch
if OPTS.key?(:t)
    FileUtils.touch(OPTS[:t])
end

exit 0

マイナーバージョン番号が上ってますがあんまり意味はないです。

2006-06-24

[][] hw-howm.rb 0.0.5

id:sshiの助言で仕様変更。


  • 引数は全てhowmファイルまたはhowmファイルがあるディレクトリとして解釈。
  • はてダラファイルを格納するディレクトリは-oオプションで指定(デフォルトはカレントディレクトリ)。

以下本体

#!/usr/bin/ruby -w
#
# hw-howm.rb -- howmメモをhw.plで扱える形式にする.
#
require "optparse"
require "fileutils"
require "find"
require "pathname"

begin
  opt = OptionParser.new
  OPTS = {}
  opt.banner= "usage: #$0 [options] src"
  opt.on_tail("-h", "--help", "show this message") {puts opt; exit 0}
  opt.on("-t", "--timestamp=FILE", "use FILE as timestamp (default: none)") {|v| OPTS[:t] = v} # touch file path
  opt.on("-g", "--group=GROUP", "assume group name"){|v| OPTS[:g] = v}
  opt.on("-o", "--outputdir=DIR", "output file in DIR (default: .)"){ |v| OPTS[:o] = v }
  opt.version = "0.0.5"
  opt.release = nil
  opt.parse!(ARGV)
rescue OptionParser::InvalidOption, OptionParser::MissingArgument
  puts $!
  puts opt
  exit 1
end

if ARGV.size == 0
  puts opt
  exit 1
end

updir = OPTS.key?(:o) ? OPTS[:o] : '.'
unless FileTest.directory? updir
  puts "invalid directory: #{dir}"
  puts opt
  exit 1
end

touch_file = ""
if OPTS.key?(:t) && FileTest.file?(OPTS[:t])
  touch_file = OPTS[:t]
end
TOUCH_MTIME = (touch_file == "") ? Time.at(0) : File.mtime(touch_file)

ARG_GROUP = OPTS.key?(:g) ? OPTS[:g] : ""

IN_NOOP = :IN_NOOP
IN_BODY = :IN_BODY
IN_DIARY = :IN_DIARY

# howmファイルの読み込み
def readhowm (path, def_date)

  status = IN_NOOP
  howm_content = Hash.new("")

  date = ""
  path.each_line do |line|    
    case status
    when IN_NOOP
      if line =~ /^= .*\{hw(:(.*))?(?=\})/
        date = def_date
        group = ""
        if !$2.nil? 
          $2.split(',').each do |str|
            str.strip!
            if str =~ /(\d{4}-\d{2}-\d{2})/
              date = $1
            elsif str =~ /g=(.*)/
              group = $1.strip
            end
          end
        end
        howm_content[date] += ""
        status = IN_BODY if ARG_GROUP == group
      end

    when IN_BODY
      if line =~ /^=( |$)/
        status = IN_NOOP
        redo
      end

      if line =~ /^%%%/
        status = IN_DIARY
        next
      end

    when IN_DIARY
      if line =~ /^=( |$)/
        status = IN_NOOP
        redo
      end

      # EOF対策。改行で終らせる。
      line += "\n" if line[-1] != ?\n
      howm_content[date] += line
    end
  end

  return howm_content
end

def scan_files(array, &block)
  array.each do |p|
    path = Pathname.new(p)
    path.find {|path| block.call(path)}
  end
end

# メインの処理
scan_files(ARGV) do |path|
  next unless path.readable?()

  # touchファイルより新しいか
  next if TOUCH_MTIME > path.mtime()

  # *.howmファイルのみ対象
  next unless /\.howm$/ =~ path.to_s

  filename = path.basename().to_s

  # ファイル名の先頭がYYYY-MM-DDならその日付を日記日付のデフォルトとして使用
  if /^(\d{4}-\d{2}-\d{2}).*\.howm$/ =~ filename
    def_date = $1
  else
    def_date = path.mtime().strftime("%Y-%m-%d")
  end

  # howmファイルの内容をハッシュに読みこみ
  howm_content = readhowm(path, def_date)

  howm_content.keys.each do |date|
    # はてダラファイル記事格納用ハッシュ
    hatena_content = Hash.new("")

    # はてダラファイルの先頭部分はhatena_content["0"]に格納
    key = "0"
    # はてダラファイルの内容をハッシュに格納
    uppath = "#{updir}/#{date}.txt"
    if FileTest.file?(uppath)
      File.foreach(uppath) do |line|
        if /^><!--(\d{4}-\d{2}-\d{2}.*\.howm)--><$/ =~ line
          key = $1
          next
        end
        hatena_content[key] += line
      end
    elsif FileTest.exist?(uppath)
      puts "#{uppath} is not file."
      next
    end

    # はてダラファイルもなく内容が空の場合はファイル出力しない
    next if !hatena_content.key?("0") and howm_content[date] == ""
     
    # はてダラファイルがなかったとき
    # とりあえずファイルの先頭は空行にしておく
    hatena_content["0"] = "\n" unless hatena_content.key?("0")

    if !hatena_content.key?(filename) or hatena_content[filename] != howm_content[date]
      hatena_content[filename] = howm_content[date]
      # はてダラファイルへ書き込み
      File.open(uppath, "w+") do |io|
        io << hatena_content["0"]
        hatena_content.keys.sort.each do |key|
          if key != "0" && hatena_content[key] != ""
            io << "><!--#{key}--><\n"
            io << hatena_content[key]
          end
        end
      end
    end
  end

end

# touch
if OPTS.key?(:t)
    FileUtils.touch(OPTS[:t])
end

exit 0

howmファイルを正規表現で一括処理するのはヤメ。

Pathnameを使うようにした。