ネタバレ注意！
member()があっさり 0 を返しすぎるのはすぐわかった。コメント欄の、ハッシュ表があふれることを否定しない表現「『要素の個数はハッシュ表のサイズBより小さいとする』という前提なので、『全部埋まっていたら』の意味にもよりますが」を読んでいて、前提条件に関わらず、同じ要素が複数回 insert()されるとハッシュ表があふれるのもわかった。さて 3つめは？ そして修正版は？
(member()相当の機能が欲しいだけなら)ソート済みの int配列にすれば…… < ハッシュテーブルじゃない！
意外にできる子とはいえ insert()と delete()でのメモリブロックの移動コストが気になる。一定サイズの配列(Chunk)をリストで管理したら……とかどうでもいい。
(元記事コメントから)> 削除済みマークを付ける
delete()で EMPTY(0)にせず DELETED(-1とか)にするのね。clear()するまで不良資産(DELETEDな要素)は貯まる一方、というわけでもなく、insert()するときに再利用できそうだ。
これ(削除済みマークを付ける)って FAじゃないのかなあ。
とりあえず、気付いた 2つの問題(delete()がからむと member()が不正確。重複要素であふれる)に対処した insert()はこう。EMPTYな要素より DELETEDな要素を優先して使用したくてフラグっぽい変数が増えてしまった。
/* 要素xをハッシュ表hに追加 */
void insert(int x) {
int i = hash(x);
int j = -1; /* i より優先して xを代入すべき位置 */
while (h[i] != EMPTY) {
if (h[i] == x) {
/* return; */
j = i;
break;
} else if (h[i] == DELETED) {
j = i;
}
i = (i + 1) % B;
}
h[j != -1 ? j : i] = x;
}
delete()の方も、EMPTYの代わりに DELETEDを代入するように変更する。
重複要素でハッシュ表があふれることがなくなったとはいっても、insert()と delete()を繰り返すうちに DELETEDな要素が増えていって EMPTY要素の数が 0になる可能性はないだろうか。EMPTY要素がなくなると、存在しない要素xを引数にした member()が無限ループに陥る。直観的にそういう可能性はない気がするけど……。
完全ハッシュ関数の状態からスタートしよう。ハッシュテーブルには最低でも一か所の穴(どの要素xも配置されない)がある。この位置を一時的にでもある要素で埋められればハッシュテーブルの全ての要素を DELETEDにできる。直接この穴に配置される要素xは存在しないからハッシュ値を衝突させて insert()で玉突き処理を行わせなければいけない。完全ハッシュ関数を二つの要素のハッシュ値だけが衝突するように変更してみよう。玉突きで穴を一つ塞ぐことができるが、完全ハッシュ関数ではなくなることで穴は二つ(以上)になっていた。以下略。
拍子抜け。要素を重複して格納せず、DELETEDな要素を再利用している限り、ハッシュ表が DELETEDであふれることはない。あっけなさすぎて自作自演臭がしてきた。
蛇足も蛇足の別バージョン。全然かわりばえしない。
/* 要素xをハッシュ表hに追加 */
void insert(int x) {
int i = hash(x);
int d = -1; /* hash(x)に一番近い DELETEDの位置 */
while (h[i] != EMPTY && h[i] != x) {
if (d == -1 && h[i] == DELETED) {
d = i;
h[d] = x;
}
i = (i + 1) % B;
}
if (d == -1) {
h[i] = x;
} else if (h[i] != EMPTY) {
h[i] = DELETED;
}
}
0 ≦ hash(x) ＜ B は暗黙の前提にしてるけど、3つ目のミスだったりして。
コメントも読めばわかるけど、ミスが 1。修正過程で陥りやすい落とし穴が 2つくらい、なんだってば。(でもわかりにくい)
最終更新: 2010-01-15T21:38+0900
C/C++ではもちろん0==false はtrueなわけですが・・・ もしかして、boolean型を整数型とキャスト比較しない仕様なんでしょうか？
この辺はC/C++も難しくて 本質的には 2==trueも本当は真なんですが偽になったりもします。
Rubyでビットフラグをチェックするときは 0との比較を忘れてはいけない。
if(flag & mask) # (意図に反して)必ず実行される end if(0 != flag & mask) # 期待通り end
というのはさておき、2==true に関して、「本質的には」という言葉が胡散臭い。その「本質」を表すコードは「(2!=false) == (true!=false)」であって、2==true は関係ないのでは？ ==は真偽値を返す演算子ではあっても、真偽値のみをオペランドにとる演算子ではないから、2==true も 1==true も -1==true までもが暗黙にそのように解釈されて真になったりしたら、むしろ気持ち悪い。それは PHPの世界だ。(偏見)
Cと逆だな
Rubyでは非0が偽だと言いたげですね。
Safe Bool (ja.wikibooks.org)という C++のイディオムがあって、つまり裏を返すと、危険な Boolean変換が C++には存在するということだ。やーめーてー。
C++09(予定)では explicitなコンストラクタみたいに、明示的なキャストを必要とする変換を定義できるようになるらしい。
先人 > Amazon Product Advertising APIの認証の件 - zorioの日記
Ruby-1.8.7と Ruby-1.8.6では String#force_encoding("ASCII-8BIT")ができず、String#ordもない(ないのはエンコーディングの概念がないからと、String#[]で代替できるからだと思われる)。それらを使い分けるために 2種類のメソッドを用意するくらいなら、unpackで配列経由でいいです。
require 'digest/sha2'
def hmac_sha256(key, message)
hash = Digest::SHA256
hash_block_size = 64 # bytes (= hash.new.block_length)
key = hash.digest( key ) if hash_block_size < (key.bytesize rescue key.size)
ikey = Array.new( hash_block_size, 0x36 )
okey = Array.new( hash_block_size, 0x5c )
key.unpack("C*").each_with_index{|key_byte, i|
ikey[i] ^= key_byte
okey[i] ^= key_byte
}
inner_hash = hash.new.update( ikey.pack("C*") )
outer_hash = hash.new.update( okey.pack("C*") )
digest = outer_hash.update( inner_hash.update( message ).digest ).digest
return digest
end
短い秘密鍵は 0を補うって書いてあった。その処理が見あたらないのになぜうまくいくのかと考えたら、0を相手に排他的論理和をとったって何も変わらないのねん。
class Digest::Base
- update(str)
- self << str
- 文字列を追加する。self を返す。複数回updateを呼ぶことは文字列を連結してupdateを呼ぶことと等しい。すなわち m.update(a); m.update(b) は m.update(a + b) と、 m << a << b は m << a + b とそれぞれ等価である。
Ruby-1.9で文字列の連結は怖いので m.update(a + b) と m << a + b と Digest::SHA256.digest(ipad + message) は避けたい。
302 Foundはわかる。リバースプロキシは何するもの？
require 'uri'
require 'base64'
def amazon_authenticated_query_string( host, params )
re_rfc3986_unreserved = /[^A-Za-z0-9\-_.~]/
query_string = params.to_a.sort_by{|x| x.first }.map{|key, value|
URI.encode(key, re_rfc3986_unreserved) +'='+ URI.encode(value, re_rfc3986_unreserved)
}.join("&")
string_to_sign = <<-"STRING_TO_SIGN".gsub(/^\t\t/, '').chomp
GET
#{host.downcase}
/onca/xml
#{query_string}
STRING_TO_SIGN
amazon_secret_access_key = "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
signature = Base64.encode64( hmac_sha256( amazon_secret_access_key, string_to_sign ) ).chomp
return "#{query_string}&Signature=#{URI.encode(signature, re_rfc3986_unreserved)}"
end
ある日のエントリの一つを更新すると、同じ日の他のエントリまでが更新されたとして上がってくる理由。たぶんそれまでに他のエントリで「ちょっとした修正」を行っていたのだろう。makerss.rbを見てみたら
add_update_proc do makerss_update unless @cgi.params['makerss_update'][0] == 'false' end
ちょっとした修正では日記の更新時に何も行っていない。これを、index.rdfの更新はしないけど cache/makerss.cacheの更新はする、というふうに変えられないだろうか。
目的は、以前に加えたちょっとした修正と、今回の普通の更新で加えた変更とを区別するため。
編集対象のセクションを特定できるなら、cache/makerss.cacheを常に更新することで、以前のちょっとした修正を検出しなくなるようにする必要はないし、むしろ LDRのようにフィードの内容の一字一字を比較するリーダー?(フィードアグリゲータ?)まで騙すことを考えると、cache/makerss.cacheの内容はちょっとした修正以前の古いままにしておく方がいいみたい。
じゃあ、なぜ既にセクション単位で編集を行ってるこの日記で、直前の編集に関係していないセクションまでが上がってくるのか？ makerss.rbの変更まで手を回す前にやる気が尽きたから。
update_procに引数の追加が必要なんだけど、改めて具体的に考えてみると単純にセクションナンバー1つを渡せばよいというものでもなさそうだ。セクション2を編集した結果、セクション2がなくなってセクション3が 2に繰り上がってる可能性がある。セクション2が分裂してセクション2と 3になってる可能性がある。
LDRといい update_procの引数といい、万全を期すと二進も三進もいかんなあ。(LDRは使ってないから外せない問題ではないし、update_procは {before=>2, after=>2..3} を渡すだけで済んでしまう気もするけど)
ああ、afterの範囲を確定するのが難しいんだ。変更前に、編集対象のセクションの前にいくつ、後にいくつのセクションがあるかを数えておく手があるけど、場合によったら直前のセクションと結合してしまうことがあるからなあ(セクション2を編集していたはずが、セクション2を削除してセクション1に追記したことになってる可能性がある)。この場合セクション1に変更があったことは無視してセクション2が削除されたことだけを考えていいなら、やっぱり前後のセクション数を数えておく方法でよさそうだ。
makerss.cacheは二つの目的を持ってるんじゃないか。変更のあったセクションを検出する目的と *.rdfのソースにする目的。
そもそも、*.rdfのソースは *.rdf自身で十分じゃないか？(深くわかってるわけじゃないけど) これに変更のあったセクションを特定できる引数が update_procに加わったら makerss.cacheを用済みにできないか。
できない。一日単位の編集機能をなくせるわけじゃないから今と同等の変更検出機能は必要。そうすると *.rdfのソースを makerss.cacheから *.rdfにスイッチする必要もなさそうに思えるけど、……ないかも。(うっかりフィードに紛れ込んだテストコメントは index.rdfからアイテムを削除するのでなく、コメントを非表示にすれば、あとあと甦ってくることもなかったんだ)
makerss.cacheは二つの役割を持っている。
変更のあったセクションの検出能力に難があったので改善を試みる。一日単位の編集機能が存在し続け、rdfのエントリの単位がセクションである限り、変更のあったセクションの検出能力の向上は無駄にならない。
makerss.cacheの日記内容をちょっとした修正でも更新する。
これでちょっとした修正のあったセクションの誤検出はなくなる。だがこの makerss.cacheをもとに *.rdfを作成するとエントリの内容がちょっとした修正後のものになり、LDRなど RSSリーダーによる過剰検知の原因となる。
*.rdfのソースを *.rdfにする。
右から左に流すだけでは過剰検知の起こりようがない。フィードを更新するときにどんな問題が発生するだろう……。手順を考える。
問題は、フィードに含まれる日記やコメントを隠したりセクションを削除したりするとエントリ数が上限より少なくなる、だけだろうか。最初は無理そうに思えたけど、なんだったんだろう。
makerss.cacheから読み込んだものと *.rdfから読み込んだものとは Rubyオブジェクトか文字列かという違いがあるんだなあ。でもそれが意味を持つのは MakeRssNoComments#itemで呼ばれる rdfsec.section.respond_to?( :body_to_html )だけみたいだから、ここを rdfsec.id.index("p") に置き換えれば *.rdfから読み込んだ xml文字列だけで makerss.cacheの代わりができそう。
セクション単位の編集機能があり、makerss.rbが update_procの引数から変更のあったセクションを知ることができれば、今以上の、変更のあったセクション検出能力は特段必要ではない。
makerss.cacheはこれまで通りちょっとした修正では更新されず、LDRをちょっとした修正以前の古い内容でだまし続けることが可能。
日記の書き手はフィードの更新を伴うデリケートな編集作業ではセクション単位の編集を行うことで、余計なセクションが上ってくることを避けられる。
こっちが断然楽そうだ。でも自分の環境で閉じてしまうから代替案なんだよね。
タイトル(脳log)にふさわしい垂れ流しっぷりじゃあないですか？
はるか上の方でこう書いた。
場合によったら直前のセクションと結合してしまうことがあるからなあ(セクション2を編集していたはずが、セクション2を削除してセクション1に追記したことになってる可能性がある)。
何を見て書いていたかというと……
unless body1.empty?
current_section = @sections.pop
if current_section then
body1 = "#{current_section.body.sub( /\n+\Z/, '' )}\n\n#{body1}"
end
@sections << WikiSection::new( body1, author )
end
解説解説
appendされた Wikiソースがサブタイトルを持っていないもの( body1 )だったら、 最後のセクションを取り除き 最後のセクションの本文( current_section.body, サブタイトルを含まない )と body1を連結し、 新しいセクション( サブタイトルなし )として追加する。
WikiSection#bodyの代わりに WikiSection#to_srcを使わないとサブタイトルが消えてしまう。
body1 = "#{current_section.to_src.sub( /\n+\Z/, '' )}\n\n#{body1}"
サブタイトルのあるセクションに、サブタイトルのない本文を追加したときに、サブタイトルのないセクションができあがるのを防ぎます > fix_and_test_append_without_subtitle.diff
セクション単位の編集機能が追加されていることが前提。そのせいでこの日記でしか使えないから気乗りしなかったんだけど、第一案が手詰まりなのと一つの実験場として可能性を示すために。
update_procに updated_sectionというパラメータを追加し、makerss.rbが過去のちょっとした修正を誤検出するのを防ぎます > add_param_updated_section_to_update_proc.diff