C++ RSS C++ RSS

Help with a 5-way balanced sort merge

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Jan 2005
Posts: 31
Reputation: tat2dlady is an unknown quantity at this point 
Solved Threads: 0
tat2dlady tat2dlady is offline Offline
Light Poster

Help with a 5-way balanced sort merge

 
0
  #1
Mar 27th, 2005
I am doing a 5-way balanced sort merge. I have 1, 000, 000 records and a toal of 10 temp files to work with (5 for input and 5 for output). After phase 1, the temp files F0 thru F4 are populated with clumps of sorted records. The clump size is 1000. I am using an array of files to work with, instead of hard coding 10 temp files. My phase 2 is not working correctly. What I am trying to do is read 1 record from each of the 5 temp files and write the smallest one to the corresponding output file. I am having trouble with what controls the loop to do this phase as well. The total number of runs 5.

Here is the main part of my code:
C++ Syntax (Toggle Plain Text) 
  1.  int main()
  2. {
  3.    cout << '\n';
  4.   cout << "**********Phase 2 Started**********" << '\n';
  5.   cout << '\n';
  6.  
  7.   Merges = ceil ((NumOfColumns / NumOfFiles));
  8.   ClumpSize = ClumpSize * NumOfFiles;
  9.   F[Counter] >> Number1;
  10.  
  11.   F[Counter+1] >> Number2;
  12.  
  13.   F[Counter+2] >> Number3;
  14.  
  15.   F[Counter+3] >> Number4; 
  16.  
  17.   F[Counter+4] >> Number5;
  18.  
  19.   if (Counter == 5)
  20.   {
  21.      Counter = 0;
  22.   }
  23.  
  24. while (PassCount < NomOfPasses)
  25. {
  26.    for (i = 0; i < Merges; i++)
  27.    {
  28.       for (j = 0; j < NumOfFiles; j++)
  29.       {
  30.         for (k = 0; k < ClumpSize; k++)
  31.         {
  32.         if ((Number1 < Number2) && (Number1 < Number3) && (Number1 < Number4) && (Number1 < Number5))
  33.         {
  34.            X.WhichFile = 1;
  35.            X.Priority = -1;
  36.            X.Number = Number1;
  37.            P.Insert(X);
  38.            F[Counter] >> Number1;
  39.            if (F[Counter].eof())
  40.            {
  41.              break;
  42.            }
  43.         }
  44.         else if ((Number2 < Number1) && (Number2 < Number3) && (Number2 < Number4) && (Number2 < Number5))
  45.         {
  46.            X.WhichFile = 2;
  47.            X.Priority = -2;
  48.            X.Number = Number2;
  49.            P.Insert(X);
  50.            F[Counter+1] >> Number2;
  51.            if (F[Counter+1].eof())
  52.            {
  53.              break;
  54.            }
  55.          }
  56.          else if ((Number3 < Number1) && (Number3 < Number2) && (Number3 < Number4) && (Number3 < Number5))
  57.          {
  58.            X.WhichFile = 3;
  59.            X.Priority = -3;
  60.            X.Number = Number3;
  61.            P.Insert(X);
  62.            F[Counter+2] >> Number3;
  63.            if (F[Counter+2].eof())
  64.            {
  65.              break;
  66.            }
  67.          }
  68.          else if ((Number4 < Number1) && (Number4 < Number2) && (Number4 < Number3) && (Number4 < Number5))
  69.          {
  70.            X.WhichFile = 4;
  71.            X.Priority = -4;
  72.            X.Number = Number4;
  73.            P.Insert(X);
  74.            F[Counter+3] >> Number4;
  75.            if (F[Counter+3].eof())
  76.            {
  77.              break;
  78.            }
  79.          }
  80.          else if ((Number5 < Number1) && (Number5 < Number2) && (Number5 < Number3) && (Number5 < Number4))
  81.          {
  82.            X.WhichFile = 5;
  83.            X.Priority = -5;
  84.            X.Number = Number5;
  85.            P.Insert(X);
  86.            F[Counter+4] >> Number5;
  87.            if (F[Counter+4].eof())
  88.            {
  89.              break;
  90.            }
  91.          }
  92.          P.Remove(X);
  93.          F[OCounter] << setprecision(15) << X.Number << '\n'; 
  94.       }
  95.       // end for
  96.  
  97.       OCounter ++;
  98.  
  99.       if (OCounter == 10)
  100.       {
  101.         OCounter = 5;
  102.       }
  103.       // end if
  104.   }
  105.   // end for
  106.   NewNumOfFiles = OCounter - NumOfFiles;
  107.  
  108.   ClumpSize = ClumpSize * NewNumOfFiles;
  109.  
  110.   CloseTheFiles (F, FileName, InputFileName, InputFile);
  111.   if (OCounter == 5)
  112.   {
  113.     OpenTempFilesAsOutput(F, FileName);
  114.     OCounter = 0;
  115.     Counter = 5;
  116.   }
  117.   else if (OCounter == 0)
  118.   {
  119.     OpenTempFilesAsInput(F, FileName);
  120.     OCounter = 5;
  121.     Counter = 0;
  122.   }
  123.  
  124.   PassCount++;
  125.   cout << "Pass " << PassCount << " completed." << '\n';
  126.   }
  127.   // end while
  128.  
  129.   return 0;
  130. } // end function main
When I run it, I get all passes complete at the same time. It should tell me when one pass is complete. It should take 4 passes. Like it is, it leaves out some numbers. I get like 95,000 in 3 files but 90,000 in the other 2. This problem has just kicked my butt! Thanks for any input.

<< moderator edit: added [code][/code] tags >>
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api array based binary c++ c/c++ calculator char char* class classes code coding compile console conversion count database delete deploy desktop developer directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp iamthwee ifstream input int integer java lib linkedlist linker linux list loop looping loops map math matrix memory multiple news number numbertoword output parameter pointer problem program programming project python random read recursion recursive reference return rpg sorting string strings struct temperature template templates test text text-file tree unix url variable vector video visualstudio win32 windows winsock wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC