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.
