2017年6月
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30  
無料ブログはココログ

« 株:現物買い約定(NSD) | トップページ | 株:現物売り約定(トッパン・フォームズ、DMG森精機) »

2017年1月24日 (火)

C#で並列実行

codeIQの問題を解いていたのだけれど、入力数値が大きくなるとループ数が多くなり、その結果、実行時間1秒以内の制限を超えてしまったので、CPUリソースでぶん殴る方法=並列実行で対応してみようとしたいきさつ。

最終的に自分のノートPCでは、0.04秒程度まで縮められたのだが、codeIQの実行環境では並列実行がまともに効かないようで、やっぱり1秒を超えてしまいクリアとならなかった。
クリアできなかったとはいえ試行錯誤で早くなったので、回答期限が切れた今、C#の並行実行について書いてみる。

  • C# 平行実行で検索すると大体、async と await というキーワードが出てくる。
    これはGUIでボタン押下の処理でレスポンスが掛かるとき(Webサーバからの応答待ちが入るとか)、画面が固まるのを防ぐためのものの意味合いが強い模様。xxxAsync()という並列実行向けを呼ぶことで並列実行というかGUIに処理を戻して、バックグラウンドでレスポンス待ちをする。
    今回の処理では使えない。
  • 今回の処理のように、ループ数が多くなってしまうので1000回毎に分割して並行実行するというような使い方で用いる方法としてTaskを使う。
    ↓以下抜粋。些かこのコードが正しいかわからないけれど、まあ、動いている。

class CodeIQSample
{

    static void Main()
    {
        String line;
        MatchCollection mc;
        long[] val = new long[2];

        for (; (line = Console.ReadLine()) != null;)
        {
            mc = Regex.Matches(line, @"\d+");
            // 引数は2つ以外はNG
            if (mc.Count != 2)
            {
                continue;
            }
            int index = 0;
            foreach (System.Text.RegularExpressions.Match m in mc)
            {
                val[index] = long.Parse(m.Value);
                index++;
            }
            //int result;
            long lower = val[0];
            long upper = val[1];

            // 入力値が2つとも同値はNG
            if (lower == upper)
            {
                continue;
            }
            if (lower > upper)
            {
                lower = val[1];
                upper = val[0];
            }

            FindSumRange fsr = new FindSumRange();
            fsr.upper = upper;
            fsr.lower = lower;

            Task<int> result = fsr.calc();

            result.Wait();             System.Console.Write("{0}\n", result.Result);         }     } } class FindSumRange {     public long upper { get; set; }     public long lower { get; set; }     private long compval_;     public async Task calc()     {         int resultCount = 0;         var tasks = new List<int>();         for (long rangeLower = lower; upper > rangeLower; rangeLower += 1000)         {             long rangeUpper = (rangeLower + 1000 > upper) ? upper : rangeLower + 1000;             var task = new task(lower, upper, compval_, rangeLower, rangeUpper);             tasks.Add(Task.Run<int>(() => { return task.calc(); }));         }         var result = await Task.WhenAll(tasks);         foreach (Task<int> task in tasks)         {             resultCount += task.Result;         }         return resultCount;     } } class task {     public async Task calc()     {         int resultCount = 0;         ・・・時間のかかる処理・・・         return resultCount;     } }

上記のコードでは、taskクラスを生成して、そこからメソッドを呼んでいる。
大体のサンプルでは、FindSumRangeクラスのメソッドを呼ぶ形になっているが、引数に渡した値が書き換えられてしまって、実際には使い物にならなかった。(なのでクラスを生成するようにしたのだが) ←githubに置いてみた
重要な点は、以下の3か所

  • Task<int> result = fsr.calc();
    result.Wait();
  • tasks.Add(Task.Run<int>(() => { return task.calc(); }));
    ・・・
    var result = await Task.WhenAll(tasks);
    foreach (Task<int> task in tasks) { resultCount += task.Result; }
  • public async Task<int> calc()
    {
        int resultCount = 0;
        ・・・時間のかかる処理・・・
        return resultCount;
    }

calc()はint型戻り値を返したいので、Task<int>型の戻り値にする。呼び出し側では、result.Wait()で全スレッドの終了を待つ。結果はResultプロパティで取得できる。

呼び出され側のcalc()では、Task.Run<int>(()=>{return task.calc();}))で並行実行を起動し、その並行実行を管理するためにList<Task<int>>にリストに追加していく。ちなみにtask.calc()はint型を返したいので
すべて並行実行の起動ができたら、終了待ちとして、await Task.WhenAll(tasks)で待つ。(これいるのかな?)

時間が掛かる処理は、並列実行でint型を返したいので、async Task<int>という風に宣言している。

という感じ。

using System;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

delegate bool PreJudgement(long fixedIdx, long movableIdx);
delegate bool PostJudgement(long tmp);

class CodeIQSample
{

    static void Main()
    {
        String line;
        MatchCollection mc;
        long[] val = new long[2];

        System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();

        for (; (line = Console.ReadLine()) != null;)
        {
            mc = Regex.Matches(line, @"\d+");
            // 引数は2つ以外はNG
            if (mc.Count != 2)
            {
                continue;
            }
            int index = 0;
            foreach (System.Text.RegularExpressions.Match m in mc)
            {
                val[index] = long.Parse(m.Value);
                index++;
            }
            int result;
            long lower = val[0];
            long upper = val[1];

            // 入力値が2つとも同値はNG
            if (lower == upper)
            {
                continue;
            }
            if (lower > upper)
            {
                lower = val[1];
                upper = val[0];
            }

            FindSumRange_Single fsrs = new FindSumRange_Single();
            fsrs.upper = upper;
            fsrs.lower = lower;

            sw.Reset();
            sw.Start();
            result = fsrs.calc();
            sw.Stop();
            SC.WriteLine("time:{0}", sw.Elapsed);
            System.Console.Write("{0}\n", result);

            FindSumRange_Para fsrp = new FindSumRange_Para();
            fsrp.upper = upper;
            fsrp.lower = lower;

            sw.Reset();
            sw.Start();
            Task<int> result_p = fsrp.calc();

            sw.Stop();             result_p.Wait();             SC.WriteLine("time:{0}", sw.Elapsed);             System.Console.Write("{0}\n", result_p.Result);         }     } } class FindSumRange_Single {     private long[] ary = { 0, 1, 3, 6, 10, 15, 21, 28, 36, 45 };     public long upper { get; set; }     public long lower { get; set; }     private long compval_;     private void calcCompVal()     {         compval_ = RangeDigitSum.sum(upper) - RangeDigitSum.sum(lower - 1);         SC.WriteLine("comp={0}", compval_);     }     public int calc()     {         calcCompVal();         long fixedIdx;         long movableIdx;         int resultCount = 0;         long offset;         PreJudgement preJudge;         PostJudgement postJudge;         bool bResult;         for (fixedIdx = lower; upper > fixedIdx; fixedIdx++)         {             // 1. 上位(lowerから開始)を固定し、下位を動かして同一になるかを確認             //    確認し終わったら、上位を+1して次の値で確認             if (upper > fixedIdx)             {                 movableIdx = fixedIdx - (upper - lower);                 if (movableIdx < 0) { movableIdx = 1; }                 preJudge = (f, m) => { return f <= m; };                 long tmpCompVal = RangeDigitSum.sum(fixedIdx) - RangeDigitSum.sum(movableIdx);                 if (compval_ > tmpCompVal)                 {                     postJudge = n => { return compval_ < n; };                     offset = -1;                 }                 else                 {                     postJudge = n => { return compval_ > n; };                     offset = 1;                 }                 SC.WriteLine("01 compval_={0}, f:{1} m:{2} -> {3} offset={4}", compval_, fixedIdx, movableIdx, tmpCompVal, offset);                 bResult = RangeDigitSum.searchResult(fixedIdx, movableIdx, offset, compval_, preJudge, postJudge);                 if (bResult) { resultCount++; }             }             // 2. 下位(lower+1から開始)を固定し、上位を動かして同一になるかを確認             //    確認し終わったら、下位を+1して次の値で確認             if (fixedIdx >= lower + 1)             {                 movableIdx = fixedIdx + (upper - lower);                 preJudge = (f, m) => { return f >= m; };                 long tmpCompVal = RangeDigitSum.sum(movableIdx) - RangeDigitSum.sum(fixedIdx);                 if (compval_ > tmpCompVal)                 {                     postJudge = n => { return compval_ < n; };                     offset = 1;                 }                 else                 {                     postJudge = n => { return compval_ > n; };                     offset = -1;                 }                 SC.WriteLine("02 compval_={0}, f:{1} m:{2} -> {3} offset={4}", compval_, fixedIdx, movableIdx, tmpCompVal, offset);                 bResult = RangeDigitSum.searchResult(fixedIdx, movableIdx, offset, compval_, preJudge, postJudge);                 if (bResult) { resultCount++; }             }         }         return resultCount;     } } class FindSumRange_Para {     public long upper { get; set; }     public long lower { get; set; }     private long compval_;     private void calcCompVal()     {         compval_ = RangeDigitSum.sum(upper) - RangeDigitSum.sum(lower - 1);     }     public async Task calc()     {         int resultCount = 0;         calcCompVal();         var tasks = new List<Task<int>>();         for (long rangeLower = lower; upper > rangeLower; rangeLower += 1000)         {             long rangeUpper = (rangeLower + 1000 > upper) ? upper : rangeLower + 1000;             var task = new task(lower, upper, compval_, rangeLower, rangeUpper);             tasks.Add(Task.Run<int>(() => { return task.calc(); }));         }         var result = await Task.WhenAll(tasks);         foreach (Task<int> task in tasks)         {             resultCount += task.Result;         }         return resultCount;     } } class task {     public long upper { get; set; }     public long lower { get; set; }     public long compval { get; set; }     public long range_lower { get; set; }     public long range_upper { get; set; }     PreJudgement isFinished_pre { set { isFinished_pre = (PreJudgement)value.Clone(); } }     PostJudgement isFinished_post { set { isFinished_post = (PostJudgement)value.Clone(); } }     public task(long _lower, long _upper, long _compval, long _range_lower, long _range_upper)     {         upper = _upper;         lower = _lower;         compval = _compval;         range_lower = _range_lower;         range_upper = _range_upper;     }     public async Task<int> calc()     {         long fixedIdx;         long movableIdx;         int resultCount = 0;         long offset;         PreJudgement preJudge;         PostJudgement postJudge;         bool bResult;         for (fixedIdx = range_lower; range_upper > fixedIdx; fixedIdx++)         {             // 1. 上位(lowerから開始)を固定し、下位を動かして同一になるかを確認             //    確認し終わったら、上位を+1して次の値で確認             if (range_upper > fixedIdx)             {                 movableIdx = fixedIdx - (upper - lower);                 if (movableIdx < 0) { movableIdx = 1; }                 preJudge = (f, m) => { return f <= m; };                 long tmpCompVal = RangeDigitSum.sum(fixedIdx) - RangeDigitSum.sum(movableIdx);                 if (compval > tmpCompVal)                 {                     postJudge = n => { return compval < n; };                     offset = -1;                 }                 else                 {                     postJudge = n => { return compval > n; };                     offset = 1;                 }                 bResult = RangeDigitSum.searchResult(fixedIdx, movableIdx, offset, compval, preJudge, postJudge);                 if (bResult) { resultCount++; }             }             // 2. 下位(lower+1から開始)を固定し、上位を動かして同一になるかを確認             //    確認し終わったら、下位を+1して次の値で確認             if (fixedIdx >= range_lower + 1)             {                 movableIdx = fixedIdx + (upper - lower);                 preJudge = (f, m) => { return f >= m; };                 long tmpCompVal = RangeDigitSum.sum(movableIdx) - RangeDigitSum.sum(fixedIdx);                 if (compval > tmpCompVal)                 {                     postJudge = n => { return compval < n; };                     offset = 1;                 }                 else                 {                     postJudge = n => { return compval > n; };                     offset = -1;                 }                 bResult = RangeDigitSum.searchResult(fixedIdx, movableIdx, offset, compval, preJudge, postJudge);                 if (bResult) { resultCount++; }             }         }         return resultCount;     } } class RangeDigitSum {     // compvalに一致するv1,v2の範囲の値を求める。     public static bool searchResult(long fixedIdx, long movableIdx, long offset, long compval, PreJudgement isFinished_pre, PostJudgement isFinished_post)     {         bool isFind = false;         long nextMovableIdx = movableIdx;         // 終了条件1         if (nextMovableIdx < 0)         {             return false;         }         while (!isFind)         {             // 終了条件1             if (isFinished_pre(fixedIdx, nextMovableIdx) || (nextMovableIdx < 1 || nextMovableIdx > 4294967296L))             {                 SC.WriteLine("1-1 compval_={0}, f:{1} m:{2} offset={3}", compval, fixedIdx, nextMovableIdx, offset);                 // 範囲外になった                 isFind = false;                 break;             }             long tmp;             if (fixedIdx > nextMovableIdx)             {                 tmp = sum(fixedIdx) - sum(nextMovableIdx - 1);             }             else             {                 tmp = sum(nextMovableIdx) - sum(fixedIdx - 1);             }             // 終了条件2             if (isFinished_post(tmp))             {                 SC.WriteLine("1-2 compval_={0}, f:{1} m:{2} -> {3} offset={4}", compval, fixedIdx, nextMovableIdx, tmp, offset);                 // 見つからずに結果を超えた                 isFind = false;                 break;             }             //見つかったので終了             if (compval == tmp)             {                 SC.WriteLine("find compval_={0}, f:{1} m:{2} -> {3} offset={4}", compval, fixedIdx, nextMovableIdx, tmp, offset);                 isFind = true;             }             nextMovableIdx = nextMovableIdx + offset;         }         return isFind;     }     private static long[] ary = { 0, 1, 3, 6, 10, 15, 21, 28, 36, 45 };     private static long d(long index)     {         return ary[index];     }     public static long sum(long v)     {         long[] x = new long[10];         String val = v.ToString();         char[] c_val = val.ToCharArray();         if (c_val.Length > 10)         {             throw new System.ArgumentException("10 digit over.", "v");         }         int counter = 0;         foreach (char c in c_val)         {             x[c_val.Length - counter - 1] = long.Parse(c.ToString());             counter++;         }         return d(x[0])                 + (d(9) * x[1] + d(x[1]) * 10 - x[1] * (9 - x[0]))                 + (d(9) * (1 + 9 + 10) * x[2] + d(x[2]) * 100 - x[2] * (99 - x[1] * 10 - x[0]))                 + (d(9) * ((1 + 9 + 10) * 10 + 100) * x[3] + d(x[3]) * 1000 - x[3] * (999 - x[2] * 100 - x[1] * 10 - x[0]))                 + (d(9) * (((1 + 9 + 10) * 10 + 100) * 10 + 1000) * x[4] + d(x[4]) * 10000 - x[4] * (9999 - x[3] * 1000 - x[2] * 100 - x[1] * 10 - x[0]))                 + (d(9) * ((((1 + 9 + 10) * 10 + 100) * 10 + 1000) * 10 + 10000) * x[5] + d(x[5]) * 100000 - x[5] * (99999 - x[4] * 10000 - x[3] * 1000 - x[2] * 100 - x[1] * 10 - x[0]))                 + (d(9) * (((((1 + 9 + 10) * 10 + 100) * 10 + 1000) * 10 + 10000) * 10 + 100000) * x[6] + d(x[6]) * 1000000 - x[6] * (999999 - x[5] * 100000 - x[4] * 10000 - x[3] * 1000 - x[2] * 100 - x[1] * 10 - x[0]))                 + (d(9) * ((((((1 + 9 + 10) * 10 + 100) * 10 + 1000) * 10 + 10000) * 10 + 100000) * 10 + 1000000) * x[7] + d(x[7]) * 10000000 - x[7] * (9999999 - x[6] * 1000000 - x[5] * 100000 - x[4] * 10000 - x[3] * 1000 - x[2] * 100 - x[1] * 10 - x[0]))                 + (d(9) * (((((((1 + 9 + 10) * 10 + 100) * 10 + 1000) * 10 + 10000) * 10 + 100000) * 10 + 1000000) * 10 + 10000000) * x[8] + d(x[8]) * 100000000 - x[8] * (99999999 - x[7] * 10000000 - x[6] * 1000000 - x[5] * 100000 - x[4] * 10000 - x[3] * 1000 - x[2] * 100 - x[1] * 10 - x[0]))                 + (d(9) * ((((((((1 + 9 + 10) * 10 + 100) * 10 + 1000) * 10 + 10000) * 10 + 100000) * 10 + 1000000) * 10 + 10000000) * 10 + 100000000) * x[9] + d(x[9]) * 1000000000 - x[9] * (999999999 - x[8] * 100000000 - x[7] * 10000000 - x[6] * 1000000 - x[5] * 100000 - x[4] * 10000 - x[3] * 1000 - x[2] * 100 - x[1] * 10 - x[0]));     } } class SC {     static public void WriteLine(string format, params object[] arg)     { #if DEBUG         System.Console.WriteLine(format, arg); #else         return; #endif     } }

« 株:現物買い約定(NSD) | トップページ | 株:現物売り約定(トッパン・フォームズ、DMG森精機) »

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/117572/69363241

この記事へのトラックバック一覧です: C#で並列実行:

« 株:現物買い約定(NSD) | トップページ | 株:現物売り約定(トッパン・フォームズ、DMG森精機) »