Wydajność mojego algorytmu generującego kombinacje znaków

0

Witam,

otóż napisałem sobie algorytm, którego działanie wymyśliłem całkowicie sam nie orientując się w obecnych rozwiązaniach. Napisałem jego implementację w javie, oraz opisałem sposób działania tu:

http://speedy.sh/xaNxp/Algorytm.pdf
Instrukcja napisana na szybko, w wersji finalnej chciałbym bardziej przybliżyć sposób działania tak, aby każdy zrozumiał.

Implementacja w javie z małym testem wydajnościowym:

package generatorslow;

import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;

public class GeneratorSlow
{
    private final String listaZnakow;
    private final int dlugosc;
    private final int iloscZnakow;
    private int[] status;
    private boolean koniec;
    
    public GeneratorSlow(String znaki, int dl)
    {
        listaZnakow = znaki;
        koniec = false;
        dlugosc = dl;
        iloscZnakow = znaki.length();
        status = new int[dlugosc];
        
        for (int i = 0; i < dlugosc; i++)
            status[i] = -1;
    }
    
    public GeneratorSlow(String znaki, int dl, String zacznijOd)
    {
        listaZnakow = znaki;
        iloscZnakow = znaki.length();
        dlugosc = dl;
        status = new int[dlugosc];     
        
		// Wypełniamy tablicę status podanym słowem, np. aabbccdd. Wada na razie jest taka, że długość zacznijOd == dlugosc
        for (int i = 0; i < dlugosc; i++)
            for (int x = 0; x < iloscZnakow; x++)
                if (listaZnakow.charAt(x) == zacznijOd.charAt(i))
                    status[i] = x;
    }
        
    public String nastepnaKombinacja()
    {
        if (status[0] != iloscZnakow-1)
            przeskocz(dlugosc-1);
        else
            koniec = true;
        
        return odczytajKombinacje();
    }
    
    public boolean czyKoniec()
    {
        return koniec;
    }
    
    private String odczytajKombinacje()
    {
        String nowaKombinacja = "";
        
        for (int i = 0; i < dlugosc; i++)
            if (status[i] != -1)
                nowaKombinacja += listaZnakow.charAt(status[i]);
        
        return nowaKombinacja;
    }
    
    private void przeskocz(int pozycja)
    {
        status[pozycja]++;
        
        if (status[pozycja] == iloscZnakow)
        {
            status[pozycja] = 0;
            
            przeskocz(pozycja-1);
        }
    }
    
    public static void main(String[] args)
    {
        String tablicaZnakow = "0123456789abcdefghijklmnopqrstuvwxyz";
        GeneratorSlow generatorSlow = new GeneratorSlow(tablicaZnakow, 8);
        
        long i = 0;
        String kombinacja;
        long czas = System.currentTimeMillis();
        
        while (!generatorSlow.czyKoniec())
        {
            kombinacja = generatorSlow.nastepnaKombinacja();
            
            i++;
            
			// Tutaj wypisujemy co milionową kombinację i ilość generowanych kombinacji/s
            if (i % 1000000 == 0)
                System.out.println(i/1000000 + "kk) " + kombinacja + "  " + ((((System.currentTimeMillis()-czas)/1000) == 0) ? "" : i/((System.currentTimeMillis()-czas)/1000)) + "/s (" + (System.currentTimeMillis()-czas)/1000 + "s)");
           
        }
        
        System.out.println("Koniec.");
    }
}

Jak już pisałem nie wiem nawet jak ludzie tworzą takie algorytmy, dlatego chciałbym Was prosić o przedstawienie takowych i ocenienie wydajnościowe. U mnie na Phenomie X4 3.2GHz przy 1-wątkowm zastosowaniu generuje on około 3 miliony kombinacji/s, a algorytm można wystartować od dowolnego słowa.

0

a czy to działa prawidłowo? Chyba nie! Masz problem z końcowymi kombinacjami.
uprość sobie tablicaZnakow = "01234"; eneratorSlow = new GeneratorSlow(tablicaZnakow, 2);
i zobacz czy dostaniesz na końcu: 41, 42, 43, 44!

0

Niedawno napisałem artykuł Generator słów (metoda znaczników) - zapoznaj się z moją wersją (napisany w delphi w formie klasy generatora); Może wpadniesz na jakiś ciekawy pomysł; Algorytm działa w 100% - jednak brak w nim słowa początkowego i końcowego - tylko możliwe ustalenie długości początkowej i końcowej;

1 użytkowników online, w tym zalogowanych: 0, gości: 1