コグノスケ


2014年 5月 1日

イテレータ

Java を始めたときにコケたので思い出深いのですが、C++ と Java ってイテレータの概念が全然違いますね。

C++ のイテレータはコレクションの要素そのものを指しています。N 個要素を持つ配列 a のイテレータ it であれば、a.begin() は a[0] を指し、it は a[0] から a[N - 1] の間まで有効な要素を指し続けます。a.end() は存在しない a[N] を指します。

C++ のイテレータ

begin()                                        end()
|                                              |
a[0]   a[1]   a[2]   ... a[N - 2]   a[N - 1]   a[N]
|      コレクションの有効範囲       |

C++ 方式の利点は、イテレータが何を指すのか直感的に理解しやすく、イテレータ経由での要素の書き換えや削除のイメージが沸きやすいことです。

欠点は begin() は参照して良いのに、end() は参照してはいけない、という非対称な仕様になってしまうことです。例えば、逆転イテレータ(reverse_iterator)を実装すると begin() を end(), ++ を -- として扱うだけでは作れずに、悲しい思いをします。

Java のイテレータは要素と要素の「間」を指しています。Java に begin(), end() はありませんが、対比のため無理やり書くと下記のようなイメージです。

Java のイテレータ

 begin() = iterator()                           end() = hasNext() が false
 |                                              |
   a[0]   a[1]   a[2]   ... a[N - 2]   a[N - 1]
   |      コレクションの有効範囲       |

Java 方式の利点は begin と end が対称的になることです。もう begin と end で悲しい思いをすることはありません。

欠点は書き換えや削除の対象がわかりづらいことです。特に双方向イテレータ(ListIterator)が顕著なので、もう少し詳しくご紹介しましょうか。

Java コレクションの仕様ではイテレータが「最後に返した要素」が書き換え(set)や削除(remove)の対象、となります。ListIterator は進む/戻るのどちらもできますから、イテレータの現在位置の「直前」あるいは「直後」どちらかの要素が対象となります。下記に図示します。

Java の ListIterator の set()/remove() の対象

最後の操作が next() だった場合
------------------------------
       set()/remove() の対象
       |    現在位置
       |    |
a[0]   a[1]   a[2]   ...


最後の操作が previous() だった場合
----------------------------------
            現在位置
            | set()/remove() の対象
            | |
a[0]   a[1]   a[2]   ...

現在位置が全く同じでも set()/remove() の対象が変わる、この動きは正直ややこしいです。

利点の両立は難しいでしょうから、あとは皆さんの好みでしょうか。私は対称性を取って Java 方式に一票かなあ…。

編集者: すずき(更新: 2014年 5月 1日 12:03)

コメント一覧

  • IKeJI 
    常に内部イテレータを使うべき(極論) 
    (2014年05月02日 13:04:45)
  • すずき 
    >IKeJIさん
    内部イテレータって foreach ですか?
    コレクションの要素が多すぎて単純な全列挙→フィルタで処理できないときや、イテレータを飛ばしたり戻したりするのが難しそうです。 
    (2014年05月06日 00:51:17)
  • IKeJI 
    foreachに限らず、eachとかmapとかfoldとかそういうのも含めて考えてました。

    > コレクションの要素が多すぎて単純な全列挙→フィルタで処理できないときや、イテレータを飛ばしたり戻したりするのが難しそうです。

    どういう処理でしょう?何か例がありますか?

    俺みたいな低能力プログラマには外部イテレータは難しすぎる気がします。
    もし、for文を書かないといけない時は、椅子に座りなおして、コーラを取ってきてから、気合を入れてかきます。 
    (2014年05月11日 04:11:41)
  • すずき 
    >IKeJI さん

    >どういう処理でしょう?何か例がありますか?

    特殊すぎる処理で申し訳ないですが、現に困ってるのは、
    「最初の 4バイトがタイプで、最初の 4バイトがサイズ、そのあとサイズ分だけのデータが続く」
    というバイナリを見るとき、もし A, B, C と並んでいれば頭から順に解析できますが、A, C, B と並んでいる場合は頭から順に解析することができない、という構造です。

    さらに C は数 GB あったりして、とにかく全部メモリに置くという作戦もとれません。

    今は外部イテレータにして、わからない部分は飛ばして、位置だけ「仮 C」として覚えておき、後で読む、としていますが、それを foreach や map や fold でどうやって書くのか思いつきませんでした。

    特に Scala の場合、map や fold を List に対してぶちかますと、List の全要素に対して述語の評価を行うので、List の要素が数 GB 以上になると map や fold が現実的な時間で帰ってきません。


    >俺みたいな低能力プログラマには外部イテレータは難しすぎる気がします。
    >もし、for文を書かないといけない時は、椅子に座りなおして、コーラを取ってきてから、気合を入れてかきます。

    たしかに for + 外部イテレータは面倒くさいです。
    外部イテレータ以外の方法があれば使ってみたいんですけど…。
     
    (2014年05月11日 17:53:07)
open/close この記事にコメントする



2014年 5月 2日

判断ミス

今の偉い人が現役だった 1990年くらいから、現在 2010年で見たら、ハード規模の増加率と、ソフト規模の増加率はどっちが上なんでしょう(組み込み系で)。

開発人員の割り振りを見る限り、日本の老舗メーカーはどうもハード規模の増加率が上だと判断し、海外のメーカーはその逆だと判断した、ように見えるのです。

どちらの判断が正解か私にはわかりませんが、今の日本メーカーの傾きっぷりを見るに、海外勢が正解だったように思えて仕方ありません。

ハード復権の時代は来るでしょうか…。

メモ: 技術系の話は Facebook から転記しておくことにした。

編集者: すずき(更新: 2015年 11月 29日 19:42)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年 5月 3日

無責任

ソ連型システム崩壊から何を汲み取るか──コルナイの理論からを読んで。

役所の税金無駄遣い、失敗だらけの第三セクター、銀行の公的資金注入、赤字企業の経営陣…、などを見る度に感じるイライラは何だろうと思っていたのですが、この記事が見事に説明してくれました。

上記いずれも、決断者はリスクを伴う決断をしますが、生じたリスクは他人に押し付けるという構造になっている、という指摘です。

要するに全員「偉そうに指示したくせに、しくじったらトンズラする無責任野郎」なのです。

見ていて腹が立つわそりゃ。非常にスッキリしました。

メモ: 技術系の話は Facebook から転記しておくことにした。

編集者: すずき(更新: 2015年 11月 29日 19:44)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年 5月 6日

日記検索システム

現在、トップページの入力フォームから、日本語を指定して日記の検索を行うと文字化けする不具合が起きています。

原因は、日記サイトの文字コードを UTF-8 に変更した際に、検索システム(Namazu)側の文字コード euc-jp と食い違ってしまったことです。kakasi は 2.3.5 にて iconv に対応したらしく UTF-8 の文書でも問題なく分かち書きできるようですが、どうも namazu.cgi が UTF-8 の入力に対応していないようです…。

困ったなー。修正できないかどうか、しばし探してみます。

編集者: すずき(更新: 2014年 5月 7日 03:40)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年 5月 11日

2048 の最高得点(その 1)

2048 の最高得点について考えてみます。

仮定: 新しい数字が常に理想的に出現した場合、4x4 のフィールドは、横 1 列の 16 マスと同等とみなせる、とします。

この仮定が正しいかどうかがイマイチ分かりませんが…考えるのは後回しにします。この仮定が正しいとして、

  • 必ず左端に新しい数字が出現
  • 常に右に移動

という動きを考えます。

2 だけ出てくる場合

新しい数字としては 2 か 4 が出ますが、まずは単純にするため 2 が出続けた場合を考えます。2 が出続けた場合の手詰まりの形は、
2, 4, 8, 16, ..., 65536
つまり、
2, 4, ..., 2^(N-1), 2^N
です。

手詰まりになるまで 4 がいくつ必要か(=4 が何回生成されるか、と同意)を考えますと、


マス数: 手詰まり形: 各マスの数字を作るのに必要な 4 の数
2マス: 2, 4        → 0, 1
3マス: 2, 4, 8     → 0, 1, 2
4マス: 2, 4, 8, 16 → 0, 1, 2, 4
となります。

N マスにおいて、手詰まりまでに生成された 4 の数 S(N, 4) は、初項 1、公比 2、項数 N-1 の等比数列の和と等しいですから、
S(N, 4) = 2^(N-1) - 1
よって得られる点数は、
4 * S(N, 4)
です。

次に 8 が何回生成されるか?を考えますと、


マス数: 手詰まり形: 各マスの数字を作るのに必要な 8 の数
4マス: 2, 4, 8, 16 → 0, 0, 1, 2
となります。

生成される新しい数字が倍になり(つまり 4 が出てくると考える)、マスは 1つ減った、と考えるとわかりやすいですかね?
S(N, 8) = S(N - 1, 4)
なので得られる点数は、
8 * S(N - 1, 4)
です。

さらに一般化すると N マスで手詰まりしたとき、それぞれのマスに存在する数は、
2, 4, 8, 16, ..., 2^N
となります。

一般項を An とおくと、
An = 2^n (ただし n = 1, 2, ..., N)
です。

各数値が何回生成されるかを 4 を基準に考えると、
S(N + 1, 4), S(N, 4), S(N - 1, 4), ..., S(2, 4)
と表せます。

一般項を Sn とおくと、
Sn = S(N + 2 - n, 4) = 2 ^ (N + 2 - n - 1) - 1 = 2 ^ (N - n + 1) - 1
(ただし n = 1, 2, ..., N)
と表せます。

各数値を生成する際に得られる点数は、An と Sn の積を合計した値になります。
0 * S(N + 1, 4), 4 * S(N, 4), 8 * S(N - 1, 8), ..., 2^N * S(2, 4)
しかし 2048 のルールでは 2 の生成時に点数は入りませんので、初項 A1 * S1を除く必要があります。

記号を使って少しかっこよく書けば、
N
Σ(Ak * Sk) - A1 * S1
k=1
となり、このとき、
Ak * Sk = 2^k * (2^(N - k + 1) - 1) = 2^(N + 1) - 2^k
A1 * S1 = 2^(N + 1) - 2
です、かね。たぶん。

先ほどの最高得点の式、試しに N = 16 で計算してみると 1835012 点、つまり 183万点です。経験上 2048 を 1つ作った時点で 2万点程度ですので、どれだけ理不尽な数かがわかると思います…。

4 だけ出てくる場合

前節では 183万点と計算しましたが、新規に生成される数値が 4 だけだった場合は、手詰まりの形は 2 だけの時の 65536 のさらに倍の数字 131072 まで生成可能です。

つまり N マスで手詰まりしたとき、それぞれのマスに存在する数は、
4, 8, 16, 32, ..., 2^(N + 1)
となります。

一般項を An とおくと、
An = 2^(n + 1) (ただし n = 1, 2, ..., N)
です。

前節で求めた点数の総和の式に当てはめて N = 16 を計算すると 3670024 点となります。うーん 367万点ねー…普通にやっていたらまず無理ですね。

しかし 2048 では 2 だけでも 4 だけでもなく、両方とも新規生成されます。これは 4 だけが新規生成される場合と比較して、空いているマスさえあれば 4 を生成することができるため、最高得点はさらに上がある、ということです。

また今度にでも考えます…。

編集者: すずき(更新: 2014年 5月 11日 03:24)

コメント一覧

  • りょう 
    はじめまして.
    私も同じ仮定で考えていたのですが,最高点は3932100点になるとの結果が得られたので,ご報告致します. 
    (2014年06月07日 05:42:09)
  • すずき 
    >りょうさん
    ご報告ありがとうございます。
    393万点は 2 と 4 が適切に出てくる場合の点数でしょうか?
    2 か 4 だけ出てくる場合を仮定されていれば、私と違う式を導かれたか、私が計算間違いしてますね…。 
    (2014年06月07日 20:21:56)
  • りょう 
    393万点は,うまいこと 2 と 4 が出てくる場合の点数として求めたものです.
    どちらかのみで仮定して場合はここに書かれているものと同じ結果になりました. 
    (2014年06月08日 01:19:34)
  • すずき 
    >りょうさん
    なるほど、ありがとうございます。良くポカミスするので、同じ結果が得られて安心しました。
    残るは盤面を 1次元にして良い、という仮定が正しいか?ですが…、残念ながら私はノーアイデアです…。 
    (2014年06月08日 03:48:30)
  • りょう 
    私もちょくちょくやらかすので同じ結果になった人がいてよかったです.
    私は,
    (2 が出続けるときは) 2^n のタイルを作るには 2 つの 2^(n-1) のタイルが必要で,この 2 つのタイルを合わせるときに 2^n 点加算.
    この 2 つの 2^(n-1) のタイルを 4 つの 2^(n-2) のタイルから作るときに 2^n 点加算.

    これを繰り返して,1 つの 2^n のタイルを作るとき (n-1)・2^n 点加算される,というのをもとに,
    (最高得点)=Σ[n:1…16](上の式)
    から求めてみたんですよね.
    (最終的な式は同じになると思いますが,アプローチのしかたがここのサイトとは少し違った気がしたので一応書いておきます)

    4 のみのときや両方のときも,1 つのタイルによる点数の合計をもとに考えました.

    それで,件の,1 次元に落としていいか,ですが,
    私もノーアイデアですね...
    手詰まり形を考えれば,2 次元のときに 1 次元のときの点数を超えないのは示そうですが...
    下回らないことはどう示せばいいものか... 
    (2014年06月08日 15:11:38)
open/close この記事にコメントする



2014年 5月 13日

DynDNS のドメインが失効した

家に置いているサーバのドメイン(katsuster.dyndns.org)は DynDNS の無料 DDNS を利用していたのですが、今年の 5月で DynDNS 無料サービスの提供が終了したとのことで、ドメインが失効してしまいました。

家のサーバにアクセスできないのは不便だな。でも、全く次を考えていなかった。どうしようかな…。

編集者: すずき(更新: 2014年 5月 14日 00:10)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年 5月 14日

自宅サーバ復活

先日 DynDNS のドメインが失効してしまい、外から自宅のサーバにアクセスする手立てがなくなってしまいました。

復活させようと思い、他の DDNS が可能なサービスを調べていたのですが、しっくりくるところがありません。もう有償しかないか?と思って VALUE DOMAIN を見ていたら、今使っているドメイン名(katsuster.net)で DDNS が使えることに気づきました。

なんということでしょう、VALUE DOMAIN にはずっとお世話になっていたのに、今までずっと気づかなかったのです…。

これを使わない手はないので www2.katsuster.net というホスト名を自宅サーバ用に割り当てました。ホスト名を追加しただけなので、追加料金も要らないし、DDNS 機能も便利で wget などで GET リクエスト送るだけで IP アドレスが更新できます。確認していませんが DiCE も使えるようです。

一時はどうなるかと思いましたが、あっさり復活できて良かった良かった。

編集者: すずき(更新: 2014年 5月 15日 01:32)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年 5月 16日

Kindle Fire HD 絶不調

目次: Kindle - まとめリンク

最近、Kindle Fire HD 8.9 で本を買おうとすると、尋常じゃなく遅くなってなかなか本が買えない上に、ホーム画面に戻るとき 1分くらい固まったまま待たされて、非常につらい。

スリープからの復帰も数秒掛かるし、壁紙が出ず背景が真っ黒。

再起動したらさらにひどくなった。何が起きてんだ、これ…。

メモ: 技術系の話は Facebook から転記しておくことにした。

編集者: すずき(更新: 2021年 12月 8日 03:47)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年 5月 24日

はじまりとおわり

国道には○○号線、と番号が振られていて、重なっている区間もあります。中には始点や終点が別の国道と重なっている場合もあります。

じゃあ、国道の始まりと終わりは誰が決めるのか?と疑問に思い調べてみると、道路法に基づいた「一般国道の路線を指定する政令」(昭和四十年三月二十九日政令第五十八号)という政令で決められているそうです。

道路法といい、政令といい、何の捻りもないストレートな名前です。わかりやすいのでありがたくもあり、あまりにあっさり見つかったのでやや物足りなくもあり。うーん…。

試しに一つ調べてみる

我が家からもっとも近い国道は R171 です。試しに R171 について調べてみましょう。

先の政令 58号によれば、国道 171 号線の起点は京都市、終点は神戸市です。重要な経過地は、向日市、長岡京市、京都府乙訓郡大山崎町、高槻市、茨木市、箕面市、池田市、伊丹市、尼崎市、西宮市(河原町)、芦屋市(清水町)です。

あれ?これだけ?どうも政令 58号では具体的な位置(交差点名、何号線に吸収される、など)は言及していないようです。

詳細な位置

道路整備促進期成同盟会全国協議会が発行していた「道路時刻表」によると、道路を走行した際の所要時間の概算値を見ることができます。

走行時間の付属情報として、始点、主な交差点(と交差する道)、終点も書いてあるため、どこで何の道が重なっているかがわかります。本来の用途と異なる使い方ですが、この際わかれば何でも良いのです。

が、しかし道路時刻表は 2008年で絶版とのこと。うーん、最新の情報はどこにあるんですかねえ…。

編集者: すずき(更新: 2014年 5月 24日 19:02)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年 5月 25日

企業も生きている

企業の生涯を追うと、若い時は素早くて何でもチャレンジするけれど、時が経つと緩慢で億劫になって何もしなくなり、やがて体が動かなくなって息絶えるんです。

なんか、企業と生き物って似ているなーと思ったら、色々浮かんできました。

不採算部門のレイオフ
内臓切るような外科手術、あるいはスタンガンですかね。体力が激減するし、調子に乗って何度もやればショック死です。
税金での救済
死体のゾンビ改造術のようなもん?ゾンビは周りにいる健康な人を襲うため、市場に悪影響が出る、ってな感じです。

メモ: 技術系の話は Facebook から転記しておくことにした。

編集者: すずき(更新: 2015年 11月 29日 19:47)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



2014年 5月 30日

ワード幅とハーフワード読み出し

RISC CPU にはワード幅での読み書きしかできないアーキテクチャがありますが、より狭いハーフワードやバイトへのアクセスってどうしているのでしょう?

単純に考えると、ひとまず近しいアドレスからワード幅で読み出して、しかるべきシフト演算を行うことで、目的のハーフワードやバイトデータを得ていそうです。

例えば、ワード幅 64bits、読みたいデータ幅 16bits、アクセス先のアドレスが 0x12 として考えてみます。

まず、データバスにはアドレス 0x12 ではアクセスできませんので、ひとまず 0x12 を超えない最大の 8の倍数(64bits = 8bytes)であるアドレス 0x10 から 64bits を読み出します。

このときバスから読み出したデータが 0x1234_5678_0246_8ace だとして、バスから読み出したデータを読みたいデータ幅(= 16bits)ごとに分割し、符号ビットから近い順から並べると、


0x1234:
0x5678:
0x0246:
0x8ace:

となります。

リトルエンディアンシステムの場合、データの上位から、アドレス+6、アドレス+4、アドレス+2、アドレスそのもの、に対応しますので、


0x1234: アドレス+6 = 0x16
0x5678: アドレス+4 = 0x14
0x0246: アドレス+2 = 0x12
0x8ace: アドレスそのもの = 0x10

と対応します。

従って目的のアドレス 0x12 にあるデータは 0x0246 であることがわかり、バスから読み出したデータをシフトすべき量は 16bits であることがわかります。

同様にアドレス 0x14 ならばデータは 0x5678 となり、シフトすべき量は 32bits です。

コードでどうぞ

このような処理をいちいち考えていると面倒で死にそうなので、コードで書いてみることにしました。

バスから読んだデータから対応するアドレスのデータを得る関数(リトルエンディアン)

public static long ADDR_MASK_64 = ~0x7L;
public static long ADDR_MASK_32 = ~0x3L;
public static long ADDR_MASK_16 = ~0x1L;
public static long ADDR_MASK_8 = ~0x0L;

/**
 * @param dataLen データ幅
 * @return アドレスマスク
 */
public long getAddressMask(int dataLen) {
    switch (dataLen) {
    case 64:
        return ADDR_MASK_64;
    case 32:
        return ADDR_MASK_32;
    case 16:
        return ADDR_MASK_16;
    case 8:
        return ADDR_MASK_8;
    default:
        throw new IllegalArgumentException("Data length" +
                String.format("(0x%08x) is not supported.", dataLen));
    }
}

/*
 * @param addr     データのアドレス
 * @param data     バスから読んだデータ
 * @param busLen   データバス幅
 * @param dataLen  データ幅
 * @return addr にあるデータ
 */
public long readMasked(long addr, long data, int busLen, int dataLen) {
    long busMask = getAddressMask(busLen);
    long dataMask = getAddressMask(dataLen);
    int sh = (int)(addr & ~busMask & dataMask) * 8;

    return data >> sh;
}

ふっざけんなー!意味がわからんわー!!と叫んでいる半年後の自分が見えたので、併せて解説も書いておきます。

バスから読み出したデータをシフトする量を求める部分が addr & ~busMask & dataMask * 8 の部分です。

まず addr & ~busMask ですが、バス幅で割った余りのアドレスを求めています。
例えば、幅が 64bits でアドレスが 0x12 ならば、8で割った余りのアドレス 0x02 を求めています。

次に addr & ~busMask & dataMask ですが、データ幅境界にアドレスを揃えています。この意味と必要性の議論は後述します。
例えばデータ幅が 16bits ならば、アドレスを 2の倍数にします。アドレス 0x01 なら 0x00、アドレス 0x02 なら 0x02、アドレス 0x03 なら 0x02 です。


アドレスからビットシフト量へ

残りの処理はアドレスに 8を掛けて右ビットシフトしています。関数の返値は上位に余計なデータが残っていますので、返り値を受け取った人は、余計な上位のデータを捨てる必要があります。


バス幅からデータ幅へ

呼び出す側のコードは、こんな感じです。

呼び出し側の例

//データバス幅
public static int BITS_DATA_BUS = 64;

public byte read8(long addr) {
    return (byte)readMasked(addr, readWord(addr), BITS_DATA_BUS, 8);
}

public short read16(long addr) {
    return (short)readMasked(addr, readWord(addr), BITS_DATA_BUS, 16);
}

public int read32(long addr) {
    return (int)readMasked(addr, readWord(addr), BITS_DATA_BUS, 32);
}

他のアドレスが渡される場合も同様です。


アドレス 0x12 から読む場合


アドレス 0x16 から読む場合

他のバス幅、他のビット幅でも同じ考え方で処理可能です。


他のデータ幅の例

データ幅の境界にアドレスを揃える意味

データ幅境界以外からデータを読んで良い、つまり 0x13 から読んだときに 0x0246 ではなくて、0x7802 を返せるシステムならば、& dataMask は不要です。


アドレス 0x13 から読む場合

この方が便利ですが良いことばかりでもなく、バス幅をまたぐ際の読み出し、例えば 0x17 から 16bits 読む際の処理が必要になります。


アドレス 0x17 から読むときの問題点

しかし前述のコードではバス幅の境界をまたぐ読み出し方に対応できませんから、データ幅境界以外からデータを読めないようにして、異常動作しないように防いでいます。

編集者: すずき(更新: 2014年 6月 1日 14:19)

コメント一覧

  • コメントはありません。
open/close この記事にコメントする



こんてんつ

open/close wiki
open/close Java API

過去の日記

open/close 2002年
open/close 2003年
open/close 2004年
open/close 2005年
open/close 2006年
open/close 2007年
open/close 2008年
open/close 2009年
open/close 2010年
open/close 2011年
open/close 2012年
open/close 2013年
open/close 2014年
open/close 2015年
open/close 2016年
open/close 2017年
open/close 2018年
open/close 2019年
open/close 2020年
open/close 2021年
open/close 2022年
open/close 2023年
open/close 過去日記について

その他の情報

open/close アクセス統計
open/close サーバ一覧
open/close サイトの情報