メモの日々

■ [service] 日経ネットナビ 第13回プロバイダー調査結果発表 （Live! netn@vi）

1位はASAHIネット。ASAHIネットからのメイルより。ふーん、おれ利用者で確かに特に不満は無いけれど、そんなにいいのかね。リムネットみたいに無料で100MBをプレゼントとかしてくれると嬉しいのだが。

■ 生活

• 起きてトイレへ入り何だかガリガリうるさいなあと思っていたら、トイレの水が流れなかった。うろたえたが、水道メータの取替工事をやっていたようだ。工事に伴う断水は5分間ということだったのに、まんまとそこへはまってしまった。
• ヘイヘイヘイ見る。島谷ひとみの家は水漏れトイレへ行くまでにドア3つある、エグザイル嘘スピーカーを買う船でさらわれそうになる、麻波25金が好き、スクープオンサムバディ30後半。
• 東京ラブシネマ見る。江口洋介の秘密主義にイライラ、伊東美咲の意地悪にプンプン。

■ 仕事のTODO

考え中

• 昨日はBALILaxという店で万年筆渡し会。お粥の味が濃すぎ。
• selectに失敗再現したー。で、失敗しているのはselectではないと判明。何が起こっているのかが分かってすっきりした。
• Perlスクリプトの改造をせねばならないのでPerl勉強中。グローバル変数だらけのひどいプログラムに思えるが、これがPerl流なのかそれともプログラマのレベルが低いのか。

■ [サッカー] 日本vsイングランド

朝4時に起きてサッカー日本vsイングランドを観戦。楢崎宮本坪井中澤加地三都主稲本小野中村玉田久保が先発。中心は小野。柳沢は100%ボールを奪われる。

■ [perl] XMLの生成

perlカテゴリも作っちゃえ。

既存のプログラムは独自の雛形ファイルを元にしてXMLを生成するようになっているが、複雑すぎて改造する気にならない。Perlプログラムが持つデータ構造をXML形式で出力すればいいだけなので、もっと単純にできるはずだと思い調べたら、いくつかモジュールがあるようだったのでメモ。

おそらく、今回の用途にはXML::Simpleというモジュールが使える。

• XML::Simple　本家。
• XML::Simpleの使い方　日本語の取り扱いなど。
• perl で 日本語 XML を扱う　ここも日本語の扱いを中心に説明。

以下のモジュールも使えるかもしれない。

• XML::Dumper
• XML::Generatorモジュール（日本語チョー訳）
• XML::Writerモジュール（日本語チョー訳）

明日試してみよう。みな Perl開発者がXMLツールボックスの中身を充実させるには から辿った。

Perlのモジュールって日本語の説明なかなか見つからない。日本語化しているプロジェクト はあったけど、何しろ量が多いからなあ。

■ やること

• プリンタ処分

• テレビは毎朝初代貴ノ花死去の話題を放送している。まあ輪島戦は名勝負だな。
• 相撲の輪島はボクシングの輪島より全然しっかりしていた。
• 咳って体力消耗するなあ。

■ [java] 「Coberturaでテスト対象範囲を調べる」 （developerWorks）

• http://www-6.ibm.com/jp/developerworks/java/050527/j_j-cobertura.html

カバレッジツールCoberturaの紹介。

■ [soft] 「Bonanza - The Computer Shogi Program」

• http://www.geocities.jp/bonanza_shogi/

将棋ソフト。スクリーンショットも載せればいいのにな。最後に将棋したのはいつだったか。勝手に将棋トピックスより。

■ やること

• リンク元のスリム化
• tDiaryバージョンアップ
• FSWikiバージョンアップ
• オーブンレンジ用べんり棚
• ブラウンの安い電動歯ブラシ買う
• 蛍光灯を捨てる

■ [dev][c++] 単一始点最短経路問題の解法

最短経路問題を解く幅優先探索とダイクストラ法をメモ。

幅優先探索

すべての辺の重みが等しいグラフに対する単一始点最短経路問題は幅優先探索で効率よく解ける。幅優先探索はキューを使って始点に近い頂点から順に経路の重みを決定していくように実装すればよい。

Aizu Online Judgeに幅優先探索の問題があるのでこれを解くC++コードをメモ。

#include <iostream>
#include <queue>
#include <vector>

struct node
{
  int name;
  std::vector<node*> neighbors;
  int distance_from_root{-1};
};

void solve(std::vector<node>& nodes)
{
  std::queue<node*> queue;
  auto& root = nodes.front();
  root.distance_from_root = 0;
  queue.push(&root);

  while (!queue.empty()) {
    auto* target = queue.front();
    queue.pop();

    for (auto* n : target->neighbors) {
      if (n->distance_from_root >= 0) continue;
      n->distance_from_root = target->distance_from_root + 1;
      queue.push(n);
    }
  }
}

int main()
{
  int n;
  std::cin >> n;

  std::vector<node> nodes(n);
  for (int i = 0; i < n; ++i) {
    int u, k;
    std::cin >> u >> k;
    auto& node = nodes.at(u - 1);
    node.name = u;
    node.neighbors.resize(k);
    for (auto& nb : node.neighbors) {
      int v;
      std::cin >> v;
      nb = &nodes.at(v - 1);
    }
  }

  solve(nodes);

  for (const auto& node : nodes) {
    std::cout << node.name << ' ' << node.distance_from_root << std::endl;
  }
}

ダイクストラ法

辺の重みが非負のグラフに対する単一始点最短経路問題にはダイクストラ法がシンプルで効率が良い。

ダイクストラ法は幅優先探索と似たコードで実装できる。キューの代わりに優先度付きキューを使い、「経路の重みの小さい頂点から辿れる頂点」から順に経路の重みを決定していくようにする。

同じくAizu Online Judgeの単一始点最短経路の問題を解くコードをメモ。

#include <iostream>
#include <limits>
#include <queue>
#include <vector>

template<typename D>
struct link
{
  D destination;
  int length;
};

struct node
{
  int name;
  std::vector<link<node*>> links;
  int distance_from_root{std::numeric_limits<int>::max()};
};

void solve(std::vector<node>& nodes, node& root)
{
  auto queue_compare = [](const node* lhs, const node* rhs) {
    return lhs->distance_from_root > rhs->distance_from_root;
  };
  std::priority_queue<
      node*,
      std::vector<node*>,
      decltype(queue_compare)
  > queue{queue_compare};

  root.distance_from_root = 0;
  queue.push(&root);

  while (!queue.empty()) {
    auto* target = queue.top();
    queue.pop();

    for (const auto& link : target->links) {
      auto* neighbor = link.destination;
      const auto d = target->distance_from_root + link.length;
      if (neighbor->distance_from_root <= d) continue;
      neighbor->distance_from_root = d;
      queue.push(neighbor);
    }
  }
}

std::string distance_string(int distance)
{
  return distance == std::numeric_limits<int>::max()
      ? "INF"
      : std::to_string(distance);
}

int main()
{
  int node_count, link_count, root_name;
  std::cin >> node_count >> link_count >> root_name;

  std::vector<node> nodes(node_count);
  for (int i = 0; i < link_count; ++i) {
    int s, t, d;
    std::cin >> s >> t >> d;
    auto& n = nodes.at(s);
    n.name = s;
    n.links.push_back(link<node*>{&nodes.at(t), d});
  }

  solve(nodes, nodes.at(root_name));

  for (const auto& n : nodes) {
    std::cout << distance_string(n.distance_from_root) << std::endl;
  }
}