Java 클래스를 작성하여 10 억 개의 정수를 정렬하십시오.

Question

Java 클래스를 작성하여 10 억 개의 정수를 정렬하는 방법 (한 번에 이들의 서브 세트 만 메모리에 저장할 수 있다고 가정).

정렬 작업을 수행했지만 질문은 어떻게 10 억 개의 값을 얻을 수 있습니까?

메모리에 일부를로드하려면 어떻게 정렬해야합니까?

소스 코드를 통해 도움을 받으실 수 있으면 감사하겠습니다.

미리 감사드립니다.

여기 내 마지막 코드입니다. 실행하면 안내 할 수 있습니다. 이 일을 가장 효율적인 방법은 임의의 값의 발생 수를 계산하는 것입니다 때문에

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<Integer> intList = new ArrayList<Integer>(); 
     int fileSize = 0 ; 

     while(scanner.hasNextInt()){ 
      intList.add(scanner.nextInt()); 
      ++fileSize; 
      if(fileSize>=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<Integer> readSortFile(String name, List<Integer> list) throws FileNotFoundException{ 

     Scanner scanner = new Scanner(new File(name)); 

     int bufferSize = 0; 
     while(scanner.hasNextInt()){ 
      ++bufferSize; 
      if(bufferSize>=MERGE_BUFFER_SIZE_PREVIOUS && bufferSize<=MERGE_BUFFER_SIZE_NEXT){ 
       list.add(scanner.nextInt()); 
      } 

      if(bufferSize>=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<Integer> comboList = new ArrayList<Integer>(); 
      boolean isDone = true; 
      PrintWriter outP = openWriter(BIG_FILE); 

      while(isDone){ 

      for(int i=0;i<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 >= 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 < RAWA_FILE_MAX_SIZE;i++){ 
       Integer value = randomGenerator.nextInt(RAWA_FILE_MAX_SIZE); 
        writeFile(value, out); 
      } 
      out.close(); 
    } 

} 

Answer 1

은 40 억 가능한 int 값이 있습니다. MappedByteBuffer 메모리를 사용할 수 있으므로 16GB의 메모리가 필요하지 않습니다. 모든 사건을 계산하면 자연히 순서대로 계산되므로 더 이상 정렬 할 필요가 없습니다. 시간 복잡도는 O (n * log n) 행 병합 정렬 또는 빠른 정렬 대신 O (n)입니다. -XX와 함께 실행할 때

---

import sun.nio.ch.DirectBuffer; 

import java.io.File; 
import java.io.IOException; 
import java.io.RandomAccessFile; 
import java.nio.MappedByteBuffer; 
import java.nio.channels.FileChannel; 

public class Sort10Billion { 
    public static void main(String... args) throws IOException { 
     Runtime runtime = Runtime.getRuntime(); 
     long used1 = runtime.totalMemory() - runtime.freeMemory(); 

     MassiveCounterStore mcs = new MassiveCounterStore(); 
     long start = System.nanoTime(); 
     long count = 10 * 1000 * 1000 * 1000L; 
     for (long i = count; i > 0; i--) 
      mcs.incrementIndex((int) (i/1019)); 
     mcs.iterator(new NumberCountFunction() { 
      @Override 
      public void counted(int n, long count) { 
//    System.out.println(n + ": " + count); 
      } 
     }); 
     long time = System.nanoTime() - start; 
     long used2 = runtime.totalMemory() - runtime.freeMemory(); 
     System.out.printf("Took %.1f seconds to sort %,d numbers, using %.3f MB%n", time/1e9, count, (used2-used1)/1e6); 
     mcs.close(); 
    } 
} 

interface NumberCountFunction { 
    public void counted(int n, long count); 
} 

class MassiveCounterStore { 
    public static final int PARTITION_BITS = 26; 
    static final int PARTITIONS = (1 << (34 - PARTITION_BITS)); // 32-bit * 4 bytes. 
    final MappedByteBuffer[] buffers = new MappedByteBuffer[PARTITIONS]; 
    final FileChannel channel; 
    int smallest = PARTITIONS; 
    int largest = 0; 

    public MassiveCounterStore() throws IOException { 
     File tmpStore = File.createTempFile("counter", "dat"); 
     tmpStore.deleteOnExit(); 

     channel = new RandomAccessFile(tmpStore, "rw").getChannel(); 
     for (int i = 0; i < PARTITIONS; i++) 
      buffers[i] = channel.map(FileChannel.MapMode.READ_WRITE, (long) i << PARTITION_BITS, 1 << PARTITION_BITS); 
    } 

    public void incrementIndex(int n) { 
     long l = (n + Integer.MIN_VALUE) & 0xFFFFFFFFL; 
     int partition = (int) (l >> (PARTITION_BITS - 2)); // 4 bytes each. 
     int index = (int) ((l << 2) & ((1 << PARTITION_BITS) - 1)); 
     MappedByteBuffer buffer = buffers[partition]; 
     int count = buffer.getInt(index); 
     buffer.putInt(index, count + 1); 
     if (smallest > partition) smallest = partition; 
     if (largest < partition) largest = partition; 
    } 

    public void iterator(NumberCountFunction nfc) { 
     int n = (smallest << (PARTITION_BITS -2)) + Integer.MIN_VALUE; 
     for (int p = smallest; p <= largest; p++) { 
      MappedByteBuffer buffer = buffers[p]; 
      for (int i = 0; i < 1 << PARTITION_BITS; i += 4) { 
       int count = buffer.getInt(i); 
       if (count != 0) 
        nfc.counted(n, count & 0xFFFFFFFFL); 
       n++; 
      } 
     } 
     assert n == Integer.MIN_VALUE; 
    } 

    public void close() { 
     try { 
      channel.close(); 
     } catch (IOException ignored) { 
     } 
     for (MappedByteBuffer buffer : buffers) { 
      ((DirectBuffer) buffer).cleaner().clean(); 
     } 
    } 
} 

지문이 : (당신에게보다 정확한 메모리 사용량을 제공합니다) -UseTLAB

Took 150.7 seconds to sort 10,000,000,000 numbers, using 0.202 MB 

나는 2백2킬로바이트를 사용하는 것은 꽤 좋은 생각합니다. ;)

참고 : 성능은 캐시의 효율성에 영향을주기 때문에 값 분포에 크게 의존합니다.