コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

利用者:Nonamea774/sandbox/Archive

cons

[編集]

cons とは、ほとんどのLisp方言において基本的な関数である。 cons は、2つの、値もしくは値へのポインタを保持するオブジェクトを構成(construct)する。これによって作られたオブジェクトは、(cons)セル、cons、non-atomic S式(NATS式)、(cons)対などと呼ばれる。 cons の結果のペアの左側(第一要素)は car と呼ばれ、右側(その残り)は cdr と呼ばれる。

使い方

[編集]

cons 自体は単に、データの順序対を保持することができるだけだが、しばしばリストや二分木などの複雑なデータ構造を保持するためにも使われる。

例えば、Lisp の式、(cons 1 2) は、左側(car部)に1 、右側(cdr部)に2 を持ったcons セルを作る。 Lisp の表記では、(cons 1 2) の値は次のようになる: 

(1 . 2)

1 と2 の間に. があるのに注意。これはこのS式が、「リスト」ではなく「ドット対」であることを示している。

リスト

[編集]
リスト(42 69 613) を表すcons セルダイヤグラム
cons を使って書いた場合: 
(cons 42 (cons 69 (cons 613 nil)))
list を用いた場合: 
(list 42 69 613)

Lisp において、cons はリストを実装するための基本的な構造である。具体的には、Lisp においては全てのリストは以下のいずれかである:

  1. 一般に nil と呼ばれる特別なオブジェクトである空のリスト ()
  2. car としてリストの第一要素を持ち、 cdr としてリストの残りの要素を持つ cons セル

この構造は、単純な連結リスト構造を作る。この連結リストは、 cons, car, and cdr のみで操作することのできる構造をしている。 nil は唯一のcons ペアでないリストで無いことに気をつけなければならない。 例として、1, 2, 3 の要素から成るリストを考えよう。そのようなリストは、以下の3ステップで作られる。

  1. 3 とnil(空リスト)のcons を作る。
  2. 2 とその結果とのcons を作る。
  3. 1 とその結果とのcons を作る。

つまり: 

(cons 1 (cons 2 (cons 3 nil)))

もしくはそれの短縮形として: 

(list 1 2 3)

結果として、以下のリストが得られる: 

(1 . (2 . (3 . nil)))

以下のような図で表すことができる。 

 *--*--*--nil
 |  |  |
 1  2  3

このリストは、一般に以下のように略記される: 

(1 2 3)

要するに、cons は、すでに存在するリストの先頭に要素をひとつ付け加えるように働く。 例えば、上で定義したリストをxとすると、(cons 5 x) は、以下のようなリストを生成する。 

(5 1 2 3)

もうひとつの便利なリスト操作関数として、 append がある。それは、二つのリストを結合する。

木構造

[編集]

葉の部分にのみ値を持つデータ構造である二分木もまた、cons によって用意に作ることができる。 例えば、以下のコードは 

(cons (cons 1 2) (cons 3 4))

以下のような結果になる。 

((1 . 2) . (3 . 4))

これはつまり、以下のような図で表すことができる: 

   *
  / \
 *   *
/ \ / \
1 2 3 4

正確には、さっきの例に出てきた(1 2 3) というリストもまた二分木である。それは、さっきの図を少し変形することで容易にわかる: 

 *--*--*--nil
 |  |  |
 1  2  3

これは、以下の図と同様である。 

   *
  / \
 1   *
    / \
   2   *
      / \
     3  nil

Use in conversation

[編集]

Cons can refer to the general process of memory allocation, as opposed to using destructive operations of the kind that would be used in an imperative programming language. For example:

I sped up the code a bit by putting in side effects instead of having it cons like crazy.

Not technically fundamental

[編集]

Lisp は、全てのオブジェクトが第一級オブジェクトであるので(cons セルも例外ではなく)、全てのデータ構造は関数を用いて実装することができる。 Since Lisp has first-class functions, all data structures, including cons cells, are not fundamentally necessary to the language, since all data structures can be implemented using functions. For example, in Scheme: 

(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))
(define (cdr z)
  (z (lambda (p q) q)))

The above code re-implements the cons, car, and cdr operations, using a function as the "cons cell". This is the usual way of defining data structures in pure lambda calculus, an abstract, theoretical model of computation that is closely related to Scheme.

This implementation, while academically interesting, is impractical because it renders cons cells indistinguishable from any other Scheme procedure, as well as introducing unnecessary computational inefficiencies.

However, the same kind of encoding can be used for more complex algebraic data types with variants, where it may even turn out to be more efficient than other kinds of encoding.[1] This encoding also has the advantage of being implementable in a statically typed language that doesn't have variants, such as Java, using interfaces instead of lambdas.

関連項目

[編集]

脚注

[編集]
  1. ^ http://www.st.cs.ru.nl/papers/2006/janj2006-TFP06-EfficientInterpretation.pdf

外部リンク

[編集]
  • SDRAW, Common Lisp code for drawing draws cons cell structures. From David S. Touretzky.



en:Cons oldid=486291783 の翻訳

Batcher odd–even mergesort

[編集]

https://en-two.iwiki.icu/w/index.php?title=Batcher_odd%E2%80%93even_mergesort&oldid=502677455

Batcher's odd–even mergesort is a generic construction devised by Ken Batcher for sorting networks of size O(n (log n)2) and depth O((log n)2), where n is the number of items to be sorted. Although it is not asymptotically optimal, Knuth concluded in 1998, with respect to the AKS network that "Batcher's method is much better, unless n exceeds the total memory capacity of all computers on earth!"[1]
It is popularized by the second GPU Gems book,[2] as an easy way of doing reasonably efficient sorts on graphics-processing hardware.
八本の入力からなる、奇偶マージソート

バッチャー奇偶マージソート(英: Batcher's odd–even mergesort) は Ken Batche(en:Ken Batcher) によって考案された、要素数nに対して、大きさ O(n (log n)2) かつ深さ O((log n)2) のソーティングネットワークである。これは漸近的に最適（en:asymptotically optimal algorithm）ではないものの、ドナルド・クヌースは1998年、 AKSネットワークに関して「n が地球上の全てのコンピュータのメモリの全てに収まり切らないほど大きくない限り、Batcheの方法のほうが (AKSネットワークよりも) 優れている。」と言った。[1] the second GPU Gems book[2]の中で、効率的なグラフィックスプロセスハードウェアによるソートの簡単な実装法として紹介されたことにより有名になった。

Pythonによる実装例

[編集]

入力として、2の累乗の長さを持ったリストを取り、ソート済みリストを返す。 

def compare_and_swap(x, a, b):
    if x[a] > x[b]:
        x[a], x[b] = x[b], x[a]
 
def oddeven_merge(x, lo, hi, r):
    step = r * 2
    if step < hi - lo:
        oddeven_merge(x, lo, hi, step)
        oddeven_merge(x, lo + r, hi, step)
        for i in range(lo + r, hi - r, step):
            compare_and_swap(x, i, i + r)
    else:
        compare_and_swap(x, lo, lo + r)
 
def oddeven_merge_sort_range(x, lo, hi):
    """ 区間lo と hiのソートを行う。

    注意: 端点 (lo と hi) は含むものとする。
    """
    if (hi - lo) >= 1:
        # ひとつ以上の要素があった場合、入力を
        # 長さの半分で前後に分割し、
        # その後それぞれをマージソートする。
        mid = lo + ((hi - lo) / 2)
        oddeven_merge_sort_range(x, lo, mid)
        oddeven_merge_sort_range(x, mid + 1, hi)
        oddeven_merge(x, lo, hi, 1)
 
def oddeven_merge_sort(x):
    oddeven_merge_sort_range(x, 0, len(x)-1)

>>> data = [2, 4, 3, 5, 6, 1, 7, 8]
>>> oddeven_merge_sort(data)
>>> data
[1, 2, 3, 4, 5, 6, 7, 8]

参考文献

[編集]
  1. ^ D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.
  2. ^ http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html

外部リンク

[編集]
en:Batcher odd-even mergesort oldid=502677455 を翻訳
「https://ja-two.iwiki.icu/w/index.php?title=利用者:Nonamea774/sandbox/Archive&oldid=45619028」から取得