Databases
StackOverflow2013
Postsdbo
POHow to speed up external merge sort in Java
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow to speed up external merge sort in Java
    primarykey
    data
    text
    <p>I am writing code for the external merge sort. The idea is that the input files contain too many numbers to be stored in an array so you read some of it and put it into files to be stored. Here's my code. While it runs fast, it is not fast enough. I was wondering if you can think of any improvements I can make on the code. Note that at first, I sort every 1m integers together so I skip iterations of the merging algorithm.</p> <pre><code>import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.DataInputStream; import java.io.DataOutputStream; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.RandomAccessFile; import java.security.DigestInputStream; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; import java.util.Arrays; public class ExternalSort { public static void sort(String f1, String f2) throws Exception { RandomAccessFile raf1 = new RandomAccessFile(f1, "rw"); RandomAccessFile raf2 = new RandomAccessFile(f2, "rw"); int fileByteSize = (int) (raf1.length() / 4); int size = Math.min(1000000, fileByteSize); externalSort(f1, f2, size); boolean writeToOriginal = true; DataOutputStream dos; while (size &lt;= fileByteSize) { if (writeToOriginal) { raf1.seek(0); dos = new DataOutputStream(new BufferedOutputStream( new MyFileOutputStream(raf1.getFD()))); } else { raf2.seek(0); dos = new DataOutputStream(new BufferedOutputStream( new MyFileOutputStream(raf2.getFD()))); } for (int i = 0; i &lt; fileByteSize; i += 2 * size) { if (writeToOriginal) { dos = merge(f2, dos, i, size); } else { dos = merge(f1, dos, i, size); } } dos.flush(); writeToOriginal = !writeToOriginal; size *= 2; } if (writeToOriginal) { raf1.seek(0); raf2.seek(0); dos = new DataOutputStream(new BufferedOutputStream( new MyFileOutputStream(raf1.getFD()))); int i = 0; while (i &lt; raf2.length() / 4){ dos.writeInt(raf2.readInt()); i++; } dos.flush(); } } public static void externalSort(String f1, String f2, int size) throws Exception{ RandomAccessFile raf1 = new RandomAccessFile(f1, "rw"); RandomAccessFile raf2 = new RandomAccessFile(f2, "rw"); int fileByteSize = (int) (raf1.length() / 4); int[] array = new int[size]; DataInputStream dis = new DataInputStream(new BufferedInputStream( new MyFileInputStream(raf1.getFD()))); DataOutputStream dos = new DataOutputStream(new BufferedOutputStream( new MyFileOutputStream(raf2.getFD()))); int count = 0; while (count &lt; fileByteSize){ for (int k = 0; k &lt; size; ++k){ array[k] = dis.readInt(); } count += size; Arrays.sort(array); for (int k = 0; k &lt; size; ++k){ dos.writeInt(array[k]); } } dos.flush(); raf1.close(); raf2.close(); dis.close(); dos.close(); } public static DataOutputStream merge(String file, DataOutputStream dos, int start, int size) throws IOException { RandomAccessFile raf = new RandomAccessFile(file, "rw"); RandomAccessFile raf2 = new RandomAccessFile(file, "rw"); int fileByteSize = (int) (raf.length() / 4); raf.seek(4 * start); raf2.seek(4 *start); DataInputStream dis = new DataInputStream(new BufferedInputStream( new MyFileInputStream(raf.getFD()))); DataInputStream dis3 = new DataInputStream(new BufferedInputStream( new MyFileInputStream(raf2.getFD()))); int i = 0; int j = 0; int max = size * 2; int a = dis.readInt(); int b; if (start + size &lt; fileByteSize) { dis3.skip(4 * size); b = dis3.readInt(); } else { b = Integer.MAX_VALUE; j = size; } while (i + j &lt; max) { if (j == size || (a &lt;= b &amp;&amp; i != size)) { dos.writeInt(a); i++; if (start + i == fileByteSize) { i = size; } else if (i != size) { a = dis.readInt(); } } else { dos.writeInt(b); j++; if (start + size + j == fileByteSize) { j = size; } else if (j != size) { b = dis3.readInt(); } } } raf.close(); raf2.close(); return dos; } public static void main(String[] args) throws Exception { String f1 = args[0]; String f2 = args[1]; sort(f1, f2); } } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USmeriton
    1. USSuperString
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow to speed up external merge sort in Java
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow to speed up external merge sort in Java
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow to speed up external merge sort in Java
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhat kind of performance expectations do you have, and how many ints do you have in these files?
      singulars
      1. POHow to speed up external merge sort in Java
      1. USQwerky
 

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