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;
}

Java - Mapのイテレーション

Mapのイテレーションをするコードをレビューすることもあるし，もはやそのやり方も人口に膾炙していると思う．しかし，keySet()を最初に取得し，keySetのイテレータを通して要素にアクセスするコードを見るのもまた事実でもある．コードの静的解析ツールを走らせばすぐに指摘してくれるはずなので，レビュー前にはぜひ修正をしてもらいたいものである．

import java.util.HashMap;
import java.util.Map;

public class MapIter {

    public static void main( String args[] ) {

        Map<String,String> data = new HashMap<String,String>();
        data.put( "F", "Fine Fare" );
        data.put( "B", "Biking" );
        data.put( "C", "C Town Town Town" );

        for( Map.Entry<String,String> ent : data.entrySet() ) {
            System.out.printf("%s:%s\n",ent.getKey(),ent.getValue());
        }

    }
}

デッドロック

時々私が使う面接の質問のひとつはデッドロックを起こすコードを書いてみてください，というものである．多くの候補者は理論的にはわかってはいるものの，コードでいざ書く段になるとなぜか正しい答えを書けないのである．

以下にサンプルのコードを示す．以下のコードや，Oracle Javaのデッドロックの参考例，哲学者の食事問題などを参考にしてほしい．

class Friend extends Thread implements Runnable {

    private Friend myFriend;
    private String name;

    public Friend( final String name ) {
        this.name = name;
    }

    public synchronized void vow() {
        System.out.printf( "Hey my friend %s..\n", name );
        myFriend.vow();
    }

    public void run() {
        vow();
    }

    public void setMyFriend( Friend myFriend ) {
        this.myFriend = myFriend;
    }

    public static void main( String args[] ) {
        Friend me = new Friend( "John Flansburgh" );
        Friend dude = new Friend( "John Linnell" );
        me.setMyFriend( dude );
        dude.setMyFriend( me );
        me.start();
        dude.start();
        System.out.println( "Have a nice day." );
    }
}

走り書き2

バブルソートの走り書きのついでに選択ソートも。。

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

void dump(int dump) {
 cout << dump << ",";
}

void selsort(vector<int>& v) {

 cout << "before:";
 for_each(v.begin(), v.end(), dump);
 cout << endl;

 int min;
 int t;
 for (int i = 0; i < v.size() - 1; i++) {
  min = i;
  for (int j = i + 1; j < v.size(); j++) {
   if (v[j] < v[min]) {
    min = j;
   }
  }
  t = v[i];
  v[i] = v[min];
  v[min] = t;
 }

 cout << "after:";
 for_each(v.begin(), v.end(), dump);
 cout << endl;

}


int main() {

 int nums[] = { 32, 22, 25, 10, 9, 38, 40, 42, 50, 51, 10, 32, 45, 27 };
 vector<int> v;
 for (int i = 0; i < sizeof(nums) / sizeof(int); i++)
  v.push_back(nums[i]);

 selsort(v);

}

走り書き

妙にバブルソート(!)が書きたくなったので，走り書きをした．
サイダーが飲みたくなった．

import java.util.List;


public class Bubb {

    static void bubble( int[] nums ) {

        int t;
        for( int i = 0;i < nums.length - 1;i++ ) {
            for( int j = i + 1; j < nums.length; j++ ) {
                if( nums[i] > nums[j] ) {
                    t = nums[i];
                    nums[i] = nums[j];
                    nums[j] = t;
                }
            }
        }
    }

    public static void main( String args[] ) {

        int[] nums = { 32, 17, 21, 26, 35, 40, 10, 5, 8, 9, 48, 23, 16, 17 };
        bubble( nums );
        for( int i = 0;i < nums.length;i++ ) {
            System.out.println( nums[ i ] );
        }

    }
}

問題 - 三角形の上段から下段へのトラバース

問題

By starting at the top of the triangle, move to adjacent numbers on the row below. On moving down to the below node, choose higher number. Produce the sum of the route.

e.g.

        6

     7     8

  6     5    12

9   8     10     6

The route should be 6 -> 8 -> 12 -> 10. So the sum of the route is 40.

簡単な問題なので，たウォーミングアップ程度には丁度よいかと思われる．

ヒント

三角形を一次元のリストにマップして，インデックスをスライドさせていく．

三角形の格段の要素数は x(n)=n．

解答

import org.apache.commons.io.FileUtils;

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

public class TrianglePuzzle {

    private static final String SEPARATOR = " ";
    private final File puzzleFile;

    public TrianglePuzzle( final String fileName ) throws IOException {
        this.puzzleFile = new File( TrianglePuzzle.class.getClassLoader().getResource( fileName ).getFile() );
        if( !puzzleFile.exists() || !puzzleFile.isFile() || puzzleFile.length() == 0 )
            throw new IOException( "File must be file with proper content" );
    }

    public long calc() throws IOException {

        Stack<Long> trace = new Stack<Long>();
        List<Long> vals = parse();
        int step = 0;
        int sel = 0;
        int stepTotal = 0;
        int val = 0;

        long lval = 0;
        long rval = 0;

        // step 1 is automatically first item
        trace.push( vals.get( 0 ) );
        stepTotal += ++step;

        // step 2 - N .. only adjacent numbers are checked
        while( stepTotal != vals.size() ) {
            lval = vals.get( stepTotal + sel );
            rval = vals.get( stepTotal + sel + 1 );
            System.out.println( lval + "," + rval );
            sel = lval > rval ? sel : sel + 1;
            System.out.println( vals.get( stepTotal + sel ) + " picked." );
            trace.push( vals.get( stepTotal + sel ) );
            System.out.println( "stepTotal=" + ( stepTotal ) );

            stepTotal += ++step;
        }

        // With Java8 code should be like return trace.stream().sum()
        Iterator<Long> iter = trace.iterator();

        int total = 0;
        while( iter.hasNext() ) {
            total += iter.next();
        }
        return total;

    }

    final List<Long> parse() throws IOException {

        List<Long> vals = new ArrayList<Long>();
        BufferedReader br = new BufferedReader( new InputStreamReader( new FileInputStream( puzzleFile ) ) );
        String line = null;
        while( ( line = br.readLine() ) != null ) {
            StringTokenizer st = new StringTokenizer( line, SEPARATOR );
            while( st.hasMoreTokens() ) {
                vals.add( Long.parseLong(st.nextToken()) );
            }
        }
        return vals;

    }

    public static void main( String args[] ) throws IOException {
        if( args.length != 1 ) {
            System.out.println( "arg length must be 1" );
            System.exit( 0 );
        }
        TrianglePuzzle tp = new TrianglePuzzle( args[ 0 ] );
    }
}

Java8 - Void 関数の参照

void関数への参照にはProducerを使う．

        Consumer<String> dumper = (x)->System.out.println(x);
        List<String> stars = Arrays.asList("mai","mao","yuzuru");
        stars.stream().forEach(dumper);