Пути ускорения чтения данных для матриц из файла(.txt) и последующего перемножения матриц

155
02 февраля 2018, 21:40
  1. Имеется. txt файл следующего вида:

3 2
1 2

1 2
2 4

4 2
1 3

1 2
2 1

Где первые 4 цифры: 3 -количество матриц в файле (любое число не более 130) 2 -размер матриц (они всегда квадратные, любой размер не более 130) 1, 2 -i, j искомого элемента результирующей матрицы Все остальные числа ниже -это сами матрицы:

1 2 матрица 1
3 4

4 2 матрица 2
1 3

1 2 матрица 3
2 1

  1. Нужно сделать. В результате нужно вывести в файл число из результирующей матрицы с координатами по строке и столбцу указанными в файле (1, 2 в приведенном примере). Результирующая матрица-это матрица полученная перемножением матриц из файла. В приведенном случае ответ: 20

Мой код:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
/**
 * Created by Pazuk on 28.01.2018.
 */
// Main idea:
// Step 1. Get all values from input file and according with it build array with numbers for matrices
// Step 2.
// Loop iteration:
// - get numbers from array and create next matrix array
// - multiply actual matrix with next matrix, get result matrix
// - mark result matrix as actual matrix
// Next iteration...
// Step 3. After last iteration, get from result matrix requested number (positions specified in input file)

public class Main {    
    static int[] list;
    static boolean fileCheckOk=true;
    static int m;
    static int n;
    static int a;
    static int b;        
    static int[][] matrixA;
    public static void main(String[] args) throws IOException {
        long startTime = System.currentTimeMillis();
        long time = System.currentTimeMillis() - startTime;
        System.out.println(time);
        readFile();
        time = System.currentTimeMillis()-startTime;
        System.out.println(time);
        if(fileCheckOk){
            calculate();
            PrintWriter writer=new PrintWriter("output.txt");
            writer.print(matrixA[a-1][b-1]);
            writer.close();
        }
        time = System.currentTimeMillis()-startTime;
        System.out.println(time);
    }
    static void readFile() throws IOException {

File file=new File("input.txt");        
    Reader reader=new FileReader(file);
    StreamTokenizer tokenizer=new StreamTokenizer(reader);
    //general input values:
    tokenizer.nextToken();
    m=(int)tokenizer.nval; // number of matricis
    tokenizer.nextToken();
    n=(int)tokenizer.nval; // matrices size
    tokenizer.nextToken();
    a=(int)tokenizer.nval; // position i of requested number
    tokenizer.nextToken();
    b=(int)tokenizer.nval; // position j of requested number                
    list=new int[m*n*n]; // array length according with quantity of matricis and their size
    int i=0;
    while(tokenizer.nextToken()!=StreamTokenizer.TT_EOF){
        list[i]=(int)tokenizer.nval;
        i++;
    }
if(reader!=null) {
            reader.close();
        }
        /*if(m>=1 && m<=130 && n>=1 && n<=130 && a>=1 && a<=n && b>=1 && b<=n){
            fileCheckOk=true; //check if input values are comply with task conditions
        }*/
    }       
    static void calculate(){ // calculate matrices
        int f, i, j, k;
        int r=0;
        int t;
        int temp;
        int[] thatColumn=new int[n];
        int[] thisRow=new int[n];
        int result=0;
        matrixA=new int[n][n]; // actual matrix
        for(f=0; f< m; f++){ // number of iterations==matrices quantity
            int[][] matrixB=new int[Main.n][Main.n]; // next matrix
            for(i=0; i< Main.n; i++){
                for(j=0; j< Main.n; j++){
                    matrixB[i][j]=list[r];
                    r++;
                }
            }
            if(f>0){
                int[][] matrixC=new int[Main.n][Main.n]; //result matrix
                for(j=0; j< Main.n; j++){
                    for(k=0; k< Main.n; k++){
                        thatColumn[k]=matrixB[k][j];
                    }
                    for(i=0; i< Main.n; i++){
                        thisRow=matrixA[i];
                        result=0;
                        for(k=0; k<Main.n; k++){
                            temp=thisRow[k]*thatColumn[k];
                            result=result+temp;                           
                        }
                         matrixC[i][j]=result;
                    }
                }
                /*for(i=0; i< Main.n; i++){
                    for(j=0; j< Main.n; j++){
                        t=matrixA[i][k];
                        for(j=0; j< Main.n; j++){
                            temp=t*matrixB[k][j]; // multiplying...                                
                            matrixC[i][j]=matrixC[i][j]+temp; // ...matrces
                        }
                    }
                }*/
                matrixA=matrixC;                    
            } else {
                matrixA=matrixB;                    
            }
        }
    }
}

Код работает и выдает правильный ответ. Но не проходит тесты из-за слишком медленной работы. Какие могут быть пути ускорения?

1 Может быть другой внутренний алгоритм перемножения матриц? Сейчас они перемножаются "в лоб":

for(int i=0; i<m; i++){
             for(int j=0; j<n; j++){
                 for(int k=0; k<o; k++){
                     resultMatrix[i][j]+=mA[i][k]*mB[k][j]; 
                 }
             }
         }

Ну, почти так. Немного быстрее (см. метод calculate).

2 Может быть разбить вычисления по отдельным потокам?

3 Может быть другой путь обработки данных файла? Сейчас каждое последующее целое число файла, первые 4 присваиваем переменным, все остальные-загоняем в одномерный массив. Из которого потом берем значения для создания матриц, которые перемножаются.

Как-то так.

READ ALSO
Получить из IP имя узла (java)

Получить из IP имя узла (java)

В локальном чате при выводе сообщения пользователя необходимо вместо IP-адреса выводить имя удаленного узлаЕсть ли методы получить из IP имя...

154
Google Play Market

Google Play Market

в Play Console написано что приложение было опубликовано , загружено было 2 дня назад но в поиске по точному названию приложения я найти его не могуЕсли...

123
Error &ldquo;Element should have been &rdquo;select&ldquo; but was &rdquo;div&ldquo; &rdquo; in java code

Error “Element should have been ”select“ but was ”div“ ” in java code

Здравствуйте, пишу тесты на Java используя Test NGСтолкнулась с такой проблемой: Есть метод выбора value с выпадающего списка (см

141
Не работает RecycleView в RecyclerView

Не работает RecycleView в RecyclerView

необходимо сделать прокрутку как в playstore, но к сожалению recycleview отображает некорректно заполняя только первый элемент списка всеми элементами

141