Сортировка файла с 55К строк и разных столбцов - PullRequest
Новая
       40

Сортировка файла с 55К строк и разных столбцов

1 голос
/ 30 марта 2010

Я хочу найти программное решение с использованием C ++.

У меня есть 900 файлов размером 27 МБ каждый.(просто чтобы сообщить о чудовищности).

Каждый файл имеет 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 ]

2 голосов
/ 30 марта 2010

Я не уверен, почему ваш код падает, но рекурсия в этом случае только сделает код менее читабельным. Однако я сомневаюсь, что это переполнение стека, потому что вы не используете много стекового пространства при каждом вызове.

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

Теперь есть одна проблема. Это будет медленно, потому что stringToDouble и getWordsFromSentence вызываются несколько раз в одной и той же строке. Возможно, вы захотите сгенерировать отдельный вектор, в котором предварительно рассчитаны значения каждой строки, а затем CompareByStringValue просто использует этот вектор в качестве справочной таблицы.

Другой способ сделать это - вставить строки в std::multimap<double, std::string>. Просто вставьте записи как (value, str), а затем прочитайте их построчно. Это проще, но медленнее (хотя и имеет ту же сложность, что и Big-O).

РЕДАКТИРОВАТЬ: Исправлено неправильный код и получено из binary_function.

1 голос
/ 30 марта 2010

Вы можете попробовать метод, который не включает рекурсию. если ваша программа аварийно завершает работу с использованием функции Sort2D с большими значениями, то вы, вероятно, переполняете стек (опасность использования рекурсии с большим количеством вызовов функций) Попробуйте другой метод сортировки, возможно, используя цикл.

0 голосов
/ 30 марта 2010

sort2D происходит сбой, потому что вы продолжаете выделять массив строк для сортировки, а затем передаете его по значению, фактически используя O (2 * N ^ 2) памяти. Если вы действительно хотите сохранить рекурсивную функцию, просто передайте vn по ссылке и не беспокойтесь о vn2. И если вы не хотите изменять исходный vn, переместите тело sort2D в другую функцию (скажем, sort2Drecursive) и вызовите ее из sort2D.

Возможно, вы захотите еще раз взглянуть на sort2D в целом, поскольку вы выполняете O (N ^ 2) работу для чего-то, что должно занять O (N + N * log (N)).

0 голосов
/ 30 марта 2010

Проблема не в вашем коде, а в инструменте, который вы выбрали для работы. Это чисто проблема обработки текста, поэтому выберите инструмент, который хорош в этом. В этом случае в Unix лучшим инструментом для работы являются Bash и GNU coreutils. В 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
...