Mein persönlicher Blog
29. August 2011 Hinterlasse einen Kommentar
Hallo,
ich habe vor einiger Zeit angefangen an einem deutschem Scala Tutorial zu schreiben.
Es richtet sich an Entwickler aus imperativen Programmiersprachen, die in die funktionale Programmierwelt eintauchen möchten.
Für Kritiken, Anregungen und Verbesserungsvorschläge wäre ich sehr dankbar.
Grüße
Antoras
8. Oktober 2010 Hinterlasse einen Kommentar
Vor kurzem hab ich mich an Problem 24 von Project Euler gewagt. Dabei ging es um das Finden von Permutationen. Ich hab mich also kurzerhand hingesetzt und in Scala zwei Klassen geschrieben, die mir Permutationen von Zahlen und Strings berechnen.
Dabei kamen hauptsächlich zwei Algorithmen zum Einsatz. Der Erste wurde von Kenneth H. Rosen in seinem Buch Discrete Mathematics and its Applications niedergeschrieben. Der Algorithmus ist auch bekannt unter dem Namen SEPA – wie er genau funktioniert ist u.A. hier beschrieben.
Beim zweiten Algorithmus bin ich mir nicht sicher ob er einen Namen trägt. Mit ihm ist es möglich selbst in hohen Zahlenbereichen eine Permutation eines bestimmten Indexes korrekt und effizient zu berechnen. Ich will ihn kurz beschreiben:
Wir benötigen mehrere Variablen:
n = Anzahl der Ziffern einer Permutation
numbers = Die einzelnen Zahlen der Permutation
digits = Die Zahlen von 0 bis n-1
index = der Index der Permutation
Angefangen wird bei der größten Zahl, also dem letzten digit. Von dieser berechnen wir die Fakultät und teilen dann den index durch diesen berechneten Wert. Angenommen unsere digits gehen von 0-9 und wir wollen den ein millionsten Index, dann sieht der erste Berechnungsschritt so aus:
digits = 0123456789, div = index = 1000000: 9! * k < div => k = 2, i = 2
2 ist die erste berechnete Ziffer. Wir bekommen sie indem wir den index durch 9! teilen und das Ergebnis abrunden. Nun notieren und entfernen wir die 2. Zahl (wir fangen bei 0 an zu zählen, die erste Zahl ist also 1, die nullte Zahl ist 0) aus den verfügbaren Zahlen und wiederholen den Vorgang für die zweitgrößte Zahl:
digits = 013456789, div = index – 9! * 2 = 274240: 8! * k < div => k = 6, i = 7
Auf den neuen Divisor kommen wir indem wir die Fakultät der nächstgrößeren Zahl mit k multiplizieren und diesen Wert dann vom vorherigen Divisor abziehen. Da k nun 6 ist notieren und entfernen wir anschließend die 6. Zahl von den noch verfügbaren Zahlen. Dieses Schema führen wir so lange fort bis alle Zahlen aufgebraucht sind.
Komplette Berechnung:
digits = 0123456789, div = index = 1000000: 9! * k < div => k = 2, i = 2
digits = 013456789, div = index – 9! * 2 = 274240: 8! * k < div => k = 6, i = 7
digits = 01345789, div = 274240 – 8! * 6 = 32320: 7! * k < div => k = 6, i = 8
digits = 0134569, div = 32320 – 7! * 6 = 2080: 7! * k < div => k = 2, i = 3
digits = 014569, div = 2080 – 6! * 2 = 640: 6! * k < div => k = 5, i = 9
digits = 01456, div = 640 – 5! * 5 = 40: 5! * k < div => k = 1, i = 1
digits = 0456, div = 40 – 4! * 1 = 16: 4! * k < div => k = 2, i = 5
digits = 046, div = 16 – 3! * 2 = 4: 3! * k < div => k = 1, i = 4
digits = 06, div = 4 – 2! * 1 = 2: 2! * k < div => k = 1, i = 6
digits = 0: i = 0
Nun müssen wir nur noch alle i’s von oben nach unten gelesen hintereinander schreiben -> die ein millionste Permutation von 0123456789 ist 2783915460.
Im Anschluss noch die beiden Generator-Klassen und ein wenig Test-Code:
import annotation._
/**
* This class generates permutations of a number with n digits.
* @author Antoras
* @version 0.6
* @since Scala 2.8.0, 04.10.2010, last update: 10.11.2010
*/
class PermutationGenerator private(
protected val n: Int,
numbers: List[Int],
digitStart: Int
) {
require(n >= 1, "n must be at least 1")
require(digitStart >= 0, "digitStart must be positive")
/**
* Creates a generator which permutes a given list with integers.
* @param numbers the list with the several numbers
*/
def this(numbers: List[Int]) = this(numbers.length, numbers, 0)
/**
* Creates a generator which permutes numbers in range of zero to n-1
* @param n the number of digits
*/
def this(n: Int) = this(n, Nil, 0)
/**
* Creates a generator which permutes numbers in range of digitStart to n+digitStart-1
* @param n the number of digits
* @param digitStart the first digit the generator begins to permute
*/
def this(n: Int, digitStart: Int) = this(n, Nil, digitStart)
private val arr, numbersStart, start = new Array[Int](n)
private var left = BigInt(0)
private val digitEnd = n + digitStart
private lazy val tot = fac(n)
private val isOrdered = (numbers == numbers.sortWith(_ < _))
reset()
/**
* Returns the total number of permutations which are available
* @return the total number of permutations as a BigInt
*/
def total: BigInt = tot
/**
* Returns the number of permutations not yet generated
* @return the number as a BigInt
*/
def numLeft: BigInt = left
/**
* Returns the current permutation. This is the same permutation as returned
* by the last call of {@link #next()}.
* @return the current permutation as a BigInt
*/
def cur: BigInt = arrToNum(if (!isOrdered) mkArr else arr)
/**
* Returns the current permutation. Several numbers are saved in an array.
* This is the same permutation as returned by the last call of {@link #next()}.
* @return the current permutation as an array of integers
*/
def curArr: Array[Int] = if (!isOrdered) mkArr else arr.clone
/**
* Returns the first permutation. This is the sequence from zero to n-1.
* Several numbers are saved in an array.
* @return the first permutation as an array of integers
*/
def startArr: Array[Int] = numbersStart.clone
/**
* Returns the first permutation. This is the sequence from zero to n-1.
* @return the first permutation as a BigInt
*/
def startNum: BigInt = arrToNum(numbersStart)
/**
* Checks if there are more permutations.
* @return {@code true} if there are more permutations
*/
def hasNext: Boolean = (numLeft > 0)
/**
* Returns the permutation at given index. Several numbers are saved in an array.
* @param index the index of the permutation
* @return the permutation as an array of integers
* @throws IllegalArgumentException if index > total number of permutations or index < 1
*/
def getArr(index: BigInt): Array[Int] = {
if (index > total)
throw new IllegalArgumentException("index is too large. There are only " + total + " permutations")
if (index < 1)
throw new IllegalArgumentException("index must be at least 1")
if (index == 1)
return startArr
var digits = for (i <- 0 until n) yield start(i)
val ret = new Array[Int](n)
@tailrec def loop(digit: Int, limit: BigInt, depth: Int) {
if (digit > 0) {
val curFac = fac(digit)
val div = ((limit - 1) / curFac).toInt
val num = digits(div)
ret(depth-2) = num
digits = digits.filter(num !=)
loop(start(n - depth), limit - curFac * div, depth + 1)
}
}
loop(start(n - 1), index, 2)
ret(n - 1) = digits(0)
if (numbers != Nil)
0 until n foreach (i => ret(i) = numbers(ret(i)))
ret
}
/**
* Returns the permutation at given index.
* @param index the index of the permutation
* @return the permutation as a BigInt
* @throws IllegalArgumentException if index > total number of permutations or index < 1
*/
def get(index: BigInt): BigInt = arrToNum(getArr(index))
/**
* Generates the next permutation. Several numbers are saved in an array.
* @return the next permutation as an array of integers
*/
def nextArr(): Array[Int] = {
if (left == total) {
left -= 1
return if (!isOrdered) mkArr else curArr
}
val largest = index(2, i => arr(i) > arr(i + 1))
val smallest = index(1, i => arr(largest) > arr(i))
swap(smallest, largest)
@tailrec def rotate(tail: Int, next: Int) {
if (next < tail) {
swap(tail, next)
rotate(tail - 1, next + 1)
}
}
rotate(arr.length - 1, largest + 1)
left -= 1
if (!isOrdered) mkArr else curArr
}
/**
* Generates the next permutation.
* @return the next permutation as a BigInt
*/
def next(): BigInt = {
arrToNum(nextArr())
}
/**
* Sets the generator to the start value.
*/
def reset() {
if (numbers == Nil)
0 until n foreach { i =>
val add = i + digitStart
arr(i) = add
numbersStart(i) = add
start(i) = add
}
else
0 until n foreach { i =>
arr(i) = if (!isOrdered) i else numbers(i)
numbersStart(i) = numbers(i)
start(i) = i
}
left = BigInt(total.toString)
}
private def swap(a: Int, b: Int) {
val t = arr(a)
arr(a) = arr(b)
arr(b) = t
}
private def index(sub: Int, f: Int => Boolean): Int = {
@tailrec def loop(i: Int): Int = if (f(i)) loop(i - 1) else i
loop(n - sub)
}
private def fac(n: Int): BigInt = {
@tailrec def loop(k: Int, prod: BigInt): BigInt = if (k <= 1) prod else loop(k - 1, prod * k)
if (n <= 1) 1 else loop(n, 1)
}
private def arrToNum(a: Array[Int]): BigInt = {
val sb = new StringBuilder(n)
a foreach sb.append _
BigInt(sb.toString)
}
private def mkArr: Array[Int] = {
val ret = new Array[Int](n)
0 until n foreach (i => ret(i) = numbers(arr(i)))
ret
}
}
/**
* This class generates permutations of a String. The String is compound
* by the several Strings of elems.
* @author antoras
* @version 0.5
* @since Scala 2.8.0, 04.10.2010
*/
final class StringPermutationGenerator(elems: List[String])
extends PermutationGenerator(elems.length) {
private val permutation = new StringBuilder(n)
private val indices = new Array[Int](n)
/**
* Returns the permutation of the String at given index.
* @param index the index of the permutation
* @return the permutation
* @throws IllegalArgumentException if index > total number of permutations or index < 1
*/
def getString(index: BigInt): String = mkString(getArr(index))
/**
* Returns the current permutation. This is the same permutation as returned
* by the last call of {@link #nextString()}.
* @return the current permutation as a String
*/
def curString: String = mkString(curArr)
/**
* Generates the next permutation of the String.
* @return the next permutation
*/
def nextString(): String = mkString(nextArr())
private def mkString(a: Array[Int]): String = {
permutation.clear()
0 until n foreach { i =>
indices(i) = a(i)
permutation.append(elems(indices(i)))
}
permutation.toString
}
}
import org.specs.SpecificationWithJUnit
class PermutationGeneratorTest extends SpecificationWithJUnit {
"PermutationGenerator" should {
"match" in {
"2783915460 by n=10" in {
val p = new PermutationGenerator(10)
p.get(1e6.toInt).toString must be matching "2783915460"
}
"7531 by numbers=1,3,5,7" in {
val numbers = List[Int](1,3,5,7)
val p = new PermutationGenerator(numbers)
while (p.hasNext) p.next()
p.cur.toString must be matching "7531"
}
"754311 by numbers=11,3,54,7" in {
val numbers = List[Int](11,3,54,7)
val p = new PermutationGenerator(numbers)
while (p.hasNext) p.next()
p.cur.toString must be matching "754311"
}
}
"throw an IllegalArgumentException if" in {
"n < 1" in {
new PermutationGenerator(-1) must throwA[IllegalArgumentException]
}
"digitStart < 0" in {
new PermutationGenerator(3, -1) must throwA[IllegalArgumentException]
}
"index > total number of permutations" in {
val p = new PermutationGenerator(3)
p.get(100) must throwA[IllegalArgumentException]
}
"index < 1" in {
val p = new PermutationGenerator(3)
p.get(0) must throwA[IllegalArgumentException]
}
}
}
"StringPermutationGenerator" should {
"match 'hg_mc' by used elements c,m,g_,h" in {
val elems = List[String]("c", "m", "g_", "h")
val sp = new StringPermutationGenerator(elems)
while (sp.hasNext) sp.nextString()
sp.curString must be matching "hg_mc"
}
}
}
29. Mai 2010 Hinterlasse einen Kommentar
Java’s hauseigene Canvas verfügen über keine Doppelpufferung was unschönes Flackern hervorrufen kann. Deshalb müssen wir uns dies selbst nachbauen. Die Klasse, die uns hier behilflich sein können nennen sich BufferStrategy und VolatileImage. VolatileImages sind Hardware-beschleunigt, weshalb uns dies einen Performance-Schub bringen kann.
Es ist zu beachten, dass unsere Zeichenfläche anweisen keine repaint()-Befehle mehr entgegen nehmen soll, da wir dies ja selbst machen wollen (Z. 35). Außerdem weist uns die Doku des VolatileImages darauf hin, dass dessen Inhalt „verloren“ gehen kann. Wir müssen also bei jedem Zeichenvorgang überprüfen ob dies der Fall war um dann ein neues VolatileImage erstellen zu können. Als letztes müssen wir noch beachten, dass wir bei jedem Neuzeichnen das vorherige angezeigte Image löschen (Z. 63) und das neu gerenderte auch anzeigen (Z. 70).
import java.awt.Canvas;
import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.GraphicsConfiguration;
import java.awt.GraphicsEnvironment;
import java.awt.image.BufferStrategy;
import java.awt.image.VolatileImage;
import javax.swing.JFrame;
public class CanvasTest implements Runnable {
private Canvas c = null;
private GraphicsEnvironment ge = null;
private GraphicsConfiguration gc = null;
private VolatileImage backBuffer = null;
private BufferStrategy strategy = null;
private int x = 0;
public static void main(String[] args) {
new CanvasTest();
}
public CanvasTest() {
c = new Canvas();
c.setPreferredSize(new Dimension(200, 200));
JFrame f = new JFrame("CanvasTest");
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.setSize(new Dimension(200, 200));
f.setLocation(100, 100);
f.add(c);
f.setIgnoreRepaint(true);
f.setVisible(true);
createBackBuffer();
c.createBufferStrategy(2);
strategy = c.getBufferStrategy();
new Thread(this).start();
}
@Override
public void run() {
while (true) {
x += 1;
renderBackBuffer();
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
private void renderBackBuffer() {
if (backBuffer == null || backBuffer.validate(gc) == VolatileImage.IMAGE_INCOMPATIBLE) {
createBackBuffer();
}
Graphics g1 = backBuffer.getGraphics();
g1.clearRect(0, 0, c.getWidth(), c.getHeight());
render(g1);
g1.dispose();
Graphics g2 = strategy.getDrawGraphics();
g2.drawImage(backBuffer, 0, 0, c);
g2.dispose();
strategy.show();
}
private void createBackBuffer() {
ge = GraphicsEnvironment.getLocalGraphicsEnvironment();
gc = ge.getDefaultScreenDevice().getDefaultConfiguration();
backBuffer = gc.createCompatibleVolatileImage(c.getWidth(), c.getHeight());
}
private void render(Graphics gr) {
Graphics g = backBuffer.getGraphics();
g.setColor(Color.BLACK);
g.drawString("" + x, 50, 50);
g.dispose();
}
}
Antoras' Blog 