Java

Question

büyük bir dosya sıralama ben bir satırda oluşan bir dosya vardır:

1 , 1 2 , 1 3 6 , 4 ,... 

Bu gösterimde, boşluk tamsayılar ve virgül ayırın. Bu dize ben RandomAccessFile.readLine ile okuyamaz o kadar büyüktür ki() (neredeyse 4 Gb tabi). Böylece 10 tamsayı içeren bir arabellek yarattım. Görevim dizedeki tüm tam sayıları sıralamak. Eğer,

yardım eder misiniz?

DÜZENLEME

@Oscar Reyes

Ben bir dosyaya tamsayılar bazı dizileri yazmaya gerek ve sonra ondan okumak için. Aslında bilmiyorum, nasıl yapılacağını. Ben yeni biriyim. Bu yüzden tamsayı yazmak için chars kullanmaya karar verdim, tamsayılar arasındaki sınırlayıcılar "," ve diziler arasındaki sınırlayıcılar "\ n \ r" dir. bunu yapmak için nasıl tavsiyelerde olsaydı

public BinaryRow getFilledBuffer(String filePath, long offset) throws IOException{ 
    mainFile = new RandomAccessFile(filePath, "r"); 

    if (mainFile.length() == 0){ 
     return new BinaryRow(); 
    } 

    StringBuilder str = new StringBuilder(); 

    mainFile.seek(mainFile.length()-4); //that is "\n" symbol 
    char chN = mainFile.readChar(); 

    mainFile.seek(offset); 
    int i = 0; 
    char nextChar = mainFile.readChar(); 
    while (i < 11 && nextChar != chN){ 
     str.append(nextChar); 
     if (nextChar == ','){ 
      i++; 
      if (i == 10){ 
       break; 
      } 
     } 
     nextChar = mainFile.readChar(); 
    } 

    if (nextChar == chN){ 
     position = -1; 
    }else{ 
     position = mainFile.getFilePointer(); 
    } 

    BinaryRow br = new BinaryRow(); 

    StringBuilder temp = new StringBuilder(); 

    for (int j = 0; j < str.length(); j++){ 
     if ((str.charAt(j) != ',')){ 
      temp.append(str.charAt(j)); 
      if (j == str.length() - 1){ 
       br.add(Integer.parseInt(temp.toString())); 
      } 
     }else{ 
      br.add(Integer.parseInt(temp.toString())); 
      temp.delete(0, temp.length()); 
     } 
    } 


    mainFile.close(); 
    return br; 

} 

, bunu lütfen =)

Answer 1

100 MB her (parçalar halinde belleğe Oku), bir öbek:? Böylece ben okuyan bir canavar yarattım Bir seferde sıralayın ve diske kaydedin.

Ardından tüm sipariş edilen parçalar açmak her birinin birinci elemanını okumak ve çıkışa düşük ekleyin. Daha sonra okuduğunuz ve tekrarladığınız yığının bir sonraki öğesini okuyun.

her yığın son int okuma dizisi tutmak ve onu en düşük almak için üzerinde sadece yineleme yapabilirsiniz birleştirilmesi. Sonra, daha önce kullandığınız değeri, alınan öbekte bir sonraki öğe ile değiştirirsiniz.

Bu tam kökenli QuickSort olan

example with chunks [1, 5, 16] [2, 9, 14] [3, 8, 10] 
array [(1), 2, 3], lowest 1 --> to output 
     [5, (2), 3], lowest 2 --> to output 
     [5, 9, (3)], lowest 3 --> 
     [(5), 9, 8],  5 
     [16, 9, (8)],  8 
     [16, (9), 10],  9 
... 

Answer 2

geri sonra prosedür disk kısmi sonuçlar depolamak için bellekte sıralamak için yeterli RAM değildi.

Peki ne yapabilirsiniz geçerli:

1. bir pivot seçin.
2. temp_file_2 için
3. tekrarlayın prosedürü result_file ve eklemek için temp_file_2
4. tekrar edin temp_file_1 da pivot büyük veya eşit verilerde eksen daha temp_file_1 içinde prosedürü sırayla dosya ve verileri depolar alt Oku ve sonucu eklenecek parçalar kadar küçük olan

result_file için sonuç

sen sıralamak mümkün olacak Bu şekilde ( 2 gibi sadece doğrudan takas onları yeter bellekte sıralanmasını) kısmi sonuçları geçici dosyalarda toplar ve saklar ve sonuçta sıralanan son bir dosya olur.

DÜZENLEME Ben hızlı sıralama mümkün olduğunu söylemiştim. Eğer sonuçta geçici dosyalar için bazı ekstra alan gerekir gibi

görünüyor.

İşte yaptığım şey.

Numaraları virgülle ayırarak 40 mb bir dosya oluşturuyorum.

ben o input isim:

input http://img200.imageshack.us/img200/5129/capturadepantalla201003t.png

_{Girdi, değerler yaratılmıştır "daha düşük" tür sırasında 40mb}

, "büyüktür" kova ile tmp dosyaları ve sıralama bittiğinde, değerler (tahmin etmek için) output

processing http://img200.imageshack.us/img200/1672/capturadepantalla201003y.png

_{Temp dosyaları}

Son olarak tüm tmp dosyaları silinir kısmi sonuçlar ile oluşturulur ve sonuç numaralarının doğru sıralanmış dizisi ile dosya "çıktı" tutulur:

output http://img203.imageshack.us/img203/5950/capturadepantalla201003w.png

_{Son olarak dosya "çıkış" oluşturulur, İşte tam progr var 40 çok mb}

olduğunu fark duyuyorum. n u m b e r , n u m b , b e r

az önce hepsini okumak ve boşlukları atlamak zorunda düzeltmek için:

import java.io.*; 
import java.util.*; 

public class FileQuickSort { 

    static final int MAX_SIZE = 1024*1024*16; // 16 megabytes in this sample, the more memory your program has, less disk writing will be used. 
    public static void main(String [] args) throws IOException { 
     fileQuickSort(new File("input"), new File("output")); 
     System.out.println(); 
    } 

    // 
    static void fileQuickSort(File inputFile, File outputFile) throws IOException { 
     Scanner scanner = new Scanner(new BufferedInputStream(new FileInputStream(inputFile), MAX_SIZE)); 
     scanner.useDelimiter(","); 

     if(inputFile.length() > MAX_SIZE && scanner.hasNextInt()) { 
      System.out.print("-"); 

      // put them in two buckets... 
      File lowerFile = File.createTempFile("quicksort-","-lower.tmp",new File(".")); 
      File greaterFile = File.createTempFile("quicksort-","-greater.tmp", new File(".")); 
      PrintStream lower = createPrintStream(lowerFile); 
      PrintStream greater = createPrintStream(greaterFile); 
      PrintStream target = null; 
      int pivot = scanner.nextInt(); 

      // Read the file and put the values greater than in a file 
      // and the values lower than in other 
      while(scanner.hasNextInt()){ 
       int current = scanner.nextInt(); 

       if(current < pivot){ 
        target = lower; 
       } else { 
        target = greater; 
       } 
       target.printf("%d,",current); 
      } 
      // avoid dropping the pivot 
      greater.printf("%d,",pivot); 
      // close the stream before reading them again 
      scanner.close(); 
      lower.close(); 
      greater.close(); 
      // sort each part 
      fileQuickSort(lowerFile , outputFile); 
      lowerFile.delete(); 
      fileQuickSort(greaterFile , outputFile); 
      greaterFile.delete(); 

      // And you're done. 
     } else { 

      // Else , if you have enough RAM to process it 
      // 
      System.out.print("."); 
      List<Integer> smallFileIntegers = new ArrayList<Integer>(); 
      // Read it 
      while(scanner.hasNextInt()){ 
       smallFileIntegers.add(scanner.nextInt()); 
      } 
      scanner.close(); 

      // Sort them in memory 
      Collections.sort(smallFileIntegers); 

      PrintStream out = createPrintStream(outputFile); 
      for(int i : smallFileIntegers) { 
       out.printf("%d,",i); 
      } 
      out.close(); 
      // And your're done 
     } 
    } 
    private static PrintStream createPrintStream(File file) throws IOException { 
     boolean append = true; 
     return new PrintStream( new BufferedOutputStream(new FileOutputStream(file, append))); 
    } 
} 

dosyaların formatı number,number,number,number

Geçerli biçimidir olduğunu.

Bunun için başka bir soru ekleyin.