Как улучшить время выполнения моего алгоритма? - PullRequest
Новая
       6

Как улучшить время выполнения моего алгоритма?

0 голосов
/ 26 марта 2020

Целью является файл, с 1-й строкой в ​​качестве числа доступных строк, найдите, сколько пар линий являются перестановками друг друга. Примером может быть то, что AABA является перестановкой BAAA. Код написан на java. Это мой текущий код: 

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.Arrays;

public class SpeedDemon {

    public class Data{
        byte[] dataValues;
        byte duplicate=1;
        int hashcode;
        public Data(byte[] input) {
            dataValues= new byte[128];
            for (byte x : input) {
                if (x==10){
                    break;
                }
                dataValues[x]++;
            }
            hashcode = Arrays.hashCode(dataValues);
        }
        public boolean equal(Data o){
            return this.hashcode==o.hashcode&&Arrays.equals(o.dataValues, this.dataValues);
        }
    }
    public int processData(String fileName){
        try {
            BufferedReader reader = new BufferedReader(new FileReader(fileName));
            int size = Integer.parseInt(reader.readLine());
            int arr_size = 2;
            while (arr_size < size) {
                arr_size *= 2;
            }
            Data[] map = new Data[arr_size];
            int z = 0;
            Data data;
            int j;
            for (int i = 0; i < size; i++) {
                data = new Data(reader.readLine().getBytes());
                j = data.hashcode;
                j ^= (j >>> 16);
                j &= (arr_size - 1);
                while (true) {
                    if (map[j] == null) {
                        map[j] = data;
                        break;
                    } else {
                        if (map[j].equal(data)) {
                            z += map[j].duplicate++;
                            break;
                        } else {
                            j = j == arr_size - 1 ? 0 : j + 1;
                        }
                    }
                }
            }
            return z;
        }catch(Exception ex){ }
        return 0;
    }
    public static void main(String[] args) {
        System.out.println(new SpeedDemon().processData(args[0]));
    }
}

Я хотел бы знать, есть ли способ улучшить эффективность использования времени программой? Это часть моего конкурса в классе, и некоторые люди справились с временем выполнения примерно на 25% быстрее. Я пробовал разные размеры массивов, и это, кажется, работает лучше всего.

Ответы [ 2 ]

0 голосов
/ 26 марта 2020

Вы уверены, что ваш код даже получает правильный ответ? Это маловероятно.

Самый простой способ определить, являются ли две строки перестановками друг друга, состоит в сортировке строк и их сравнении. Имея это в виду, более простой и быстрый способ написания кода - использовать Map. Примерно так: 

Create a new Map where the key and value are both strings
for each line of the file
    s = read string from file
    sortedString = sort(s) // sort characters in the string
    if (map.contains(sortedString))
        you found a duplicate
    else
        map.insert(sortedString, string) // the key is the sorted string
end for

Есть и другие способы сделать это, но это самый простой из известных мне способов и, вероятно, самый быстрый.

0 голосов
/ 26 марта 2020

Умножьте arr_size на 4. Вам нужно много свободных слотов, чтобы сделать открытую адресацию эффективной, и в зависимости от того, что size, возможно, вы не получаете очень много прямо сейчас.

Укажите большее размер буфера в буферизированном считывателе, чтобы уменьшить количество операций ввода-вывода. Было бы разумно 32768.

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

...