Как я могу оптимизировать эту «сортировку»? - PullRequest
Новая
       20

Как я могу оптимизировать эту «сортировку»?

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

Итак, я пишу алгоритм, который получает массив отсортированных строк и заполняет массив строк, определенных пользователем, связанными списками. Каждый связанный список представляет собой список анаграмм. Например, список может содержать «car» и «ar c», потому что оба содержат буквы a, c и r.

Каждый заголовок массива должен быть в алфавитном порядке исходного списка. Таким образом, в основном, если бы у меня был ввод {"ar c", "bed", "car", "deb", "xylophone"}, я бы получил вывод:

ar c, car

bed, deb

ксилофон

Как этого добиться, используя вложенное значение для l oop. Внешний l oop принимает i-й элемент или «ключ» списка, а внутренний l oop принимает j-й элемент массива связанного списка. Если заголовок j-го списка содержит ноль, немедленно поместите ключ в j и разбейте. Если заголовок не имеет нулевого значения и если ключ является анаграммой заголовка, он добавляется в список. Мой связанный список автоматически сортирует.

Теперь это работает очень хорошо для небольших входов. Но для очень больших входных данных, скажем, для n = 15000, понадобилось до 2 с половиной минут, чтобы завершить sh вложенных циклов, и это занимает слишком много времени. Я не думаю, что это имеет какое-либо отношение к моим методам LinkedList, поскольку в нем нет вложенных циклов. Могу ли я действительно оптимизировать это? Желательно что-то лучше, чем O (n ^ 2). Может быть, разбить входной массив на два и сделать рекурсивные вызовы? 

//receives a lexicographically sorted string array called "input"
//some other code
//"sortAlphabetical(String)" is a sorting algorithm which lexicographically sorts a string. Used to compare two strings, uses a quick sort and is very fast... doesn't appear to be the issue.


        ArrayList<LinkedList> theList = new ArrayList<>();  //creates new linked lists for elements of the arraylist
        for(int k = 0; k < input.length; k++) {
            theList.add(new LinkedList());
        }
        int numberOfLists = 0;                      //tracks the number of non empty lists created, not relevant
        long startTime = System.nanoTime();         //begin tracking time
        for(int i = 0; i < input.length; i++) {
            String theKey = input[i];
            for(int j = 0; j < theList.size(); j++) {

                if(theList.get(j).getHeadM() != null) {

                    if(sortAlphabetical(theList.get(j).getHeadM()).equals(sortAlphabetical(theKey))) {
                        theList.get(j).add(theKey);
                        break;
                    }
                }
                else if(theList.get(j).getHeadM() == null){

                    theList.get(j).add(theKey);
                    numberOfLists++;
                    break;
                }
            }
        }

        elapsed = System.nanoTime() - startTime;
        System.out.println("The nested for loops in sortList ran. It took " + elapsed + " nanoseconds.");
//more code

и я получаю следующий вывод: 

The nested for loops in sortList ran. It took 117061964600 nanoseconds.

Это примерно 120 секунд или две минуты. Любая помощь или предложения будут оценены. Если мне нужно добавить дополнительную информацию, дайте мне знать.

edit: Мне не разрешено использовать Java библиотечные сортировки, такие как hashsets, et c.

1 Ответ

0 голосов
/ 03 марта 2020 
for(int i = 0; i < input.length; i++) {
String theKey = input[i];
for(int j = 0; j < theList.size(); j++) {

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

int inputLength = input.length;
int theListSize = theList.size();
for(int i = 0; i < inputLength; i++) {
String theKey = input[i];
for(int j = 0; j < theListSize; j++) {

Это сохранит вызов метода при каждой итерации при проверке состояние.

...