challenge 隣り合う二項の差

整数のリストがxsが与えられたときに、 隣り合う2要素の差のリストを作る関数diffを作ってください。

サンプル入力
[3, 1, 4, 1, 5, 9, 2, 6, 5]
サンプル出力
[-2, 3, -3, 4, 4, -7, 4, -1]

Posted feedbacks - Nested

Flatten Hidden

	
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
using System;
class Program
{
  static void Main()
  {
    int[] xs = { 3, 1, 4, 1, 5, 9, 2, 6, 5 };
    foreach (int k in Diff(xs))
      Console.WriteLine(k);
  }
  static int[] Diff(int[] xs)
  {
    int[] diff = new int[xs.Length - 1];
    for (int i = 0; i < xs.Length - 1; ++i) diff[i] = xs[i + 1] - xs[i];
    return diff;
  }
}
ごく普通に do で。
1
2
3
4
5
(defun diff (list)
  (do ((rest list (cdr rest))
       (acc ()))
      ((null (cdr rest)) (nreverse acc))
    (push (- (cadr rest) (car rest)) acc)))

	
1
2
3
4
5
6
7
8
9
def diff(xs)
	raise ArgumentError unless xs.size >= 2 

	(0..xs.size-1-1).map{ |n|
		xs[n+1] - xs[n]
	}
end

p diff( [3, 1, 4, 1, 5, 9, 2, 6, 5] )
ざくっと書いた
1
2
diff (x:[]) = []
diff (x:(y:ys)) = (:) (y-x) $ diff $ y:ys

	
1
2
3
4
diff([_], []).
diff([X1,X2|Xs], [D|Ds]) :-
	D is X2 - X1,
	diff([X2|Xs], Ds).
普通にIteratorを使っています。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
import java.util.*;

public class Sample {
    public static List<Integer> diff(List<Integer> a) {
        List<Integer> result = new ArrayList<Integer>();
        Iterator<Integer> i = a.iterator();
        int prev = i.next();
        while (i.hasNext()) {
            int next = i.next();
            result.add(next - prev);
            prev = next;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(diff(Arrays.asList(3, 1, 4, 1, 5, 9, 2, 6, 5)));
    }
}
うーん・・・。美しくないな。。
1
sub diff { $n = shift; map { $r = $_ - $n; $n = $_; $r } @_; }

	
1
2
3
4
5
6
7
8
Array.prototype.diff = function() {
    for (var i = 0, l = this.length, buf = []; i < l-1; i++) {
        buf[i] = this[i+1] - this[i];
    }
    return buf;
}

alert([3, 1, 4, 1, 5, 9, 2, 6, 5].diff());
STLのadjacent_differenceを使用。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <vector>

std::vector<int> diff(const std::vector<int>& in)
{
    std::vector<int> out(in.size());

    std::adjacent_difference(in.begin(), in.end(), out.begin());

    if (! out.empty()) out.erase(out.begin());

    return out;
}

int main()
{
    const int a[] = {3, 1, 4, 1, 5, 9, 2, 6, 5};

    const std::vector<int> xs(a, a + sizeof(a) / sizeof(*a));

    const std::vector<int> v = diff(xs);

    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ", "));
}
Sコンビネータ(starling)をつかってポイントフリー
1
2
starling f g x = f x (g x)
diff = starling (zipWith subtract) tail
ApplicativeにはSコンビネータ(と同じ働きをする演算子)が用意されていて、こんな風にも書けます。
1
2
import Control.Applicative
diff = zipWith subtract <*> tail
リストを返すようなreduceの使い方がよくわかっていないので、なんだかなーって感じになってしまった。
1
2
use List::Util qw/reduce/;
sub diff {my @d;reduce {push @d,$b-$a; $b} @_;@d;}
普通に。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def diff(xs):
    if xs:
        return [xs[i + 1] - xs[i] for i in xrange(len(xs) - 1)]
    else:
        return []

def main():
    print diff([3, 1, 4, 1, 5, 9, 2, 6, 5])

if __name__ == '__main__':
    main()

	
1
2
3
4
5
6
7
8
#light
let rec diff = function
    | [] -> failwith "invalid argument"
    | x::[] -> failwith "invalid argument"
    | x::x'::[] -> (x'-x)::[]
    | x::x'::xs -> (x'-x)::diff (x'::xs)

let xs = [3;1;4;1;5;9;2;6;5]
修正。
1
2
3
4
5
6
7
#light
let rec diff = function
    | [] -> []
    | x::[] -> []
    | x::x'::xs -> (x'-x)::diff (x'::xs)

let xs = [3;1;4;1;5;9;2;6;5]

	
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
List diff := method(
    res := list()
    for(i, 0, self size - 2,
        res append(self at(i+1) - self at(i))
    )   
    return res 
)

xs := list(3, 1, 4, 1, 5, 9, 2, 6, 5]
xs diff println
mapでOK
1
(define (diff xs) (map - (cdr xs) xs))
Squeak Smalltalk で。
1
2
3
| xs |
xs := #(3 1 4 1 5 9 2 6 5).
^xs overlappingPairsCollect: [:a :b | b - a]
nobsun の #2400 を見て、そうだ、こんなふうにする手もあったな…と。
1
2
3
| diff |
diff := [:xs | xs allButFirst - xs allButLast].
^diff value: #(3 1 4 1 5 9 2 6 5)   "=> #(-2 3 -3 4 4 -7 4 -1) "
C + glib で
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
#include <stdlib.h>
#include <glib.h>

GSList *diff(GSList *list)
{
    int p;
    GSList *ret = NULL;
    if(!g_slist_length(list)) return NULL;
    p = (int)list->data;
    while(list = g_slist_next(list)){
        ret = g_slist_append(ret, GINT_TO_POINTER((int)list->data - p));
        p = (int)list->data;
    }
    return ret;
}

GSList *list_new(int nums[], int len)
{
    int i;
    GSList *list = NULL;
    for(i=0; i<len; i++){
        list = g_slist_append(list, GINT_TO_POINTER(nums[i]));
    }
    return list;
}

int main(int argc, char *argv[])
{
    int nums[] = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    GSList *list, *d, *l;
    list = list_new(nums, sizeof(nums) / sizeof(int));
    d = diff(list);
    do printf("%d\n", d->data); while(d = g_slist_next(d));
    return EXIT_SUCCESS;
}
% awk -f diff.awk
1 2 3 4 5
[1, 1, 1, 1]
9 7 5 3 1
[-2, -2, -2, -2]
3 1 4 1 5 9 2 6 5
[-2, 3, -3, 4, 4, -7, 4, -1]
[3, 1, 4, 1, 5, 9, 2, 6, 5]
[-2, 3, -3, 4, 4, -7, 4, -1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
{
	gsub(/[^0-9]/," ")
	src_size = split($0,src)

	dest_size = diff(src,dest,src_size)
	show(dest,dest_size)
}

function diff(src,dest,size,  i)
{
	for (i=1; i<size; i++) dest[i] = src[i+1] - src[i]
	return size-1
}

function show(ar,size,  i)
{
	printf "["
	for (i=1; i<size; i++) printf ar[i] ", "
	printf ar[size] "]\n"
}
再帰したかったんです
1
2
3
4
5
sub diff {
    my ( $a, $b ) = @_;
    return if !defined($b);
    return ( $b - $a, diff( @_[ 1 .. $#_ ] ) );
}
うーん、あんまりスマートじゃない。
1
2
3
4
5
sub diff {
    my @rv;
    push @rv, $_[$_] - $_[$_+1] for 0..$#_-1;
    return @rv;
}

	
1
2
(defun diff (xs)
  (mapcar #'- (cdr xs) xs))
あ,もう Scheme でやられてましたね.
KL1で。いやぁ、懐かしい。
見た目Prologの書き方が冗長になっただけだけど。
1
2
3
4
5
6
:-module main.

main:-diff([3,1,4,1,5,9,2,6,5],R),io:outstream([print(R),nl]).

diff([_],R) :- R=[].
diff([X1,X2|Xs],R):-R=[R1|Rs],R1:=X2-X1,diff([X2|Xs],Rs).
1
2
3
4
def diff(as:List[int]):List[int] = as match {
  case a::(as@b::bs) => (b-a)::diff(as)
  case _      => Nil
}
1
2
def diff(xs:List[int]) = 
  xs.zipAll(xs.tail,0,0).map(p=>p._2-p._1).reverse.tail.reverse
 ブックマークレットだし元のリストは壊してもいいや,と割り切って。
1
javascript:(function(a,i){for(i=a.length-1;i>0;a[i]-=a[--i]);a.shift();return(a)})([3,1,4,1,5,9])
srfi-42 の comprehension を使ってみました。
1
2
3
4
5
6
(use srfi-42)
(define (diff xs)
  (list-ec (:do ((x (car xs)) (y (cdr xs)))
                (not (null? y))
                ((car y) (cdr y)))
           (- (car y) x)))
:parallelで複数の変数に対してループを回せます。
1
(define (diff xs) (list-ec (:parallel (: x xs) (: y (cdr xs))) (- y x)))
なるほどです。どうもありがとうございます。
:parallel は知っていたのに気付かなかったのが残念です。
最初 diff は Array を引数に取り、その Array の Iterator と一個先に進めたIterator を zip して map していたんですが、無限列を diff したくなったので Array ではなく Iterator を引数に取るようにしました。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Iterator::each_pair: method fiber {
    prev: null;
    this { prev = it; break; }
    this {
        yield prev, it;
        prev = it;
    }
}

diff: fun(iter) {
    return iter.each_pair.map(|a,b| b - a);
}

diff([3, 1, 4, 1, 5, 9, 2, 6, 5].each).to_a.p;


// 無限列のテスト
random_generator: fiber {
    while (true) {
        yield math::ceil(math::random_range(1, 10));
    }
}
diff(random_generator).take(20).to_a.p;
mapを使った。
1
2
3
4
def diff(xs):
    return map(lambda (x,y):y-x, zip(xs[:-1], xs[1:]))

print diff([3, 1, 4, 1, 5, 9, 2, 6, 5])

言語をPythonに変更しておきました。

ついでなので少しつっこむと、この方法は2回のスライシングで2回コピーを行うのでxsが長いときには非効率ですね。

Pythonのzipは一番短いものにあわせるて長いものを切り捨てるのでzip(xs, xs[1:])で問題ないです。それでも1回コピーが起きるわけですが。

#2396 oceanさんの方法はコピーが起きません。下のコードはそれをさらにジェネレータにしたバージョンです。

1
2
3
def diff(xs):
	for i in range(1, len(xs)):
		yield xs[i] - xs[i - 1]

スライスもそうだけど zip も非効率といえば非効率ですね。 というわけで itertools & generator expression で。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
from itertools import izip, islice

def tail(xs):
    return islice(xs, 1, len(xs))

def diff(xs):
    """
    >>> diff([3, 1, 4, 1, 5, 9, 2, 6, 5])
    [-2, 3, -3, 4, 4, -7, 4, -1]
    """
    return (x - y for x, y in izip(tail(xs), xs))
enumerator版
1
2
3
def diff(a)
  a.enum_cons(2).map {|x, y| y - x }
end
すみません・・
require 'enumerator'
を追加していませんした。
1
2
3
4
5
require 'enumerator'

def diff(a)
  a.enum_cons(2).map {|x, y| y - x }
end
げ、かぶった><
map使った
1
diff xs = map (\(x,y) -> x - y) $ zip (tail xs) (init xs)
zipは短い方にあわせるので init は不要かな。
でも対象性を意識してついているのかな。。。
map を使うなら uncurry というのもいいかも。。
1
diff xs = map (uncurry (-)) (zip (tail xs) xs)
でね。結局 

map f (zip xs ys) ≡ zipWith (curry f) xs ys 
あるいは
map (uncurry f) (zip xs ys) ≡ zipWith f xs ys
なので、
1
diff xs = zipWith (-) (tail xs) xs