2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

リスト構造を使わない速いschemeを作ろう

1 :nanashi:2006/07/21(金) 14:24:58
速いschemeを作りたい(遺伝的プログラムをschemeで速く実行したい)などと思ってスレ立てます。

メリット
1.ポインタをたどる回数が減って速度が向上する
2.リストではなく配列を使えるので、メモリの節約になる
3.GCがいらなくなる(?)

実装に際してまずは、どうすべきでしょうか?

2 :nanashi:2006/07/21(金) 14:26:18
prefix型の式を stack counter を使って解く。
(stack counterという考え方では、2項演算子を-1、演算子を1と考える)
例:3xy+y
これを prefix で表現すると
+ * 3 * x y y
-1 -1 1 -1 1 1 1 (stack count)
となる。S式では
( + (* 3 ( * x y))y)
-1 -1 1 -1 1 1 1 (stack count)
(部分木の stack count の総和は1になる。)
見やすくするため、1を+、-1を-で表す。
prefix表現
+ * 3 * x y y
- - + - + + +
S式
(+ (* 3 (* x y))y)
- - + - + + +
()内が1になるか計算
(- - + - + + +) = 1
- (- + - + +) + = 1
- - + (- + +) + = 1
基点は必ず - となる。
どの基点から開始しても必ず1となる終点がある。
+ が示すノードは終端ノードという。
- が示すノードは非終端ノードという。
全ての非終端ノードは2項演算子である。
右側の非終端ノードから計算する。

3 :nanashi:2006/07/21(金) 14:38:27
誤(stack counterという考え方では、2項演算子を-1、演算子を1と考える)
正(stack counterという考え方では、2項演算子を-1、非演算子を1と考える)
間違ったorz

4 :nanashi:2006/07/21(金) 14:50:04
s/非/被
さらに間違った…

5 :nanashi:2006/07/21(金) 19:18:31
以上、前置きでした。

反応少ないし...
既に常識?

6 :デフォルトの名無しさん:2006/07/21(金) 20:28:18
'((1 0) (0 1)) みたいな場合は?

7 :デフォルトの名無しさん:2006/07/21(金) 21:15:43
ぜんぜんわかんねー
ついてけねーよ

萌アニメの話しようぜ

8 :デフォルトの名無しさん:2006/07/21(金) 22:31:42
リストにあらずんば scheme に非ず。

array を使いたいだけなら以下を実装している処理系(ry
http://srfi.schemers.org/srfi-25/srfi-25.html

9 :nanashi:2006/07/21(金) 23:28:04
基本的には、全て2項演算にしたいと思ってます。

考えてみたんですけど

gosh> (quote ((quote (1 0)) (quote (0 1))) )
('(1 0) '(0 1))

は'が余分についてしまうし

gosh> (cons (cons 1 (cons 0 ())) (cons 0 (cons 1 ())))
((1 0) 0 1)

はネストがなんか違うし

もう少し考えて見ます。

10 :nanashi:2006/07/21(金) 23:31:17
>> 8
既にありましたか。
翻訳しないと判らないですけど(汗

11 :デフォルトの名無しさん:2006/07/21(金) 23:50:17
内部実装の話じゃなかったのかYO
srfi-25は配列関係の拡張なんだぜ?

12 :nanashi:2006/07/22(土) 14:03:08
機械翻訳
http://translate.google.com/translate?hl=ja&sl=en&u=http://srfi.schemers.org/srfi-25/srfi-25.html&sa=X&oi=translate&resnum=1&ct=result&prev=/search%3Fq%3DMulti-dimensional%2BArray%2BPrimitives%26hl%3Dja%26lr%3D%26rls%3DGGLD,GGLD:2005-14,GGLD:ja

>>11
内部実装の話です。
srfi-25は(リスト構造を内部実装とした)schemeの拡張ですか?

13 :nanashi:2006/07/22(土) 15:15:32
だとしたら、まだ考える余地はありそうですね。
どう実装していくか指針を立てないと。

14 :デフォルトの名無しさん:2006/07/22(土) 15:47:21
それが出来たとして、速度はまず遅くなるべ、コレじゃ

15 :nanashi:2006/07/22(土) 16:26:13
遅くなりますか?
リスト構造を陽にとらない配列を使って逐次処理させてもですか?

16 :デフォルトの名無しさん:2006/07/22(土) 16:30:42
cons とか rest とかはどうすんの?


17 :nanashi:2006/07/22(土) 16:49:28
http://audacity.sourceforge.net/help/nyquist?lang=ja
リストから物を取得するには、first関数とrest関数を使います。(伝統的には、これらの関数はそれぞれcarとcdrと呼ばれていますが、firstと restは覚えるのにより簡単です。Nyquistではどちらの組み合わせを使っても構いません。)

cdr = rest ですね。

例えばconsは
(cons 1 (cons 2 (cons 3 nil)))
-1 +1 -1 +1 -1 +1 +1
restは
(cdr (cons 1 (cons 2 (cons 3 nil))))
0 -1 +1 -1 +1 -1 +1 +1

という風にcar,cdrは0にしてcdrならcons 1を飛び越えさせるとか?
(nilはschemeじゃないですね。本来()にすべきですけど説明のため使いました。)

18 :デフォルトの名無しさん:2006/07/22(土) 18:31:53
>>9
亀レスだけども…

> (cons (cons 1 (cons 0 ())) (cons (cons 0 (cons 1 ())) ()))
((1 0) (0 1))

こうすれば全て 2 項演算にできるよ.
当たり前過ぎてわざわざ書くまでもないかも知れないけど,一応.


19 :nanashi:2006/07/22(土) 18:36:34
ありがとうございます。
参考になりました。
(まだ、schemeそのもののレベルが低いかも(汗

20 :デフォルトの名無しさん:2006/07/22(土) 19:07:06
scheme っぽい俺言語を作ろうとしてんのか、
早いscheme を作ろうとしてんのか、どっちだ?

21 :デフォルトの名無しさん:2006/07/22(土) 19:24:51
>>17
cdrも知らないレベルなの?

何の言語でインプリメントするのかわからんけど、
その言語で書いた方が早いだろ。

22 :デフォルトの名無しさん:2006/07/22(土) 19:42:37
の前に1は普通のScheme
インタプリタを書いたことがあるのか?

23 :デフォルトの名無しさん:2006/07/22(土) 20:01:51
学生時代にはScheme使ったけど、業務でScheme使うことってアル?

24 :デフォルトの名無しさん:2006/07/22(土) 22:59:29
>>9
いあ、そーいう話でなくて内部でデータとして '((1 0) (0 1)) を格納するときには
何を基準にしてリストの先頭を見分けようとしてるのかって話

25 :デフォルトの名無しさん:2006/07/23(日) 07:43:18
>>23

大学に就職しろ

26 :nanashi:2006/07/23(日) 09:49:42
>>20
> 早いscheme を作ろうとしてんのか、どっちだ?

早いscheme を作ろうとしてます。
(結果として俺言語になってしまう場合を除いて)


>>21
> cdrも知らないレベルなの?

cdrではなくrestを知りませんでした。
car = first
cdr = rest
と呼ばれることがあることをはじめて知りました。

>何の言語でインプリメントするのかわからんけど、
>その言語で書いた方が早いだろ。

CかC++でインプリメントする予定です。
(もしschemeで書こうと思われているなら私の説明不足でした。)


>>22
>の前に1は普通のScheme
>インタプリタを書いたことがあるのか?

見よう見まねですが、SICPの4章と5章、それぞれの方式で書きました。
この場合schemeによるschemeインタプリタでCなどでは実装したことはないです。

27 :nanashi:2006/07/23(日) 09:51:08
>>23
>業務でScheme使うことってアル?
今のところありません。


>>24
>いあ、そーいう話でなくて内部でデータとして '((1 0) (0 1)) を格納するときには
>何を基準にしてリストの先頭を見分けようとしてるのかって話

(cons (cons 1 (cons 0 ())) (cons (cons 0 (cons 1 ())) ()))
- - + - + + - - + - + + +

(ここでは、-は-1の意味、+は+1の意味)
とすればスタックカウンタが1になった時点、つまり最後の()をリードした時点で
「どこから開始して1になったか」を基準に見分けられます。
1になったところから逆順にpopしていけば見分けられます。

28 :nanashi:2006/07/23(日) 10:05:15
http://save.k.u-tokyo.ac.jp/jsces/trans/trans2004/No20040026.pdf
この文献の「4.並列分散線形GP」の部分の説明がわかりやすいと思います。

29 :デフォルトの名無しさん:2006/07/23(日) 10:18:07
ほほほほほ

30 :デフォルトの名無しさん:2006/07/23(日) 10:19:35
スキーマスキーマ

31 :デフォルトの名無しさん:2006/07/23(日) 10:21:35
ねむねむ

32 :デフォルトの名無しさん:2006/07/23(日) 11:04:13
セーラー服を

33 :デフォルトの名無しさん:2006/07/23(日) 11:06:53
脱がさないで山本君

34 :デフォルトの名無しさん:2006/07/23(日) 11:07:41
ブタが豚箱で臭い飯ププ

35 :nanashi:2006/07/23(日) 11:42:01
気になる資料が…
http://home.pipeline.com/~hbaker1/LinearLisp.html

36 :nanashi:2006/07/23(日) 12:21:01
機械翻訳
http://translate.google.com/translate?hl=ja&sl=en&u=http://home.pipeline.com/~hbaker1/LinearLisp.html&sa=X&oi=translate&resnum=1&ct=
result&prev=/search%3Fq%3DLively%2BLinear%2BLisp%2B--%2B%2527Look%2BMa,%2BNo%2BGarbage%26hl%3Dja%26lr%3D%26rls%3DGGLD,GGLD:2005-14,GGLD:ja

37 :デフォルトの名無しさん:2006/07/23(日) 12:49:11
>>27
何が何でも2項演算子付けた形で格納する気なのか・・・
本来定数オーダーで処理できる cdr やら基本的な処理ですら
配列読んで探しにいかなきゃならんってのはどうなんだろう

38 :nanashi:2006/07/23(日) 13:54:18
むむ。確かにそうかも。
帰って遅くなりるかもしれない希ガス

何か別な方法ありますか?

39 :nanashi:2006/07/23(日) 14:24:13
翻訳途中報告

Abstract
線形のロジックは、ガーベジ・コレクションの問題の1つの解決策として提案されており、より多くの関数型言語内の効率的な「update-in-place」能力を提供しています。

線形論理はアクセスのしやすさを持ちます。そしてその結果、コピーは明示的な分配されたメモリの並列処理に、より適切な機械的メタファーを提供します。

しかし、線形理論における分割の不足は、それ自身の著しい非能率を導入するかもしれません。



私たちは非線形の論理に関する恒常的要因の中を走るLinear Lispと呼ばれる直線的な論理の効率的な実現を示します。

このLinear LispはRPLACXに操作を許して、非線形のLispと同じくらい安全にストレージを管理しますが、ガベージコレクターを必要としません。

割り当てを提示するが、共有を提示しないので、それは関数型言語と命令的な言語の間の中間層を占めます。

連結/グラフリダクションマシンと同じ能力の多くを提供しますが、私たちのLinear Lisp Machineは連結/グラフリダクションマシンのコピーとガーベージコレクション問題なしでそうします。


...意味が通ってない...orz

40 :nanashi:2006/07/23(日) 16:06:01
翻訳途中報告2

Introduction
お互いに借り手であり、そして貸し手でもありなさい;

ローンはたびたびローンそれ自体と友人の両方を失うから… [Shakespeare, Hamlet, I. iii 75]



共有がコピーの代わりになるので、データ構造の共有は効率的である場合があります。しかし、それは誰がそれらの管理に責任を負うかに関して曖昧さを作成します。

この曖昧さは静的に[Barth77][Bloss89][Chase87][Hederman88][Inoue88][Jones89][Ruggieri88]を削除するのが難しい。
また、私たちは、静止の共有分析(純粋な関数型言語用のさえ)がそうかもしれない[Baker90]を示しました、MLタイプ推論と同じくらい困難な、それは指数関数的な[Mairson90]であると知られています。

[脚注2]私たちはここに次のことを示します。共有に関連しているあいまいさを無くす必要があるというよりむしろ、共有の偶発的(副次的)利点を活用するシステムであり、共有が効率を提供することができるのを示します。



線形論理は、陽に共有、もしくはコピーされるべきでないオブジェクトに対処する方法としてジラード[Girard87]によって発明されました。

Wadler[Wadler91]は、単一性参照を備えたデータ構造の使用がガーベジ・コレクションの問題を回避し、かつO(1)配列最新版に備えるためにカウントする方法を提案しました。

Wakeling[Wakeling91]は線形のロジックをインプリメントし、コピー要求がそのインプリメントでは困難であり、非常に遅いことを知りました。

私たちのLinear Lisp マシンは、単一参照がカウントデータ構造であるWakelingのマシンより効率的にインプリメントし、従来の連結/グラフリダクションマシンのインプリメントより「競争力があります。」


41 :nanashi:2006/07/23(日) 16:11:06
(´ρ`)

42 :nanashi:2006/07/23(日) 18:50:30
翻訳途中報告3

A Linear Lisp Machine
このセクションの中で、私たちは、全てのconsセルが
ちょうど1の参照カウントを持っているLisp Machine の
オートマトン理論モデル(それはデータ構造がすべて木であることを暗示する)
を導入します――なぜなら、それらは共有またはサイクルを持っていません。例えば、私たちの線形のリスプでは、NREVERSEはREVERSEに同形です。



私たちの機械は、consセルにアトムかポインターのいずれかを固定することができる有限状態コントロールおよびnポインターレジスタから成ります。

アトムはNILかシンボルのいずれかです。

レジスタの1つ(fr)は、「free list」レジスタとして区別されて、NILの無限のリストを示すために初期化されます。

別のレジスタ(sp)は「スタックポインタ」レジスタとして指定されます。

43 :nanashi:2006/07/23(日) 18:51:20
マシンは以下のアトム操作のどれかを実行することができます:
r1<->r2;/* swap r1,r2. */
r1<->CAR(r2);/* r1,r2 distinct; precondition(not ATOM(r2)) */
r1<->CDR(r2);/* r1,r2 distinct; precondition(not ATOM(r2)) */
NULL(r1);/* predicate for r1=NIL */
ATOM(r1);/* predicate for r1=NIL or symbolp(r1) */
EQ(r1,r2);/* defined only for atomic r1,r2; see [Baker93ER] */
r1:='foo;/* precondition(ATOM(r1) and ATOM('foo)) constant 'foo */
r1:=r2;/* precondition(ATOM(r1) and ATOM(r2)) */

CONS(r1,r2):/* r1,r2 distinct; r2<-CONS(r1,r2) and set r1=NIL */
{r1<->CAR(fr); r2<->fr; fr<->CDR(r2);};

PUSH(r1,r2):/* r1,r2 distinct; Push r1 onto r2 and set r1=NIL */
CONS(r1,r2);

POP(r1,r2):/* r1,r2 distinct; Pop CAR(r2) into r1 if r1=NIL */
if NULL(r1) and not ATOM(r2)
then {fr<->CDR(r2); r2<->fr; r1<->CAR(fr);}
else die;


この文献を掘り下げる価値はあるのだろうか…

44 :デフォルトの名無しさん:2006/07/23(日) 22:17:01
今は亡きCマガ2002/4「学問のススメ」にLinear Lispの概要が
2ページに渡って載ってた。参考文献は>35のもの。

45 :nanashi:2006/07/24(月) 09:42:07
どうやら、Linear Lispで言っているのは
単一のセルをふたつ以上のポインタが決して指さないように評価機を構成することであり、
プログラム自身がどう表現されているかはとは関係ない模様です。orz

46 :nanashi:2006/07/24(月) 18:52:21
重要な情報を提供していただいたので掲載

参照を1回に制限することで「GCを不要にしている」Lisp処理系としては、newlispというものがある。
http://www.newlisp.org/
メモリ管理の詳細↓
http://newlisp.org/MemoryManagement.html

47 :デフォルトの名無しさん:2006/07/24(月) 22:56:16
GC周りは過去の成果を沢山あさる必要があるかも…
手助けできそうにないが、がんがれ

48 :デフォルトの名無しさん:2006/07/25(火) 00:17:24
28の文献を読んだが……
速いScheme評価器実装の助けにはならないんじゃないかと

28の文献は「解の探索問題」を遺伝的プログラミングで解こうとしている.
「解の探索」はマシンが多いほど早く解けるので,
クラスタを使って並列でやろうという話になった.
クラスタでやるとマシン間の通信がネックになるし,
このケースだと↓のような問題もある.

マシンが持っている式(遺伝子)をツリーで表現したとすると
通信の前後でシリアライズ・デシリアライズみたいなのが
必要になってオーバヘッドが大きくなる.

そこで,式をツリーでは無く「配列+スタックカウント」で
表現するようにして,なるべく簡単に送受信できるようにした.

49 :nanashi:2006/07/25(火) 11:25:47
それもあるでしょうが、

LinearGPシステムの構築と評価
http://www.miv.t.u-tokyo.ac.jp/ibalab/papers/98/tokui98.pdf

は通信とか並列化とか関係なくやってるようです。
どう思います?

50 :nanashi:2006/07/25(火) 18:27:06
なんか、もう両方に書くのが面倒なので
http://d.hatena.ne.jp/ufo23/
さらします。
荒らさないでください。

51 :デフォルトの名無しさん:2006/07/25(火) 23:42:03
>>49 読みました.
確かに,通信とか関係なく効率よくなってます.

でも>>49にしても>>28にしても,成果は
遺伝的プログラミングの計算が速くできた,ということで
速いScheme評価器を作るのとは別の話では

>>1が作りたいのは,汎用のSchemeじゃなくて,
遺伝的プログラミングの解法に特化したScheme
ということですか?
Schemeを間にはさむ意味がちょっとわからないです

52 :デフォルトの名無しさん:2006/07/26(水) 04:04:29
GPでの事例はわかったのだが、Schemeに使って意味があるのかどうか・・・
評価されるコードの部分はバイトコードに落として、そも配列としてアクセスできるので意味ないし
関数listが生成するリストを>>1の方式に差し替えるくらいなら、ユーザー側でvector使うだろうし
>>1はどの部分の高速化に使えると考えてるわけよ?その辺がさっぱりわからん

53 :nanashi:2006/07/26(水) 10:38:48
>>51

> でも>>49にしても>>28にしても,成果は
> 遺伝的プログラミングの計算が速くできた,ということで
> 速いScheme評価器を作るのとは別の話では

なるほど、実はそれに気がついて
同じような疑問を自分でもなんとなくですが抱いていました。

> >>1が作りたいのは,汎用のSchemeじゃなくて,
> 遺伝的プログラミングの解法に特化したScheme
> ということですか?
> Schemeを間にはさむ意味がちょっとわからないです

そうすると「遺伝的プログラミングの解法に特化したScheme」に必然的になってしまいます。

54 :nanashi:2006/07/26(水) 10:39:51
>>52
> 関数listが生成するリストを>>1の方式に差し替えるくらいなら、ユーザー側でvector使うだろうし
> >>1はどの部分の高速化に使えると考えてるわけよ?その辺がさっぱりわからん

ユーザー側でvector使うと言う手が確かにありますね。
思い当たりませんでした(汗
どの部分の高速化をするのかと言うと、
遺伝的プログラミング組んだ場合の
個体の評価プロセスの高速化ということになります。

結局、schemeそのものの高速化にはならない気がしてきました。
この方法は遺伝的プログラミングの高速化にしかならないですね。
そうすると、最初の発想の時点で外していたことになってしまいますね。

なんか、だめぽ...orz

でも「遺伝的プログラミングの解法に特化したScheme」という手があるか?
いや、あまりメリットがなさそうな気もする…

55 :デフォルトの名無しさん:2006/07/26(水) 23:11:03
失礼だが1はANSI common lispは読んだ?
gcさけて高速かするためにリスト以外の型がある。

56 :nanashi:2006/07/27(木) 11:11:35
common lispはさっぱり判らないです。

GC避ける方法は
>>46
に書かれていそうですが、
その本なら日本語で読めるってことでしょうか?

57 :nanashi:2006/07/27(木) 14:56:49
)gcさけて高速かするためにリスト以外の型がある。
む、なんか勘違いかも…
schemeにその型はなさそうです。
>>46の new lisp もそうやって居るのかもしれないですけど、
そっちの翻訳、保留にしてしまったので不明です。

58 :nanashi:2006/07/27(木) 21:03:09
初期の構想はそもそもGPを早くすることが出来ると思って考えたことでした。
どうやら、その構想には欠陥があると感じてます。

そこで、方針を変えて、GPのサンプルをschemeで実装してから、
速度に問題があるならschemeの実装そのものを見直すとか
C++でGP実装するとかしたいと思います。

59 :nanashi:2006/07/27(木) 21:22:54
>>58はちょっと、説明ミスです。
正確には「GPを速くすることが出来ると思った」ではなく
「GPを速くする方法でschemeを速くすることが出来ると思った」ですね。

60 :nanashi:2006/07/27(木) 21:24:26
遺伝的プログラミング(GP)の概要
http://mikilab.doshisha.ac.jp/dia/research/report/2004/0802/002/report20040802002.html
だいたい、これを基準にGPを実装しようと考えています。

61 :nanashi:2006/07/27(木) 21:29:34
任意のリストから解となるリストを出力可能なS式を求めるのを
目標にしたいと思います。

例:(a b c)を(c d e f)に変換するS式を求める。

これは、人工無脳の対話に応用できるかもしれないと思ったからです。

62 :nanashi:2006/07/27(木) 21:31:03
今日実装したのは非終端記号(関数)と終端記号(引数)をランダムに出力するものです。

63 :nanashi:2006/07/27(木) 21:33:04
非終端記号(関数)をランダムに出力するコード

(use math.mt-random)

(define mt (make <mersenne-twister> :seed (sys-time)))

(define (non-terminal)
(let ((rdm (mt-random-integer mt 8) ))
(cond ((eq? rdm 0) 'car)
((eq? rdm 1) 'cdr)
((eq? rdm 2) 'cons)
((eq? rdm 3) 'quote)
((eq? rdm 4) 'define)
((eq? rdm 5) 'if)
((eq? rdm 6) 'eq?)
((eq? rdm 7) 'list?)
(else '()))))

64 :nanashi:2006/07/27(木) 21:35:54
終端記号(引数)をランダムに出力するコード

(use math.mt-random)

(define mt (make <mersenne-twister> :seed (sys-time)))

(define (terminal)
(let ((rdm (mt-random-integer mt 26) ))
(cond ((eq? rdm 0) 'a)
((eq? rdm 1) 'b)
((eq? rdm 2) 'c)
((eq? rdm 3) 'd)
((eq? rdm 4) 'e)
((eq? rdm 5) 'f)
((eq? rdm 6) 'g)
((eq? rdm 7) 'h)
((eq? rdm 8) 'i)
((eq? rdm 9) 'j)
((eq? rdm 10) 'k)
((eq? rdm 11) 'l)
((eq? rdm 12) 'm)

65 :nanashi:2006/07/27(木) 21:36:39
...続き

((eq? rdm 13) 'n)
((eq? rdm 14) 'o)
((eq? rdm 15) 'p)
((eq? rdm 16) 'q)
((eq? rdm 17) 'r)
((eq? rdm 18) 's)
((eq? rdm 19) 't)
((eq? rdm 20) 'u)
((eq? rdm 21) 'v)
((eq? rdm 22) 'w)
((eq? rdm 23) 'x)
((eq? rdm 24) 'y)
((eq? rdm 25) 'z)
(else '()))))

冗長かも、ループ使って短く出来そうな…


66 :デフォルトの名無しさん:2006/07/27(木) 21:39:13
consセル・リストやGCと共にSchemeの速度の足を引っ張っている
動的型付けに関してはどう考えているのかね。

67 :デフォルトの名無しさん:2006/07/27(木) 21:44:31
動的型の実行時収集と最適化はSelfの論文読めばいいんでないの?>>66


68 :デフォルトの名無しさん:2006/07/27(木) 22:56:20
おれlisper見習いなんだけど…誰か1がやりたいことを翻訳してくれないか?
すげー高度な話?

69 :nanashi:2006/07/28(金) 10:03:58
すげー簡単に翻訳すると「プログラムをプログラムで進化させる」です。
(だれか、と言っているのに自分で書いてどうする…)

70 :nanashi:2006/07/29(土) 08:41:32
はしょりすぎた。申し訳ないm(_ _;m

今回、GPでやろうとしていることはテストであって自然言語処理ではない。
あるリストを別のリスト、さらに次のリストという風に変換する
プログラムを作るプログラムのを実装する。
今は文字列ではなくa〜zのリストと言うことになっているが、
ゆくゆくは自然言語処理も可能かもしれない。

という事をやろうとしてます。

71 :nanashi:2006/07/29(土) 11:28:48
判りづらいと指摘を受けたので直しました。

進化的手法の代表例でるGPは現在盛んに研究されいます。
GPを自然言語処理に応用するための基礎技術として
「任意のリスト(アルファベット小文字1文字のみのリスト)から、
 解となるリスト(アルファベット小文字1文字のみのリスト)を
 出力するプログラム」
を実現するプログラムをGPで実現させようとしています。
このとき、GPも、それで作成されるプログラムも使用する言語に
schemeを選択しました。
ある数列から、解となる別の数列を作るでもいいかもしれません。
単純だけど対話プログラムに発展できる可能性があるかも。

72 :nanashi:2006/07/29(土) 11:30:50
以下に例を示します。

* 解くべき問題の例としては、リスト'(a b c)を
 リスト'(d e f g)に変換するプログラムを求めます。
* 自然言語処理を例とするなら、「自然 は 大切だ」を
 「科学 は 人類 の 英知だ」に変換するためのプログラムを
 遺伝的プログラムで生成することになります。
 この文章「自然は大切だ」は要素別に並べると
 「自然」「は」「大切だ」となり、
 これはリストで表現できます。
 つまりLispでは'(自然 は 大切だ)になります。

だいたい、趣旨は伝わったでしょうか?

73 :デフォルトの名無しさん:2006/07/29(土) 11:45:51
リストの実装を不定長配列にして、
インターフェースはcons/car/cdrのまま、
って実装は昔から良く実装報告があるよ。
信学技報にも探せばあると思う。

74 :デフォルトの名無しさん:2006/07/29(土) 15:59:43
>>68
Lisp系の言語はデータをListとして持ってて各要素は

element{
 pointer data;
 pointer nextElement;
}

みたいな構造体になっているんだけど、各要素を処理して、
次のnextElementにいくときのポインタ操作がコストが掛かる

data[];

みたいな配列にしてしまえば次の要素移動するには、
アドレスをインクリメントするだけだから早いんだぜ!

って話だと思ったんだけどどうよ?

75 :デフォルトの名無しさん:2006/07/29(土) 16:06:12
古のcdrコーディングなんてのを思い出したよ。



76 :デフォルトの名無しさん:2006/07/29(土) 16:18:13
話を聞けば聞くほど「何故Schemeなのか」がまるで解らない。

77 :nanashi:2006/07/29(土) 16:40:13
>>76
それはあなたが「GP」について無知だからでしょう。
解るようになるまでgoogle等で勉強してから来てください。

78 :デフォルトの名無しさん:2006/07/29(土) 17:00:23
>>77みたいな騙りが出るからトリップ付けろ>>1

79 :nanashi:2006/07/29(土) 17:40:34
騙りではありません。
少々冷たい物言いにカチンと来たのかもしれませんが
そんなことで騙り扱いするのはやめてください。
解らないことを勉強するのは当然のことですから。

80 :nanashi:2006/07/29(土) 17:58:32
あ、偽者だ>>77 >>79 は僕じゃないです。
2chならではの面白い現象に遭遇してどきどき。
ところで、トリップって何ですか?


81 :hoge ◆MvRbZL6NeQ :2006/07/29(土) 18:01:46
名前欄に、名前の後に#で始まる文字列を入れておくと、こんなふうにハッシュされた
値が表示されます。#の後の文字列を知らない限りこれと同じ値を作るのは難しいので、
なりすましを防止できます。

82 :hoge ◆MvRbZL6NeQ :2006/07/29(土) 18:02:58
これは名前欄に hoge#hoge と入れた例。

そういえばなんでトリップっていうんだろうね。

83 :nanashi ◆XQNqqmrLFw :2006/07/29(土) 18:14:38
こんな感じですか?

84 :nanashi ◆XQNqqmrLFw :2006/07/29(土) 18:21:19
>>74さん
途中から趣旨が「速いschemeを作る」から
「schemeでGPを動かして、遅かったら速いschemeを作るなりCかC++でGPを実装する」
に変わりました。
すいませんm(_ _m

>>76さん
最近のGPの動向ではC++で作るようです。
なぜschemeかはschemeの勉強もかねているからです。

とりあえず、今日やってみたことを日記に書いたのでリンク張っておきます
http://d.hatena.ne.jp/ufo23/20060729
(これって販促ですか?>日記にリンク)

85 :nanashi ◆XQNqqmrLFw :2006/07/29(土) 18:24:00
しまった。
s/販促/反則
だったorz

86 :nanashi ◆XQNqqmrLFw :2006/07/29(土) 20:52:20
補足しておくと
当初は>>74さんの言うとおりの目論見でした。
だけど、スレッドの>>53 >>54で破綻してます。

…スレッド立て直したほうがいいですか?

87 :デフォルトの名無しさん:2006/07/29(土) 21:14:44
リストがポインタたどるから遅い、っての常識だよね?
schemeって本ものの配列は無いんだっけ??

88 :デフォルトの名無しさん:2006/07/29(土) 21:16:21
常識じゃないよ

89 :デフォルトの名無しさん:2006/07/29(土) 21:20:00
つうか、もうこのスレ要らないだろ。ちゃんと削除依頼出しとけよ
アホの子>1は。

90 :デフォルトの名無しさん:2006/07/29(土) 21:27:43
GAやGPのスレとして立て直すのも手だと思うが、>>1の日記スレになっても萎えるしな
つか、GAのスレどこいったんだぜ?

91 :nanashi ◆XQNqqmrLFw :2006/07/29(土) 21:47:22
わかりました。終了します。
というか、放置すれば自動でdat落ち?

92 :デフォルトの名無しさん:2006/07/29(土) 22:10:22
死ね。責任もって削除依頼だせ

93 :デフォルトの名無しさん:2006/07/30(日) 06:18:46
シミュ板にGPのスレがあるな

94 :デフォルトの名無しさん:2006/07/30(日) 06:20:08
GP(遺伝的プログラミング)ってどうよ!
http://science4.2ch.net/test/read.cgi/sim/1027647042/

これ

95 :デフォルトの名無しさん:2006/07/30(日) 07:20:11
>>92
なんだろね、君がスキルのかけらもない人間なのが
それだけの文面でわかっちゃうよw

96 :デフォルトの名無しさん:2006/07/30(日) 10:42:36
>>95
お前の文面では
お前は生きる価値も無い人間だというのがわかっちゃうけどなw

97 :デフォルトの名無しさん:2006/07/30(日) 11:21:08
逝きます
さようなら

98 :デフォルトの名無しさん:2006/07/30(日) 11:48:23
とっとと死ね

99 :デフォルトの名無しさん:2006/07/30(日) 11:55:46
lispの高度な話でもりあがるかと期待したんだが残念だ。それでも
何にせよ動いた奴>>>何にもしない奴

1はがんばれ!

100 :デフォルトの名無しさん:2006/07/30(日) 12:21:38
がんばって自分の体重を支えられるロープを買ってきて吊れ

101 :デフォルトの名無しさん:2006/07/30(日) 17:46:08
スキル無いって言い当てられてからの
迷走ぶりがひどいなw

102 :デフォルトの名無しさん:2006/07/30(日) 18:06:02
どっちかというと、生きてる価値がないとバレてからの迷走ぶりの方が酷いと思われw

103 :デフォルトの名無しさん:2006/07/30(日) 19:07:25
ひとを苛むことで悦に入ってる100-102よりましだと思うがな(笑

104 :sage:2006/07/30(日) 20:01:42
全員逝ってよし

105 :デフォルトの名無しさん:2006/07/30(日) 20:56:25
>>104
オマエモナー

106 :デフォルトの名無しさん:2006/07/30(日) 21:08:56
オウム返しは全部同一人物だろうな

107 :デフォルトの名無しさん:2006/07/30(日) 21:31:41
削除依頼まだやってないのかよ。とことん低脳だな。

108 :デフォルトの名無しさん:2006/07/30(日) 23:24:06
最初はみんな>>1はどんな凄い事をやろうとしているんだろうと>>1が何を書いているか
意味が分からなかったからドキドキして読んでたんだけど、
>>74が簡潔にCでやりたい事を説明した途端、たいした事無いと分かって大荒れ

って感じだろうな。

109 :デフォルトの名無しさん:2006/07/31(月) 05:58:50
セルが普通のconsかvectorかで条件分岐するから、
一手間かかって遅くなるわな。
可変長データになって、GCも手間がかかる。

Lisp machineはマイクロコードで、条件分岐できるから、
cdr encodingを採用したヤツが多かった。

110 :デフォルトの名無しさん:2006/07/31(月) 09:35:51
昔ならユーザーがばりばり型指定してリストをさけるコードが
結局一番速い気がする…今だとどうだろねぇ

111 :nanashi ◆XQNqqmrLFw :2006/07/31(月) 11:16:45
一日チェックする暇がなかったので、
今日チェックしてみてまだ、書き込みがあったので驚き。
なんか、みなさんありがとうございます。

でも続きは
>>94さんの言っていた
GP(遺伝的プログラミング)ってどうよ!
http://science4.2ch.net/test/read.cgi/sim/1027647042/
に書いたほうがいいと思っています。

>>92さんの逆鱗に触れてしまったことは謝らないといけません
ただ、なぜそんなに怒っているのか、さっぱり判りません
できれば、だれもを納得させる反論されない理由を
書いていただけませんか?
(それとも、このように>>92さんを相手にするのは私が
2ch初心者だからであって、本来は放置するものなのでしょうか?)

112 :デフォルトの名無しさん:2006/07/31(月) 22:22:27
あらら、ムカついてるw

113 :デフォルトの名無しさん:2006/08/01(火) 07:29:06
ぎゃくりん(←なぜか変換出来ない)

114 :デフォルトの名無しさん:2006/08/01(火) 09:24:02
ムカついた時しか長文書かない子は
長文の書き手がみんなムカついてるように見えるっていうしな

115 :nanashi ◆XQNqqmrLFw :2006/08/01(火) 09:38:14
やっぱり、そう見られるよなぁ>ムカついてる
書いた後、放置すればよかったと後悔した…

116 :デフォルトの名無しさん:2006/08/01(火) 21:35:28
いいから削除依頼出して死ねよ

117 :デフォルトの名無しさん:2006/08/02(水) 00:37:43
んー、俺は最後までやってほしいな、とりあえずメル覧にsageって入れて書き込めば良いと思うよ。

118 :デフォルトの名無しさん:2006/08/02(水) 08:45:45
↑お前スレちゃんと読んでないだろ

もうこのスレ終わったっつーの。何を最後までやるんだよ。

119 :デフォルトの名無しさん:2006/08/02(水) 11:00:19
一人でスレ潰そうと頑張るのもいいけど、
もう少し「多人数のふり」を頑張らないとピエロでしかないです(^_^;

120 :デフォルトの名無しさん:2006/08/02(水) 11:05:52
自演で2〜3日でスレ潰してる香具師もよくいるしなぁ


121 :デフォルトの名無しさん:2006/08/02(水) 11:06:40
出来るもんならやってみろカス

122 :デフォルトの名無しさん:2006/08/02(水) 21:11:07
うむ。1はもうちょっと考えて自演すべきだったよな

123 : ◆2jURWQKdyk :2006/08/03(木) 23:29:17
1は全く関係ないですよ。

そんな私は助言してた友人その・・・5?(適当

124 :デフォルトの名無しさん:2006/08/04(金) 08:07:06
自演じゃん

125 :デフォルトの名無しさん:2006/08/16(水) 22:46:59
このスレの存在意義がよくわからんのだが、ちょっと便乗していい?
ただの関数や制御構造程度ならCにならってGCレスで作れそうだけど、
クロージャの管理はGCないと無理だよね?


126 :デフォルトの名無しさん:2006/08/16(水) 22:54:04
存在意義は無いから便乗しようがない。

127 :デフォルトの名無しさん:2006/08/16(水) 23:00:29
手動で管理すりゃ GC なしでもいいんじゃね。つか age ないでくれませんか。

128 :デフォルトの名無しさん:2006/08/17(木) 00:20:32
なんで?

129 :デフォルトの名無しさん:2006/08/17(木) 00:41:47
ログをよく読みなさい。
>>1が議論を放棄したから、ここはもう終わったスレなのだ。

130 :デフォルトの名無しさん:2006/09/23(土) 15:40:43
ここってようは、リンクドリストを使わないで、
vectorとかArrayListみたいな動的配列を使ってリストを表現しようということなのかな?
それはありだと

131 :デフォルトの名無しさん:2006/09/24(日) 00:22:59
ログをよく読みなさい。
>>1が議論を放棄したから、ここはもう終わったスレなのだ。

132 :デフォルトの名無しさん:2006/10/11(水) 07:20:36
じゃあ再利用しよう
scheme最高!

133 :デフォルトの名無しさん:2006/10/11(水) 07:36:00
最近Gaucheで、Schemeの勉強始めた!
「プログラミング言語SCHEME」読んでます

134 :デフォルトの名無しさん:2006/10/13(金) 19:38:36
gae

135 :デフォルトの名無しさん:2006/10/31(火) 04:24:56
             r y、
             / / }
           _/ノ.. /、
           /  <   }
      ry、     {k_ _/`;,  ノノ パンパン
    / / }      ;'     `i、 
   _/ノ../、   _/ 入/ /   `ヽ, ノノ
  / r;ァ  }''i" ̄.   ̄r'_ノ"'ヽ.i   ) ―☆
 {k_ _/,,.'  ;.  :.      l、  ノ  
    \ `  、  ,i.    .:, :, ' / / \
     ,;ゝr;,;_二∠r;,_ェ=-ー'" r,_,/   ☆


38 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)