Hatena::Grouprubyist

Rubyで遊ぶよ

|

2010-01-15

話題のA*とかいうやつ

07:03

A* - Wikipedia を1回読んでから書たけど、この部分は自分の方法とは違った。

  • m の状態に応じて以下の操作を行う
    • m が Openリストにも Closeリストにも含まれていない場合 f*(m) = f '(m) とし m を Openリストに追加する。このとき m の親を n として記録する。
    • m が Openリストにある場合、f '(m) < f*(m) であるなら f*(m) = f '(m) に置き換える。このとき記録してある m の親を n に置き換える。
    • m が Closeリストにある場合、f '(m) < f*(m) であるなら f*(m) = f '(m) として m を Openリストに移動する。また記録してある m の親をn に置き換える。

たぶん自分のやつのほうがメモリを食う気がする。

#!/usr/bin/ruby

class Node
  attr_accessor :x, :y
  attr_accessor :prev
  attr_accessor :accum_cost

  def initialize(x,y,prev)
    @x = x
    @y = y
    @prev = prev || nil
    @accum_cost = prev ? prev.accum_cost + 1 : 0
  end

  def coord
    return [x,y].join(',')
  end
end

class A_star
  def initialize(maze)
    @maze = maze
    start = find_start()
    @open_list = { start.coord => start }
    @closed_list = {}
  end

  def find_start()
    @maze.each_with_index do |row,i|
      j = row.index('S')
      return Node.new(j,i,nil) if j
    end
  end

  def goal?(node)
    return @maze[node.y][node.x] == 'G'
  end

  def movable?(node)
    return @maze[node.y][node.x] != '*'
  end

  def forward(current)
    x = current.x
    y = current.y
    [[1,0],[-1,0],[0,1],[0,-1]].each{|d|
      dx, dy = *d
      next_node = Node.new(x+dx, y+dy, current)
      return next_node if goal?(next_node)
      if movable?(next_node)
        coord = next_node.coord
        next if @closed_list[coord]
        pending = @open_list[coord]
        @open_list[coord] = next_node if !pending || pending.accum_cost > next_node.accum_cost
      end
    }
    @open_list.delete(current.coord)
    @closed_list[ current.coord ] = current
    return nil
  end

  def get_closest()
    next_node = @open_list.first[1]
    @open_list.each_value {|node|
      next_node = node if node.accum_cost < next_node.accum_cost
    }
    return next_node
  end

  def show_result(goal)
    maze = @maze.dup()
    current = goal.prev # no need to mark goal
    while(current)
      maze[current.y][current.x] = '$' if current.prev # no need to mark start
      current = current.prev
    end
    puts maze.map{|row| row.join('')}.join("\n")
  end

  def solve()
    i = 0
    while(true)
      current = get_closest()
      #p [i += 1, current.accum_cost] 
      goal = forward(current)
      return show_result(goal) if goal
    end
  end
end

if $0 == __FILE__
  maze = <<-END.chop.split("\n").map{|row| row.split("")}
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
  END

  A_star.new(maze).solve()
end

そのあとで↓ ku-ma-me さんのやつを見てちびりそうになった。何やってんのかまったくわからない。。


追記

A* で問いたように思ったけど、もしかしたら↓の部分を激しく読み間違えてたのかも…

  • Openリストに格納されているノードの内、最小の f*(n) を持つノード n を取り出す。

自分のだとむしろダイクストラ法になるっぽい?

トラックバック - http://rubyist.g.hatena.ne.jp/edvakf/20100115

2010-01-10

Mac OS X 用、open コマンドの zsh 補完関数

11:33

を作るための ruby スクリプト。アプリケーションフォルダの中身をスキャンして補完関数に埋め込む方針。

その前に2つ準備がいる。

その1。$HOME/.zsh/functions というディレクトリを作成しておく。

その2。zshrc に、

fpath=(~/.zsh/functions ${fpath})
autoload -U compinit
compinit

と書く。(もし autoload -U compinit が既に書かれてる場合は、fpath をそれより上で指定しないとだめ)


準備ができたら、以下のスクリプトを実行する。

#!/usr/bin/ruby

home = ENV['HOME']

$apps = []
def find_apps (dir)
  return unless File.directory?(dir)
  Dir.foreach(dir) do |file|
    if file != '.' && file != '..' && File.directory?(File.join(dir,file))
      if file =~ /^(.*)\.app$/
        $apps.push($1)
      else
        find_apps(File.join(dir,file))
      end
    end
  end
end

['/Applications','/Developer/Applications',"#{home}/Applications"].each do |dir|
  find_apps (dir)
end

filename = "#{home}/.zsh/functions/_open"

str = <<END
#compdef open

_arguments \\
  '-a[open with specified application]:application name:( \\
#{$apps.map{|app| "\"#{File.basename(app)}\""}.join(' ')} \\
)' \\
'-e[open with TexEdit]' \\
'*:files:_files'
END

open(filename, 'w') do |f|
  f.print str
end

そうすると、$HOME/.zsh/functions/_open として以下のようなファイルができる。(うちの場合)

#compdef open

_arguments \
  '-a[open with specified application]:application name:( \
"Address Book" "All2MP3" "AppCleaner" "Automator" "BBT2" "Caffeine" "Calculator" "Chess" "Chromium" "ClamXav" "Dashboard" "Dictionary" "Dropbox" "DTerm" "DVD Player" "EIJIRO Viewer" "ffmpegX" "Firefox" "WMV Player" "Font Book" "Freedom" "Front Row" "GoogleAppEngineLauncher" "UninstallGoogleJapaneseInput" "gyazo" "iCal" "iChat" "Image Capture" "iPaint" "iSync" "iTunes" "LyX" "MacKeyHoleTV" "AquaTerm" "Build Applet" "IDLE" "Python Launcher" "Mail" "Mendeley Desktop" "Microsoft Language Register" "Remove Office" "Microsoft Document Connection" "Microsoft Entourage" "Microsoft Excel" "Microsoft Messenger" "Microsoft PowerPoint" "Microsoft Word" "Alerts Daemon" "Equation Editor" "Microsoft Cert Manager" "Microsoft Chart Converter" "Microsoft Clip Gallery" "Microsoft Database Daemon" "Microsoft Database Utility" "Microsoft Graph" "Microsoft Office Reminders" "Microsoft Office Setup Assistant" "Microsoft Project Gallery" "Microsoft Sync Services" "My Day" "Organization Chart" "OpenOffice.org" "Opera" "Opera1050" "Paintbrush" "Photo Booth" "Preview" "Quicksilver" "QuickTime Player" "Reggy" "RichFLV" "Safari" "Songbird" "Stickies" "System Preferences" "BibDesk" "Excalibur" "LaTeXiT" "TeX Live Utility" "TeXShop" "TeXworks" "TextEdit" "Time Machine" "Activity Monitor" "Adobe AIR Application Installer" "Adobe AIR Uninstaller" "AirPort Utility" "AppleScript Editor" "Audio MIDI Setup" "Bluetooth File Exchange" "Boot Camp Assistant" "ColorSync Utility" "Console" "DigitalColor Meter" "Disk Utility" "Expose" "Grab" "Grapher" "i-Installer" "Java Preferences" "Keychain Access" "Migration Assistant" "Network Utility" "Podcast Capture" "RAID Utility" "Remote Install Mac OS X" "Spaces" "System Profiler" "Terminal" "VoiceOver Utility" "X11" "AU Lab" "HALLab" "Dashcode" "Core Image Fun House" "OpenGL Driver Monitor" "OpenGL Profiler" "OpenGL Shader Builder" "Pixie" "Quartz Composer Visualizer" "Quartz Debug" "Instruments" "Interface Builder" "BigTop" "CHUD Remover" "Reggie SE" "SpindownHD" "Saturn" "MallocDebug" "Quartz Debug" "Shark" "Spin Control" "Quartz Composer" "Accessibility Inspector" "Accessibility Verifier" "Applet Launcher" "Bluetooth Diagnostics Utility" "Bluetooth Explorer" "PacketLogger" "CrashReporterPrefs" "FileMerge" "Help Indexer" "Icon Composer" "IORegistryExplorer" "iSync Plug-in Maker" "Jar Bundler" "Build Applet" "PackageMaker" "Property List Editor" "Build Applet" "SleepX" "Repeat After Me" "SRLanguageModeler" "Syncrospector" "USB Prober" "VisualVM" "Xcode" \
)' \
'-e[open with TexEdit]' \
'*:files:_files'

次に zsh を起動したら補完がきいてるはず。

open のオプションは -a と -e 以外にもいくつかあるけど、それらは考慮してない。あしからず。

トラックバック - http://rubyist.g.hatena.ne.jp/edvakf/20100110

2009-10-14

sqlite3-rubyのエンコーディング問題についてメモ

11:29

簡単なメモ。

こういう問題がある。


SQLite3 のドキュメント (強調したところ) によると、

Support for UTF-8 and UTF-16

The new API for SQLite 3.0 contains routines that accept text as both UTF-8 and UTF-16 in the native byte order of the host machine. Each database file manages text as either UTF-8, UTF-16BE (big-endian), or UTF-16LE (little-endian). Internally and in the disk file, the same text representation is used everywhere. If the text representation specified by the database file (in the file header) does not match the text representation required by the interface routines, then text is converted on-the-fly. Constantly converting text from one representation to another can be computationally expensive, so it is suggested that programmers choose a single representation and stick with it throughout their application.

In the current implementation of SQLite, the SQL parser only works with UTF-8 text. So if you supply UTF-16 text it will be converted.This is just an implementation issue and there is nothing to prevent future versions of SQLite from parsing UTF-16 encoded SQL natively.

When creating new user-defined SQL functions and collating sequences, each function or collating sequence can specify it if works with UTF-8, UTF-16be, or UTF-16le. Separate implementations can be registered for each encoding. If an SQL function or collating sequences is required but a version for the current text encoding is not available, then the text is automatically converted. As before, this conversion takes computation time, so programmers are advised to pick a single encoding and stick with it in order to minimize the amount of unnecessary format juggling.

SQLite is not particular about the text it receives and is more than happy to process text strings that are not normalized or even well-formed UTF-8 or UTF-16. Thus, programmers who want to store IS08859 data can do so using the UTF-8 interfaces. As long as no attempts are made to use a UTF-16 collating sequence or SQL SQLite is not particular about the text it receives and is more than happy to process text strings that are not normalized or even well-formed UTF-8 or UTF-16. Thus, programmers who want to store IS08859 data can do so using the UTF-8 interfaces. As long as no attempts are made to use a UTF-16 collating sequence or SQL function, the byte sequence of the text will not be modified in any way.

SQLite Version 3 Overview
  • テキストは UTF-8UTF-16 で保存できる。
  • もし UTF-16 で保存したテキストを UTF-8 で要求したら、内部で変換される。逆も然り。
    • (UTF-8 で要求とはどういうことだろう?)
  • SQL パーサーは UTF-8 しか受け付けない。
    • 将来は UTF-16 も使えるようにするかも。
  • 実際のところ、UTF-8UTF-16 じゃなくても気にせず受け入れている。

こっちも参考。


現在の最新版はどんな感じか

去年の11月にjamis さんが開発から手を引いて、現在は luislavena さんのところにあるらしい。

しかしけっこうフォークされてて、多くはマージされてないもよう。(たぶん)

f:id:edvakf:20091014094017p:image:w600 f:id:edvakf:20091014093933p:image:w600

Tracker はほぼ機能していないのかと思っていたのだけど、ごく最近あった書き込みにも対応されているっぽい。

とりあえず luislavena さんの master を見る限り、エンコーディングのことは何も気にされてない。


修正するとしたら

  • ASCII-8BIT 文字列で返されて自分で force_encoding しないといけないのは直したい。

基本的にはデータベースのエンコーディングを UTF-8 に決め打ちして、

  • SQL 文、プレースホルダー、共に .encode("UTF-8") する。
  • 結果を .force_encoding("UTF-8") する。

UTF-8 ではないデータベースを開きたいときのために、

  • Database.open 時にエンコーディングを指定できるようにする。
    • エンコーディング指定なしは UTF-8 に。

それだと現在との互換性がなくなるので、とりあえず

  • Database.open 時に「変換しない」オプションを付けるとエンコーディングを変換しないように。(今とまったく同じ)

これで急場を凌げるようにしたらいいんじゃないかな。しかしこのオプションは Not Recommended ということにする。


.force_encoding("UTF-8").encode(Encoding.default_internal) のほうがいいかも? よくわからん。

この結果、各種ライブラリは

  • 基本UTF-8を返せばよい、入力もUTF-8を期待
  • より親切なライブラリはdefault_internalで返す。入力はencodingを見て対処
Re: Encoding.default_internal のためのパッチ

default_internal にしてもいいけど、パフォーマンスを考えるとどうなんだろう?


utf16フラグは

utf16 オプションが付いているかどうかは気にしなくてもいいような気がする。なぜなら、

require 'sqlite3'
idb = SQLite3::Database.open('foobar.db', {:utf16 => true})
db.execute('CREATE TABLE tbl (txt TEXT)')
db.execute('INSERT INTO tbl VALUES (?)', 'aiueo あいうえお'.encode('UTF-16LE'))
db.execute('SELECT * FROM tbl')
#=> [["a"]]

↑ちゃんと保存できてない。(UTF-16 にすると NULL 文字が入るので、そこで切られる)

The new API for SQLite 3.0 contains routines that accept text as both UTF-8 and UTF-16 in the native byte order of the host machine. とあるのにマシンのエンコーディングである UTF-16LE をそのまま入れてもだめというのはどういうことだろう?

そんなわけで、:utf16 => true の場合でも引数 UTF-8 にして、内部の変換にまかせるのがよさそう。

変換はちゃんとされているっぽい。(データベースファイルを strings コマンドで見た)

出力時も UTF-8 バイト列に変換されるっぽい。ただしエンコーディングは ASCII-8BIT。

require 'sqlite3'
db = SQLite3::Database.open('foobar.db', {:utf16 => true})
db.execute('CREATE TABLE tbl (txt TEXT)')
db.execute('INSERT INTO tbl VALUES (?)', 'あいうえお')
p db.execute('SELECT * FROM tbl')
#=> [["\xE3\x81\x82\xE3\x81\x84\xE3\x81\x86\xE3\x81\x88\xE3\x81\x8A"]]
puts db.get_first_value('SELECT * FROM tbl')
#=>あいうえお
puts db.get_first_value('SELECT * FROM tbl').encoding
#=>ASCII-8BIT

実際のところ、utf16 フラグを付けて open したファイルの名前は UTF-16 と解釈される (微妙に違う?) ので、

db = SQLite3::Database.open('foobar.db', {:utf16 => true})

とやってファイルを開くと、UTF-8 のターミナルでは「潦扯牡搮b」("\xE6\xBD\xA6\xE6\x89\xAF\xE7\x89\xA1\xE6\x90\xAEb") になってしまう。foobar.db を開いたつもりが foobar.db じゃないのは混乱の元だと思う。これも直したほうがいいのかも。どうなんだろう?

db = SQLite3::Database.open('foobar.db'.encode('UTF-16LE'), {:utf16 => true})

これだったら「foobar.dbĀ?」("foobar.dbA\xCC\x84\x01") というファイルができる。よくわからん。

まあそんなわけで、たぶん sqlite3-ruby で utf16 オプションを使っている人は皆無なんじゃないかな?


Pythonはどうなってるんだろう?

CPython の SQLite ライブラリは C で書かれてる。

text_factory というのを指定するらしい。

class TextFactoryTests(unittest.TestCase):
    def setUp(self):
        self.con = sqlite.connect(":memory:")

    def CheckUnicode(self):
        austria = unicode("Österreich", "latin1")
        row = self.con.execute("select ?", (austria,)).fetchone()
        self.assertTrue(type(row[0]) == unicode, "type of row[0] must be unicode")

    def CheckString(self):
        self.con.text_factory = str
        austria = unicode("Österreich", "latin1")
        row = self.con.execute("select ?", (austria,)).fetchone()
        self.assertTrue(type(row[0]) == str, "type of row[0] must be str")
        self.assertTrue(row[0] == austria.encode("utf-8"), "column must equal original data in UTF-8")

    def CheckCustom(self):
        self.con.text_factory = lambda x: unicode(x, "utf-8", "ignore")
        austria = unicode("Österreich", "latin1")
        row = self.con.execute("select ?", (austria.encode("latin1"),)).fetchone()
        self.assertTrue(type(row[0]) == unicode, "type of row[0] must be unicode")
        self.assertTrue(row[0].endswith(u"reich"), "column must contain original data")

    def CheckOptimizedUnicode(self):
        self.con.text_factory = sqlite.OptimizedUnicode
        austria = unicode("Österreich", "latin1")
        germany = unicode("Deutchland")
        a_row = self.con.execute("select ?", (austria,)).fetchone()
        d_row = self.con.execute("select ?", (germany,)).fetchone()
        self.assertTrue(type(a_row[0]) == unicode, "type of non-ASCII row must be unicode")
        self.assertTrue(type(d_row[0]) == str, "type of ASCII-only row must be str")

    def tearDown(self):
        self.con.close()

self.con.text_factory = sqlite.OptimizedUnicode だと、文字列が ascii 範囲内なら str にして、それ以外なら unicode にすると。

UTF-16 のことについてはまったくノータッチっぽい。


実は

もうほとんどパッチは出来てるんだけど、調べてたらちょっと変えたほうがいいところもあると思ったので、もうちょっと弄ろうと思う。

2009-09-17

日本語ブログから最もリンクされているメディアサイト

03:25

続き。

気づけば半年以上も放ったらかしにしてた。

生の結果はこんな感じだった。

15459	twitter.com
6698	d.hatena.ne.jp
3630	match.seesaa.jp
3094	blog.fc2.com
2966	www.amazon.co.jp
1587	getnews.jp
1481	hb.afl.rakuten.co.jp
1271	rd.yahoo.co.jp
1070	blog.livedoor.jp
1033	jugem.jp
911	ameblo.jp
713	www.surf-current.com
660	blog.with2.net
660	www.infocart.jp
602	www.nicovideo.jp
598	japanese.engadget.com
596	news.yukoba.jp
500	www.youtube.com
474	ja.wikipedia.org
455	bit.ly
445	headlines.yahoo.co.jp
368	photozou.jp
344	px.a8.net
319	hiyoshilog.blog9.fc2.com
301	dog.blogmura.com
295	sankei.jp.msn.com
289	www.dmm.com
280	blogranking.fc2.com
279	tinyurl.com
268	yurikonakaga.blog67.fc2.com
252	futures.blog4.fc2.com
230	www.loudtwitter.com
221	www.infotop.jp
214	technorati.jp
210	toyangel.blog81.fc2.com
200	image.blog.livedoor.jp
196	tumblr.com
192	www.afpbb.com
192	plaza.rakuten.co.jp
188	www.asahi.com
187	www.geocities.jp
178	slashdot.jp
177	pt.afl.rakuten.co.jp
169	slurl.com
164	mikikosroom.blog43.fc2.com
162	www.blogmura.com
157	amana.jp
156	click.linksynergy.com
154	www.appbank.net
152	www.google.co.jp
145	www.amazlet.com
144	www.itmedia.co.jp
144	blog.goo.ne.jp
142	www.info-style.co.jp
142	b.hatena.ne.jp
140	taka7tahablog.blog105.fc2.com
138	mainichi.jp
137	www.kk-fan001.com
134	baby.blogmura.com
133	www.yomiuri.co.jp
132	labs.accesstrade.net
129	blogs.yahoo.co.jp
128	ft07.com
126	news.goo.ne.jp
123	itunes.apple.com
120	hanahana437.blog57.fc2.com
120	job.j-sen.jp
117	keyword.blogmura.com
117	mugennovel.blog26.fc2.com
114	jgourmet.blog22.fc2.com
113	cocomo.cocolog-nifty.com
107	anond.hatelabo.jp
107	badomintondan.blog46.fc2.com
104	jumppage.ddo.jp
104	weloveok.com
100	jp.autoblog.com
100	www.mag2.com

一つのブログ記事に同じドメインの URL が何度も出てきたら2つ目からは無視する仕様にしとけばよかったのだけど、残念ながらそうしなかったので、Twitter が一位という結果に。(1日のログをまとめているようなブログがあるから)

あと Google ブログ検索の結果が自動生成のアフィリエイトブログを完全には弾いてくれなくて、rd.yahoo.co.jp とか hb.afl.rakuten.co.jp とかが上位に来てしまった。

こんな結果に意味があるのかわからないけど、ニュースサイトとしてはこんな結果に。

1587	getnews.jp
598	japanese.engadget.com
596	news.yukoba.jp
445	headlines.yahoo.co.jp
295	sankei.jp.msn.com
214	technorati.jp
192	www.afpbb.com
188	www.asahi.com
178	slashdot.jp
164	mikikosroom.blog43.fc2.com
144	www.itmedia.co.jp
138	mainichi.jp
133	www.yomiuri.co.jp
126	news.goo.ne.jp
78	japan.cnet.com
77	gigazine.net
76	r25.jp
74	www.nikkei.co.jp
66	news.livedoor.com
65	itpro.nikkeibp.co.jp
64	labaq.com
63	www.gizmodo.jp
63	journal.mycom.co.jp
62	maps.google.co.jp
58	www.nhk.or.jp
54	www.iza.ne.jp
54	www.nikkansports.com
48	www.jiji.com
46	ascii.jp
45	www.tbs.co.jp
44	plusd.itmedia.co.jp
42	www.4gamer.net
42	digimaga.net
41	www.j-cast.com
40	www.atmarkit.co.jp
38	www.tokyo-np.co.jp
37	www.sanspo.com
37	natalie.mu
36	internet.watch.impress.co.jp
33	www.tv-tokyo.co.jp
32	www.cinemaonline.jp
32	wiredvision.jp
32	www.sponichi.co.jp
31	www.famitsu.com
31	jp.techcrunch.com

感想としては、ブログへのリンクはニュースサイトへのリンクと比べて桁違いに多い。「アフィリエイトで○○万稼げました」的なサイトが上位にたくさんあった。


こうして見ると、大手サイトも小規模でやっているようなサイトも、被リンクではそんなに変わらない。

そりゃあ新聞社は儲からんわなあ。

トラックバック - http://rubyist.g.hatena.ne.jp/edvakf/20090917

2009-09-15

大きなテキストファイルを一定行数ごとに分割

| 06:23

ruby19 -e 's="katakana";a="";c=0;n=10000;open(s+".txt"){|f|while f.gets do a<<$_; c += 1; if c%n==0 then open("#{s}_#{c/n}.txt","w"){|f| f.print(a)}; a=""; end; end}'

この前作ったやつだけど、100万語もあると扱いにくくて。

トラックバック - http://rubyist.g.hatena.ne.jp/edvakf/20090915
|