ElasticSearch IntegrationTest

ElasticSearch IntegrationTestを使えば，メモリ上での仮想クラスタ上で単体テストを走らせることができる優れものだが，あまりサンプルコードが見つからない気がする．

package org.tanuneko;

import org.apache.commons.io.FileUtils;
import org.elasticsearch.action.get.GetResponse;
import org.elasticsearch.action.index.IndexResponse;
import org.elasticsearch.action.search.SearchResponse;
import org.elasticsearch.action.search.SearchType;
import org.elasticsearch.common.xcontent.XContentBuilder;
import org.elasticsearch.index.query.FilterBuilders;
import org.elasticsearch.index.query.QueryBuilders;
import org.elasticsearch.test.ElasticsearchIntegrationTest;
import org.elasticsearch.test.ElasticsearchIntegrationTest.ClusterScope;
import org.junit.Test;

import java.io.File;
import java.text.SimpleDateFormat;
import java.time.LocalDateTime;
import java.util.Date;
import java.util.Map;
import java.util.function.Function;

import static org.elasticsearch.common.xcontent.XContentFactory.jsonBuilder;
import static org.hamcrest.core.Is.is;


@ClusterScope(scope= ElasticsearchIntegrationTest.Scope.SUITE,numDataNodes=2)
public class ESIntegrationTest extends ElasticsearchIntegrationTest {

    private static final String INDEX_NAME = "tanuapp";
    private static final String DOCTYPE_NAME = "posting_msg";
    private static final String TODAY_DATE_STR = new SimpleDateFormat("yyyy-MM-dd").format(new Date());

    @Test
    public void testSearch() throws Exception {
        createIndex(INDEX_NAME);
        client().admin().indices().preparePutMapping(INDEX_NAME)
                .setType(DOCTYPE_NAME)
                .setSource(readMappingFile(DOCTYPE_NAME + "_mappings.json"))
                .execute().actionGet();

        assertThat(indexDoc(INDEX_NAME, DOCTYPE_NAME, "1", "neko32", "hellou").isCreated(), is(true));
        assertThat(indexDoc(INDEX_NAME, DOCTYPE_NAME, "2", "ushi", "poooo").isCreated(), is(true));
        assertThat(indexDoc(INDEX_NAME, DOCTYPE_NAME, "3", "neko64", "ka-kakinkin ka-kinkin").isCreated(), is(true));

        flushAndRefresh(INDEX_NAME);
        ensureGreen(INDEX_NAME);
        assertThat(indexExists(INDEX_NAME), is(true));

        GetResponse resp = client().prepareGet(INDEX_NAME, DOCTYPE_NAME, "3")
                .execute()
                .actionGet();

        Map source = resp.getSource();
        assertThat((String)source.get("user"), is("neko64"));
        assertThat((String)source.get("message"), is("ka-kakinkin ka-kinkin"));
        final String postedDate = (String)source.get("postDate");
        Function isSameDate = x -> x.startsWith(TODAY_DATE_STR);
        assertTrue(isSameDate.apply(convertToGMT(postedDate)).booleanValue());

        SearchResponse searchResp = client().prepareSearch(INDEX_NAME)
                .setTypes(DOCTYPE_NAME)
                .setSearchType(SearchType.DFS_QUERY_THEN_FETCH)
                .setQuery(QueryBuilders.fuzzyLikeThisFieldQuery("user").likeText("neko50"))
                .setPostFilter(FilterBuilders.idsFilter(DOCTYPE_NAME).ids("1"))
                .execute()
                .actionGet();

        assertThat(searchResp.getHits().getHits().length, is(1));
        assertThat(searchResp.getHits().getAt(0).getSource().get("user"), is("neko32"));
    }


    private String readMappingFile(final String fileName) throws Exception {
        return FileUtils.readFileToString(new File(ESIntegrationTest.class.getClassLoader().getResource(fileName).getPath()));
    }

    private String convertToGMT(String dateStr) {
        return LocalDateTime.parse(dateStr.substring(0,dateStr.length()-1)).toString();
    }

    private IndexResponse indexDoc(final String idxName,
                                    final String docName,
                                    final String id,
                                    final String user,
                                    final String msg) throws Exception {
        return client().prepareIndex(INDEX_NAME, DOCTYPE_NAME)
                .setSource(genMsg(user, msg))
                .setId(id)
                .execute().actionGet();
    }

    private XContentBuilder genMsg(String user, String msg) throws Exception {
        return jsonBuilder().startObject()
                .field("user", user)
                .field("postDate", new Date())
                .field("message", msg)
                .endObject();
    }
}

貪欲なアルゴリズム

会社で誰かが貪欲なアルゴリズムの問題を出していたので，日本の硬貨単位に合わせたものを解いてみた．DPを使わなければまぁ大概はこのような解になるだろう．

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

int coins[] = { 1, 5, 10, 50, 100, 500 };
int nums[] = { 6, 3, 4, 5, 3, 2 };

void useCoins(int amounts, std::vector<std::pair<int,int>*>& pV) {
 int num;
 for (int i = sizeof(coins) / sizeof(int) - 1; i >= 0; i--) {
  if (amounts <= 0) {
   return;
  }
  num = std::min(amounts / coins[i], nums[i]);
  amounts -= num * coins[i]; 
  pV.push_back(new std::pair<int,int>(coins[i], num));  
 }
}

int main() {
 std::vector<std::pair<int,int>*> v;
 useCoins(1280, v);
 for_each(v.begin(), v.end(), [](std::pair<int,int>* x){ std::cout << x->first << ":" << x->second << std::endl; });

}

std::to_string

C++11以降では数値型から文字列に変換するのにstd::to_string()を使えばよい．これは便利である．以下は整数値を文字列に変換する例．

#include <iterator>
#include <iostream>
#include <list>
#include <algorithm>
#include <sstream>
#include <string>

int main() {
 std::list<int> v{ 25, 30, 10, 90, 500 };
 std::list<std::string> v2;
 std::transform(v.begin(), v.end(), std::back_inserter(v2), [](int x)->std::string { return std::to_string(x); });
 std::stringstream ss;
 std::for_each(v2.begin(), v2.end(), [&ss](std::string s)->void {ss << s << ","; });
 std::cout << ss.str().substr(0,ss.str().length()-1) << std::endl;
}

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

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

Java8 - mapToObj()でキャラクタストリームの作成

文字列からキャラクタストリームを作るにはどうしたらよいか？
色々とやり方はあるだろうがワンライナーでやりたいとしたらおそらくこうなるのでは．

"abcde".chars().mapToObj(x->(char)x).forEach(System.out::println);

今更デザインパターン - Strategy

Strategyパターンは，既存システムの機能拡張，とりわけ別のプロトコルへの適応といった場合や，汎用的なケースに対応できるシステムの開発において使われると思われる．

例えば最初はデータをすべてNFSディスクに保存する仕様だったのが，次に，代わりにデータをHDFSに保存するように仕様変更する，といった具合である．

このような場合に解放/閉鎖原則に遵守しつつシステム変更を行う定石の一つとしてStrategyパターンを適用することであろう．

Strategyパターンはアルゴリズム・ロジックをカプセル化し，呼び出しクラスからはそれらが可換であることを満たす必要がある．

以下の例は日本語変換ロジックとドイツ語変換ロジックをカプセル化し，呼び出し元において変換ロジックをドイツ語から日本語に取り換えている．

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

class TransAlg {
public:
 virtual string translate(const string str) = 0;
};

class GermanTrans:public TransAlg {
public:
 virtual string translate(const string str) {
  if( str == "welcome" )
   return "willkommen";
  else
   return "weiss nicht";
 }
};

class JapanTrans:public TransAlg {
public:
 virtual string translate(const string str) {
  if( str == "welcome" )
   return "yokoso";
  else
   return "wakannai";
 }
};

class Translator {

private:
 TransAlg* m_alg;
 bool isReady;
public:
 Translator():isReady(false) {}
 string translate(const string str);
 void SetAlg(TransAlg* alg) { m_alg = alg; isReady = true; }
};

string Translator::translate(const string str ) {

 if( isReady ) {
  return m_alg->translate(str);
 }
 else
  throw logic_error("algorithm not set") ;
}


int main() {

 TransAlg* alg;
 alg = new GermanTrans();
 Translator trans;

 try {
  trans.SetAlg(alg);
  cout << "translating to German:" << trans.translate("welcome") << endl;
  delete alg;
  alg = new JapanTrans();
  trans.SetAlg(alg);
  cout << "translating to Japanese:" << trans.translate("welcome") << endl;
  delete alg;
 }catch(exception& e) {
  cerr << "err:" << e.what() << endl;
 }

}

今更デザインパターン - Visitor

知ってて当然というレベルまで普及した(少なくともGoFの)デザインパターンであるが，中には使用頻度が低いものもある．

使用頻度が低いといってもそれらを知っていて，適切に利用できるかどうかは大きな違いを生むのではないだろうか．

ということでそのようなややFactoryやsingletonに比べてマイナーなデザインパターンをいくつか取り上げる．

Visitor

アルゴリズム及びロジック部分をオブジェクトから切り離す，正に関心の分離を体現するデザインパターンの一つがVisitorである．

あるオブジェクトがロジックを持つのではなく，代わりにvisitorオブジェクトにロジックを持たせる．

そしてそのvisitorオブジェクトを他オブジェクトに訪問(visit)を受け入れ(accept)させて，ロジックをそのオブジェクト内で実行させる．

以下の例はNodeの子クラスにDumpVisitor具象クラスの訪問を受け入れる例である．

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

class VisitorIF;

class Node {
public:
 virtual void accept(VisitorIF* v) = 0;
};

class FileNode:public Node {
private:
 int m_id;
public:
 FileNode(int id):m_id(id){}
 int GetID() { return m_id; }
 virtual void accept(VisitorIF* v);
};

class DirectoryNode:public Node {
private:
 int m_id;
public:
 DirectoryNode(int id):m_id(id){}
 int GetID() { return m_id; }
 virtual void accept(VisitorIF* v);
};

class VisitorIF {
public:
 virtual void visit(FileNode* n) = 0;
 virtual void visit(DirectoryNode* n) = 0;
};

class DumpVisitor:public VisitorIF {

 virtual void visit(FileNode* n){ cout << "<<FILE>>" << n->GetID() << endl; }
 virtual void visit(DirectoryNode* n){  cout << "<<DIR>>" << n->GetID() << endl; }

};

void FileNode::accept(VisitorIF* v) {

 v->visit(this);

}

void DirectoryNode::accept(VisitorIF* v) {

 v->visit(this);

}

int main() {

 VisitorIF* v = new DumpVisitor();
 FileNode fn(10);
 DirectoryNode dn(20000);
 fn.accept(v);
 dn.accept(v);
 delete v;
}

Java8 - 関数の合成 1 .. andThen

Java8のラムダは関数の合成に対する操作も用意されている．
そのうちの一つがandThen()である．以下の例は引換券のIDを入力として本のタイトルを返す．

package org.tanuneko;

import java.util.*;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;

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

public class AndThenSample {

    private static List<ClaimTicket> tickets;

    private static void init() {

        tickets = new ArrayList<ClaimTicket>();
        tickets.add( new ClaimTicket( 1, new Book( Janre.Sports, "All about Payton Manning") ) );
        tickets.add( new ClaimTicket( 2, new Book( Janre.Sports, "Andy - how to win at playoff") ) );
        tickets.add( new ClaimTicket( 3, new Book( Janre.Education, "ABC") ) );
        tickets.add( new ClaimTicket( 101, new Book( Janre.Education, "Waldorf education - how it works") ) );

    }

    public static void main( String args[] ) {

        init();
        Function<ClaimTicket,Book> getBookByClaimId = ClaimTicket::getBook;
        Function<Book,String> getTitle = Book::getTitle;
        Function<ClaimTicket,String> getTitleOfClaimedBook = getBookByClaimId.andThen(getTitle);
        System.out.println( tickets.stream().filter(x->x.getId()<100)
                .map(getTitleOfClaimedBook)
                .collect( Collectors.reducing((x,y)-> x + "," + y))
                .toString() );
    }

}

enum Janre {
    Education,
    Sports
}

class Book {

    private Janre janre;
    private String title;

    public Book( Janre janre, String title ) {
        this.janre = janre;
        this.title = title;
    }

    public Janre getJanre() { return janre; }
    public String getTitle() { return title; }
}

class ClaimTicket {

    private int id;
    private Book book;

    public ClaimTicket( final int id, final Book book ) {
        this.id = id;
        this.book = book;
    }

    public int getId() { return id; }
    public Book getBook() { return book; }
}

Java8 - Infiniteのstream

Stream.iterate()を使うとinfiniteのstreamを生成できる．infiniteのstream - ここではiterateの２番目の引数UnaryOperator<T> ( 引数Tを取り，処理後結果として入力と同型Tを返す.つまりFunction<T,T> )を無制限に適用しstreamの要素を生成する．

おおよその場合はStream.limit()と組み合わせて使う．

package org.tanuneko;

import java.util.stream.Stream;

public class ToMapSample {

    public static void main( String args[] ) {

        Stream.iterate( 'S', (x)->"ABC".charAt((int)(Math.random()*3)))
                .limit(30)
                .forEach(System.out::println);

    }

}

Java8 - キーごとに分類

以下の例は本オブジェクトのリストに対し，各本のジャンルごとに分類した結果をマップにして返す例．IntelliJのエディタではシンタックスエラーが出るが，コンパイルも実行も問題ない．

package org.tanuneko;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import static java.util.stream.Collectors.*;

public class ToMapSample {

    private static List<Book> books;

    private static void init() {

        books = new ArrayList<Book>();
        books.add( new Book( Janre.Sports, "All about Payton Manning") );
        books.add( new Book( Janre.Sports, "Andy - how to win at playoff")  );
        books.add( new Book( Janre.Education, "ABC") );
        books.add( new Book( Janre.Education, "Waldorf education - how it works")  );

    }

    public static void main( String args[] ) {

        init();
        Map<Janre,List<String>> map = books.stream()
                .collect(groupingBy(Book::getJanre,TreeMap::new,mapping(Book::getTitle,toList())));
        System.out.println(map);

    }

}

enum Janre {
    Education,
    Sports
}

class Book {

    private Janre janre;
    private String title;

    public Book( Janre janre, String title ) {
        this.janre = janre;
        this.title = title;
    }

    public Janre getJanre() { return janre; }
    public String getTitle() { return title; }
}

Java8 - streamとDirectoryWalkerで効率よくファイル探索

Java IO CommonsのDirectoryWalkerとstreamを組み合わせて，効率よくファイルシステム上のデータを探すコード．かなり荒削りのサンプルだが，とりあえず動く．

package org.tanuneko.tanukin;

import org.apache.commons.io.DirectoryWalker;
import org.apache.commons.io.filefilter.FileFilterUtils;
import org.apache.commons.io.filefilter.IOFileFilter;

import java.io.File;
import java.io.FileFilter;
import java.io.IOException;
import java.util.Collection;
import java.util.List;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.stream.Collectors;

public class DirWalker extends DirectoryWalker<File> {

    private static FileFilter filter = getFilter();

    public DirWalker() {

        super( filter,-1 );

    }

    protected void handleFile( File file, int depth, Collection<File> results ) {

        results.add( file );

    }

    public Collection<File> start( File startDir ) throws IOException {
        Collection<File> results = new ConcurrentLinkedQueue<File>();
        super.walk( startDir, results );
        return results;
    }

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

        DirWalker walker = new DirWalker();
        System.out.println(
                        walker.start(new File("C:\\cygwin\\srv")).parallelStream()
                        .map(x -> x.getAbsolutePath())
                        .collect(Collectors.toStringJoiner("\n"))
                        .toString());

    }

    // if you want to handle directory, define below
    /*
    protected boolean handleDirectory( File dir, int depth, Collection<File> results ) {

        if( ".svn".equals( dir.getName() ) ) {
            return false;
        }
        else {
            return true;
        }
    }
    */

    private static FileFilter getFilter() {

        //    you can define filter
        //    IOFileFilter suffixFilt =  FileFilterUtils.suffixFileFilter( ".txt" );
        //    FileFilterUtils.makeSVNAware( suffixFilt );
        //   FileFilter filter = FileFilterUtils.or( suffixFilt );
        //    return filter;
        return null;

    }

}

Java8 - オブジェクトへのmapper適用

以下の例はJava8のmapを用いて，

1. カスタムオブジェクトItemのマスタリスト中から興味のある品だけを取り出し
2. 更に10000円以上のものだけを選び
3. かつ価格を安いものから昇順に並べる

例である．

package org.tanuneko;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Reducer {

    public static void main( String args[] ) {

        // since this is lazy evaluation, WareHouse::findItembyId is not called for all entries in item list held by WareHouse
        List<Integer> interests = Arrays.asList( 1,2,3,4,5,6 );
        List<Item> items = interests.stream().map(WareHouse::findItembyId)
                            .filter((x)->x.getPrice()>10000)
                            .sorted( (x,y)->x.getPrice() - y.getPrice() )
                            .collect(Collectors.toList());
        items.stream().forEach(System.out::println);
 
     }

}

class WareHouse {

    static final List<Item> items = genItems();

    public static Item findItembyId( int id )  {
        // better to use orElse()
        return items.stream().filter(x->x.getId()==id).findFirst().get();

    }

    private static List<Item> genItems() {
        List<Item> items = new ArrayList<>();
        items.add( new Item( 1, 500, "Basket" ) );
        items.add( new Item( 2,1200, "Rack" ) );
        items.add( new Item( 3, 700, "Small Table" ) );
        items.add( new Item( 4, 50000, "Granite Table" ) );
        items.add( new Item( 5, 15000, "Closet" ) );
        items.add( new Item( 6, 400, "Grout" ) );
        items.add( new Item( 7, 28000, "Small Couch" ) );
        return items;
    }
}

Items.java

package org.tanuneko;

public class Item {

    private int id;
    private int price;
    private String name;

    public Item( int id, int price, String name ) {
        this.id = id;
        this.price = price;
        this.name = name;
    }

    public int getId() { return id; }
    public int getPrice() { return price; }
    public String getName() { return name; }

    @Override
    public String toString() {
        return "Item{" +
                "id=" + id +
                ", price=" + price +
                ", name='" + name + '\'' +
                '}';
    }
}

Item{id=5, price=15000, name='Closet'}
Item{id=4, price=50000, name='Granite Table'}

Java8 - reduceとmapで集計

ついでにmapでカスタムオブジェクト群のあるフィールド値の合計をmapとreduceで行う例．

package org.tanuneko;

import java.util.ArrayList;
import java.util.List;
import java.util.function.BinaryOperator;

public class Reducer {

    public static void main( String args[] ) {

        System.out.println( genItems().stream().map( Item::getPrice ).reduce( Integer::sum ).get() );
        
     }

    private static List<Item> genItems() {
        List<Item> items = new ArrayList<>();
        items.add( new Item( 500, "Basket" ) );
        items.add( new Item( 1200, "Rack" ) );
        items.add( new Item( 700, "Small Table" ) );
        items.add( new Item( 50000, "Granite Table" ) );
        items.add( new Item( 15000, "Closet" ) );
        items.add( new Item( 400, "Grout" ) );
        return items;
    }

    private static Item getCheapestOne() {
        return new Item( Integer.MIN_VALUE, "VOID" );
    }
}

package org.tanuneko;

public class Item {
    private int price;
    private String name;

    public Item( int price, String name ) {
        this.price = price;
        this.name = name;
    }

    public int getPrice() { return price; }
    public String getName() { return name; }

    @Override
    public String toString() {
        return "Item{" +
                "price=" + price +
                ", name='" + name + '\'' +
                '}';
    }
}

Java8 - reduceで検索

Java8のstreamのreduceを使ってカスタムオブジェクト(この例ではItem)の検索をする例．


Item.java

package org.tanuneko;

import java.util.ArrayList;
import java.util.List;
import java.util.function.BinaryOperator;

public class Reducer {

    public static void main( String args[] ) {

        BinaryOperator<Item> costsMore = (m,n)->
                                          { return ( m.getPrice() > n.getPrice() ? m:n ); };

        System.out.println(genItems().stream().reduce(getCheapestOne(), costsMore));
     }

    private static List<Item> genItems() {
        List<Item> items = new ArrayList<>();
        items.add( new Item( 500, "Basket" ) );
        items.add( new Item( 1200, "Rack" ) );
        items.add( new Item( 700, "Small Table" ) );
        items.add( new Item( 50000, "Granite Table" ) );
        items.add( new Item( 15000, "Closet" ) );
        items.add( new Item( 400, "Grout" ) );
        return items;
    }

    private static Item getCheapestOne() {
        return new Item( Integer.MIN_VALUE, "VOID" );
    }
}

Item.java

package org.tanuneko;

public class Item {
    private int price;
    private String name;

    public Item( int price, String name ) {
        this.price = price;
        this.name = name;
    }

    public int getPrice() { return price; }
    public String getName() { return name; }

    @Override
    public String toString() {
        return "Item{" +
                "price=" + price +
                ", name='" + name + '\'' +
                '}';
    }
}

実行結果
Item{price=50000, name='Granite Table'}

Java8 - stream

Java8の変更点の目玉の一つがstreamである．今までのfor文よりもずっときれいにデータプロセス用のコードが書けるようになる．

以下の例は，とある場外取引システムにおけるトレードデータから以下の条件を満たすものを抽出した例．

• TradeDateが2013年１月１日以降
• アクション名がADD
• 取引相手先国が日本

package org.tanuneko.sample;

import java.time.ZonedDateTime;
import java.util.ArrayList;
import java.util.List;

public class StreamSample {

    private static List<Trade> trades = populateTrades();
    private static List<CounterParty> cps = populateCPs();

    private static List<Trade> populateTrades() {
        List<Trade> list = new ArrayList<Trade>();
        list.add( new Trade( "TRD111.1", 1, "ADD", parse( "2013-01-20" ), 1001, true, "15000000ABC" ) );
        list.add( new Trade( "TRD123.1", 1, "ADD", parse( "2013-01-20" ), 1006, true, "16000000ABC" ) );
        list.add( new Trade( "TRD123.1", 2, "MOD", parse( "2013-01-26" ), 1006, true, "16000000ABC" ) );
        list.add( new Trade( "TRD145.1", 1, "ADD", parse( "2013-09-20" ), 1009, true, "T7000000ABC" ) );
        list.add( new Trade( "TRD133.1", 1, "ADD", parse( "2013-06-20" ), 1001, true, "16600000ABC" ) );
        list.add( new Trade( "TRD080.1", 1, "ADD", parse( "2010-07-20" ), 1001, true, "TRD080.1" ) );
        list.add( new Trade( "TRD092.1", 1, "ADD", parse( "2010-09-15" ), 1008, true, "TRD092.1" ) );
        list.add( new Trade( "TRD092.1", 2, "MOD", parse( "2010-09-30" ), 1020, true, "TRD092.1" ) );
        return list;
    }

    private static List<CounterParty> populateCPs() {
        List<CounterParty> cps = new ArrayList<CounterParty>();
        cps.add( new CounterParty( 1001, "US" ) );
        cps.add( new CounterParty( 1009, "Ireland" ) );
        cps.add( new CounterParty( 1006, "Japan" ) );
        cps.add( new CounterParty( 1020, "India" ) );
        cps.add( new CounterParty( 1008, "France" ) );
        cps.sort((l,r) -> l.getCounterPartyId() - r.getCounterPartyId()  );
        return cps;
    }

    private static ZonedDateTime parse( String date ) {
        return ZonedDateTime.parse( date + "T00:00:00-05:00[America/New_York]" );
    }

    public static void main( String args[] ) {
        
        trades.stream()
                .filter(t -> t.getTradeDate().isAfter(parse("2013-01-01")))
                .filter(t -> t.getActionName().equals("ADD") )
                .filter(t -> cps.stream().anyMatch( x -> x.getCounterPartyId() == t.getCounterPartyId() && x.getCountry().equals( "Japan" ) ) )
                .forEach(t -> System.out.println(t));
        cps.forEach( c -> System.out.println( c ) );
    }
}

class CounterParty {

    private int counterPartyId;
    private String country;

    CounterParty(int counterPartyId, String country) {
        this.counterPartyId = counterPartyId;
        this.country = country;
    }

    public int getCounterPartyId() {
        return counterPartyId;
    }

    public String getCountry() {
        return country;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        CounterParty that = (CounterParty) o;

        if (counterPartyId != that.counterPartyId) return false;

        return true;
    }

    @Override
    public int hashCode() {
        return counterPartyId;
    }

    @Override
    public String toString() {
        return "CounterParty{" +
                "counterPartyId=" + counterPartyId +
                ", country='" + country + '\'' +
                '}';
    }
}

class Trade {

    private String tradeId;
    private int eventId;
    private String actionName;
    private ZonedDateTime tradeDate;
    private int counterPartyId;
    private boolean isSDREligible;
    private String USI;

    public Trade( String tradeId, int eventId, String actionName, ZonedDateTime tradeDate,
                   int counterPartyId, boolean isSDREligible, String USI ) {
        this.tradeId = tradeId;
        this.eventId = eventId;
        this.actionName = actionName;
        this.tradeDate = tradeDate;
        this.counterPartyId = counterPartyId;
        this.isSDREligible = isSDREligible;
        this.USI = USI;
    }

    public String getTradeId() {
        return tradeId;
    }

    public int getEventId() {
        return eventId;
    }

    public String getActionName() {
        return actionName;
    }

    public ZonedDateTime getTradeDate() {
        return tradeDate;
    }

    public int getCounterPartyId() {
        return counterPartyId;
    }

    public boolean isSDREligible() {
        return isSDREligible;
    }

    public String getUSI() {
        return USI;
    }

    @Override
    public String toString() {
        return "Trade{" +
                "tradeId='" + tradeId + '\'' +
                ", eventId=" + eventId +
                ", actionName='" + actionName + '\'' +
                ", tradeDate=" + tradeDate +
                ", counterPartyId=" + counterPartyId +
                ", isSDREligible=" + isSDREligible +
                ", USI='" + USI + '\'' +
                '}';
    }
}

Java8 新しい Date and Time API

Java8の新機能の一つが新しいDate and Time API(JSR-310)の追加だろう．ご存じの通り標準SDKに付属していた従来のDate関連のクラスは機能が貧弱であったり，Calendarクラスmutabilityに起因する懸念から，Joda Timeを使っていた．
この新しいDate and Time API(JSR-310)を使うか，Joda Timeを使い続けるかはあなた次第だが，少なくとも旧来のDateの実装で無理をし続ける必要だけはなさそうである．

ちなみに以下のサイトは良質なDate and Time APIのサマリ，Joda TimeとJSR-310の比較記事だと思う．

http://sssslide.com/www.slideshare.net/JustinSDK/2013-java-developer-day-joda-timejsr310
http://howtodoinjava.com/2013/05/15/date-and-time-api-changes-in-java-8-lambda/

LocalDate, ZoneDateTimeそしてDateTimeFormatterの使用例

import java.time.LocalDate;
import java.time.ZoneId;
import java.time.ZonedDateTime;
import java.time.format.DateTimeFormatter;
import java.time.format.DateTimeFormatterBuilder;

/**
 * Created by morinoko on 12/29/13.
 */
public class Kerorin {

    public static void main( String args[] ) {

        LocalDate date = LocalDate.now();
        System.out.println( "today:" + date );
        System.out.println( "after five days from today:" + date.plusDays(5) );
        //ZoneId.getAvailableZoneIds().forEach(x -> System.out.println(x));
        ZonedDateTime zTime = ZonedDateTime.now(ZoneId.of("America/New_York"));
        DateTimeFormatter fmt = new DateTimeFormatterBuilder().append( DateTimeFormatter.ISO_DATE )
                .appendLiteral("-")
                .appendZoneId().toFormatter();

        System.out.println( fmt.format( zTime ) );
        System.out.println( "Converting to JST" );
        System.out.println( fmt.format( zTime.withZoneSameLocal( ZoneId.of( "Asia/Tokyo" ) ) ) );
      }

}

Java8 ラムダ

関数言語の使用者には十二分におなじみのlambda式がついにJava バージョン8で正式採用である．今まで無名クラスを書いてはコードが汚れるたびに，関数ポインタのように書ければなぁ，と思っていたのだが．．これからはLambda式で綺麗にかけるようになるわけである．実にありがたい．

Lambda式を使ってリストをソート後ダンプ

import java.util.Arrays;
import java.util.List;

/**
 * Created by morinoko on 12/29/13.
 */
public class Tanukin {

    public static void main( String args[] ) {

        List<String> list = Arrays.asList( new String[]{"tanu", "tanuku", "hello"} );
        list.sort( (l,r) -> l.length() - r.length()  );
        list.forEach( s -> System.out.println( s ) );

    }

}

C++での例

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

bool cmp(const string& l, const string& r) { return l.size() < r.size(); }
void dump(const string& s){ cout << s << endl; }

int main() {

 vector<string> v;
 v.push_back( "tanu" ); v.push_back( "tanuku" ); v.push_back( "hello" );
 sort( v.begin(), v.end(), cmp );
 for_each( v.begin(), v.end(), dump );
 
}

C++ STL - Partition関数

STL algorithmのpartition関数は特定の要素をリスト中で仕分けできる便利な関数なので覚えておくとよいことが色々あるかも．以下の例はファイル名のリスト中jpegファイル名の要素とそうでない要素を分類する例．

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

static vector<string> JPEG_POSTFIX;

void init() {

 JPEG_POSTFIX.push_back(".jpg");
 JPEG_POSTFIX.push_back(".jpeg");

}

bool IsJpeg(const string& s) {
        // should use boost's to_lower, though!
 vector<string>::iterator iter;
 for(iter = JPEG_POSTFIX.begin();iter != JPEG_POSTFIX.end();iter++ ) {
  if(s.find(*iter) != string::npos)
   return true;
 }
 return false;

}

int main() {

 init();
 istringstream f("neko.jpg tako.jpeg ika.png rakko.gif fugu.jpg");
 vector<string> fileList;
 string s;
 while(getline(f,s,' ')) {
  fileList.push_back(s);
 }
 cout << "## before partitioning.." << is_partitioned( fileList.begin(),fileList.end(),IsJpeg ) << endl;
 for_each(fileList.begin(),fileList.end(),[](string& s){cout << s << " "; });
 partition(fileList.begin(),fileList.end(),IsJpeg);
 cout << endl << "## after partitioning.." << is_partitioned( fileList.begin(),fileList.end(),IsJpeg ) << endl;
 for_each(fileList.begin(),fileList.end(),[](string& s){cout << s << " "; });
 cout << endl;

 return 0;

}

Java - StrSubstitutor

Apache Commons langからまた一つ便利なクラスのご紹介をさせていただきたい．

StrSubstitutorクラスは名前の通り文字列中のキーワード変換を行う．キーワードのプレフィックス・ポストフィックスの変更並びに変換後の値中のキーワードに対しての変換もサポートしている優れものである．この車輪の再発明はしないのが賢明だろう．

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

import org.apache.commons.lang3.text.StrSubstitutor;
import org.junit.Test;
import static org.junit.Assert.assertThat;
import static org.hamcrest.CoreMatchers.*;

public class StrSubstTest {

 @Test
 public void testSubst() {
  
  final String TEST_STR = "${PATTERN} cat";
  final String EXPECTED_STR = "black cat";
  
  StrSubstitutor subst = new StrSubstitutor( prepareValueMap() );
  assertThat( subst.replace( TEST_STR ), is( EXPECTED_STR ) );
  
 }
 
 @Test
 public void testSubstWithPrefix() {
  
  final String TEST_STR = "<<PATTERN>> cat";
  final String EXPECTED_STR = "black cat";
  
  StrSubstitutor subst = new StrSubstitutor( prepareValueMap(), "<<", ">>" );
  assertThat( subst.replace( TEST_STR ), is( EXPECTED_STR ) );
  
 }
 
 @Test
 public void testSubstInVariable() {
  
  final String TEST_STR = "${PATTERN} cat";
  final String EXPECTED_STR = "calico(white,black,brown) cat";
  
  StrSubstitutor subst = new StrSubstitutor( prepareValueMap2() );
  subst.setEnableSubstitutionInVariables( true );
  assertThat( subst.replace( TEST_STR ), is( EXPECTED_STR ) );
  
 }
 
 private Map<String,String> prepareValueMap() {
  
  Map<String,String> map = new HashMap<String,String>();
  map.put( "PATTERN", "black" );
  map.put( "SIZE", "big" );
  return map;
  
 }
 
 private Map<String,String> prepareValueMap2() {
  
  Map<String,String> map = new HashMap<String,String>();
  map.put( "PATTERN", "calico(${COLORS})" );
  map.put( "COLORS", "white,black,brown" );
  return map;
  
 }

}

all of, any of, none of

リスト・配列要素検査の関数all_of,any_of,none_ofは是非覚えておくとよい．

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

bool chk(string s) {
 return s.size() > 5;
}

int main() {

 vector<string> v;
 v.push_back("Warsaw");
 v.push_back("NewYork");

 // all of
 cout << ( all_of(v.begin(),v.end(),chk) ? "[GOOD] all good" : "some failed or all failed" ) << endl;
 v.push_back("Tokyo");
 cout << ( all_of(v.begin(),v.end(),chk) ? "[GOOD] all good" : "some failed or all failed" ) << endl;

 v.clear();
 v.push_back("Rome");
 v.push_back("Nagoya");

 // any of
 cout << ( any_of(v.begin(),v.end(),chk) ? "[GOOD] some good" : "all failed" ) << endl;
 v.erase( find( v.begin(),v.end(),"Nagoya"));
 v.push_back("Osaka");
 cout << ( any_of(v.begin(),v.end(),chk) ? "[GOOD] some good" : "all failed" ) << endl;

 // none of
 cout << ( none_of(v.begin(),v.end(),chk) ? "[GOOD] all failed" : "not all failed" ) << endl;
 v.erase(find(v.begin(),v.end(),"Osaka"));
 v.push_back("Mangalore");
 cout << ( none_of(v.begin(),v.end(),chk) ? "[GOOD] all failed" : "not all failed" ) << endl;

 return 0;

}

C++でforeach

ForeachはJavaやPythonといった他の言語で多用されている反復処理用構文である．
C++ではSTLのalgorithmがそれを提供してくれている．是非使おう．

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

void show(const string s) {
 cout << s << ' ';
}

int main() {

 vector<string> v;
 v.push_back("Algonquin");
 v.push_back("Iroquois");

 for_each(v.begin(),v.end(),show);

 return 0;

}

lvalueとrvalue

C++のコンテクストでたまに見かける用語の一つがlvalueとrvalueである．
これを知らないと苦労することもあるかもしれないので是非覚えておいてほしい．

lvalue .. いわゆる変数・定数．２回以上使いまわされることもあるかもしれないデータである．
rvalue .. いわゆる代入される又は出現後即揮発するデータ．

int i = 100 * 3;

とあればiがlvalue, 100 * 3 がrvalueである．

インライン関数

Q. classの宣言中に関数を定義した場合，その関数はインライン扱いされるか？

A. yes

プチクイズ8 - コピーコンストラクタ

Q. 以下のコードのコンパイル＆実行結果は？

#include <cstdio>
#include <cstdlib>
#include <string>

class C {
private:
 int d;
public:
 C() { d = 5;};
 ~C() {};
 C(C m) { d = m.d; }
 virtual void a() { printf("aaa"); }
 int GetD() { return d; }
};

int main() {

 C m;
 C m2(m);
 
 printf("%d\n",m2.GetD());
}

A.
大抵のコンパイラではコンパイルできないはず．上記コピーコンストラクタは値渡しのパラメータが定義されているので，このコピーコンストラクタが呼ばれ，ランタイム上で値渡しのパラメータmを”コピー”しようとコピーコンストラクタを更に呼び...　と永遠に再帰呼び出しが発生する．
この問題を避けるには，const C&にパラメータの宣言を変更すればよい．

プチクイズ 7 - クラスのsizeof

Q1. 空のクラスに対してのsizeofの結果は？

A1. (visual studioでもgnu c++でも)1．実質データは０だがクラスの存在を示すためにダミーのデータ(size 1)が作られる．

Q2. コンストラクタとデストラクタを宣言した場合？

A2. 変わらず．ただしvirtualであればvtableを作るのでその分のサイズは増える．32bitマシン上なら4, 64bitマシン上なら8.

Q3. 関数を宣言すると？

A3. コンストラクタ・デストラクタに同じ．virtualであればvtable分の増加，さもなければ何も変わらず．

Q4. intの変数をクラスに追加すると？

A4. int型分のサイズが増加．

アルゴリズム問題を解く 13 - 回文

問題

Please implement a function that checks whether a positive number is a palindrome or not.
For example, 121 is a palindrome, but 123 is not. Please write an answer in C.
( Coding interviewsより抜粋 )

ヒント

山本山，とかたけやぶやけた，に共通するのは，文字列長が奇数であることである．この問題はマイナスでない整数であることも忘れずに．

答え1

先頭と最後尾，先頭+1と最後尾-1..を比較していけばよいのでO(N/2)の計算量でよい．
NULLの場合，負の場合等々といったチェックも忘れずに．

#include <cstdio>
#include <cstdlib>
#include <string>

int isdigits(const char* const s, int len) {

 int result = 1;
 for( int i = 0;i < len;i++ ) {
  if( !isdigit(s[i]) ) {
   result = 0;
   break;
  }
 }

 return result;

}

int ispalindrome(const char* const s, unsigned int len) {

 // prerequisite check
 if( s[0] == '-' ||
  !(len % 2) ||
  len == 1 ||
  s == NULL ||
  !isdigits(s,len))
  return 0;
  
 int result = 1;
 unsigned int half = len >> 1;
 for( unsigned int i = 0;i < half;i++ ) {
  if(s[i] != s[len-1-i]) {
   result = 0;
   break;
  }
 }
 return result;
}

int main() {

 char* s1 = "142";
 char* s2 = "5";
 char* s3 = "282";
 char* s4 = "2820";
 char* s5 = "-10";
 char* s6 = "ABA";
 printf("%d\n",ispalindrome(s1,strlen(s1)));
 printf("%d\n",ispalindrome(s2,strlen(s2)));
 printf("%d\n",ispalindrome(s3,strlen(s3)));
 printf("%d\n",ispalindrome(s4,strlen(s4)));
 printf("%d\n",ispalindrome(s5,strlen(s5)));
 printf("%d\n",ispalindrome(s6,strlen(s6)));

 char ch;
 scanf(&ch);
}

答え2

答え１よりはるかに優れたコードである．

#include <cstdio>
#include <cstdlib>
#include <string>

int ispalindrome(unsigned int n) {

 if( n <= 110 )
  return 0;

 unsigned int orig = n;
 unsigned int rev = 0;
 while( n != 0 ) {
  rev = rev * 10 + n % 10;
  n /= 10;
 }

 return (rev == orig) ? 1 : 0;

}

int main() {

 unsigned int s1 = 142;
 unsigned int s2 = 5;
 unsigned int s3 = 282;
 unsigned int s4 = 2820;
 unsigned int s5 = 111;

 printf("%d\n",ispalindrome(s1));
 printf("%d\n",ispalindrome(s2));
 printf("%d\n",ispalindrome(s3));
 printf("%d\n",ispalindrome(s4));
 printf("%d\n",ispalindrome(s5));

}

constの使い方

面接をしていて感じたのが，意外にconstの使い方をわかっていない又は誤って理解しているケースも多いということである．

constの正しい用法はcode as documentationとして重要なのでしっかり理解しておきたいところ．

int i = 500;
// 1. 
const int* pVal = &i;
// 2.
int* const pVal = &i;
// 3.
const int* const pVal = &i;

1はconst修飾子が適用されたint型，つまり定数intを指すポインタである．
ゆえにポインタを経由してpValの値を変更することはコンパイラが許可しないが，pVal自体別のconst int型を指し示すことはできる．

2はint型を示すconst修飾子が適用されたポインタ，言い換えるとそのポインタの持つ値，つまりはアドレスの変更が不可能なポインタである．ポインタ経由でiの値を変更することは認めるが，i意外の変数を指し示すことは許さない．

3は定数int型を示す定数ポインタである．ポインタ経由での値の変更も許されなければ，またポインタの指す値を変えることも出来ない．

マージ

２つのソート済み配列を一つの配列にマージし，ソートするコードは以下の通り．厳密にはマージソートと全く異なるので注意．

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

void dump(const vector<int> v) {

 vector<int>::const_iterator iter;
 for( iter = v.begin(); iter != v.end();iter++ )
  cout << *iter << ' ';
 cout << endl;

}

void merge(const vector<int>& arr1, const vector<int>& arr2, vector<int>& merged) {

 int i,j;
 i = j = 0;
 while( i < arr1.size() && j < arr2.size() ) {
  if( arr1.at(i) <= arr2.at(j) )
   merged.push_back( arr1.at(i++) );
  else
   merged.push_back( arr2.at(j++) );
 }
 while( i < arr1.size() )
  merged.push_back( arr1.at( i++ ) );
 while( j < arr2.size() )
  merged.push_back( arr2.at( j++ ) );

}

int main() {

 vector<int> v1;
 vector<int> v2;
 vector<int> merged;
 v1.push_back(3);
 v1.push_back(5);
 v1.push_back(7);
 v2.push_back(1);
 v2.push_back(2);
 v2.push_back(3);
 v2.push_back(7);
 v2.push_back(9);
 merge(v1,v2,merged);
 dump(merged);

}

マージソート

マージソートを書いてみてください，というのは私が面接官をするときに必ず聞いている質問の一つ．というわけでマージソートである．

最初からソートした２つの配列を１つにする答えをもらえれば，及第点ではあるが，以下のようにソートされていない１つの配列を文字通りソートするアルゴリズムの答えであれば，満点である
．

#include <iostream>
#include <array>
#include <cmath>
using namespace std;

#define ARRAY_SIZE 8

void init(array<int,ARRAY_SIZE>& a) {

 a[0] = 10; a[1] = 5; a[2] = 3; a[3] = 6;
 a[4] = 6; a[5] = 9; a[6] = 15; a[7] = 1;
}

void dump(array<int,ARRAY_SIZE>& a) {

 for( int i =0;i < a.size();i++ )
  cout << a.at(i) << ' ';
 cout << endl;
 
}

void mergesort(array<int,ARRAY_SIZE>& arr) {
 
 int divider = 2;
 int compartment;
 int t;
 while( divider <= ARRAY_SIZE ) {
  compartment = ARRAY_SIZE / divider;
  for( int i = 0;i < compartment;i++ ) {
   for( int j = i * divider;j < divider;j++ ) {
    for( int k = j + 1;k < divider;k++ ) {
     if( arr[j] > arr[k] ) {
      t = arr[j];
      arr[j] = arr[k];
      arr[k] = t;
     }
    }
   }
  }
  divider *= 2;
 }
}

int main() {
 array<int,ARRAY_SIZE> arr;
 init(arr);
 dump(arr);

 mergesort(arr);
 dump(arr);
}

実行結果は以下の通り

10 5 3 6 6 9 15 1
1 3 5 6 6 9 10 15

vectorのリサイズによるアドレスの変更？

SafeC++にはvectorに要素が多く積み込まれると，リサイズ(デフォルトサイズは恐らく１６)により，ベクタは他のメモリアドレス上にコピーを作りそこにデータをコピーする，とあった．それが本当であるならば，コンポジションクラス中のvector参照メンバ及びポインタメンバはリサイズが発生した場合，無効になるわけである．

本当だろうか？検証してみた．

以下のコードはvector参照メンバ v をクラスにセットして，vにデータを積み込む単純なコードである．データ積み込みの前と後で番地の値を取得し，かつsize()を呼んでいる．

結果はデータ積み込み前と後でアドレスは一緒，size()も無事動作した．
ちなみにg++は4.7.3, OSはFedora18. Visual Studioは2010, OSはWindows7 32bit．

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

class MyClass {
private:
 vector<int>& v;
public:
 MyClass(vector<int>& vParam) : v(vParam) {}
 const vector<int>& GetV() { return v;}
 
 void Init() {

  for(int i = 0;i < 10;i++ ) {
   v.push_back(i);
  }
 }
 
 void Expand() {

  for(int i = 0;i < 50000;i++ ) {
   v.push_back(i);
  }
 }
 
 int size() {
  return v.size();
 }

};

int main() {

 vector<int> v;
 v.resize(20);
 
 MyClass m(v);
 m.Init();
 cout << &(m.GetV()) << m.size() << endl;
 m.Expand();
 cout << &(m.GetV()) << m.size() << endl;

}

結果

0x22ac5430
0x22ac5450030

C/C++のタイマー

#include <iostream>
#include <ctime>
#include <unistd.h>
using namespace std;

int main() {

 clock_t st = clock();
 for( long l = 0;l < 100000000;l++ );
 clock_t end = clock();
 cout << st << ":" << end << endl;
 cout << "elapsed - " << (end - st) * 1000 / CLOCKS_PER_SEC << endl;
 return 0;

}

自作クラスの比較オペレータを効率的に定義する方法

以下のアイデアはSafe C++で紹介されている．

#include <iostream>
using namespace std;

class MyClass {
private:
 int price;
public:
 explicit MyClass(int priceParam) : price(priceParam) {}
 int CompareTo(const MyClass& a) const {
  if( price == a.price )
   return 0;
  else if( price < a.price )
   return -1;
  else
   return 1;
 }

#define CMP(Class) \
 bool operator < (const Class& that) const { return CompareTo(that) < 0; } \
 bool operator > (const Class& that) const { return CompareTo(that) > 0; } \
 bool operator == (const Class& that) const { return CompareTo(that) == 0; } \
 bool operator <= (const Class& that) const { return CompareTo(that) <= 0; } \
 bool operator >= (const Class& that) const { return CompareTo(that) >= 0; } \
 bool operator != (const Class& that) const { return CompareTo(that) != 0; }

 CMP(MyClass);


};

int main() {

 MyClass A(32),B(60),C(32);
 if( A == C )
  cout << "A == C" << endl;
 if( B > A )
  cout << "B > A." << endl;
 if( A < B )
  cout << "A < B." << endl;
 if( A != B )
  cout << "A != B." << endl;

}

gcc/g++でスレッドをスリープさせる

#include <pthread.h>
#include <unistd.h>
#include <cstdio>

void *run(void *p) {
 int t = *(static_cast<int*>(p));
 printf("sleeping %d seconds..\n",t);
 sleep(t); // unit is msec
 pthread_exit(NULL);
}

int main() {

 pthread_t th;
 void* th_result;
 int duration = 2;
 pthread_attr_t attr;
 pthread_attr_init(&attr);
 pthread_attr_setdetachstate(&attr,PTHREAD_CREATE_JOINABLE);
 pthread_create(&th,&attr,run,&duration);
 pthread_attr_destroy(&attr);
 pthread_join(th,&th_result);
 pthread_exit(NULL);

}

Pthread

Ptheadとmutexのサンプルコードを書いてみた．．

#include <iostream>
#include <sstream>
#include <pthread.h>
#include <cstdlib>
#include <unistd.h>
using namespace std;


class Account {
private:
 long _balance;
 pthread_mutex_t mutex;
public:
 explicit Account(long balance): _balance(balance) { pthread_mutex_init(&mutex,NULL); }
 virtual ~Account() { pthread_mutex_destroy(&mutex);}
 void Deposit(long val);
 long Withdraw(long val);
 friend ostream& operator << (ostream& os, const Account& acct);
};

inline ostream& operator << (ostream& os, const Account& acct) {
 os << acct._balance;
 return os;
}

typedef struct {
 Account* a;
 Account* b;
} Accts;

void Account::Deposit(long val) {

 pthread_mutex_lock(&mutex);
 _balance += val;
 pthread_mutex_unlock(&mutex);

}

long Account::Withdraw(long val) {

 pthread_mutex_lock(&mutex);
 _balance -= val;
 pthread_mutex_unlock(&mutex);
 return val;

}

void* PerformDrawer(void* param) {

 Accts* acct = static_cast<Accts*>(param);
 long l = 0;
 for( int i = 0;i < 50;i++ ) {
  cout << "[W" << i << "]:Draw money 300 from A and deposit the money into B.. " << endl;
  l = acct->a->Withdraw(300);
  acct->b->Deposit(l);
  cout << "current balances - A:" << *(acct->a) << ",B:" << *(acct->b) << endl;
  sleep(1);
 }
 
}

void* PerformDepositter(void* param) {

 Accts* acct = static_cast<Accts*>(param);
  for( int i = 0;i < 50;i++ ) {
  cout << "[D" << i << "]:Deposit money 500 into A.. " << endl;
  acct->a->Deposit(500);
  cout << "current balances - A:" << *(acct->a) << ",B:" << *(acct->b) << endl;
  sleep(1);
 }
}

void InitThreadAttr(pthread_attr_t* attr) {
 pthread_attr_init(attr);
 pthread_attr_setdetachstate(attr,PTHREAD_CREATE_JOINABLE);
}

int main() {

 pthread_t depositter;
 pthread_t withdrawer;
 void *status_depositter;
 void *status_withdrawer;
 
 Account A(4000);
 Account B(2000);
 Accts accts;
 accts.a = &A;
 accts.b = &B;
 pthread_attr_t attr;

 InitThreadAttr(&attr);
 
 pthread_create(&depositter, &attr,PerformDepositter,(void *)&accts);
 pthread_create(&withdrawer, &attr,PerformDrawer,(void *)&accts);
 pthread_attr_destroy(&attr);
 pthread_join(depositter, &status_depositter);
 pthread_join(withdrawer, &status_withdrawer);
 
 cout << "A:" << A << endl;
 cout << "B:" << B << endl;

 pthread_exit(NULL); 

}

実行結果は以下の通り
(途中略)

[D46]:Deposit money 500 into A..
current balances - A:13700,B:15800
[W46]:Draw money 300 from A and deposit the money into B..
current balances - A:13400,B:16100
[D47]:Deposit money 500 into A..
current balances - A:13900,B:16100
[W47]:Draw money 300 from A and deposit the money into B..
current balances - A:13600,B:16400
[D48]:Deposit money 500 into A..
current balances - A:14100,B:16400
[W48]:Draw money 300 from A and deposit the money into B..
current balances - A:13800,B:16700
[D49]:Deposit money 500 into A..
current balances - A:14300,B:16700
[W49]:Draw money 300 from A and deposit the money into B..
current balances - A:14000,B:17000
A:14000
B:17000

プチクイズ 6 - コンストラクタの例外

Q. 何故コンストラクタが例外を送出するのは良くないのか，理由を述べよ．

A. もしコンストラクタの処理最中で例外が送出された場合，デスクトラクタは呼ばれない．その結果メモリリークが発生する可能性がある．

ただし，safe C++ではスマートポインタを使って，更にデストラクタを空にしたならば，むしろコンストラクタから例外を投げることも悪くはないと述べている．

プチクイズ 4 - std::vectorの要素アクセス

Q. std::vectorのat()とオペレータ[]の違いを述べよ

A. オペレータ[]での要素アクセスのほうが早いがout_of_range例外を投げない．
一方at()はout_of_range例外を投げる．

C++ - 自作クラスをcoutに<<オペレータで出力

自作のクラスを cout に<<オペレータで出力できると色々便利である．

以下のコードでそれを実現できるが，コンパイラによっては以下のコードはコンパイル出来ない．例えばg++はOKだがvc++10ではコンパイルに失敗する．

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

class MyClass {
private:
 string name;
public:
 MyClass(const string s): name(s){}
 friend ostream& operator << (ostream& os, const MyClass& obj);

};

inline ostream& operator <<(ostream& os, const MyClass& obj) {
 os << obj.name;
 return os;
}

int main() {

 MyClass m("otter");
 cout << "Dump myclass -- " << m << endl;
 return 0;
}

UNIXコマンド One liner 5

過去に実行したg++を実行する ( !xxx ではなく．かなり意味なし )

touch temp;history|egrep -E '.*g\+\+ -o'|\
awk -e {'print $2,$3,$4,$5'}|tail -1 > ./temp;\
chmod 755 ./temp;./temp;rm ./temp

プチクイズ 3 - C++の列挙型

Q.

以下のC++コードのリファクタリングすべき点を述べよ．

enum { ELEM1, ELEM2 } ENUM_1;
enum { SUN, MON, TUE, WED, THU, FRI, SAT };

void ShowEnumVal(int e) {
    cout << e << endl;
}

A.

列挙体に関しての2つのDON'Tを直す必要がある．
１つはplain vanilla enumを使用している点，２つは関数がEnum型ではなくintを引数の型としている点である．
上記コードはコンパイルもランタイムも問題なく動くが，非常にリスクの大きいコードである．
なぜなら関数ShowEnumVal()は本来，オブジェクトとして全くことなる(として扱うべき)２つのEnumを受け入れてしまう点である．各enumはtypedefを用いてコンパイルに明示的に違う型のように扱ってもらうべきであり，関数ShowEnumVal()も，その関数が扱うべきenumオブジェクトだけを受け入れるべきである．
上記２点を修正したコードは以下の通り．

typedef enum { ELEM1, ELEM2 } ENUM_1;
typedef enum { SUN, MON, TUE, WED, THU, FRI, SAT } DAY_OF_WEEK;

void ShowEnum1Val( ENUM_1 e ) {

 cout << e << endl;

}

アルゴリズム問題を解く 12 - 最頻単語のリスト

問題

You are reading a sequence of strings separated by white
space from a very large stream. You are allowed to read the stream twice.
Devise an algorithm that uses only O(k) memory to identify all the words
that occur more than [n/k] times in the stream, where n is the length of the stream.
( Algorithms for interviewsより引用)

ヒント

今度は最頻出する複数の単語を調べる必要がある．しかも決められた O(k) メモリ しか利用できない．固定長のディクショナリがいいだろう．

解答

ヒントで述べたとおり，固定長のディクショナリを使う．固定長ゆえ，閾値 k 以上のエントリが入ってきた場合は最も少ない出現数のエントリをスイープする．
以下の解答は出現回数も表示するが，必ずしも正しい数字ではない．なぜなら，最終的に最頻となったエントリが計算中にスイープされている可能性があるからである．
もしO(k)メモリの縛りがなければ，スイープ無しにディクショナリを構築後，頻度の多い順にソート，上からm番目までを表示するといいだろう．ちなみに計算量はO(N)の定数時間である．

入力ファイル，入力ファイル読み込みのロジックは前回と同じ．
追加したコードは以下の通り．

void Sweep(map<string,int>* dict) {

 set<string> toRemove;

 map<string,int>::iterator iter;
 for( iter = dict->begin(); iter != dict->end();iter++ ) {
  iter->second--;
  if( !iter->second ) 
   toRemove.insert(iter->first);
 }
 set<string>::iterator sIter;
 for( sIter = toRemove.begin(); sIter != toRemove.end(); sIter++ ) {
  if( dict->find(*sIter) != dict->end() )
   dict->erase(*sIter);
 }

}

void GetPopularWords(const vector<string> v, map<string,int>* dict, int k) {

 cout << "GetPopularWords()" << endl;
 
 vector<string>::const_iterator iter;
 for( iter = v.begin(); iter != v.end();iter++ ) {
  
  if( dict->find(*iter) != dict->end() ) {
   if( dict->size() > k )
    Sweep( dict );
   else
    (*dict)[*iter] = (*dict)[*iter] + 1;
  }
  else
   (*dict)[*iter] = 1;
 }

}

アルゴリズム問題を解く 11 - 最頻単語の検索

問題

You are reading a sequence of words from a very long
stream. You know a priori that more than half the words are repetitions of
a single word W but the positions where W occurs are unknown. Design
an efficient algorithm that reads this stream only once and uses only a
constant amount of memory to identify W.
( algorithms for interview より引用)

ヒント

"A priori"を自分に有利なように解釈するのもテクニックのひとつ．

解答

ここではWの出現条件が以下を満たすものとする

• Wが最初から現れることもある
• Wがストリームスナップショットの半分以上を占める

以上の前提に基づくと，W最初からストリームスナップショットの最後まで50%以上の確率で現れることになるので，ストリームの最初からある任意の位置Mまでサンプリングを行えばほぼ確実にWを推定できる．以下のコードのAssumeMajority()はより正確性を求め，ストリームスナップショット全体をサンプリングする - O(N)．一方AssumeMajority2()は先頭から５番目の要素までサンプリングをする - O(5)．

#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

static const string FILE_PATH = "C:\\tmp\\data\\rec.txt";

void ReadFile(string& buf, string path) {

 ifstream fin(path.c_str());
 char ch;
 while( fin.good() ) {
  fin.get(ch);
  if( fin.good() )
   buf += ch;
 }
 cout << "Data loaded from " << FILE_PATH << endl;
 
}

void tokenize(vector<string>& v,const string str) {

 char *pch;
 pch = strtok(const_cast<char*>(str.c_str())," ");

 while( pch != NULL ) {
  
  v.push_back( pch );
  pch = strtok(NULL," ");

 }

}

string* AssumeMajority(const vector<string>& v) {

 cout << "@AssumeMajority()" << endl;
 int count = 0;
 vector<string>::const_iterator iter;
 string* cand = new string();
 for(iter = v.begin(); iter != v.end();iter++) {
  if( !count ) {
   *cand = *iter;
   cout << "current candidate is " << *cand << endl;
   count = 1;
  }
  else if( *iter == *cand )
   count++;
  else
   count--;
 }
 
 return cand;
 
}

string* AssumeMajority2(const vector<string> v) {

 cout << "@AssumeMajority2()" << endl;
 const int sampleMax = 5;
 int count = 0;
 string *cand = new string();
 for(int i = 0;i < sampleMax;i++ ) {
  if( !count ) {
   *cand = v[i];
   cout << "current candidate is " << *cand << endl;
   count = 1;
  }
  else if( v[i] == *cand )
   count++;
  else
   count--;
 }

 return cand;

}

void dump(const vector<string>& v) {

 vector<string>::const_iterator iter;
 for(iter = v.begin(); iter != v.end();iter++) {
  cout << *iter << " ";
 }
 cout << endl;

}

int main() { 

 string s;
 ReadFile(s,FILE_PATH);
 vector<string> v;
 tokenize(v,s);
 dump(v);
 string* pch = AssumeMajority(v);
 cout << "Majority would be .. " << *pch << endl;
 delete pch;
 pch = AssumeMajority2(v);
 cout << "Majority would be .. " << *pch << endl;
 delete pch;

 return 0;
}

入力ファイル 中身

202 200 200 200 404 200 200 200 200 200 404 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 404 200

アルゴリズム問題を解く 10 - ハッシュで検索

問題

Given an array A of integers, find an integer k that is not present in A.
Assume that the integers are 32-bit signed integers.
( Algorithms for Interviews より引用 )

ヒント

ハッシュの写像．

解答

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

static const int MAX = 100;

void InitList(vector<int>& v) {

 v.push_back(32);
 v.push_back(55);
 v.push_back(11);
 v.push_back(42);
 v.push_back(98);
 v.push_back(51);
 v.push_back(80);
 v.push_back(6);

}

void BucketSort(vector<int>& dest, const vector<int>& src) {

 dest.resize(MAX);
 for( int i = 0;i < MAX;i++ )
  dest[i] = false;
 for( vector<int>::const_iterator iter = src.begin();iter != src.end();iter++ ) {
  dest[*iter] = true;
 }
}

bool found(const vector<int> A, int k) {

 vector<int>::const_iterator iter;
 return A[k];
 
}

int main() {

 vector<int> v;
 vector<int> sorted;
 InitList(v);
 BucketSort(sorted,v);
 cout << found(sorted,42) << endl;
 cout << found(sorted,44) << endl;

 return 0;
}

プチクイズ2 - コンポジションクラスの初期化

Q

const修飾子のついたメンバ，参照指定のメンバ，オブジェクトメンバ．これらをJavaの方法と同様な初期化をコンストラクタ中で行うことはできるか？

A

出来ない．コンパイラからお叱りをうけるだけである．
以下のコードはコンパイルでも実行時でも問題ない．

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


class InnerObject { 
private:
 int id;
public:
 InnerObject(int paramId):id(paramId){ cout << "InnerObject init " << id << endl; }
 int GetId() { return id; }
};

class MyClass {
private:
 const char* str;
 int& r;
 InnerObject in;
public:
 MyClass(const char* paramStr, int& paramR, InnerObject paramIn ):
  str(paramStr),r(paramR),in(paramIn) {
   cout << "MyClass init " << endl;
  }
 void dump();
};

void MyClass::dump() {

 ostringstream os;
 os << "str:" << str << " ";
 os << "r:" << r << " ";
 os << "In's Id:" << in.GetId() << endl;
 cout << os.str().c_str() << endl;
 
}


int main() {

 InnerObject in(20);
 string s("neko");
 int r = 3;
 MyClass m("abc",r,in);
 m.dump();

 return 0;

}

Algorithm問題を解く 9 - 複数タグのマッチ判定

問題

You are building a social networking site where each user specifies a set of attributes. You would like to pair each user with another unpaired user that specifies exactly the same set of attributes. Specifically, you are given a sequence of users where each user has a unique key, say a 32-bit integer and a set of attributes specified as a set of strings. As soon as you read a user, you should pair it with another previously read user with identical attributes who is currently unpaired, if such a user exists. If the user cannot be paired, you should keep him in the unpaired set.

(Algorithms for interviewsより引用)

ヒント

文字列の一致でハッシュを使うのは，原則的にはご法度である．アナグラムのケースがあった場合プログラムは誤作動してしまう．

解答

#include <iostream>
#include <string>
#include <map>
#include <list>
#include <algorithm>
using namespace std;

class User {
private:
 int id;
 list<std::string> attrs;
 list<int> matchedIds;
 const std::string GetFullTag();
public:
 User() {}
 User(int paramId,list<std::string>& paramAttr) : id(paramId),attrs(paramAttr) {};
 virtual ~User() {};
 bool match(User& user);
};

const std::string User::GetFullTag() {

 string s = "";
 attrs.sort();
 list<std::string>::iterator iter;
 for(iter = attrs.begin();iter != attrs.end();iter++) {
  s.append( *iter );
 }
 return s;

}

bool User::match(User& user) {

 if( std::find(matchedIds.begin(), matchedIds.end(), user.id) == matchedIds.end() ) {
  
  if( GetFullTag() == user.GetFullTag() ) {
   matchedIds.push_back(user.id);
   return true;
  }
  else
   return false;

  return false;

 }
 else {
  // already matching
  cout << "already in your list!!" << endl;
  return true;
 }
 return true;
}

int main() {
 
 list<string> my;
 my.push_back("C++");
 my.push_back("Java");
 User s( 10, my );
 list<string> you;
 you.push_back("Java");
 you.push_back("C++");
 User u( 20, you );
 cout << "you and me - " << s.match( u ) << endl;
 list<string> t;
 t.push_back("C++");
 t.push_back("Java");
 User th( 30, t );
 cout << "someone and me - " << s.match( th ) << endl;
 list<string> b;
 b.push_back("Python");
 b.push_back("Java");
 User br( 40, b );
 cout << "brother and me - " << s.match( br ) << endl;

 return 0;
}

プチクイズ1 .. JavaのUnsigned型

プチクイズ1


Q.

Javaでの唯一のUnsignedの型は？

A.

char. Byteでさえもsignedである．Javaの設計者はunsignedなんて必要ないと言い切った．正直あったらあったで便利だし，なくても全くなんとかなっているのが個人的な実情である．

Algorithm問題を解く 8 - ハッシュ2

問題

You are required to write a method that takes two text documents: an anonymous letter L and text from a magazine M. Your method is to return true if L can be written using M and false otherwise.
(if a letter appears k times in L, it must appear at least k times in M. )
(Algorithm for interviewsより引用)

ヒント

マガジンMから部分文字列Lを取り出せという問いではないことに注意．

解答

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

class Dict {
private:
 map<char,int> mD;
 void AddOrIncrement(char ch);
public:
 Dict() {};
 bool Analyze(string l,string m);
};

void Dict::AddOrIncrement(char ch) {
 if( mD.find(ch) != mD.end() )
  mD[ch]++;
 else
  mD[ch] = 1;
}

bool Dict::Analyze(string l, string m) {

 mD.clear();

 for( unsigned int i = 0;i < m.size();i++ ) {
  AddOrIncrement(m.at(i));
 }
 for( unsigned int i = 0;i < l.size();i++ ) {
  mD[l.at(i)]--;
  if( mD[l.at(i)] < 0 )
   return false;
 }
 return true;

}


int main() {

 Dict d;
 cout << d.Analyze("wanco", "wanchan coco ni oide") << endl;
 cout << d.Analyze("nyanco", "wanchan coco ni oide") << endl;

 return 0;

}

Algorithm問題を解く 7 - Hashキーで検索

問題

Let A be a sorted array of integers and S a target integer.

Design an efficient algorithm for determining if there exist
a pair of indices i,j (not ncessarily distinct) such that A[i] + A[j] = S.
( Algorithms for interview より引用 )

ヒント

sorted array .. ２分探索？２分探索でも勿論解ける．しかしバイナリサーチより効率の良いアルゴリズムは？

解答1

適当にループで回してもO(N^2)で解を出すことはできるが，もう一工夫．
バイナリサーチで検索の範囲を狭めれば良くてO((N/2)^2)，悪くてO(N^2)となる．

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

void init_vector(vector<int>& v) {
 v.push_back( 5 );
 v.push_back( 8 );
 v.push_back( 12 );
 v.push_back( 20 );
 v.push_back( 33 );
 v.push_back( 45 );
 v.push_back( 53 );
 v.push_back( 64 );
 v.push_back( 80 );

}

int search_max(const vector<int>& v, int s) {

 int min = 0;
 int max = v.size() - 1;
 int mid;
 int midval;
 bool found = false;
 
 // pre .. if s is less than v[0], no way to find pair.
 if( s <= *(v.begin()) )
  throw "not qualify pre-requisite";
  

 while( min <= max ) {
  mid = (min + max) / 2;
  midval = v.at(mid);
  if( s == midval ) {
   found = true;
   break;
  }
  else if( s > midval) {
   min = mid + 1;
  }
  else {
   max = mid - 1;
  }
 }

 return found ? mid : max;
}

bool search(const vector<int>& v, int s) {
 
 int max;
 try {
  max = search_max(v,s);
  cout << "max for search:" << max << endl;
 }catch(const char* msg) {
  cerr << "errmsg:" << msg << endl;
  return false;
 }

 for( int i = 0;i < max;i++ ) {
  for( int j = i;j < max;j++ ) {
   if( v[i] + v[j] == s ) 
    return true;
  }
 }

 return false;

}

void dump(const vector<int>& v) {
 
 for( vector<int>::const_iterator iter = v.begin();iter != v.end();iter++ ) {
  cout << *iter << endl;
 }

}


int main()
{
 vector<int> v;
 init_vector(v);
 dump(v);
 try {
  cout << search(v,3) << endl;
 } catch( const char* err) {
  cerr << err << endl;
 }

 cout << search(v,55) << endl;
 cout << search(v,53) << endl;

 return 0;
}

解答2

プログラムは長くなった割に得たものは少ない．ならばアプローチを変えよう． 目的の数Sからループ中の要素v[i]を引いてcを得る．そのcがハッシュテーブルにあれば(O(1)オーダで検索可)，v[i]+v[j]=Sを満たすのである． プログラムは非常にすっきりするし，オーダもO(N)である．

bool search2(const vector<int>& v, int s ) {
 map<int,int> m;
 vector<int>::const_iterator iter;
 int c;
 int i;
 for(i = 0,iter = v.begin();iter != v.end();iter++,i++) {
  c = s - v[i];
  m[v[i]] = i;
  if( m.find( c ) != m.end() )
   return true;
 }
 return false;

}