2008年7月8日
#
インスパイア元 → ソートなんかしていないんですけど
もっすぬごいソート・アルゴリズムを編み出してしまいました。
その名も「チルノ・ソート」
Module CirnoSort
' 配列内に対象があればTrue
Function あった(ByVal 配列() As Integer, ByVal 対象 As Integer) As Boolean
For Each 値 As Integer In 配列
If 値 = 対象 Then
Return True
End If
Next
Return False
End Function
Sub Main()
Dim N As Integer = 10
Dim ソート対象(N) As Integer
Dim 乱数 As Random = New Random(DateTime.Now.Millisecond)
Dim 添え字 As Integer
Dim 値 As Integer
' 対象初期化
For 添え字 = 0 To N - 1
ソート対象(添え字) = 乱数.Next(1, 100)
Next
'表示
For Each 値 In ソート対象
Console.Write("{0} ", 値)
Next
Console.WriteLine(vbCrLf & "------------------")
' ソート対象内の最小値/最大値を求めておく
Dim 最小値 As Integer = ソート対象(0)
Dim 最大値 As Integer = ソート対象(0)
For Each 値 In ソート対象
If 最小値 > 値 Then 最小値 = 値
If 最大値 < 値 Then 最大値 = 値
Next
'ソート(あたいったら最強ね!)
For 値 = 最小値 To 最大値
If あった(ソート対象, 値) Then
Console.Write("{0} ", 値)
End If
Next
Console.WriteLine(vbCrLf & "------------------")
Console.ReadKey()
End Sub
End Module
ソート対象内の要素の重複が許されませんがそこはご勘弁(チルノだから)。
...のんちゃん、お願いだから真に受けないでね。
なんか流れ的に ソート祭り になってます♪
のんちゃんのVBお勉強に協力する試み (1) のお題にソートを
選んだのがことの発端。
のんちゃんのお勉強が目的なのでヅバリな回答を挙げられず、
みなさんがそれぞれ斜に構えたエントリで楽しませてくれてます。
いや実におもしろい。
この面白さがわからんのはプログラマとして可哀想なりー
2008年7月7日
#
ネタ元 → ソートが熱いらしいので
くそっ、一個多くしてやる...
Module Module1
Sub 逆順なら交換(ByRef x As Integer, ByRef y As Integer)
If x > y Then
Dim tmp As Integer = x
x = y
y = tmp
End If
End Sub
Sub Main()
Dim ソート対象(3) As Integer
Dim rnd As Random = New Random(DateTime.Now.Millisecond)
' 対象初期化
ソート対象(0) = rnd.Next(1, 100)
ソート対象(1) = rnd.Next(1, 100)
ソート対象(2) = rnd.Next(1, 100)
ソート対象(3) = rnd.Next(1, 100)
'表示
For Each 値 In ソート対象
Console.Write("{0} ", 値)
Next
Console.WriteLine(vbCrLf & "------------------")
'ソート
逆順なら交換(ソート対象(0), ソート対象(1))
逆順なら交換(ソート対象(1), ソート対象(2))
逆順なら交換(ソート対象(2), ソート対象(3))
逆順なら交換(ソート対象(0), ソート対象(1))
逆順なら交換(ソート対象(1), ソート対象(2))
逆順なら交換(ソート対象(0), ソート対象(1))
'表示
For Each 値 In ソート対象
Console.Write("{0} ", 値)
Next
Console.WriteLine(vbCrLf & "------------------")
Console.ReadKey()
End Sub
End Module
※ﾄﾃｰﾓ大きなヒントになってんだよ♪ > のんちゃん
カレーは晒すきまりでしたよね?
ナスとプチトマトのカレー(ジャワ辛口)。
じゃがいもが入らないので煮込みが短いのも
夏向き。そのぶんさらっとしてるなり。
はい、そゆわけで おにょれ赤坂 でちらっとこぼしたネタをば
CodeZine 「STL/CLRツアーガイド」に書きました。
白状すればSTL/CLRはまだまだいぢり倒してないんですよねー
関東地方は雨模様。
おなじみ"おりひめ"と"ひこぼし"のお話、オリジナルはちょっと違うみたいす。
Wikipediaによりますと、
「天の河の東に織女有り、天帝の子なり。
年々に機を動かす労役につき、雲錦の天衣を織り、容貌を整える暇なし。
天帝その独居を憐れみて、河西の牽牛郎に嫁すことを許す。
嫁してのち機織りを廃すれば、天帝怒りて、河東に帰る命をくだし、
一年一度会うことを許す」
...へぇ。
「おりひめがひこぼしに惚れてデートにかまけて
仕事うっちゃらかしたもんだから神様に怒られて
デート禁止処分くらってめそめそ泣いてるのが
可哀想だから年に一度デートを許した」
んじゃないみたいよ。
2008年7月6日
#
夏も初めのけだるい朝は 趣味のコードとたわむれる
夏も初めの以下省略:ふぉろー
このふたつにおいてもすぬごいバグを見逃しておりました。
そのために時間計算量がΟ(NlogN)になりません。
mergeでチョンボこいてまして、せっかく繋がった連を断ち切っておりました。
おわびに、改行で区切られた文字列の並ぶテキストファイルの各文字列を昇順に並べます。
凝ったマネはしてないけどかなり高速です。
10万行を5秒弱でソートしてくれました。
<業務連絡>鶏唐揚さーん、コレVBに仕立ててくれるぅ?
using System;
using System.IO;
namespace MergeSortOnFile_csharp {
interface IQueReader<T> where T : IComparable<T> {
bool Available { get; }
T Current { get; }
void Next();
bool InOrder { get; }
bool Disorder { get; }
void Reset();
}
interface IQueWriter<T> {
void Write(T val);
}
class StringQueReader : IQueReader<string> {
private TextReader reader_;
private string current_;
private string last_ = null;
public StringQueReader(string path) {
reader_ = new StreamReader(path);
Next(); Reset();
}
public bool Available { get { return current_ != null; }}
public string Current { get { return current_; }}
public void Next() { last_ = current_; current_ = reader_.ReadLine();}
public void Close() { reader_.Close();}
public bool InOrder { get { return Available && last_.CompareTo(current_) <= 0; }}
public bool Disorder { get { return !InOrder; }}
public void Reset() { last_ = current_ ; }
}
class StringQueWriter : IQueWriter<string> {
private TextWriter writer_;
public StringQueWriter(string path) { writer_ = new StreamWriter(path); }
public void Write(string obj) { writer_.WriteLine(obj);}
public void Close() { writer_.Close(); }
}
class Program {
// 二つのキューをマージ(併合)して一つにする
private static void merge<T>(IQueReader<T> reader1, IQueReader<T> reader2, IQueWriter<T> writer) where T : IComparable<T> {
// 入力である二つのキューが共に要素を持っている間
while ( reader1.Available && reader2.Available ) {
// いずれかが連の切れ目に達したら他方の連の切れ目までを出力して仕切り直し。
if ( reader1.Disorder ) {
while ( reader2.InOrder ) { writer.Write(reader2.Current); reader2.Next(); }
reader1.Reset(); reader2.Reset(); continue;
}
if ( reader2.Disorder ) {
while ( reader1.InOrder ) { writer.Write(reader1.Current); reader1.Next(); }
reader1.Reset(); reader2.Reset(); continue;
}
// より小さい要素を取り出して出力する
if ( reader1.Current.CompareTo(reader2.Current) < 0 ) {
writer.Write(reader1.Current);
reader1.Next();
} else {
writer.Write(reader2.Current);
reader2.Next();
}
}
// キューに残る(取り出されなかった)要素を出力する
while ( reader1.Available ) { writer.Write(reader1.Current); reader1.Next(); }
while ( reader2.Available ) { writer.Write(reader2.Current); reader2.Next(); }
}
// 一つの入力列を二つのキューに分割する
private static bool split<T>(IQueReader<T> reader, IQueWriter<T> writer1, IQueWriter<T> writer2) where T : IComparable<T> {
bool dest = true;
bool switched = false;
while ( reader.Available ) {
// 直前の要素より小さな要素を読み込んだら出力キューを切り替える
if ( reader.Disorder ) {
switched = true;
dest = !dest;
}
if ( dest ) writer1.Write(reader.Current); else writer2.Write(reader.Current);
reader.Next();
}
return switched;
}
public static void merge_sort(string in_path, string out_path) {
bool switched;
do {
StringQueReader reader = new StringQueReader(in_path);
StringQueWriter writer1 = new StringQueWriter("tmp1.txt");
StringQueWriter writer2 = new StringQueWriter("tmp2.txt");
switched = split(reader, writer1, writer2);
reader.Close();
writer1.Close();
writer2.Close();
StringQueReader reader1 = new StringQueReader("tmp1.txt");
StringQueReader reader2 = new StringQueReader("tmp2.txt");
StringQueWriter writer = new StringQueWriter(out_path);
merge(reader1, reader2, writer);
reader1.Close();
reader2.Close();
writer.Close();
in_path = out_path;
} while ( switched );
File.Delete("tmp1.txt");
File.Delete("tmp2.txt");
}
public static void Main() {
merge_sort("input.txt","result.txt");
}
}
}
C++/CLI「επιστημηさんまで私を忘れたのですか？」
書いてみた...つか、C#版を機械的にportしただけ。
using namespace System;
using namespace System::Collections::Generic;
// 二つのキューをマージ(併合)して一つにする
generic<typename T> where T : IComparable<T>
void merge(Queue<T>^ in_q1, Queue<T>^ in_q2, ICollection<T>^ out_c) {
// 入力である二つのキューが共に要素を持っている間
while ( in_q1->Count != 0 && in_q2->Count != 0 ) {
// より小さい要素を取り出して出力する
out_c->Add(( in_q1->Peek()->CompareTo(in_q2->Peek()) < 0 )? in_q1->Dequeue():in_q2->Dequeue());
}
// キューに残る(取り出されなかった)要素を出力する
while ( in_q1->Count != 0 ) { out_c->Add(in_q1->Dequeue()); }
while ( in_q2->Count != 0 ) { out_c->Add(in_q2->Dequeue()); }
}
// 一つの入力列を二つのキューに分割する
generic<typename T> where T : IComparable<T>
bool split(ICollection<T>^ in_c, Queue<T>^ out_c1, Queue<T>^ out_c2) {
T last;
Queue<T>^ out_c = out_c1;
bool switched = false;
for each ( T current in in_c ) {
// 直前の要素より小さな要素を読み込んだら出力キューを切り替える
if ( last != nullptr && current->CompareTo(last) < 0 ) {
out_c = (out_c == out_c1) ? out_c2 : out_c1;
}
out_c->Enqueue(last = current);
// 一度でも切り替えが起こったらswitchedをtrueにする
if ( !switched ) switched = (out_c == out_c2);
}
return switched;
}
generic<typename T>
void print(String^ head, IEnumerable<T>^ collection) {
Console::Write("{0} : ", head);
for each ( T item in collection ) {
Console::Write("{0} ", item);
}
Console::WriteLine();
}
generic<typename T> where T : IComparable<T>
void merge_sort(ICollection<T>^ data) {
Queue<T>^ q1 = gcnew Queue<T>();
Queue<T>^ q2 = gcnew Queue<T>();
while ( split(data, q1, q2) ) {
Console::WriteLine(L"--------------------------------");
print(L"input ", data);
Console::WriteLine("split:");
print(L"queue1 ", q1);
print(L"queue2 ", q2);
data->Clear();
merge(q1, q2, data);
Console::WriteLine(L"merge:");
print(L"output ", data);
q1->Clear();
q2->Clear();
}
}
int main() {
List<int>^ data = gcnew List<int>(gcnew array<int> { 1, 3, 2, 5, 4, 7, 6, 9, 8, 0, 13, 12, 11 });
merge_sort(data);
Console::WriteLine(L"--------------------------------");
print(L"result ", data);
}
2008年7月5日
#
ネタ元 → 私のできなさ加減がわかりますね
いいのいいの、僕もえムナウ先生もはつね先生もかるぼCTP先生も
中大人もぽぴ王子もNANIQLOも、誰でもはじめはできん子でした。
それはそぉとして:
考えると、初めてのVBとかでもソートとか書籍になく、
通信でもテキストになかったです。
...なんだよなー。
プログラミングのビギナ向け教本にソートがないのはどぉゆぅ了見かと。
# 聞き飽きた? 僕もいいかげん言い飽きてんですけども ^^;
ソートてのはあらゆるデータ処理の基礎の基礎ぢゃねぇの?
変数の宣言に始まって条件分岐とか繰り返しとかきっちり詰まった
演習問題の鑑みたいなもんじゃないすか。
加えてそのアルゴリズムはたーくさんあってそれぞれに特徴があって考えドコロ満載やし。
イタ飯コック修行におけるペペロンチーノ、若奥様の肉じゃが、大工見習の犬小屋じゃないのかと。
名著「アルゴリズムとデータ構造」なんざソートだけで一冊になってるよなもんや。
こんないいネタをなんでビギナ本で端折るかなー
ネタ元 → この勉強VisualBasicの件ですが・・・・
愛娘のんちゃんがお勉強したいらしい。
んではぼちぼちと問題を出すとしよう。
(はつね先生@VB-MVPが問題作成と答案の添削に協力していただけるそうな)
※ 注意:
1. のんちゃんはトラックバックで回答すること。
2. ヒントが欲しいときゃコメントすること。
3. のんちゃんより先に(解くのはいいが)公開しないこと > ALL
では第１問:
int 配列 を昇順にソートする 関数:
Sub Sort(data() As Integer) を三通り以上のアルゴリズムで書き、
Sub Main() から呼び出して結果を確認しなさい。
(ひとつ25点+Main25点)
なぜかマージソート。
メモリを食わずにファイルIOだけでもソートできる優れもののアルゴリズム。時間計算量はΟ(logN)。
データの振り分けと併合を繰り返してソートを行います。
元データ: 1 3|2 5|4 7|6 9|8|0 13|12|11
※ | はその位置で昇順になっていないことを表します。
ファイルを二本用意し、| の位置で出力先を切り替えながら出力します:
ファイル1: 1 3 4 7 8|12
ファイル2: 2 5 6 9|0 13|11
次にこの二本を読み、より小さいほうを取り出して一本の元データに出力します:
元データ: 1 2 3 4 5 6 7 8 9|0 12 13|11
| で区切られた要素列(これを'連'という)はソートされてて、
振り分けと併合によって連の数が減っていきます。
最終的に連の数が1になればソート完了。
C#で書いてみた。ファイルIOはめんどっちーのでBCLコレクションで:
using System;
using System.Collections.Generic;
class Program {
// 二つのキューをマージ(併合)して一つにする
private static void merge<T>(Queue<T> in_q1, Queue<T> in_q2, ICollection<T> out_c) where T : IComparable<T> {
// 入力である二つのキューが共に要素を持っている間
while ( in_q1.Count != 0 && in_q2.Count != 0 ) {
// より小さい要素を取り出して出力する
out_c.Add(( in_q1.Peek().CompareTo(in_q2.Peek()) < 0 )? in_q1.Dequeue():in_q2.Dequeue());
}
// キューに残る(取り出されなかった)要素を出力する
while ( in_q1.Count != 0 ) { out_c.Add(in_q1.Dequeue()); }
while ( in_q2.Count != 0 ) { out_c.Add(in_q2.Dequeue()); }
}
// 一つの入力列を二つのキューに分割する
private static bool split<T>(ICollection<T> in_c, Queue<T> out_c1, Queue<T> out_c2) where T : IComparable<T> {
T last = default(T);
Queue<T> out_c = out_c1;
bool switched = false;
foreach ( T current in in_c ) {
// 直前の要素より小さな要素を読み込んだら出力キューを切り替える
if ( last != null && current.CompareTo(last) < 0 ) {
out_c = (out_c == out_c1) ? out_c2 : out_c1;
}
out_c.Enqueue(last = current);
// 一度でも切り替えが起こったらswitchedをtrueにする
if ( !switched ) switched = (out_c == out_c2);
}
return switched;
}
public static void print<T>(string head, IEnumerable<T> collection) {
Console.Write("{0} : ", head);
foreach ( T item in collection ) {
Console.Write("{0} ", item);
}
Console.WriteLine();
}
public static void merge_sort<T>(ICollection<T> data) where T : IComparable<T> {
Queue<T> q1 = new Queue<T>();
Queue<T> q2 = new Queue<T>();
while ( split(data, q1, q2) ) {
Console.WriteLine("--------------------------------");
print("input ", data);
Console.WriteLine("split:");
print("queue1 ", q1);
print("queue2 ", q2);
data.Clear();
merge(q1, q2, data);
Console.WriteLine("merge:");
print("output ", data);
q1.Clear();
q2.Clear();
}
}
public static void Main() {
List<int> data = new List<int>(new int[] { 1, 3, 2, 5, 4, 7, 6, 9, 8, 0, 13, 12, 11 });
merge_sort(data);
Console.WriteLine("--------------------------------");
print("result ", data);
}
}
...のんちゃんがVBがんがってるらしいから、
僕もグチこぼしてばっかじゃなくVBでも書いてみる:
Imports System
Imports System.Collections.Generic
Module Program
' 二つのキューをマージ(併合)して一つにする
Private Sub merge(Of T As IComparable(Of T))(ByVal in_q1 As Queue(Of T), ByVal in_q2 As Queue(Of T), ByVal out_c As ICollection(Of T))
' 入力である二つのキューが共に要素を持っている間
While in_q1.Count <> 0 AndAlso in_q2.Count <> 0
' より小さい要素を取り出して出力する
If in_q1.Peek().CompareTo(in_q2.Peek()) < 0 Then
out_c.Add(in_q1.Dequeue())
Else
out_c.Add(in_q2.Dequeue())
End If
End While
' キューに残る(取り出されなかった)要素を出力する
While in_q1.Count <> 0
out_c.Add(in_q1.Dequeue())
End While
While in_q2.Count <> 0
out_c.Add(in_q2.Dequeue())
End While
End Sub
' 一つの入力列を二つのキューに分割する
Private Function split(Of T As IComparable(Of T))(ByVal in_c As ICollection(Of T), ByVal out_q1 As Queue(Of T), ByVal out_q2 As Queue(Of T)) As Boolean
Dim last As T = Nothing
Dim out_q As Queue(Of T) = out_q1
Dim switched As Boolean = False
For Each current As T In in_c
' 直前の要素より小さな要素を読み込んだら出力キューを切り替える
If last IsNot Nothing AndAlso current.CompareTo(last) < 0 Then
If out_q Is out_q1 Then
out_q = out_q2
' 一度でも切り替えが起こったらswitchedをtrueにする
switched = True
Else
out_q = out_q1
End If
End If
last = current
out_q.Enqueue(current)
Next
Return switched
End Function
Public Sub print(Of T)(ByVal head As String, ByVal collection As IEnumerable(Of T))
Console.Write("{0} : ", head)
For Each item As T In collection
Console.Write("{0} ", item)
Next
Console.WriteLine()
End Sub
Public Sub merge_sort(Of T As IComparable(Of T))(ByVal data As ICollection(Of T))
Dim q1 As New Queue(Of T)
Dim q2 As New Queue(Of T)
While split(data, q1, q2)
Console.WriteLine("-------------------------")
print("input ", data)
Console.WriteLine("split:")
print("queue1 ", q1)
print("queue2 ", q2)
data.Clear()
merge(q1, q2, data)
Console.WriteLine("merge:")
print("output ", data)
q1.Clear()
q2.Clear()
End While
End Sub
Sub Main()
Dim data As New List(Of Integer)(New Integer() {1, 3, 2, 5, 4, 7, 6, 9, 8, 0, 13, 12, 11})
merge_sort(data)
Console.WriteLine("-------------------------")
print("result ", data)
End Sub
End Module
2008年7月2日
#
早いねぇ。ちっちゃい頃は一日がめっちゃ長かったように思えるのですが。
それはともかく、7/12は わんくま同盟 東京勉強会 #22 でございますよ。
にわか相棒(?)のアキラたんが一席ぶつし。
赤坂ﾀﾝのXNAもﾜｸﾃｶだし(今回はどんな芸見せてくれるんかなー)。
ありえねー豪華プレゼントも企画されてっし。
前回参加できんかったのもあって、7/12はちゃんと空けときました。
参加申し込みも済ませました。中華街に茶ぁ買いにいかなきゃだわ。
アキラたんのセッション、C++屋にはたまらんネタです。
C++の未来が見えます。もきゅもきゅします。
# スタッフ特権で一足先にぱわぽ資料を見せてもろたんですが、すげーっす。
# 僕もちょこちょこ追いかけてはいたんだけど、一気に並ぶと壮観です > C++の新機能
<業務連絡>
当日関西よりお越しの皆様、大阪勉強会#20に参加した愛娘のんちゃんの報告によると
「関西限定じゃがりこ:ねぎ焼き味」がとてつもなく旨いとのこと。手土産好適品。
<!-- こんだけ紅く太くしとけばきっと -->
</業務連絡>
2008年6月26日
#
/*
* 可及的速やかに破棄したい
* マネージ対象外リソースを持ったクラスのテンプレ
* C++/CLI版
*/
public ref class SampleClass : System::IDisposable {
private:
char* unmanaged_resource; // マネージ対象外リソース
protected:
bool disposed; // Dispose()済みならtrue
// Dispose()後にメソッドが呼ばれたときの用心のため、
// 各public/protectedメソッドはその処理に先立ちこいつを呼ぶことを推奨する。
void method() {
if ( disposed ) {
throw gcnew System::ObjectDisposedException(
this->GetType()->ToString(),
"has been disposed.");
}
}
// Dispose()の実処理はココで行う
virtual void Dispose(bool disposing) {
if ( !disposed ) {
if ( disposing ) {
// managed-resourceを持っている
// ならここでDispose()
}
// ここでunmanaged-resourceを廃棄
delete[] unmanaged_resource;
}
disposed = true;
}
public:
// コンストラクタ
SampleClass() {
unmanaged_resource = new char[100];
disposed = false;
}
// デストラクタ: Dispose() に相当する。
virtual ~SampleClass() {
Dispose(true);
// 後続するFinalize()を抑止する
System::GC::SuppressFinalize(this);
}
// ファイナライザ: Finalize()に相当する
!SampleClass() {
Dispose(false);
}
};
※ 修正: doDispose → Dispose
じゃないんだってさ!
ref class SampleClass {
public:
~SampleClass() { this->!SampleClass(); }
!SampleClass() { /* unmanaged-resourceを破棄する */ }
};
これで十分なんだって。
ネタ元 → コーディングスタイル
読みやすいコード
とは、多くのプログラマの最大公約数のようなものだろうか？
最大公約数てーことはいちばんわからんちんに合わせるってことですか。
何が哀しうてわからんちんに足引っ張られにゃあかんのですか。
コック集団のなかに見習いが一人いたら出来合いの
レトルトハンバーグあっためて客に出しますか。
void string_copy(char dst[], const char src[]) {
int i;
for ( i = 0; src[i] != '\0'; ++i ) {
dst[i] = src[i];
}
dst[i] = '\0';
}
...コレ、読みやすいですか?
なんかね、ひらがなだけで論文書いたような居心地の悪さを感じます。
ひらがなだけでかいたぶんしょうがよみやすいはずがないじゃないですか
void string_copy(char* dst, const char* src) {
while ( *dst++ = *src++ ) {}
}
僕にはむしろコッチの方が読みやすいだけでなくわかりやすいんですｹﾄﾞ
添削お願いしますぅ > えらいひと
/*
* 可及的速やかに破棄したい
* unmanaged-resourceを持ったクラスのテンプレ
*/
public class SampleClass : System.IDisposable {
private object unmanaged_resource; // マネージ対象外リソース
protected bool disposed = false; // Dispose()済みならtrue
// コンストラクタ
public SampleClass() {
// ここでnewしなければならんわけじゃないが
unmanaged_resource = new object();
}
// Dispose()後にメソッドが呼ばれたときの用心のため、
// 各public/protectedメソッドはその処理に先立ちこいつを呼ぶことを推奨する。
protected void assertDisposed() {
if ( disposed ) {
throw new System.ObjectDisposedException(
this.GetType().ToString(),
"has been disposed.");
}
}
// Dispose()の実処理はココで行う
protected void doDispose(bool disposing) {
if ( !disposed ) {
if ( disposing ) {
// managed-resourceを持っている
// ならここでDispose()
}
// ここでunmanaged-resourceを廃棄
}
disposed = true;
}
// Dispose
public virtual void Dispose() {
doDispose(true);
// 後続するFinaraize()を抑止
System.GC.SuppressFinalize(this);
}
// デストラクタ(=Finalize)
public ~SampleClass() {
doDispose(false);
}
}
※ Finalize→~SampleClass に修正しました