ディーペスト問題の星間直行便のソーシャルグラフをarbor.jsで描いたよ

　先日CodeIQで結城 浩さんが出題していた星間飛行ルートを作ろう！に挑戦したのでその解答をポストします。あとついでに今回の問題で使われたデータをarbor.jsを使って可視化したのでそれも載せておきます。
　
　結果は満点の5点でした。わーい。

問題の概要

　今回の問題は、特定のポイントを経由し、目的地までたどり着くルートを算出するというものでした。ルートはWeb APIから1件ずつしか取得出来ない仕様となっており、また取得出来るデータはA->Bという一方向のルートとなります。解き方としては、startの星から行ける星のデータをWeb APIから取得して、その星から行ける星のデータを取得して…という操作を繰り返して特定のポイントを経由して目的地にたどり着く形となります。

利用言語、環境について

　今回は普段使ってない言語でやろう、という事でRubyを使いました。問題を解くのに必要なのはhttp通信周りや配列操作だけだったので特に問題なく解けました。

処理概要とソース

　処理としては指定した星から行ける直行便のリストを取得して、その中にゴールがあるまで読み込み続けるというものでした。Routeクラスを作り、各ルートをお互い繋げる事で、startから目的地までのルート情報を保持出来る様にしています。大体30分程度で書きました。
　

require 'net/http'

#start 5426528869786
#deep 4363616111476
#deeper 5092488161056
#deepest 8838746292440

class DirectFlightRoute
  @id
  @routes
  attr_accessor :id, :routes
end

class Route
  @prev
  @current
  def initialize

  end
  attr_accessor :prev, :current
end

class RouteResolver
  @@API_ROOT = "http://133.242.134.37"
  @@API_PATH = "/deepest.cgi?"
  @@ID = "id"
  @@NTH = "nth"

  @allRouteData
  attr_accessor :allRouteData
  def initialize
    @allRouteData = []
  end
  def getDirectFlight(id, nth)
    url = URI.parse(@@API_ROOT)
    req = Net::HTTP::Get.new(@@API_PATH + @@ID + "=" + id + "&" + @@NTH + "=" + nth.to_s)
    res = Net::HTTP.start(url.host, url.port) {|http|
      http.request(req)
    }
    if res.code.eql?("200")
      return res.body.chomp()
    end
    return "-3"
  end

  def getDirectFlightList(id)
    result = []
    nht = 0
    while true
      df = getDirectFlight(id, nht)
      puts "df:"+nht.to_s + ":" + df
      if "0".eql?(df)
        break
      end
      if !"-3".eql?(df)
        result.push(df)
        nht += 1
      else
        puts "error -3"
      end
      sleep 1
    end
    puts id+":"+result.to_s
    directFlightRoutes = DirectFlightRoute.new
    directFlightRoutes.id = id
    directFlightRoutes.routes = result
    @allRouteData.push(directFlightRoutes)
    return result
  end

  def isConflictRoute?(node, id)
    while node.prev != nil
      prev = node.prev
      if prev.current == id
        return true
      end
      node = prev
    end
    return false
  end

  def isAlready?(id)
    #答えのルートを得る場合は以下4行をコメントアウトする
    #@allRouteData.each{|route|
    #  if route.id.eql?(id)
    #    return true
    #  end
    #}
    return false;
  end

  def resolveRoute(start, goal)
    result = []
    candidates = []
    startRoute = Route.new
    startRoute.current = start
    candidates.push(startRoute)
    while !candidates.empty?
      candidate = candidates.pop()
      directFlightList = getDirectFlightList(candidate.current)
      directFlightList.each{|df|
        #ゴールに到達した?
        #※全ルートを得る場合はコメントアウト
        if goal.eql? df
          node = candidate
          result.unshift df
          result.unshift node.current
          while node.prev != nil
            n = node.prev
            result.unshift n.current
            node = n
          end
          return result
        end
        #既に登場したか?
        if !isConflictRoute?(candidate, df)
          if !isAlready?(df)
            newRoute = Route.new
            newRoute.current = df
            newRoute.prev = candidate
            candidates.push(newRoute)
          end
        end
      }
    end
    return result
  end

  def resolve(routes)
    result = ["dummy"]
    routes.each{|r|
      route = resolveRoute(r[0], r[1])
      result = result.slice(0, result.size-1).concat(route)
    }
    return result
  end
end

routeResolver = RouteResolver.new
results = routeResolver.resolve([["5426528869786", "4363616111476"],["4363616111476", "5092488161056"],["5092488161056","8838746292440"]])
puts "result-------------------------------"
puts results.to_s

得られた結果

　上記プログラムで以下のルートデータを取得する事が出来ました。想定された答えより大分ながーいルートです。手当たり次第で探索したので無駄なルートを沢山通っています。

["5426528869786", "2484466449149", "4326837688991", "6021351385219", 
"8814668496374", "1074912512567", "7560374248806", "8217940346560",
 "6159521237181", "6248392538888", "5792719602457", "7713050646130",
  "6493203887111", "3014332099928", "4363616111476", "2615115005762", 
  "3492704769369", "6101275938556", "5793542169547", "4217007177539", 
  "2970040126310", "6218636660558", "1563577571047", "8742972189444", 
  "8433634935614", "8564585174926", "6730551897632", "8279347398297", 
  "5813746423067", "3459654931377", "8244481309445", "8279056819547", 
  "8054128267676", "7401422935060", "5099100039591", "5471056644598", 
  "7892247098840", "8479078158931", "8986753372139", "6137149535463", 
  "7934869824134", "7782150475311", "4498551666547", "6023249450084", 
  "7014829010728", "7322686465928", "5702278445116", "2864141700776", 
  "8735695204612", "5174811483802", "5873652513502", "3536542280812", 
  "6178493999671", "8188288894326", "7797971735921", "3971331745645", 
  "5485131078541", "3876548341627", "1588698186896", "4656064657053", 
  "3065937285535", "3437245100188", "5833671447983", "6714942513619", 
  "7049674030681", "5813482662518", "2547413633555", "2966922227746", 
  "1843019516033", "5092488161056", "8250347815782", "4775196002726", 
  "8784346813978", "8636102321011", "8345370958267", "8787239992833", 
  "7230764147984", "8701256641199", "8682011082922", "8225271457185", 
  "8179247968273", "8573279739883", "8025149145454", "7840395069634", 
  "6925571750184", "7706339201843", "6159786607508", "8108466497204", 
  "6912947983983", "6870921135953", "6931349063153", "5848253839570", 
  "7170473222416", "8033311672835", "7194628242299", "6762287044283", 
  "8526665430645", "7116209295800", "7652884912454", "3101910152403", 
  "5985346038182", "8741714209435", "6199888663851", "4597865188910", 
  "5692390052367", "3545866022750", "6449164628142", "8978032168895", 
  "4946412662661", "3840068516051", "4205606644588", "5256084349572", 
  "6201473389311", "6146124596038", "3943178099168", "7758274483738", 
  "6085641567012", "5596295380961", "6707581077767", "5717371807428", 
  "6040500266078", "2109165486888", "5260999957124", "4491504900204", 
  "2223936654310", "3575202947166", "3070747769765", "2812280975542", 
  "4940548870566", "5576554716124", "2152647356070", "2994428026714", 
  "3031196364476", "5591596393385", "5865952095146", "8838746292440"]

直行便データを全て取得してソーシャルグラフを描く

　なんか適当にクロールしてたらゴールにたどり着いたので、折角だし星間の関係を可視化したいよなと思って、上のスクリプトを少しいじって全ての星の直行便データを取り出してグラフ書こうと考えたわけです。

arbor.jsでグラフを描く

　
　得られたデータは1162件ありました。このデータをarbor.jsにちょろっと食わせると良い感じにグラフ化してくれます。実際arbor.jsで動くものも見れます。 (※動作超重い可能性があるので注意して下しあ)
http://ec2-54-214-204-32.us-west-2.compute.amazonaws.com/codeiq_deepest/

仕掛けられた罠達

　グラフを見てみるとループする参照の仕方をする星達がごちゃっと塊になった領域がありますね。動く方を追いかけるとわかりますが、deepとdeeperの間にある"1814964223463"も袋小路になってドサッと発散してるのが分かります。
　

ループする星たち

相互参照する星に突き当たるとループしてしまう事になります。既に通った星に行くルートは除外する処理を入れる必要があります。

発散する星

例えば"1814964223463"とかいう星はnthをいくら大きくしても終端を表す"0"が返ってきません。グラフの方では花の様になっている星が発散する星です。他の星は大体10件程度しか直行便が無いので、取得数の制限をすれば回避する事が出来ます。
　
図を見た上で探索する方法を検討する分には割と簡単ですが、APIだけしか公開されていない状態だとなかなか気付けないかもしれないですね。

おわりに

　おもろかった。

シャフラーズ問題の回答 @sys1yagi編

　CodeIQで結城 浩さんが出題していた断片情報からデータを復元しよう！に挑戦したので解答をポストします。結果は満点でした。よかつた。今回はすごく簡単でした。30分程度で書き散らかしたのでソースは汚いです。
　

問題

　問題は以下の様なデータから、 aa = 10とかいった風にペアのデータを突き止めろ、というモノでした。てっきりデータ数が膨大だったりするのかと思ってたら1000件程度。サクーッといけました。

 10 22 24 = aa bb cc
 53 33 10 = dd ee aa
 24 33 53 = bb ee dd

　

解答ソース

　上記フォーマットのデータファイルを食わすと、ペアを解析してprintlnする感じのソースです。最初データを見たとき、「連立方程式っぽいな」と思ったんでそういう感じで解くようにしました。

 10 22 24 = aa bb cc
 53 33 10 = dd ee aa
 24 33 53 = bb ee dd

というデータがあった時、aaに着目すると、1行目ではaaの候補は10, 22, 24になります。
んで、2行目と比較すると53, 33, 10のうち10だけが1行目に存在してます。つー事でaa=10だ！という事。そんだけです。

 10 22 24 = aa
 53 33 10 = aa
 ↓重複する数字だけ取り出す
 10 = aa

　あとはデータを読み込んでkey,valueのリストを保持するShufflerクラスのリストを作って、名前の一覧を抽出し、名前に着目しながら1件ずつ特定していく感じ。特定された名前と数字はShufflerクラスにフィードバックして、Shuffler内でそれらの値をリストから削除する、という構造です。今見返すと実装大分汚いですが、大体そんな感じです。

package jp.dip.sys1.shufflers;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class Main {
    static class Shuffler {
        private List<String> mIdList = new ArrayList<String>();
        private List<String> mNameList = new ArrayList<String>();

        public Shuffler(String[] ids, String[] names) {
            for (String id : ids) {
                this.mIdList.add(id);
            }
            for (String name : names) {
                this.mNameList.add(name);
            }
        }

        public List<String> getIdList() {
            return mIdList;
        }

        public List<String> getNameList() {
            return mNameList;
        }

        public void found(String id, String name) {
            mIdList.remove(id);
            mNameList.remove(name);
        }
        public User getUser(){
            if(mIdList.size() == 1 && mNameList.size() == 1){
                User user = new User(mIdList.get(0), mNameList.get(0));
                found(mIdList.get(0), mNameList.get(0));
                return user;
            }
            return null;
        } 
        @Override
        public String toString() {
            if(mIdList.isEmpty() && mNameList.isEmpty()){
                return null;
            }
            StringBuilder sb = new StringBuilder();
            for (String id : mIdList) {
                sb.append(id + " ");
            }
            sb.append("= ");
            for (String name : mNameList) {
                sb.append(name + " ");
            }
            return sb.toString();
        }
    }

    static class ShufflerFactory {
        public static Shuffler createShuffler(String line) {
            if (line == null) {
                return null;
            }
            String[] pair = line.split(" = ");
            String[] ids = pair[0].split(" ");
            String[] names = pair[1].split(" ");
            Shuffler shuffler = new Shuffler(ids, names);

            return shuffler;
        }
    }

    static class User {
        private String mId;
        private String mName;

        public User(String id, String name) {
            mId = id;
            mName = name;
        }

        public String getId() {
            return mId;
        }

        public String getName() {
            return mName;
        }

        @Override
        public String toString() {
            return mId + " = " + mName;
        }
        @Override
        public int hashCode() {
            return toString().hashCode();
        }
        @Override
        public boolean equals(Object obj) {
            return this.hashCode() == obj.hashCode();
        }
    }

    static class Matcher {
        private String mTargetName = null;
        private List<String> mCandidateIds = new ArrayList<String>();
        private User mUser = null;

        public Matcher(String targetName) {
            mTargetName = targetName;
        }
        public boolean identify(Shuffler shuffler) {
            for (String name : shuffler.getNameList()) {
                if (mTargetName.equals(name)) {
                    if (mCandidateIds.isEmpty()) {
                        for (String id : shuffler.getIdList()) {
                            mCandidateIds.add(id);
                        }
                    } else {
                        List<String> newCandidateIds = new ArrayList<String>();
                        for (String id : shuffler.getIdList()) {
                            if(mCandidateIds.contains(id)){
                                newCandidateIds.add(id);
                            }
                        }
                        mCandidateIds = newCandidateIds;
                    }
                }
            }
            if(mCandidateIds.size() == 1){
                mUser = new User(mCandidateIds.get(0), mTargetName);
                return true;
            }
            else{
                return false;
            }
        }

        public User getUser() {
            return mUser;
        }
    }

    List<Shuffler> loadShufflers(String path) {
        List<Shuffler> list = new ArrayList<Main.Shuffler>();
        FileInputStream fis = null;
        InputStreamReader isr = null;
        BufferedReader br = null;
        try {
            fis = new FileInputStream(path);
            isr = new InputStreamReader(fis);
            br = new BufferedReader(isr);
            String line = null;
            while ((line = br.readLine()) != null) {
                Shuffler shuffler = ShufflerFactory.createShuffler(line);
                if (shuffler != null) {
                    list.add(shuffler);
                } else {
                    System.out.println("error.");
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                br.close();
                isr.close();
                fis.close();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        return list;
    }

    List<String> treatName(List<Shuffler> list) {
        List<String> names = new ArrayList<String>();
        for (Shuffler shuffler : list) {
            for (String name : shuffler.getNameList()) {
                if (!names.contains(name)) {
                    names.add(name);
                }
            }
        }
        System.out.println(names.size());
        return names;
    }

    public void matching(String path) {
        List<Shuffler> list = loadShufflers(path);
        List<User> users = new ArrayList<Main.User>();
        List<String> names = treatName(list);
        for (String name : names) {
            Matcher matcher = new Matcher(name);
            for (Shuffler shuffler : list) {
                if (matcher.identify(shuffler)) {
                    break;
                }
            }
            User user = matcher.getUser();
            if (user != null) {
                if(!users.contains(user)){
                    users.add(user);
                }
                for (Shuffler shuffler : list) {
                    shuffler.found(user.getId(), user.getName());
                }
            }
        }
        for(Shuffler shuffler : list){
            User user = shuffler.getUser();
            if(user != null){
                if(!users.contains(user)){
                    users.add(user);
                }
                for(Shuffler shuffler2 : list){
                    shuffler2.found(user.getId(), user.getName());
                }
            }
        }
        Collections.sort(users, new Comparator<User>() {
            @Override
            public int compare(User o1, User o2) {
                return Integer.parseInt(o1.getId()) - Integer.parseInt(o2.getId());
            }
        });
        for (User user : users) {
            System.out.println(user);
        }
        List<String> remains = new ArrayList<String>();
        for(Shuffler shuffler : list){
           String remain = shuffler.toString();
           if(remain != null){
               if(!remains.contains(remain)){
                   remains.add(remain);
               }
           }
        }
        for(String remain : remains){
            System.out.println(remain);
        }
    }
    public static void main(String[] args) {
        Main main = new Main();
        //main.matching("shufflers/sample.txt");
        main.matching("shufflers/shufflers.txt");
    }
}

ピッグデータ問題の解答 @sys1yagi編

　先日CodeIQで結城 浩さんが出題していた《ピッグデータ》に負けないで！ に挑戦したのでその解答をポストします。以下の内容はほぼ提出した解答そのままです。4/30の夜中に挑戦を開始して、翌日5/1の夕方辺りに解答を提出しました。
　
　結果は正解！「評価5 ベスト・ピッグデータ賞（結果が正しく技術メモも十分な解答）」だそうです。わーい。結城さんの解答も同じ考え方だったので二度わーい。

はじめに

　本書は、「ピッグデータ問題」のドキュメントである「problem.txt」、「pigdata.pdf」を読み、ピッグデータの仕様について理解している事を前提とした技術メモです。「ピッグデータ問題」の詳細については「《ピッグデータ》に負けないで！ https://codeiq.jp/ace/yuki_hiroshi/q303」を参照して下さい。

利用言語、環境について

　言語はjavaを利用する事にしました。標準ライブラリにSHA-1によるハッシュ計算を行う事が出来るMessageDigestクラスが存在する点と、マルチスレッド処理が容易な点、実行速度がスクリプト言語より優位と考えられる点から選択しました。
　実行の環境は以下の通りです。

OS: OS X 10.8.3(Mountain Lion)

CPU: 1.8 GHz Intel Core i7 (4コア)

メモリ: 4GB

java: 1.8.0-ea (1.6系、1.7系でも問題なく動作は可能のはず。たまたま入っていたのでそのまま利用した)

getsign(107374182400, 16777216)の答え

209679232

処理概要

　getdataでは、SHA-1によるハッシュ計算のインプットとなるqがindexを10で除算した値である事から、qが変化するまでハッシュ値を保存する事によってハッシュ値計算の回数が減少する様にしています。getsignではExecutorServiceを利用しマルチスレッドによって同時に計算処理をする構造になっています。getsignで必要な指定count数のピッグデータの取得とソートについては、65536(16bit)個のlong配列を使って、getdataで得られた値の個数をカウントする方式としました。この処理方式に至った経緯の詳細については"処理詳細と工夫について"を参照して下さい。

処理詳細と工夫について

オンメモリの処理ではメモリが足りない問題

　当初getsignでは、与えられたcountの個数だけgetdataを実行し、結果をArrayListに格納していました。count個の値が出揃った後ArrayListをソートし、skipsに従ってシグネチャを計算しました。getsign(100, 10)の場合は問題無く動作しましたが、count個のデータをArrayListに格納するので、getsign(107374182400, 16777216)では当然メモリが足りなくなります。この方法ではgetsign(107374182400, 16777216)は計算出来ない事が分かりました。

データを保存する場合2600GB必要になる

　オンメモリで大規模なgetdataの値を保持する事は困難である事から、外部記憶装　置にindexから得られるピッグデータを保存する事を考えました。後ほどソートが必要となる為、データは以下の様なリンクドリストの性質を持つ構造にしました。

index(64bit), ピッグデータ(16bit), 前のindex(64bit), 次のindex(64bit)

　1データ辺り64+16+64+64=208bit=26byteとなり、これを107374182400個保存する場合、107374182400*24=2600GBの外部記憶装置が必要となります。2600GB=2.6TBは今ではそこまで大きなサイズとは言えませんが、2.6TBの読み書きとなると膨大な時間がかかる事が予想されます。その他、リンクドリストという構造上skipsとkに従ったシグネチャ計算を行う場合全データにシーケンシャルにアクセスする必要があったり、データサイズの大きさから実行可能な環境に大きな制約を与える事になります。この方式も見送る事にしました。

ピッグデータが16bitである点に着目

　ピッグデータはpigdata.pdfの仕様から、符号なしの16bitの整数です。つまり0-65535の範囲の計65536種類という事になります。そこで、65536個の配列を作成し、getdataから返されたピッグデータを添字にして以下の様にgetdataから得られたピッグデータの取得回数を数え上げる事で省メモリ化出来ると考えました。

int[] counter = new int[65536];
int data = getdata(i);
counter[data]++;

　また、この方式によりgetdataで得た一連の値のsortが不要となります。counterにアクセスする為の添字はgetdataで得られるピッグデータで、その添字でアクセスするcounterの値はgetdataで得られたピッグデータの回数を表します。添字を0から65535まで数え上げながら個数を足し合わせる事でソート済みのgetdataの配列と同等の情報が得られます。以下に例を示します。

例:
得られた値

  20536 6446 24555 213 9583 33333 24555

counterの内部

 counter[213] = 1
 counter[6446] = 1
 counter[9583] = 1
 counter[20536] = 1
 counter[24555] = 2
 counter[33333] = 1

ソート済み配列として扱う

  213 6466 9583 20536 24555 24555 33333

　この構造により、シグネチャを計算する為のskipsとkがアクセスする添字の位置のピッグデータを取得する事が出来ます。上記の例のデータを用いると、k=4の場合はcounter内の値を足し合わせて4を越えた時の値(>4)である24555が得られる値となります。このデータ構造の場合、各ピッグデータの元のindexデータは消失します。しかしシグネチャ計算においてはソート済みのピッグデータだけが必要となるので問題ないと判断しました。

マルチスレッド化

　実行環境のPCはCPUのコアが4つあったので、getsignの計算をマルチスレッド化する事によって効率化を図りました。与えられた範囲のgetdataで得られた個数をカウントするCounterクラスを作成し、ExecutorServiceで任意の個数のスレッドを実行する様にしました。計算する値は1スレッド当たりcount/スレッド総数個とし、全てのスレッド計算が終わったあと、カウント用配列(65536個の配列)をマージする事でcount個のカウントデータが得られる様にしました。

SHA-1がボトルネックとなる

　getdataのソート情報は省メモリで得られる様になりましたが、107374182400回SHA-1のハッシュ計算をするのは大きな負荷です。処理時間の殆どがSHA-1のハッシュ計算に使われてるので、この部分を最適化する事で高速化を図れると考えられます。処理概要にも記述した通り、getdataではSHA-1によるハッシュ計算のインプットとなるqがindexを10で除算した値である事から、index〜index+9の範囲でqは同じになります。そこでqが変化するまでハッシュ値を一時的に保存する事によってハッシュ値計算の回数を減らす様にしました。これによりSHA-1のハッシュ計算の回数が1/10となりました。前述した実行環境においては従来10時間の実行時間だったものが1時間まで短縮する事が出来ました。

ソース

package jp.dip.sys1.pigdata;

import java.security.MessageDigest;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Main {
    public final static int SIZE_OF_16 = 65536;
    public static int THREAD_COUNT = 1;
    static class Count {
        long[] mCount = new long[SIZE_OF_16];

        public long[] getCount() {
            return mCount;
        }

        public void merge(long[] src) {
            for (int i = 0; i < src.length; i++) {
                mCount[i] += src[i];
            }
        }
    }

    static class Counter implements Callable<Count> {
        protected long mBegin;
        protected long mEnd;
        protected byte[] mDigest;
        protected long mPrevQ;
        protected MessageDigest mMessageDigest;

        public Counter(long begin, long end) {
            try {
                mBegin = begin;
                mEnd = end;
                mPrevQ = -1;
                mMessageDigest = MessageDigest.getInstance("SHA-1");
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

        private byte[] toSHA1(String source) {
            mMessageDigest.update(source.getBytes());
            return mMessageDigest.digest();
        }

        public int getdata(long index) {
            long q = index / 10;
            long r = index % 10;
            if (mPrevQ != q) {
                mDigest = toSHA1(String.valueOf(q));
            }
            mPrevQ = q;
            int upper16 = (0xff & mDigest[(int) r * 2]) << 8;
            int lower16 = 0xff & mDigest[(int) r * 2 + 1];
            return upper16 + lower16;
        }

        @Override
        public Count call() throws Exception {
            Count count = new Count();
            long[] countData = count.getCount();
            for (long i = this.mBegin; i < this.mEnd; i++) {
                int data = getdata(i);
                countData[data]++;
            }
            return count;
        }
    }

    public static long getsign(final long count, final long skips) {
        if (count < 1 || skips < 1) {
            return -1;
        }
        int threadCount = THREAD_COUNT;
        ExecutorService executor = Executors.newFixedThreadPool(threadCount);
        List<Future<Count>> futures = new ArrayList<Future<Count>>();
        for (int i = 0; i < threadCount; i++) {
            long begin = (count / threadCount) * i;
            long end = (count / threadCount) * (i + 1);
            if (i + 1 >= threadCount) {
                end += count % threadCount;
            }
            futures.add(executor.submit(new Counter(begin, end)));
        }
        Count resultCount = new Count();
        for (Future<Count> future : futures) {
            try {
                Count c = future.get();
                resultCount.merge(c.getCount());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        long[] countData = resultCount.getCount();
        long result = 0;
        for (long k = 0; k < count; k += skips) {
            long index = 0;
            for (int l = 0; l < SIZE_OF_16; l++) {
                index += countData[l];
                if (index > k) {
                    result += l;
                    break;
                }
            }
        }
        executor.shutdownNow();
        return result;
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(getsign(107374182400L, 16777216L));
        System.out.println(System.currentTimeMillis() - start + "ms");
    }
}

おわりに

　おもろかった。