Java - Alternativa za vnořené cykly?

Chtěl bych opětovně otevřít toto téma, na které jsem zanevřel a teď jsem se k tomu opětovně vrátil. Jak už bylo zmíněno, náhrada za vnořené cykly je rekurze, kromě kódu v odpovědi, jsem našel různé způsoby, např. tento

// add the next character to the string, or the string to the list
public void variations(List<String> list, int remaining, String soFar, int... codePoints) {
    if (remaining == 0) {
        list.add(soFar);
    } else {
        for (int i = 0; i < codePoints.length; ++i) {
            variations(list, remaining - 1,
                soFar + Character.toString(codePoints[i]), codePoints);
        }
    }
}

// recursively generate all possible combinations
public List<String> getVariation(int number, int... codePoints) {
    List<String> list = new ArrayList<>();
    variations(list, number, "", codePoints);
    return list;
}

Tento kód jednoduše zavolám příkazem

Zmíněnou chybu java.lang.reflect.InvocationTargetException bych odsunul stranou. Tu zavinila knihovna OpenJavaFX, se kterou je více potíží než užitku (od té doby, co není součástí Java) a po odebrání chyba zmizela.

Avšak, stále tu zůstává problém s nedostatkem paměti. Pokud zavolám kód výše např. tímto příkazem

var list = getVariation(7, "abcdefghijklmnop".codePoints().toArray());

Program poběží cca 3 minuty a pak zhavaruje s chybou Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

Problém přetrvává i potom, co jsem NetBeans navýšil paměť na 5 GB (před tím to zhavarovalo mnohem dříve)

Nevíte, prosím Vás, jak to vyřešit? Samozřejmě je tu ještě problém s nedostatkem kapacity pole, ale to jsem chtěl jednoduše vyřešit použitím více polí.

Nicméně, to bych první musel vyřešit problém s pamětí. Popravdě se mně ani nepodařilo zjistit, jak velké pole vlastně je, když to zhavaruje.

Děkuji za odpověď.

No tak si to spočítáme. Máš tam 16 znaků, děláš variace s opakováním o délce 7. Takže celkem 16^7 = 268435456 variací. Každá z těch variací je 7 znaků dlouhá, znak zabírá v paměti 2 byty. Takže celkem 3758096384 B = 3,5 GB. Ve skutečnosti to bude víc, protože instance stringu nejsou jenom samotné znaky.

Problém je ale i v tom, jak ty variace vytváříš:

soFar + Character.toString(codePoints[i])

Vytvoří nový string, do kterého nakopíruje původní a k tomu ten jeden znak. Najednou máš v paměti ten string prakticky dvakrát, než to uklidí garbage collector. A pokud je vytváříš rychleji, než se stihne uklízet, tak ti dojde paměť.

Pak by se jeste mohl podivat, co dela metoda ensureCapacity na ArrayListu...

Určitě ano. Ale tady bych už to viděl jako ten nejmenší problém.

No to je dost velky problem, protoze se ten list musi prekopirovat, ale da se vyresit nastavenim pocatecni kapacity.

Asi bych ty variace neukládal (k čemu je vlastně potřebuješ ???), ale každou hned "použil". Nějak mi uniká, k čemu to může být dobré ... Jinak, nemá smysl řešit něco, co vlastně k ničemu není aneb udělal bych to jinak.

Asi bych ty variace neukládal (k čemu je vlastně potřebuješ ???)

To máte asi pravdu, přímým použitím by paměť nepřetekla. Jenže napsat kód, který první ty variace vytvoří do pole a až potom je využije, je mnohem přehlednější, než když je budu používat hned při vytváření.

Uloz si je do souboru, ne do pameti a pak je cti rovnou ze souboru. Velikost hedne variace znas, tak muzes rovnou precist tu n-tou, ktera te zajima

Uloz si je do souboru, ne do pameti a pak je cti rovnou ze souboru.

To je velmi zajímavá myšlenka, která mě upřímně nenapadla, jenže vůbec netuším, jak ten kód upravit.

Místo přidání do listu do zapíšeš do souboru.
Ale spíš bys měl zodpovědět otázku, proč ty variace chceš mít vygenerované. Mám takové tušení, že je vůbec nepotřebuješ.

    public static void main(String[] args) {
        var chars = "abcdefghijklmnop".toCharArray();
        int variations = 7;

        var length = chars.length;
        var list = new LinkedList<String>();
        StringBuilder out = new StringBuilder();

        for (int i = 0; i < variations; i++) out.append(chars[0]);

        top:
        while (true) {
            list.add(out.toString());
            if (list.size() % 10000 == 0) {
                append(list);
                list.clear();
            }
            for (int pos = variations - 1; pos >= 0; pos--) {
                char c = out.charAt(pos);
                int cPos = Arrays.binarySearch(chars, c);
                if (cPos < length - 1) {
                    // We can just increment this one and we're done
                    out.setCharAt(pos, chars[cPos + 1]);
                    continue top;
                } else {
                    // 9-> 10: Every 'lower' digit is reset to first (0).
                    out.setCharAt(pos, chars[0]);
                }
            }
            break;
        }
    }

    public static void append(List<String> combinations) {
        try {
            Files.write(Paths.get("combinations.txt"), String.join("\n", combinations).getBytes(),
                    StandardOpenOption.APPEND, StandardOpenOption.CREATE);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

Ukladani do souboru combinations.txt. A nepotrebujes ani zadne gigabajty heapu. Jako mustr jsem pouzil jeden z tvych kodu, co jsi jsem dal. Ten ktery se mi zdal nejlepsi...

Mala chybicka, zapomnel jsem zapsat posledni davku kombinaci. Oprava:

    public static void main(String[] args) {
        var chars = "abcdefghijklmnop".toCharArray();
        int variations = 7;

        var length = chars.length;
        var list = new LinkedList<String>();
        StringBuilder out = new StringBuilder();

        for (int i = 0; i < variations; i++) out.append(chars[0]);

        top:
        while (true) {
            list.add(out.toString());
            if (list.size() % 10000 == 0) {
                append(list);
                list.clear();
            }
            for (int pos = variations - 1; pos >= 0; pos--) {
                char c = out.charAt(pos);
                int cPos = Arrays.binarySearch(chars, c);
                if (cPos < length - 1) {
                    // We can just increment this one and we're done
                    out.setCharAt(pos, chars[cPos + 1]);
                    continue top;
                } else {
                    // 9-> 10: Every 'lower' digit is reset to first (0).
                    out.setCharAt(pos, chars[0]);
                }
            }
            break;
        }
        append(list);
    }

    public static void append(List<String> combinations) {
        try {
            Files.write(Paths.get("combinations.txt"), String.join(System.lineSeparator(), combinations).getBytes(),
                    StandardOpenOption.APPEND, StandardOpenOption.CREATE);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

Ted uz budou v souboru vsechny kombinace...