@rosstik9

Java. Как отпимизировать работу программы?

Хочу начать с того, что являюсь новичком, мой код далёк от идеальности и скорей всего его нужно править или переделывать.
Так вот, задача стоит вот в чём: Программа должна выводить все перестановки мультимножества без повторений, мультимножество вводиться с клавиатуры.

Сам код приведён ниже. Сразу скажу, что он работает, при этом весьма корректно.
Суть проблемы такова: программа работает только до ввода 10 чисел, дальше не хочет. Так как 10! - это уже 4млн комбинаций. Аррайлист заполнен видимо до упора, в результате выникает Exeption OutOfMemoryError. Что делать ? Как быть? Буду рад любой помощи.

Забыл сказать об самой теории. Мультимножество - набор чисел.
A = {1^2 ,2^3 ,3^3 ,4^2 ,5^1};
Тут степень - количество повторов. Т.е. это мультмн. можна было предствить в виде:
A = {1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5};
На основании таких чисел нужно строить перестановки без повторений.

Моя прога:
1.Я достаю такое множество в Аррайлист
2.Рекурсивно делаю перестановки
3.Отсееваю лишние с помощью Хэшсэта
4.Записываю в файл. Т.к. в консоле все перестановки не вмещаются.

import java.io.*;
import java.util.*;

import static java.util.Collections.swap;


public class Main {

    private static ArrayList <String> rec_filter = new ArrayList<>();
    private static String fileName = "new_file.txt";
    private static ArrayList<String> in = new ArrayList<String>();

    public static ArrayList<Integer> return_Arrlist() throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> list = new ArrayList<Integer>();

        while (true) {
            String s = bufferedReader.readLine();
            if (s.equals("")) break;
            int num = Integer.parseInt(s);
            System.out.print(num + "^");
            String tmp_step = bufferedReader.readLine();
            int stepin = Integer.parseInt(tmp_step);
            in.add(num + "^" + tmp_step);
            while (stepin > 0) {
                list.add(num);
                stepin--;
            }
        }

        System.out.println("Введена мультимножина: " +"\n А = " +in);
        return list;
    }

    public static void permute(ArrayList<Integer> list, int start) throws IOException {
        for (int j = start; j <= list.size() - 1; j++) {
            swap(list, start, j);
            //System.out.println(list);
            permute(list, start + 1);
            swap(list, start, j);
        }
        rec_filter.add(list.toString());
    }

    public static void main(String[] args) throws IOException {
        permute(return_Arrlist(), 0);
        int count = 0;
        List <String> list = rec_filter;
        Set <String> set = new HashSet<>(list);
        rec_filter.removeAll(rec_filter);
        list.removeAll(list);
        in.removeAll(in);
        long startTime = System.currentTimeMillis();

        File file = new File(fileName);
        try {
            BufferedWriter writer = new BufferedWriter(new FileWriter(file, true));
            for (Iterator iter = set.iterator(); iter.hasNext();) {
                count++;
                //System.out.println(count+") "+ iter.next());
                writer.write(count+") "+ iter.next()+"\n");
            }
            writer.close();
        }
        catch (Exception ex){
            ex.printStackTrace();
        }

        String s = "----------------------------------------\n";
        System.out.printf("%s",s);
        System.out.println("Всього можливих комбінацій: " +count);
        System.out.printf("%s",s);
        long timeSpent = System.currentTimeMillis() - startTime;
        System.out.println("програма виконувадась " + (timeSpent*10e-6) + " секунд");
    }
}
  • Вопрос задан
  • 241 просмотр
Пригласить эксперта
Ответы на вопрос 3
TheKnight
@TheKnight
Программист
Во первых - вам нет необходимости хранить все перестановки в памяти компьютера. Их можно скидывать на диск, сразу после генерации. Но не факт.
Во вторых - возможно, вам нужен алгоритм Нарайны.
В третьих - далеко не везде нужен ArrayList. Во многих ситуациях вы можете обойтись массивом фиксированной длины. Например, для хранения текущей перестановки.
В четвертых - если у вас так много генерируется перестановок - есть шанс, что они и в хэшсет не влезут. Думается мне, вам стоит задуматься о сортировке и фильтрации во внешней памяти.
В пятых - существуют ли ограничения по используемой памяти и общему времени работы?
В шестых - если вы воспользуетесь алгоритмом Нарайны - вы сможете сэкономить память на хранение результата в некоторых случаях. Подсказка - посмотрите на мультимножество вида {1^10, 2^1} с 11 неуникальными и двумя уникальными перестановками и предположите, сколько из этих перестановок будут храниться в HashSet.

P.S.: А язык вывода у вас украинский или белорусский? Слово "мультимножина" стоит запомнить. Кроме того, вам нет необходимости использовать printf, там, где достаточно написать println(s). А вот там, где printf пригодился бы - вы используете println. Сравните со своим кодом.
String s = "----------------------------------------";
System.out.println(s);
System.out.printf("Всього можливих комбінацій: %d ",count);
System.out.println(s);
long timeSpent = System.currentTimeMillis() - startTime;
System.out.printf("програма виконувадась %f секунд", (timeSpent*10e-6));
Ответ написан
Комментировать
@FoxInSox
в результате выникает Exeption OutOfMemoryError. Что делать ? Как быть?

Увеличьте объем памяти у компьютера.
Ответ написан
Комментировать
@asd111
насколько я понял у вас больше всего памяти съедает list<string> и set<string> из за того что у вас в памяти хранятся миллионы строк.
я думаю что лучше не делать list<string>из множеств а делать hashcode() получившегося из одного множества string и затем этот полувшийся из hashcode() integer добавить в set<integer>и если добавилось то сохранить строку на диск - такое решение должно кушать в несколько раз меньше памяти
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы