std::future

JavaのFutureとほぼ同様の機能を持つ，std::futureがC++11では利用可能である．

#include <cmath>
#include <future>
#include <chrono>
#include <iostream>

int main() {

 std::future<double> fut = std::async([](double x)->double { return pow(x,2); }, 80);
 fut.wait();
 std::shared_future<double> shared = fut.share();
 std::cout << shared.get() << std::endl;
 return 0;

}

STL - partial_sort

STLのalgorithmにはpartial_sort()が用意されており，部分的にソートを適用することが出来る．
第一引数は開始要素，第二引数はソートを適用する上限，第三引数は終端要素．

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main() {

 vector<int> v{ 25, 80, 12, 5, 50, 61, 24, 37, 45, 70 };
 partial_sort(v.begin(), v.begin() + 3, v.end());
 for_each(v.begin(), v.end(), [](int x)->void { cout << x << endl; });

 return 0;

}

結果

5
12
24
80
50
61
25
37
45
70

auto_ptrからunique_ptrへ移行

auto_ptrは既にdeprecatedとされており，短所もご存じの通りかと思う．(こちらはその短所を簡潔に良くまとめている)
auto_ptrからunique_ptrへの移行は非常に簡単である．

以下の例はauto_ptrの代わりにunique_ptrを使用して簡単なツリーをインオーダ順で走査するコード．

tree.h

#ifndef __TREEPRJ_TREE_H__
#define __TREEPRJ_TREE_H__

#include <string>
#include <memory>
#include <iostream>


class Node {
public:
 Node(int idVal, std::string nameVal) :id(idVal), name(nameVal){}
 virtual ~Node() { std::cout << "ID[" << id << "] is being released" << std::endl; }
 int id;
 std::string name;
 std::unique_ptr<Node> l;
 std::unique_ptr<Node> r;
};


class Tree {
private:
 std::unique_ptr<Node> root;
 void _add(std::unique_ptr<Node>& n, int id, std::string name);
 void _traverseInorder(std::unique_ptr<Node>& n);
public:
 Tree(int id, const std::string n);
 virtual ~Tree() {}
 void add(int id, std::string name);
 void traverseInorder();

};

#endif

tree.cpp

#include "tree.h"
#include <iostream>

Tree::Tree(int id, const std::string name) {

 root.reset(new Node(id, name));

}

void Tree::add(int id, std::string name) {

 _add(root, id, name);

}

void Tree::_add(std::unique_ptr<Node>& n, int newId, std::string newName) {

 if ( !n ) return;

 if (n->id > newId) {
  if (n->l) {
   _add(n->l, newId, newName);
  }
  else {
   n->l.reset(new Node(newId, newName));
  }
 }
 else {
  if (n->r) {
   _add(n->r, newId, newName);
  }
  else {
   n->r.reset(new Node(newId, newName));
  }
 }

}

void Tree::traverseInorder() {

 _traverseInorder(root);

}

void Tree::_traverseInorder(std::unique_ptr<Node>& n) {

 if (!n) return;
 _traverseInorder(n->l);
 std::cout << "ID:" << n->id << ",NAME:" << n->name << std::endl;
 _traverseInorder(n->r);

}

int main() {

 Tree t(30, "The Colton");
 t.add(25, "The Warwick");
 t.add(21, "Hawthorne Court");
 t.add(45, "Hampton Court Garden");
 t.add(15, "The Belvedere");
 t.add(50, "Stratford Hall");
 t.traverseInorder();

}

Spring プロファイル

プロファイルを変えることでインジェクトするデータ内容を変えたりしたいこともあるかもしれない．
Springでプロファイルを使用するのは簡単で，単にProfileアノテーションを使えばよい．
以下の例はプロファイルを有効に利用しているとは言えない例ではあるが..

package org.tanuneko;

import org.springframework.context.annotation.AnnotationConfigApplicationContext;

public class App {

    public static void main( String args[]) {

        AnnotationConfigApplicationContext ctx = new AnnotationConfigApplicationContext();
        ctx.getEnvironment().setActiveProfiles( "profileA" );
        ctx.register( AppConfig.class );
        ctx.refresh();
        Data data = ctx.getBean( Data.class );
        System.out.println( data.getData() );

    }
}

package org.tanuneko;

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.ComponentScan;
import org.springframework.context.annotation.Configuration;
import org.springframework.context.annotation.Profile;


@Configuration
@ComponentScan("org.tanuneko")
@Profile( {"profileA","profileB"} )
public class AppConfig {

    @Bean(initMethod="init",destroyMethod="destruct")
    public Data data() {
        return new Data();
    }
}

package org.tanuneko;

public class Data {

    private String data;

    public Data() {
        data = "test data.";
    }

    public void init() {
        System.out.println( "initialized" );
    }

    public void destruct() {
        System.out.println( "destroyed" );
    }

    public String getData() { return data; }
}

モックのDI

IoCコンテナを使えば，テスト用にドライバ/スタブを容易にDIできる．
当然のことなのだが，意外にこの利点をあえて使わない(?)テストケースを書いてくることがままある．これを使えば当然テストコードはかなり可読性が高くなるので，使わない手はないはずだが．

以下はモックのDIの参考例．
以下の例では，DataDumpServiceのインタフェースを介してConsoleDataDumpService並びにDataNodeNodeIFインタフェースを介して テスト用データを持つDataNodeをユニットテスト中にDIする．

DataDumpServiceインタフェース

package org.tanuneko;

public interface DataDumpService {

    public void dump( Object obj );

}

ConsoleDumpServiceクラス

package org.tanuneko;

import org.springframework.stereotype.Service;

@Service
public class ConsoleDataDumpService implements DataDumpService {

    public void dump( Object obj ) {
        System.out.println( obj );
    }
}

NodeIFインタフェース

package org.tanuneko;

public interface NodeIF<X> {

    public X getData();
}

DataNodeクラス

package org.tanuneko;

public class DataNode<X> implements NodeIF {

    private X data;

    public DataNode( X data ) {
        this.data = data;
    }

    public X getData() {
        return data;
    }
}

AppConfig(非テスト用)

package org.tanuneko;

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.ComponentScan;
import org.springframework.context.annotation.Configuration;


@Configuration
@ComponentScan("org.tanuneko")
public class AppConfig {

    @Bean
    public NodeIF data() {
        return new DataNode( "This is prod" );
    }
}

App(非テスト用)

package org.tanuneko;

import org.springframework.context.annotation.AnnotationConfigApplicationContext;


public class App {

    public App() {

        AnnotationConfigApplicationContext ctx = new AnnotationConfigApplicationContext();
        ctx.register( AppConfig.class );
        ctx.refresh();
        NodeIF node = ctx.getBean( DataNode.class );
        System.out.println( node.getData() );
        DataDumpService srv = ctx.getBean( ConsoleDataDumpService.class );
        srv.dump( node.getData() );

    }

    public static void main( String args[] ) {

        App a = new App();

    }
}

テストアップランチャ

package org.tanuneko;

import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Component;


@Component
public class TestAppLauncher {

    @Autowired
    DataDumpService dp;

    @Autowired
    NodeIF dataNode;

}

AppConfig(テスト用)

package org.tanuneko;

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.ComponentScan;
import org.springframework.context.annotation.Configuration;


@Configuration
@ComponentScan("org.tanuneko")
public class AppTestConfig {

    @Bean
    public NodeIF data() {
        return new DataNode( "This is test" );
    }

}

テストクラス

package org.tanuneko;

import org.junit.BeforeClass;
import org.junit.Test;
import org.springframework.context.annotation.AnnotationConfigApplicationContext;


public class AppTest {

    private static TestAppLauncher testApp;

    @BeforeClass
    public static void init() {

        AnnotationConfigApplicationContext ctx = new AnnotationConfigApplicationContext();
        ctx.register( AppTestConfig.class );
        ctx.refresh();
        testApp = ctx.getBean( TestAppLauncher.class );

    }

    @Test
    public void testDataNode() {

        testApp.dp.dump( testApp.dataNode.getData() );

    }

}

Java8 - Collectors 平均関連

業務用のコードでは使うことはあまりないが，あったら便利な，ストリームの要素から平均を抽出するコード．

        System.out.println(

            Stream.of(50d, 62d, 79.4d, 62d, 80.0d, 89.25d, 5d)
                .collect( Collectors.averagingDouble( (x)->x) ).doubleValue() + " " +
            Stream.of(20,15,30,45,50,25)
                .collect( Collectors.averagingInt( (x)->x ) ).intValue() + " " +
            Stream.of(300L, 200L, 100L, 400L, 500L )
                .collect( Collectors.averagingLong( (x)->x ) ).longValue()

        );

現実的な用途の一つとして考えられるのはメッセージキュー中のデータの平均サイズを取得するようなものだろう．以下は５つの別スレッド上で動作するデータプロバイダーがデータキューにデータを書き込んで、サンプラーが先頭から３０個のデータの長さの平均を計算する例．

package org.tanuneko;

import java.util.Random;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.Executors;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class DataSampler {

    private static final int MAX_SAMPLESIZE = 30;
    private CopyOnWriteArrayList<Data> q;

    public DataSampler() {
        q = new CopyOnWriteArrayList<>();
        Executors.newFixedThreadPool(5).execute( new DataProvider( this ) );
    }

    public void doSampling() {

        while( true ) {

            System.out.println(
            q.stream().limit( MAX_SAMPLESIZE ).mapToInt( Data::getDataSize )
                    .summaryStatistics().getAverage()
            );

            try {
                Thread.sleep( 2000 );
            } catch( InterruptedException iE ) {
                iE.printStackTrace();
                System.exit(1);
            }
            System.out.println( "(QSIZE=" + q.size() + ",MAXSAMPLESIZE=" + MAX_SAMPLESIZE + ")" );

        }

    }

    public void addData( Data d ) {
        q.add( d );
    }

    public static void main (String args[] ) {

        DataSampler d = new DataSampler();
        d.doSampling();

    }

}

class DataProvider implements Runnable {

    private DataSampler sampler;

    public DataProvider( DataSampler sampler ) {
        this.sampler = sampler;
    }

    public void run() {

        Random r = new Random();
        r.setSeed( System.currentTimeMillis() );

        while( true ) {

            sampler.addData( new Data( genRandBytes() ) );
            try {
                Thread.sleep( r.nextInt( 3000 ) );
            } catch (InterruptedException iE) {
                throw new RuntimeException(iE);
            }

        }
    }

    private byte[] genRandBytes() {

        Random r = new Random();
        r.setSeed( System.currentTimeMillis() );
        return Stream.generate(()->"a").limit( r.nextInt( 100 ) )
                .collect( Collectors.joining() )
                .getBytes();

    }
}

class Data {

    private byte[] buffer;
    public Data( byte[] buffer ) {
        this.buffer = new byte[ buffer.length ];
        System.arraycopy( this.buffer, 0, buffer, 0, buffer.length );
    }
    public byte[] getData() {
        return buffer;
    }
    public int getDataSize() {
        return buffer.length;
    }

}

C++11 - std thread

C++11でstd::threadがサポートされた．pthreadがJavaでいうところのネイティブスレッドであれば，std::threadはさしずめExecutorServicesのような使いやすさである．

#include <mutex>
#include <chrono>
#include <random>
using namespace std;

mutex mutexObj;
random_device rd;
mt19937 mt(rd());

void dump(int val) {

 mutexObj.lock();
 this_thread::sleep_for(chrono::seconds(mt()%3));
 cout << "[" << this_thread::get_id() << "]:" << val*50 << endl;
 mutexObj.unlock();

}

int main() {

 vector<thread> threads;
 for (int i = 0; i < 5; i++)
  threads.push_back(thread(dump, i));

 for (auto& t : threads)
  t.join();

}

C++11 - ムーブコンストラクタ

C++の特徴の一つ，ムーブコンストラクタ．rvalue参照により余計なデータのコピーを避けることができるため，大きなクラスや構造体のハンドリングに関しては高速化が期待できる．

以下の例はムーブコンストラクタを使ってトレードデータクラスをスワップする例．コピーコンストラクタと異なり，セールスパーソンのリスト及びブロブデータ(この例では簡略化の為stringで代用)の転送をしている．

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef std::shared_ptr BLOB;

class TradeData {
private:
 int _tradeId;
 vector _salesPersonIds;
 string _note;
 BLOB _blob;

public:
 TradeData(int tradeId, initializer_list salesPersonIds, string note, string blobInfo) : _tradeId(tradeId), _salesPersonIds(salesPersonIds), _note(note){
  for (auto iter = salesPersonIds.begin(); iter != salesPersonIds.end(); iter++) {
   _salesPersonIds.push_back(*iter);
  }
  _blob = make_shared(blobInfo);
 }

 virtual ~TradeData() {
 }

 const char* operator()() {
  strstream buf;
  buf << _tradeId << ":[";
  for_each(_salesPersonIds.begin(), _salesPersonIds.end(), [&buf](int id){ buf << id << ","; });
  buf << "]," << _note << "," << *_blob << "(@" << _blob << ")" <<  ends;
  return buf.str();
 }

 TradeData& operator=(TradeData&& trade) {
  _blob = trade._blob;
  trade._blob = nullptr;
  _tradeId = trade._tradeId;
  _salesPersonIds = trade._salesPersonIds;
  _note = trade._note;
  return *this;

 }

};

void SwapTrade(TradeData& td1, TradeData& td2) {

 TradeData temp = std::move(td1);
 td1 = std::move(td2);
 td2 = std::move(temp);

}

int main() {

 TradeData t1(100, { 1, 2, 3 }, "test trade1", "blobdata1..");
 TradeData t2(300, { 1 }, "test trade2", "blobdata2..");
 cout << "! before swap" << endl;
 cout << "*** tradedata1 *** " << t1() << endl;
 cout << "*** tradedata2 *** " << t2() << endl;
 SwapTrade(t1, t2);
 cout << "! after swap" << endl;
 cout << "*** tradedata1 *** " << t1() << endl;
 cout << "*** tradedata2 *** " << t2() << endl;

}

C++11 - 簡単なランダム順列

C++11の一部機能を用いて簡単なランダム（値の重複無し)の順列を生成するコード．

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
using namespace std;

void d(const vector<int> v) {
 for_each(v.begin(), v.end(), [](int x)->void{ cout << x << endl; });
}

int main() {

 random_device rd;
 mt19937 mt(rd());
 vector<int> vals{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
 for (auto i = 0; i < vals.size(); i++) {
  auto idx = mt() % vals.size();
  auto t = vals[idx];
  vals[idx] = vals[i];
  vals[i] = t;
 }

 d(vals);


}

C++のラムダ

Java8でついにラムダ式が．．というのは間違いなくビッグニュースではあるが，一方C++も既にラムダをC++0x以降で既にサポート済みであることを述べておかないのはある意味フェアではなかろう．

以下の例はinitializer_list経由でリストの 配列を取り，リストの値はラムダ式のpredを使いソート，そして指定された関数で出力する例．

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


class Tako {
private:
 vector<signed> v;
public:
 Tako(initializer_list<signed> listVal);
 virtual ~Tako() {}
 void dump(void (f)(const signed));
 void sort();
};

Tako::Tako(initializer_list<signed> listVal) {

 for (auto a : listVal) {
  v.push_back(a);
 }
}

void Tako::dump(void (f)(const signed)) {
 for (auto x : v) {
  f(x);
 }
}

void Tako::sort() {

 if (v.size() >= 2) {
  std::sort(v.begin(), v.end(), [](signed x, signed y)-> signed { return x > y; });
 }

}

void dump_to_stdout(const signed v) {
 cout << v << endl;
}

int main() {

 Tako t = { 32, 27, 30, 50, 64, 10 };
 void(*myfunc)(signed) = dump_to_stdout;
 t.sort();
 t.dump(myfunc);


}

Java8 - コレクター マップ

問題

String型のリストをstreamを使用してマップに変換せよ．そのリストの各要素は変換されたマップの値とする．キーは任意の整数値を割り当ててよい．

ヒント

Collectors.map()メソッドの基本知識をただ問うているだけの問題．

解答

       Stream.of("tako", "pako")
                .collect( toMap( x -> ++ctx, y -> y, (a,b) -> a + b ) )
                .forEach( (x,y) -> System.out.println( x + ":" + y ) );

走り書き - 草を生やす

草を生やす，緑豊かなコードである．

package org.tanuneko;

import java.util.Arrays;

public class Kusa {

    public static void main( String args[] ) {

        System.out.println(
            Arrays.asList( "This is a pen".split( " " ) ).stream()
                    .map( x -> "ww" + x + "ww" )
                    .reduce( "(^o^)", String::concat )
                    .toString()
        );

    }

}

２次元配列から重複を検索

問題
In a 2-D matrix, every row is increasingly sorted from left to right, and the last number in each row is not greater than the first number of the next row. A sample matrix follows. Please implement a function to check whether a number is in such a matrix or not. It returns true if it tries to find the number 7 in the sample matrix, but it returns false if it tries to find the number 12.

1   3   5

7   9   11

13  15  17

(Coding Interviews: Questions, Analysis & Solutionsより引用)

ヒント

２次元配列である必要などない．

解

基本的には２次元配列である必要がないため，一次元配列にするか，このまま２次元配列に２分検索をするか．ここでは前者の方法をとっている．

package org.tanuneko;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created by morinoko on 5/3/2014.
 */
public class DupeFound {

    static int bsearch( List<Integer> l, int val ) {

        int s = 0;
        int e = l.size() - 1;
        int m = 0;
        while( s <= e ) {
            m = l.get((s + e) / 2);
            if (m == val)
                return (s + e) / 2;
            else if (m < val)
                s = ((s + e) / 2) + 1;
            else
                e = ((s + e) / 2) - 1;
        }
        return -1;
    }


    public static void main( String args[] ) {

     
    List<Integer> l = Arrays.asList( "1 3 5", "7 9 11", "13 15 17" )
            .stream()
            .flatMap(x -> Arrays.stream(x.split(" ")))
            .mapToInt(x -> Integer.parseInt(x))
            .collect(ArrayList::new, ArrayList::add, ArrayList::addAll);

    int m = l.get( l.size() / 2 );

    System.out.println( bsearch( l, 5 ) );
    System.out.println( bsearch( l, 14 ) );
}
}

マルチスレッド - notifyとwait

問題
There are three threads in a process. The first thread prints 1 1 1 …, the second one prints 2 2 2 …, and the third one prints 3 3 3 … endlessly. How do you schedule these three threads in order to print 1 2 3 1 2 3 …?
(Coding Interviews, Analysis & Solutions より引用)

ヒント
各スレッド間でchain of responsibility的に連係動作させるか，マスタスレッドがnotify/waitを利用してオーケストレーションするか等，解法は色々ある．

解答

ここではヒントの後者の方法を実装してみた．

package org.tanuneko;

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

/**
 * Created by morinoko on 5/3/2014.
 */
public class MyThread implements Runnable {

    private static final int NUM_TH = 3;
    private final int id;
    private final int val;
    private static Object[] objs = new Object[NUM_TH];

    static {
        for( int i = 0;i < objs.length;i++ ) {
            objs[i] = new Object();
        }
    }

    public MyThread( int id,int val ) {
        this.id = id;
        this.val = val;
    }

    public void run() {

        while( true ) {

            synchronized( objs[id] ) {

                try {
                    objs[id].wait();
                } catch ( InterruptedException iE ) {
                    iE.printStackTrace();
                }
            }
            System.out.println( val );

        }
    }

    public static void main( String args[] ) throws InterruptedException {

        ExecutorService s = Executors.newFixedThreadPool( NUM_TH );
        for( int i = 0;i < NUM_TH;i++ ) {
            s.execute( new MyThread( i, i + 1) );
        }

        int invokeTarget = 0;
        while( true ) {
            synchronized( objs[invokeTarget] ) {
                objs[invokeTarget].notify();
            }

            Thread.sleep( 1000 );
            invokeTarget = ++invokeTarget % NUM_TH;
        }

    }

}

Groovy - JsonSlurperとJsonBuilder

最近仕事でGroovyを選ぶことが多い．やはりスピードを最優先かつシェルスクリプトでは要求にこたえられない場合はGroovy又はPythonを選ぶことになる．

しかしGroovyは書けば書くほど，便利で病みつきになる言語である．Groovy JDKも便利なものばかりで，おそらく通常のJavaコードを書くより効率は倍，コード量も半分以下になっていると感じる．

とりわけ便利であると思ったものをいくつか紹介していきたい．

一つ目はJsonSlurperとJsonBuilder．JSonSlurperは，名前の通りJsonオブジェクトをずずっとパースしてGroovyオブジェクトにアンマーシャルしてくれる．JsonSlurperは多くのparseオーバロード メソッドを提供しているので，JsonSlurperの為に入力データを加工する手間も省けることも多いだろう．
一方JsonBuilderはGroovyオブジェクトからJSONデータへのマーシャリング機能を提供している．
以下の例はJSONメッセージをアンマーシャル後，再びマーシャルする例．

import groovy.json.JsonBuilder
import groovy.json.JsonSlurper

jsonMsg = "{\n" +
        "    \"title\": \"The Latin Bit\",\n" +
        "    \"Label\": \"BlueNote\",\n" +
        "    \"Janre\": \"Jazz\",\n" +
        "    \"Leader\": [\n" +
        "        \"Grant Green\"\n" +
        "    ],\n" +
        "    \"Release\": 1962,\n" +
        "    \"TrackRecords\": [\n" +
        "        {\n" +
        "            \"All Tracks\": [\n" +
        "                \"Grant Green(g)\",\n" +
        "                \"John Acea(p)\",\n" +
        "                \"Wendell Marshall(b)\",\n" +
        "                \"Willie Bobo(ds)\",\n" +
        "                \"Carlos 'Patato' Valdes(conga)\",\n" +
        "                \"Garvin Masseaux(chekere)\"\n" +
        "            ]\n" +
        "        }\n" +
        "    ]}"

def parseJson( jsonData ) {

    JsonSlurper json = new JsonSlurper()
    return json.parseText( jsonData )

}

def buildJson( obj ) {

    def builder = new JsonBuilder( obj )
    return builder.toPrettyString()
}

// main

def parsed = parseJson( jsonMsg )
println( parsed )
assert parsed.title == "The Latin Bit"
assert parsed.Release == 1962
assert parsed.Leader[0] == "Grant Green"
assert parsed.TrackRecords["All Tracks"][0].indexOf( "John Acea(p)" ) != -1

println( buildJson( parsed ) )

フィボナッチ数を求めるコード

フィボナッチ数の漸化式を考えてみれば - f(n+2) = f(n) + f(n+1) -, いうまでもなく再帰を書きたくなるだろうし，実際にそういう解答をする人も多いし，そんなコードのサンプルをあげているサイトも多いし．．という．まぁ曲者である．Java，C++等をはじめとするコードでそんなコードを書いて，大きな値の引数を渡せばあっというまにスタックオーバーフローで動かない．現代のコンパイラやインタプリタならきっと末尾再帰で最適化してくれる，なんていうことを期待してコードを書くのはやめたほうがよいと思う．

フィボナッチ数のように，複数の再帰呼び出しを必要とするロジックなら素直にループで書こう．

    private static void fib( int max ) {

        int total = 0;
        int prev1 = 0;
        int prev2 = 1;

        for( int i = 0;i < max;i++ ) {
            if( i == 0 ) prev1 = 0;
            else if( i == 1 ) prev2 = 1;
            else {
                prev2 = prev1;
                prev1 = total;
            }
            total = prev1 + prev2;
        }

        System.out.println( total );

    }

Java - インターセクションの検出

インターセクションを検出するコードで，以下のサイトの解答例にはなかなか感心したので紹介．
シンプルでよいコードである．成程，HashSetのcontains()ならO(1)だ．

http://codereview.stackexchange.com/questions/9909/intersection-of-arrays-java

テストしたと書いていながら若干間違いがあるので，以下のように書き直し．

package org.tanuneko;

import java.util.*;

public class Intersect {

    private static List<Integer> intersect( final List<Integer> a, final List<Integer> b ) {

        Set<Integer> canAdd = new HashSet<Integer>(a);
        List<Integer> result = new ArrayList<>();
        for( int n : b ) {
            if( canAdd.contains(n) ) {
                result.add(n);
                canAdd.remove(n);
            }
        }
        return result;
    }

    public static void main( String args[] ) {

        List<Integer> a = Arrays.asList( 4,2,6,1,8,9,5 );
        List<Integer> b = Arrays.asList( 8,6,3,5,0,10,1 );

        System.out.println( intersect( a,b ) );
    }

}

メシウマという言葉

メシウマというネットスラングがあり，その意味は他人の不幸を肴に飯がうまい，という意味であるが，何とも心が貧しい感じで関心しない．

好きな球団が勝利して，そのあとの飯がうまい，というのが良いと思うが．

自己結合

自己結合は必ず使いこなせたほうが良い，というのはいうまでもないことだが，意外とわかってない人もどうやら多いようだ．

自己結合は，言ってみればなんのこともない，単にある外部キーが同テーブル上にあるプライマリキーと結合するだけである．良い好例と説明がこちらにあるので，理解があいまいだと思われる方は是非とも一読されたい．以下はSQLite3.5.9上で動作する解答例．

drop table if exists Employee
go
create table Employee (
 Id int not null primary key,
 Name varchar(64) not null,
 ManagerId int,
 Salary int not null 
)
go
insert into Employee (Id,Name,ManagerId,Salary) values( 1, "Kotora", 3, 500000 )
go
insert into Employee (Id,Name,ManagerId,Salary) values( 2, "Kodanuki",3,  5000 )
go
insert into Employee (Id,Name,Salary) values( 3, "Tanu", 100000 )
go
insert into Employee (Id,Name,Salary) values( 4, "Ushi", 5000 )

select e2.Name,"earns more than" as fact,e1.Name from Employee e1
join Employee e2 on e1.Id = e2.ManagerId
where e2.Salary > e1.Salary

BTreeの判定

何かよいインタビュー用の問題はないかリサーチしていたところ，ツリー構造のデータが二分木であるかどうか判定するコードを書け，というのが結構あることがわかった．

確かに基礎を見るにはよい問いかもしれない．
深さ優先ではこんな感じだろうか．

#include <iostream>
#include <string>
using namespace std;

typedef struct Node_Struct {
 int value;
 struct Node_Struct* l;
 struct Node_Struct* r;
} Node;

Node * add(Node* base, int value) {

 if (base == NULL) {
  cout << "adding " << value << " to this node" << endl;
  base = new Node;
  base->l = base->r = NULL;
  base->value = value;
 }
 else if (base->value > value) {
  cout << base->value << ">" << value << ".. L" << endl;
  base->l = add(base->l,value);
 }
 else {
  cout << base->value << "<" << value << ".. R" << endl;
  base->r = add( base->r, value);
 }
 return base;

}

void dump(const Node* n) {
 cout << "{" << "value:" << n->value << "}" << endl;
}

void traverse_r( Node* n ) {

 if (n == NULL)
  return;

 if (n->l != NULL)
  traverse_r(n->l);
 dump(n);
 if (n->r != NULL)
  traverse_r(n->r);

 
}


Node* build_btree( Node* n) {

 n = add(n, 15);
 n = add(n, 30);
 n = add(n, 48);
 n = add(n, 10);
 n = add(n, 15);
 n = add(n, 72);
 n = add(n, 60);
 n = add(n, 66);
 n = add(n, 26);
 n = add(n, 55);
 return n;

}

bool is_btree_d(Node *n, bool decision) {
 
 if (n == NULL || decision == false)
  return decision;
 if (n->l != NULL && n->r != NULL) {
  cout << n->l->value << ":" << n->r->value << endl;
  decision = n->l->value < n->r->value ? true : false;
 }

 cout << "movin to l" << endl;
 decision = is_btree_d(n->l, decision);
 cout << "moving to r" << endl;
 decision = is_btree_d(n->r, decision);
 return decision;
 
}

int main() {

 Node* n = NULL;
 n = build_btree(n);
 traverse_r( n );
 cout << "is this btree valid? - " << is_btree_d(n, true) << endl;

 return 0;
}