700ms未満で巨大なマトリックスを印刷するには？

Question

私はSPOJの問題を解決することができました。そのタイムラインは1秒です。しかし私のアルゴリズムは400ms未満で実行されますが、マトリックスを印刷するには約2秒かかります。これは700ms未満でこれを印刷することは可能ですか？

char matrix[30000][30]; 

Iは、行によって文字列の行としてのprintfで、私もenought高速なかったプットを試み、ループのための2つでそれをprintfのしようとしました。 また、putsで900000文字の配列を出力しようとしました。現在、最速の方法（1.6秒）です。

以下のコードは、私が配列（30000 * 30 = 900000）で書いた中で最も速いコードです。

#include <iostream> 
#include <ctime> 
#include<stdio.h> 

using namespace std; 

int main() 
{ 

    char array[900000]; 

    for(int i = 0; i < 900000; i++) 
     array[i] = '.'; 


    clock_t time_a = clock(); 
    puts(array); 
    clock_t time_b = clock(); 
    cout << endl; 
    cout << "Execution time of puts: " << (unsigned int)(time_b - time_a) << endl; 
    return 0; 
} 

Answer 1

SPOJはコンソール（std::cout）の出力を探しています。残念ながら、これはテストが実際には醜いものになります。なぜなら、出力には数秒かかり、グラフィックスカードの限界に向かってプログラムランタイムを歪ませ、共通コンソールは出力全体を保持することができず、 。

解決策1：出力をstd :: coutを使用してコンソールに出力しますが、オペレーティングシステムがコンソール出力をファイルにリダイレクト（AKAパイプ）します。これは、両方のウィンドウと私が演奏したほとんどすべての* nixの変形で、次の演算子で行われます。

program.exe > outputfile.txt 

>オペレータはリダイレクトを通知します。これを実証する

シンプルなハックテストコードは次のとおりです。

test > test.txt 

典型的な出力として実行

#include <iostream> //cout 
#include <chrono> // clock 
#include <cstring> //memset 

char courtMatrix[90000]; 

void printFile(char * matrix, 
       size_t len) 
{ 
    for (size_t i = 0; i < len - 1; i++) 
    { 
     std::cout << matrix[i] << "\n"; 
    } 
    std::cout << matrix[len - 1]; 
} 

int main() 
{ 
    // not using c-style standard IO, no sense paying for it. 
    std::cout.sync_with_stdio(false); 

    //initialize array contents 
    memset(courtMatrix, '.', sizeof(courtMatrix)); 

    //start timer 
    auto start = std::chrono::high_resolution_clock::now(); 
    //TODO generate output here 
    //print output 
    printFile(courtMatrix, sizeof(courtMatrix)); 
    // compute duration 
    auto dur = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - start); 

    //output execution time. Note cerr, not cout. Different data stream and 
    //won't pipe to file 
    std::cerr << "Execution time : " << dur.count() << std::endl; 
    return 0; 
} 

：1つのtest.txtのファイルと

実行時間：0

速報（size_t） size_tは、システム上で表現可能な最大のオブジェクトを索引付けするのに十分な大きさの符号なし整数です。つまり、構築可能な配列を処理するのに十分な大きさです。また、負の数をテストする必要がなくなり、負の数が大きな正の値にラップされ、上限のチェックによって捕捉されるため、そのようなことをする必要はありません。インデックスに便利です。

トピックに戻ると、上記のprintFileの出力はSPOJによって拒否されます。出力要件は2Dマトリックスを必要とし、これを逸脱するとおそらく失敗するからです。その場合：

void printFile(char * matrix, 
       size_t len, 
       size_t rowlength) 
{ 
    size_t rowleft = rowlength; 
    for (size_t i = 0; i < len; i++) 
    { 
     std::cout << matrix[i] << ' '; 
     rowleft--; 
     // test if we've printed an entire row 
     if (rowleft == 0) 
     { 
      // we have, so end the line and reset the counter 
      rowleft = rowlength; 
      std::cout << '\n'; 
     } 
     /* could use the more elegant-looking 

     if (i % rowlength) std::cout << '\n'; 

     but the % operator is often pretty expensive compared to -- 
     As always, test it and find out which suits your needs better. 
     */ 
    } 
} 

は、2次元配列を使用して恐れてはいけないと、ここでループのネストされました。最適化されたコンパイラがそれで実行されると、読みやすさが向上します。私が間違っていれば、プロファイリングのビットがかなり素早くあなたに伝えられます。

Answer 2

リキャップ、すでにコメントで指摘されているもの：

1. 変数arrayがnullで終了する必要があります - あなたがいるので、起こることができるループまたは悪い事のためで初期化後array[900000-1] = '\0';が必要std::putは、いつ他の時間を止めるべきかを知らない。
2. は本当にあなたが（SPOJ-裁判官は何をすべきかである）、コンソールまたはファイルに印刷するかどうかは大きな違いがあります：

コンソールに出力を印刷する（./programは）上で2秒かかり、私の出力がファイルにパイプされている場合は、わずか0.001秒です（./program > out.txt）。

Answer 3

出力をファイルにリダイレクトする方法はなく、何らかの形で出力ファイルの回答を確認するようにSPOJに指示します。

しかし、あなたにできる最適化がいくつかあります。たとえば、coutは、何かを標準出力に書き込む最速の方法ではありません。

この記事を見てみましょう：Yet again on C++ input/output

著者は、C++でのいくつかのI/O方法を説明し、比較は、競争力のあるプログラミングに適用されます。