1

C++を使用したプログラムによる解決策を見つけたいです。

私はそれぞれ27MBのサイズの900個のファイルを持っています。（巨大さについて知らせるためだけに）。

各ファイルには55K行とさまざまな列があります。しかし、ヘッダーは列を示しています

行を列値の順序で並べ替えたいと思います。

私はこのためのソートアルゴリズムを作成しました（間違いなく私の初心者の試みです、あなたは言うかもしれません）。このアルゴリズムは少数の数値では機能しますが、それより大きい数値では失敗します。

これが同じコードです：メインコード内で使用するために定義した基本関数：

int getNumberOfColumns(const string& aline)
{
 int ncols=0;
 istringstream ss(aline);
 string s1;
 while(ss>>s1) ncols++;
 return ncols;
}

vector<string> getWordsFromSentence(const string& aline)
{
 vector<string>words;
 istringstream ss(aline);
 string tstr;
 while(ss>>tstr) words.push_back(tstr);
 return words;
}

bool findColumnName(vector<string> vs, const string& colName)
{
 vector<string>::iterator it = find(vs.begin(), vs.end(), colName);
 if ( it != vs.end()) 
 return true;
 else return false;
}

int getIndexForColumnName(vector<string> vs, const string& colName)
{
 if ( !findColumnName(vs,colName) ) return -1;
 else {
  vector<string>::iterator it = find(vs.begin(), vs.end(), colName);
 return it - vs.begin();
 }
}

////////// I like the Recurssive functions - I tried to create a recursive function
///here. This worked for small values , say 20 rows. But for 55K - core dumps
void sort2D(vector<string>vn, vector<string> &srt, int columnIndex)
{
  vector<double> pVals;
 for ( int i = 0; i < vn.size(); i++) {
  vector<string>meancols = getWordsFromSentence(vn[i]);
  pVals.push_back(stringToDouble(meancols[columnIndex]));
 }

        srt.push_back(vn[max_element(pVals.begin(), pVals.end())-pVals.begin()]);
        if (vn.size() > 1 ) {
        vn.erase(vn.begin()+(max_element(pVals.begin(), pVals.end())-pVals.begin()) );
        vector<string> vn2 = vn;
 //cout<<srt[srt.size() -1 ]<<endl;
        sort2D(vn2 , srt, columnIndex);
        }
}

今メインコード：

 for ( int i = 0; i < TissueNames.size() -1; i++)
 {
  for ( int j = i+1; j < TissueNames.size(); j++)
  {
   //string fname = path+"/gse7307_Female_rma"+TissueNames[i]+"_"+TissueNames[j]+".txt";
   //string fname2 = sortpath2+"/gse7307_Female_rma"+TissueNames[i]+"_"+TissueNames[j]+"Sorted.txt";
   string fname = path+"/gse7307_Male_rma"+TissueNames[i]+"_"+TissueNames[j]+".txt";
   string fname2 = sortpath2+"/gse7307_Male_rma"+TissueNames[i]+"_"+TissueNames[j]+"4Columns.txt";
   vector<string>AllLinesInFile;
   BioInputStream fin(fname);
   string aline;
   getline(fin,aline);
   replace (aline.begin(), aline.end(), '"',' ');
   string headerline = aline;
   vector<string> header = getWordsFromSentence(aline);

   int pindex = getIndexForColumnName(header,"p-raw");
   int xcindex = getIndexForColumnName(header,"xC");
   int xeindex = getIndexForColumnName(header,"xE");
   int prbindex = getIndexForColumnName(header,"X");

   string newheaderline = "X\txC\txE\tp-raw";
   BioOutputStream fsrt(fname2);
   fsrt<<newheaderline<<endl;

   int newpindex=3;
   while ( getline(fin, aline) ){

   replace (aline.begin(), aline.end(), '"',' ');
   istringstream ss2(aline);
   string tstr;
   ss2>>tstr;
   tstr = ss2.str().substr(tstr.length()+1);
   vector<string> words = getWordsFromSentence(tstr);
   string values = words[prbindex]+"\t"+words[xcindex]+"\t"+words[xeindex]+"\t"+words[pindex];
    AllLinesInFile.push_back(values);
   }

   vector<string>SortedLines; 
   sort2D(AllLinesInFile, SortedLines,newpindex);

   for ( int si = 0; si < SortedLines.size(); si++)
    fsrt<<SortedLines[si]<<endl;
   cout<<"["<<i<<","<<j<<"] = "<<SortedLines.size()<<endl;
  }
 }

誰かが私にこれを行うためのより良い方法を提案できますか？大きな値では失敗する理由。？

このクエリの主な対象関数はSort2D関数です。

時間と忍耐に感謝します。

プラサド。

4

4 に答える 4

2

コードがクラッシュする理由はわかりませんが、その場合の再帰はコードを読みにくくするだけです。ただし、各呼び出しでスタックスペースをあまり使用していないため、スタックオーバーフローではないかと思います。

C ++にはすでにありますがstd::sort、代わりにそれを使用してみませんか？あなたはこのようにそれを行うことができます：

// functor to compare 2 strings
class CompareStringByValue : public std::binary_function<string, string, bool>
{
public:
    CompareStringByValue(int columnIndex) : idx_(columnIndex) {}
    bool operator()(const string& s1, const string& s2) const
    {
        double val1 = stringToDouble(getWordsFromSentence(s1)[idx_]);
        double val2 = stringToDouble(getWordsFromSentence(s2)[idx_]);
        return val1 < val2;
    }
private:
    int idx_;
};

次に、行を並べ替えるには、

std::sort(vn.begin(), vn.end(), CompareByStringValue(columnIndex));

さて、1つの問題があります。とが同じ文字列で複数回呼び出されるためstringToDouble、これは遅くなります。getWordsFromSentence各文字列の値を事前に計算した個別のベクトルを生成し、CompareByStringValueそのベクトルをルックアップテーブルとして使用することをお勧めします。

これを行う別の方法は、文字列をに挿入することですstd::multimap<double, std::string>。エントリをとして挿入して(value, str)から、行ごとに読み取ります。これは単純ですが遅くなります（ただし、big-Oの複雑さは同じです）。

編集：いくつかの誤ったコードをクリーンアップし、から派生しましbinary_functionた。

于 2010-03-29T22:34:04.490 に答える
1

再帰を伴わない方法を試すことができます。大きな値を持つSort2D関数を使用してプログラムがクラッシュした場合は、おそらくスタックがオーバーフローしています（多数の関数呼び出しで再帰を使用する危険性があります）。おそらくループを使用して、別の並べ替え方法を試してください。

于 2010-03-29T22:24:12.687 に答える
0

問題は、ジョブに選択したツールよりもコードが少ないことです。これは純粋にテキスト処理の問題なので、それが得意なツールを選択してください。この場合、Unixでの作業に最適なツールは、BashとGNUcoreutilsです。Windowsでは、PowerShell、Python、またはRubyを使用できます。PythonとRubyは、Unixフレーバーのマシンでも動作しますが、ほぼすべてのUnixマシンにBashとcoreutilsがインストールされています。

$FILES処理するファイルのリストを空白で区切って保持します。Bashのコードは次のとおりです。

for FILE in $FILES; do
  echo "Processing file $FILE ..."
  tail --lines=+1 $FILE |sort >$FILE.tmp
  mv $FILE.tmp $FILE
done
于 2010-03-29T22:48:28.540 に答える
0

sort2Dソートする文字列の配列を割り当て続け、それを値で渡すためにクラッシュします。実際には、O（2 * N ^ 2）メモリを使用します。再帰関数を本当に保持したい場合はvn、参照を渡すだけで、を気にしないでvn2ください。また、元の関数を変更したくない場合はvn、の本体sort2Dを別の関数（たとえばsort2Drecursive）に移動し、から呼び出しますsort2D。

sort2DO（N + N * log（N））を取るべきものに対してO（N ^ 2）作業を行っているので、一般的にもう一度見てみるとよいでしょう。

于 2010-03-30T00:07:56.290 に答える