テキストファイルに行列を転置する効率的な方法は何ですか？

Question

私は2次元マトリックスを保持するテキストファイルを持っています。次のようになります。

01 02 03 04 05 
06 07 08 09 10 
11 12 13 14 15 
16 17 18 19 20 

ご覧のとおり、各行は改行で区切られ、各列はスペースで区切られています。私は効率的な方法で行列を転置する必要があります。

01 06 11 16 
02 07 12 17 
03 08 04 05 
04 09 14 19 
05 10 15 20 

実際には、マトリックスは10,000×14,000である。個々の要素はdouble/floatです。不可能ではないにしても、このファイル/行列をすべてメモリ上で転置しようとすると、コストがかかります。

誰かがutil APIを知っていますか？

私が試したこと：私の素朴なアプローチは、（転置行列の）各列の一時ファイルを作成することでした。 10,000行では、私は10,000の一時ファイルを持っています。私は各行を読むとき、私は各値をトークン化し、対応するファイルに値を追加します。上の例では、私は次のようなものを持っています。

file-0: 01 06 11 16 
file-1: 02 07 12 17 
file-3: 03 08 13 18 
file-4: 04 09 14 19 
file-5: 05 10 15 20 

次に、各ファイルを読み込んで1つのファイルに追加します。私はファイルを知っているので、よりスマートな方法があるのだろうか？/ o操作は苦労するでしょう。

Answer 1

解決策：

import org.apache.commons.io.FileUtils; 

import java.io.BufferedWriter; 
import java.io.File; 
import java.io.FileWriter; 
import java.io.IOException; 

public class MatrixTransposer { 

    private static final String TMP_DIR = System.getProperty("java.io.tmpdir") + "/"; 
    private static final String EXTENSION = ".matrix.tmp.result"; 
    private final String original; 
    private final String dst; 

    public MatrixTransposer(String original, String dst) { 
    this.original = original; 
    this.dst = dst; 
    } 

    public void transpose() throws IOException { 

    deleteTempFiles(); 

    int max = 0; 

    FileReader fileReader = null; 
    BufferedReader reader = null; 
    try { 
     fileReader = new FileReader(original); 
     reader = new BufferedReader(fileReader); 
     String row; 
     while((row = reader.readLine()) != null) { 

     max = appendRow(max, row, 0); 
     } 
    } finally { 
     if (null != reader) reader.close(); 
     if (null != fileReader) fileReader.close(); 
    } 


    mergeResultingRows(max); 
    } 

    private void deleteTempFiles() { 
    for (String tmp : new File(TMP_DIR).list()) { 
     if (tmp.endsWith(EXTENSION)) { 
     FileUtils.deleteQuietly(new File(TMP_DIR + "/" + tmp)); 
     } 
    } 
    } 

    private void mergeResultingRows(int max) throws IOException { 

    FileUtils.deleteQuietly(new File(dst)); 

    FileWriter writer = null; 
    BufferedWriter out = null; 

    try { 
     writer = new FileWriter(new File(dst), true); 
     out = new BufferedWriter(writer); 
     for (int i = 0; i <= max; i++) { 
     out.write(FileUtils.readFileToString(new File(TMP_DIR + i + EXTENSION)) + "\r\n"); 
     } 
    } finally { 
     if (null != out) out.close(); 
     if (null != writer) writer.close(); 
    } 
    } 

    private int appendRow(int max, String row, int i) throws IOException { 

    for (String element : row.split(" ")) { 

     FileWriter writer = null; 
     BufferedWriter out = null; 
     try { 
     writer = new FileWriter(TMP_DIR + i + EXTENSION, true); 
     out = new BufferedWriter(writer); 
     out.write(columnPrefix(i) + element); 
     } finally { 
     if (null != out) out.close(); 
     if (null != writer) writer.close(); 
     } 
     max = Math.max(i++, max); 
    } 
    return max; 
    } 

    private String columnPrefix(int i) { 

    return (0 == i ? "" : " "); 
    } 

    public static void main(String[] args) throws IOException { 

    new MatrixTransposer("c:/temp/mt/original.txt", "c:/temp/mt/transposed.txt").transpose(); 
    } 
} 

Answer 2

合計サイズは1.12GB（doubleの場合）、floatの場合の半分です。これは、今日のマシンではメモリ内でできるほど小さいです。しかし、移調はインプレースで行いたいかもしれませんが、それはむしろ重要な作業です。 wikipedia articleにはさらにリンクがあります。最小限のメモリ消費量と非常に低い性能で

Answer 3

私は多くのメモリを消費していない間、あなたが読むことができる列の数を評価するために助言します。次に、いくつかの時間をソースファイルに列の数を含むチャンクで読んで、最終的なファイルを書きます。 10000列あるとします。最初に、コレクション内のソースファイルの0〜250の列を読み、最後のファイルに書き込みます。それから250〜500桁目についてもう一度やり直してください。

public class TransposeMatrixUtils { 

    private static final Logger logger = LoggerFactory.getLogger(TransposeMatrixUtils.class); 

    // Max number of bytes of the src file involved in each chunk 
    public static int MAX_BYTES_PER_CHUNK = 1024 * 50_000;// 50 MB 

    public static File transposeMatrix(File srcFile, String separator) throws IOException { 
     File output = File.createTempFile("output", ".txt"); 
     transposeMatrix(srcFile, output, separator); 
     return output; 
    } 

    public static void transposeMatrix(File srcFile, File destFile, String separator) throws IOException { 
     long bytesPerColumn = assessBytesPerColumn(srcFile, separator);// rough assessment of bytes par column 
     int nbColsPerChunk = (int) (MAX_BYTES_PER_CHUNK/bytesPerColumn);// number of columns per chunk according to the limit of bytes to be used per chunk 
     if (nbColsPerChunk == 0) nbColsPerChunk = 1;// in case a single column has more bytes than the limit ... 
     logger.debug("file length : {} bytes. max bytes per chunk : {}. nb columns per chunk : {}.", srcFile.length(), MAX_BYTES_PER_CHUNK, nbColsPerChunk); 
     try (FileWriter fw = new FileWriter(destFile); BufferedWriter bw = new BufferedWriter(fw)) { 
      boolean remainingColumns = true; 
      int offset = 0; 
      while (remainingColumns) { 
       remainingColumns = writeColumnsInRows(srcFile, bw, separator, offset, nbColsPerChunk); 
       offset += nbColsPerChunk; 
      } 
     } 
    } 

    private static boolean writeColumnsInRows(File srcFile, BufferedWriter bw, String separator, int offset, int nbColumns) throws IOException { 
     List<String>[] newRows; 
     boolean remainingColumns = true; 
     try (FileReader fr = new FileReader(srcFile); BufferedReader br = new BufferedReader(fr)) { 
      String[] split0 = br.readLine().split(separator); 
      if (split0.length <= offset + nbColumns) remainingColumns = false; 
      int lastColumnIndex = Math.min(split0.length, offset + nbColumns); 
      logger.debug("chunk for column {} to {} among {}", offset, lastColumnIndex, split0.length); 
      newRows = new List[lastColumnIndex - offset]; 
      for (int i = 0; i < newRows.length; i++) { 
       newRows[i] = new ArrayList<>(); 
       newRows[i].add(split0[i + offset]); 
      } 
      String line; 
      while ((line = br.readLine()) != null) { 
       String[] split = line.split(separator); 
       for (int i = 0; i < newRows.length; i++) { 
        newRows[i].add(split[i + offset]); 
       } 
      } 
     } 
     for (int i = 0; i < newRows.length; i++) { 
      bw.write(newRows[i].get(0)); 
      for (int j = 1; j < newRows[i].size(); j++) { 
       bw.write(separator); 
       bw.write(newRows[i].get(j)); 
      } 
      bw.newLine(); 
     } 
     return remainingColumns; 
    } 

    private static long assessBytesPerColumn(File file, String separator) throws IOException { 
     try (FileReader fr = new FileReader(file); BufferedReader br = new BufferedReader(fr)) { 
      int nbColumns = br.readLine().split(separator).length; 
      return file.length()/nbColumns; 
     } 
    } 

} 

それはI/Oのトンを生成します一時ファイルの多くを作成するよりもはるかにeffecientする必要があります。

たとえば、10000 x 14000行列の場合、このコードは転置ファイルの作成に3分かかりました。 1024 * 50_000の代わりにMAX_BYTES_PER_CHUNK = 1024 * 100_000を設定した場合、2分かかりますが、RAMを消費します。