Databases
StackOverflow2013
Postsdbo
POWrite a Java class to sort 10 billion integers
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWrite a Java class to sort 10 billion integers
    primarykey
    data
    text
    <p>how to write a Java class to sort 10 billion integers, assuming we can only fit a subset of them in memory at once.</p> <p>I have done sorting but questions is how i would get the 1 billion values ?</p> <p>How I am gonna sort them if i am going to load a portion of them in memory ?</p> <p>If you can help me with source code it would be much appreciated.</p> <p>Thanks in advance.</p> <p>here is my last code, you can run it and guide me now.</p> <pre><code>import java.io.BufferedWriter; import java.io.File; import java.io.FileNotFoundException; import java.io.FileWriter; import java.io.IOException; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Random; import java.util.Scanner; /** * @project jqcontacts * @date Mar 26, 2012 * @time 11:16:35 AM */ public class SortIntegers { private static String BIG_FILE="g:/bigFile.txt"; private static String SORT_FILE_PREFIX = "g:/sortFile"; /*private static final int SORT_FILE_MAX_SIZE = 1000000;*/ private static final int SORT_FILE_MAX_SIZE = 10; private static final String MAIN_FILE = "g:/rawfile1.txt"; private static int RAWA_FILE_MAX_SIZE = 100; // if i keep the size of MERGE_BUFFER_INITIAL_SIZE = SORT_FILE_MAX_SIZE, the end big file is sorted. private static int MERGE_BUFFER_INITIAL_SIZE=5; private static int MERGE_BUFFER_SIZE_NEXT = MERGE_BUFFER_INITIAL_SIZE; private static int MERGE_BUFFER_SIZE_PREVIOUS = 0; private static int countFile = 0; public static void readFile(String name) throws FileNotFoundException{ Scanner scanner = new Scanner(new File(name)); List&lt;Integer&gt; intList = new ArrayList&lt;Integer&gt;(); int fileSize = 0 ; while(scanner.hasNextInt()){ intList.add(scanner.nextInt()); ++fileSize; if(fileSize&gt;=SORT_FILE_MAX_SIZE){ Collections.sort(intList); /*System.out.println("list size: " + intList.size());*/ String fileName = SORT_FILE_PREFIX + countFile +".txt"; ++fileSize; PrintWriter out = openWriter(fileName); for(int i:intList){ writeFile(i, out); } out.close(); intList.clear(); ++countFile; fileSize = 0; } } System.out.println("done!"); } public static List&lt;Integer&gt; readSortFile(String name, List&lt;Integer&gt; list) throws FileNotFoundException{ Scanner scanner = new Scanner(new File(name)); int bufferSize = 0; while(scanner.hasNextInt()){ ++bufferSize; if(bufferSize&gt;=MERGE_BUFFER_SIZE_PREVIOUS &amp;&amp; bufferSize&lt;=MERGE_BUFFER_SIZE_NEXT){ list.add(scanner.nextInt()); } if(bufferSize&gt;=MERGE_BUFFER_SIZE_NEXT){ break; } } Collections.sort(list); return list; } private static PrintWriter openWriter(String name) { try { File file = new File(name); PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(file)), true); return out; } catch (IOException e) { //System.out.println("I/O Error"); e.printStackTrace(); System.exit(0); } return null; } private static void writeFile(int i, PrintWriter out) { /* String line = "0" + "\t" + Integer.toString(i);*/ String line = Integer.toString(i) + "\t"; out.println(line); } /** * @param args */ public static void main(String[] args) { generateRawIntFile(); try { readFile(MAIN_FILE); } catch (FileNotFoundException e) { e.printStackTrace(); } System.out.println("countFile: " + countFile); // merge sort here, merge the sorted files into one List&lt;Integer&gt; comboList = new ArrayList&lt;Integer&gt;(); boolean isDone = true; PrintWriter outP = openWriter(BIG_FILE); while(isDone){ for(int i=0;i&lt;countFile;i++){ try { //TODO: do we need the return type for readSortFile ???? comboList = readSortFile(SORT_FILE_PREFIX+i+".txt", comboList); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } } // System.out.println("hun writing on big file " + comboList.size()); // add the list into bigfile and clear it for further processing try{ for(int value:comboList){ writeFile(value, outP); } comboList.clear(); MERGE_BUFFER_SIZE_PREVIOUS = MERGE_BUFFER_SIZE_NEXT; MERGE_BUFFER_SIZE_NEXT += MERGE_BUFFER_INITIAL_SIZE; System.out.println("MERGE_BUFFER_SIZE_PREVIOUS: " + MERGE_BUFFER_SIZE_PREVIOUS + " MERGE_BUFFER_SIZE_NEXT:" + MERGE_BUFFER_SIZE_NEXT); if(MERGE_BUFFER_SIZE_PREVIOUS &gt;= RAWA_FILE_MAX_SIZE){ System.out.println("sorting is finished"); isDone = false; break; } }catch (Exception e) { e.printStackTrace(); } } } /** * */ public static void generateRawIntFile() { Random randomGenerator = new Random(); PrintWriter out = openWriter(MAIN_FILE); for (Integer i = 0; i &lt; RAWA_FILE_MAX_SIZE;i++){ Integer value = randomGenerator.nextInt(RAWA_FILE_MAX_SIZE); writeFile(value, out); } out.close(); } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USuser1430003
    1. USuser1430003
    plurals
    1. PL
      singulars
      1. LTLinked
    2. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POWrite a Java class to sort 10 billion integers
      1. USChandra Sekhar
      1. VTFavorite
    2. VO
      singulars
      1. POWrite a Java class to sort 10 billion integers
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. POWrite a Java class to sort 10 billion integers
      1. This table or related slice is empty.
      1. VTDownMod
    1. COCommon interview question :) [One answer out of many out there](http://www.umbrant.com/blog/2011/external_sorting.html).
      singulars
      1. POWrite a Java class to sort 10 billion integers
      1. USRay Toal
    2. COand why use Java?
      singulars
      1. POWrite a Java class to sort 10 billion integers
      1. USdbrin
    3. COTry starting with sorting within your subset (trivial), then sort your subsets amongst your other subsets (not so trivial)
      singulars
      1. POWrite a Java class to sort 10 billion integers
      1. UShkf
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload