Hatena::ブログ(Diary)

salmonsnareの日記

     
     自己紹介

2013-08-28

Cygwin 導入時の setup.ini と setup.bz2 に関する注意 (2013/8/28)

21:14

はじめに

最近、 Cygwin の setup.exe に32 bit 版と64 版のものが用意されたようで、

その影響で setup.ini と setup.bz2 の場所が変わり、エラーが生じているようです。


変更前: $mirror/setup.ini, $mirror/setup.bz2


変更後:

32 bit 版: $mirror/x86/setup.ini, $mirror/x86/setup.bz2

64 bit 版: $mirror/x86_64/setup.ini, $mirror/x86_64/setup.bz2


ただし、$mirror はミラーサイトURL です。


いくつか解決法が分かったので、ここに情報元と併せて記します。

また、 apt-cyg という素晴らしいパッケージ管理システムを覚えたので、上記に付随するエラー対策とともに記します。

当方の環境は 32 bit なので、64 bit の方は適宜読み替えて頂けると幸いです。

新しい setup.exe

数か月前に Cygwin を再インストールして、久しぶりに setup.exe を起動したところ、

なぜかうまく動きませんでした。


そこで、再度公式ページから setup.exe を取得することにしました。

公式ページ: http://cygwin.com/install.html

すると、驚いたことに、32 bit 版の setup-x86.exe, 64 bit 版の setup-x86_64.exe という

新しい setup.exe がダウンロードできるようでした。

僕の環境では setup-x86.exe により、上手く再インストールできました。


apt-cyg との出会い

それから 3 日後、何気なくツイッターをしていたら、手さん (@myg_ さん) のツイートで、

apt-cyg」というパッケージ管理システムが、最近インストール時にエラーを起こしているという情報を得ました。


まず、僕自身、apt-cyg は初耳で衝撃を受けました。おそらく、ネーミングから apt-get みたいなものだろうな

というのは分かるんですが、Cygwin にもこの種のツールがあることに衝撃を受けました。

迷わず、即座に、下記 URL を参考にインストールすることにしました。

Cygwinapt-cyg, http://kkayataka.hatenablog.com/entry/2013/05/03/220854

apt-cyg の導入自体は大変すんなりいきました。apt-get に似た使用感、素晴らしいものがありました。

ただ、ここで、 setup.ini のエラーでうまく apt-cyg からインストールができませんでした。


色々探していると、下記 URL を見つけました。

cygwinで「`setup.ini' というファイルはありません。 Error updating setup.ini, reverting」の対処法,

http://qiita.com/DQNEO/items/f49d5a534eee6c3352a8


上記の修正個所において、setup.bz2 と setup.ini を取ってくる際のディレクトリ名の

「x86_64」を「x86」にすることで、僕の環境でも apt-cyg が上手く動作しました。

そして、先に書いた、新しい setup.exe に 32 bit 版と 64 bit 版が用意されたこととつながりました。

2013-08-21

勉強ノートの置き場

09:20

勉強ノートとして、はてなダイアリーを主に使ってたんですが、

今後はこちらに PDF にしたものをアップロードします。

salmonsnare のノート, https://sites.google.com/site/salmonsnare/

2013-05-24

GitHub を使い始めました。

08:21

4 年前にアカウントを取得して放置していた GitHub を使い始めました。

練習用に、K&R の邦訳の p92 (Chap.4, §4.3) より、逆ポーランド電卓プログラムを、

オライリーC++: The Core Language を参考に、

C++ のクラスを用いて書き換えたコードを書いて GitHub に上げました。

https://github.com/salmonsnare/test/blob/master/reverse_poish.cc

2013-05-22 ヒープソートの実装

はじめに

C++ を勉強したり、久々にコードを書いたりしている経緯で、

練習用に、[Cormen+Leiserson+Rivest+Stein 01] Introduction to Algorithms 2nd edition の Chap. 6 から、

ヒープソートを実装したので貼り付けました。


サブルーチンの切り分けは、

pp127〜142 に記載の擬似コードにできるだけ忠実にしました。

エレガントで新しいデバッグ技法をほとんど存じ上げない為、

「cout」がデバッグ用に頻出しております。


main 関数内に「/* */」のコメントが膨大にありますが、

これは関数それぞれのテスト用です。

こちらも、エレガントで新しいテスト技法をほとんど存じ上げない為、

こういうテストをしております。


課題

ソースコード

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>

using namespace std;

#define INFTY 99999

/* prototype declarations */
int parent(int);
int left(int);
int right(int);

void hsort(int []);
void max_heapify(int [], int);
void build_max_heap(int []);
void swap(int [], int, int);

int heap_maximum(int []);
int heap_extract_max(int []);

void heap_increase_key(int [], int, int);
void max_heap_insert(int[], int);

void build_max_heap_p(int []);

int heap_size = 4;

/* a main function */
main()
{
  int v[5] = {2, 3, 5, 1, 4};
  int i;

  /* heap sort
  hsort(v);
  for (i = 0; i <= 4; i++)
  cout << v[i] << " ";

  cout << "\n";
  */

  /* build max heap and heap extract max
  build_max_heap(v);
  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";
  
  cout << "heap_extract_max = " << heap_extract_max(v) << "\n\n";
  for (i = 0; i <= heap_size ; i++)
  cout << v[i] << " ";

  cout << "\n";
  */

  /* build max heap and increase key and insert key
  build_max_heap(v);
  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";
  
  heap_increase_key(v, 4, 8); 
  cout << "heap_increase_key 3 to 8 \n\n";
  for (i = 0; i <= heap_size ; i++)
  cout << v[i] << " ";

  cout << "\n";

  max_heap_insert(v, 3);
  cout << "insert 3 \n\n";
  for (i = 0; i <= heap_size ; i++)
  cout << v[i] << " ";

  cout << "\n";
  */

  /* build max heap' */

  cout << "input \n";

  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";

  cout << "build_max_heap' \n";
  build_max_heap_p(v);
  for (i = 0; i <= heap_size; i++)
  cout << v[i] << " ";

  cout << "\n";

  return 0;
}

void hsort(int v[])
{
  int length_v = 4;
  int i, j;
  
  build_max_heap(v);
  cout << "build max heap has done.\n\n";

    for (i = 0; i <=4; i++)
    cout << v[i] << " ";

  cout << "\n";
  cout << "heap_maximum = " << heap_maximum(v) << "\n";

  cout << "a main routine of a heap sort starts.\n\n";
  
  for (i = length_v; i >= 2; i--) {
    cout << "length_v are down to 2. Now i = " << i << "\n";
    swap(v, 0, i);
    cout << "swap(v, 0, i): i = " << i << "\n";
 
    for (j = 0; j <= heap_size; j++){
    cout << v[j] << " ";
    }
    cout << "\n";

    heap_size--;
    max_heapify(v, 0);
  }
}

void max_heapify(int v[], int i)
{
  int l = left(i);
  int r = right(i);
  int largest;

  if ((l <= heap_size) && (v[l] > i)){
    largest = l;
    cout << "a largest is left:" << l << "\n";  
  }
  else {
    largest = i;
    cout << "a largest is i:" << i << "\n";  
  }
  if ((r <= heap_size) && (v[r] > v[largest])){
    largest = r;
    cout << "a largest is right:" << r << "\n";  
  }
  if (largest != i){
    cout << "Since a largest is not i, swap and max_heapify:" << i <<"\n";  
    swap(v, i, largest);

    for (i = 0; i <=4; i++)
    cout << v[i] << " ";

  cout << "\n";

  cout << "Now, max_heapify recursively calls max heapify.\n";

    max_heapify(v, largest);
  }
}

void build_max_heap(int v[])
{
  int length_v = 4;
  int i;

  for (i = int(floor(length_v / 2) - 1); i >= 0; i--){
    cout << "build max heap: i = " << i << " max heapify starts.\n";
    max_heapify(v, i);
    cout << "\n\n";
  }
}

void swap(int v[], int i, int j)
{
  int temp; 

  temp = v[i];
  v[i] = v[j];
  v[j] = temp;
  cout << i << " and " << j << " are swapped. \n";
}

int parent(int i)
{
  cout << "a parent is " << int(floor((i - 1) / 2)) << "\n"; 
  return int(floor((i - 1) / 2));
}

int left(int i)
{
  cout << "a left is " << 2 * i + 1 << "\n"; 
  return 2 * i + 1;
}

int right(int i)
{
  cout << "a right is " << 2 * i + 2 << "\n"; 
  return 2 * i + 2;
}

int heap_maximum(int v[])
{
  return v[0];
}

int heap_extract_max(int v[])
{
  int max;

  if (heap_size < 0) {
    cout << "heap underflow \n";
  }

  max = v[0];
  v[0] = v[heap_size];
  heap_size--;
  max_heapify(v, 0);
  return max;
}

void heap_increase_key(int v[], int i, int key)
{
  if (key < v[i]) {
    cout << "new key is smaller than current key\n";
  }
  v[i] = key;
  while ((i > 0) && v[parent(i)] < v[i]) {
    swap(v, i, parent(i));
    i = parent(i);
  }
}

void max_heap_insert(int v[], int key)
{
  heap_size++;
  v[heap_size] = -INFTY;
  heap_increase_key(v, heap_size, key);
}

void build_max_heap_p(int v[])
{
  int i;

  heap_size = 0;
  for (i = 1; i <= 4; i++){
    max_heap_insert(v, v[i]);
  }
}

2013-04-18

組合せ最適化の定本

21:24

組合せ最適化の定本はいくつかあるようですが、

いろんな方にオススメを伺って購入したところ、

下記 3 冊がお気に入りです。

Combinatorial Optimization (Algorithms and Combinatorics)

Combinatorial Optimization (Algorithms and Combinatorics)


グラフ理論の資料について

下記の記事をご参照ください。

無向グラフ http://d.hatena.ne.jp/salmonsnare/20090313/1236942950

有向グラフ http://d.hatena.ne.jp/salmonsnare/20100830/1283154201

マトロイドの資料について

下記の記事をご参照ください。

http://d.hatena.ne.jp/salmonsnare/20090314/1237026194