Как эффективный способ транспонировать матрицу в текстовом файле? - PullRequest
1 голос
/ 20 марта 2012

У меня есть текстовый файл, который содержит 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. было бы дорого, если не невозможно, попытаться перенести этот файл / матрицу в память.

Кто-нибудь знает об утилитарном 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

Затем я читаю каждый файл обратно и добавляю их в один файл. Интересно, есть ли более разумный способ, потому что я знаю, что файловые операции ввода / вывода будут болезненной точкой.

Ответы [ 3 ]

1 голос
/ 20 марта 2012

Решение с минимальным потреблением памяти и чрезвычайно низкой производительностью:

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();
  }
}
0 голосов
/ 24 ноября 2016

Я бы посоветовал оценить количество столбцов, которые вы можете прочитать, не занимая много памяти. Затем вы записываете окончательный файл, несколько раз читая исходный файл, используя количество столбцов. Допустим, у вас есть 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;
        }
    }

}

Это должно быть гораздо эффективнее, чем создавать множество временных файлов, которые будут генерировать тонны ввода / вывода.

Для вашего примера матрицы 10000 x 14000 этот код занял 3 минуты для создания транспонированного файла. Если вы установите MAX_BYTES_PER_CHUNK = 1024 * 100_000 вместо 1024 * 50_000, это займет 2 минуты, но, конечно, потребляет больше оперативной памяти.

0 голосов
/ 20 марта 2012

Общий размер составляет 1.12 ГБ (если двойной), половина от этого, если float.Это достаточно мало для современных машин, чтобы вы могли делать это в памяти.Возможно, вы захотите сделать транспозицию на месте, и это довольно нетривиальная задача.В статье в википедии содержатся дополнительные ссылки.

...