Benjamins Blog

Caches dienen in der Informatik als Methode, Zugriffe auf bestimmte Daten zu beschleunigen, in dem diese vorgelagert/gepuffert werden. Sie sind in verschiedensten Bereichen zu finden, unter anderem auf Prozessoren, in Festplatten, aber auch in Technologien wie dem Web. Verschiedene Verdrängungsstrategien ermöglichen es, die beschränkte Kapazität eines Caches zu berücksichtigen, so dass nur wichtige Werte im Cache gelagert werden. Least Recently Used (LRU), ist eine solche Strategie, die häufig angewandt wird. Sie sortiert die Werte im Cache nach der letzten Nutzung. Wird auf ein Element über einen längeren Zeitraum nicht mehr zugegriffen, so wird es aus dem Cache verdrängt.

In Java lässt sich ein solcher LRU-Cache besonders einfach implementieren, da die Klasse java.util.LinkedHashMap bereits die wesentlichen Mechanismen unterstützt. Eine HashMap ist eine Hash-Tabelle, die Zugriffe auf Werte über ihre Schlüssel regelt. Zusätzlich verkettet die LinkedHashMap aber die Werte noch in einer Liste, womit auch eine Traversierung in Einfügereihenfolge ermöglicht wird. Mithilfe eines Flags in einem der Konstruktoren kann dieses Verhalten geändert werden, so dass bei jedem Zugriff das angesprochene Element neu in diese Liste eingereiht wird. Damit verwaltet die Liste die Zugriffe und ist Basis für die LRU-Strategie.

Die Methode removeEldestEntry() der LinkedHashMap wird bei jedem Schreibezugriff auf die Map, also nach Einfügeoperationen über put() oder putAll() automatisch aufgerufen und bietet die Möglichkeit, durch Überschreiben der Methode die Verdrängungsstrategie zu implementieren. Diese Methode gibt ein boolean zurück, ob der älteste Eintrag gelöscht werden soll. Es ist auch möglich, innerhalb der Methode selbst die Liste zu manipulieren, dann sollte allerdings die Methode immer false zurückgeben. Für den LRU-Cache reicht es aus, die Größe der Map mit dem gewünschten Maximum zu vergleichen. Ist der Inhalt der Map zu groß, so soll das letzte Element gelöscht werden.

Im Folgenden nun der Code dazu. Zu beachten ist noch, dass es sich um eine threadsichere Klasse handelt, da die Map explizit synchronisiert wird.

import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * A thread-safe LRU cache implementation based on internal LinkedHashMap.
 * 
 * @author Benjamin Erb
 *
 * @param <K> Entry Key Type
 * @param <V> Entry Value Type
 */
public class LRUCache<K, V>
{
	public static final int DEFAULT_MAX_SIZE = 1000;

	private final Map<K, V> internalMap;

	public LRUCache()
	{
		this(DEFAULT_MAX_SIZE);
	}

	public LRUCache(final int maxSize)
	{
		this.internalMap = (Map<K, V>) Collections.synchronizedMap(new LinkedHashMap<K, V>(maxSize + 1, .75F, true)
		{
			private static final long serialVersionUID = 5369285290965670135L;

			@Override
			protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
			{
				return size() > maxSize;
			}
		});
	}

	public V put(K key, V value)
	{
		return internalMap.put(key, value);
	}

	public V get(K key)
	{
		return internalMap.get(key);
	}

}

Diesen Beitrag auf IOException.de lesen.

Anders als manch andere imperative Programmiersprachen, unterstützt Java nur die Rückgabe eines Wertes bei einem Methodenaufruf. Jedoch ist es häufig interessant, mehrere Werte zurückzugeben. Grundsätzlich lassen sich hier zwei Szenarien unterscheiden. Bei der Rückgabe von mehreren gleichartigen Typen wird meist eine Klasse des Collections-Frameworks verwendet, wie zum Beispiel List oder ein Array. Manchmal will man aber auch völlig verschiedene Typen gemeinsam zurückgeben. Gängige Praxis ist es hier, ein Object-Array zurückzugeben und dann quasi beim Implementieren festzulegen, von welchem Typ die einzelnen Werte sind und entsprechen zurückzucasten. Dies ist leider weder typsicher, noch lässt sich die vorherige Festlegung im Code erzwingen. Abhilfe schafft hier eine generische Holder-Klasse, die einzelnen Werte typsicher kapselt und als einziger Rückgabewert verwendet werden kann.

Hier ein Beispiel für die Rückgabe über ein Object-Array:

private Object[] doItUnchecked()
{
	String s = "foo";
	Date d = new Date();

	return new Object[] { s, d };
}

Aufruf:

// unchecked variant: dangerous!
Object[] returnValues = t.doItUnchecked();
String s = (String) returnValues[0];
Date d = (Date) returnValues[1];

Eine generische Holderklasse (hier: immutable):

/**
 * Immutable holder type for two values.
 * 
 * @author Benjamin Erb
 *
 * @param <F> type of first value
 * @param <S> type of second value
 */
public class PairHolder<F, S>
{
	private final F first;
	private final S second;
	
	public PairHolder(F first, S second)
	{
		this.first = first;
		this.second = second;
	}
	
	public F getFirst()
	{
		return first;
	}
	
	public S getSecond()
	{
		return second;
	}
}

Verwendung in Methode:

private PairHolder<String, Date> doItChecked()
{
	String s = "foo";
	Date d = new Date();

	return new PairHolder<String, Date>(s, d);
}

Aufruf:

// check variant: safe already at compile-time
PairHolder<String, Date> h = t.doItChecked();
String s = h.getFirst();
Date d = h.getSecond();

Die Holderklasse lässt sich auch noch beliebig erweitern, um Tripel, Quadrupel etc. zu halten. Wer für 2-Tupel keine eigene Klasse implementieren möchte, kann übrigens auf AbstractMap.SimpleEntry<K,V> oder AbstractMap.SimpleImmutableEntry<K,V> zurückgreifen.

Viele Netzwerkprotokolle teilen ihre Kommunikationsentitäten in Pakete oder Nachrichten auf. Manche Protokolle erwarten außerdem eine sequentielle Abarbeitung (z.B. TCP auf Transportebene), auch wenn die darunterliegenden Protokollschichten dass nicht unbedingt unterstützen. Für die Implementierung eines Nachrichtenpuffers für RTSP-Nachrichten, die ungeordnet ankommen können, aber sequentiell abgearbeitet werden müssen, habe ich eine entsprechende Datenstruktur in Java erstellt. RTSP-Nachrichten besitzen ein Cseq-Header-Feld, welches die einzelnen Nachrichten durchnummiert und als ordnendes Element genutzt werden kann.

Die folgende generische Implementierung erwartet, dass alle Nachrichtenelemete eindeutige und miteinander vergleichbare Identifier besitzen. Desweiteren erlaubt diese Implementierung zwar das parallele Schreiben in die Queue, allerdings sollte das Lesen durch einen einzelnen Thread realisiert werden. Ansonsten kann die Ordnung nach dem Entnehmen aus der Queue durch unterschiedlich lange Laufzeiten der Worker-Threads wieder verloren gehen. Außerdem realisiert diese Implementierung die sequentielle Ordnung eines vollständigen Nachrichtenstroms. Nachrichtenverluste oder Timeouts werden nicht behandelt. Hierfür eignen sich eher Automatic repeat request Protokolle.
Vollständigen Artikel lesen...

Bei der Entwicklung größerer Java-Projekte kann schnell die Übersicht verloren gehen. Zum Glück bietet Eclipse eine Vielzahl von Shortcuts und Funktionen, um sich auch noch bei einer Vielzahl von Klassen zurecht zu finden.

• Strg + 3
  Öffnet den intelligenten Quick Access Dialog.


• Strg + Shift + R
  Öffnet einen Schnelldialog zum Öffnen einer Ressource. Ist insbesondere hilfreich, um eine Datei mit bekanntem Dateinamen direkt zu öffnen, ohne im Package Explorer zu suchen.
  
• Strg + Shift + T
  Öffnet einen Schnelldialog zum Öffnen einer Java-Ressource. In der Auswahl kann der Name der Klasse/Interface/etc. direkt eingegeben werden.
  
• Strg + Linksklick auf Klassenname
  Sprung zum Quelltext der Klasse, auf die im Editor geklickt wird.
  
• Strg + T
  Übersicht der Vererbungshierarchie der Klasse, die sich im Fokus des Editors befindet. Nochmaliges Drücken von Strg + T dreht die Hierarchierichtung (Superklassen/Subklassen) um.
  
• Strg + O
  Übersicht der Membervariablen und Methoden der aktuellen Klasse. Nochmaliges Drücken von Strg + O zeigt zusätzlich geerbte Member an.
  
• Strg + Shift + G
  Sucht nach Verwendungen der Methode im Fokus des Editors in alles Klassen der Workspaces.
  
• Strg + . und Strg + '+'
  Sprung durch die Quelltextzeilen mit Warnungen


• Strg + L
  Öffnet Dialog für einen Sprung in eine bestimmte Codezeile.
  
• Strg + E
  Zeigt Liste aller offenen Editors-Tabs an und ermöglicht Direktauswahl eines offenen Editorstabs per Texteingabe.
  
• Strg + Bild Auf und Strg + Bild Ab
  Springen durch die offenen Editor-Tabs.
  
• Alt + ← und Alt + →
  Springen durch die Historie der geöffneten Tabs.

Dieser Post ist ein Beitrag auf ioexception.de

Jedem Eclipse-Benutzer dürfte es bekannt vorkommen, wenn langsam die ganzen Projekte den Package Explorer füllen und dabei die Übersicht verloren geht. Natürlich besteht hier die Möglichkeit, durch verschiedene Workspaces die einzelnen Projekte oder Projektgruppen zu separieren, jedoch stellt eine Unterteilung in Workspaces eine sehr restriktive Trennung dar.
Abhilfe schaffen in Eclipse die so genannten Working Sets – wie bei allen Eclipse-Funktionen muss man halt erstmal überhaupt davon wissen. Working Sets lassen sich über New => Java => Java Working Set erstellen und erzeugen Überordner, in denen sich Projekte gruppieren lassen. Um im Package Explorer die Ansicht nach Working Sets aufzuschlüsseln, müssen diese jedoch als Top Level Elements gewählt werden:

Für die Wahl eines Informatikstudiums sollte es völlig irrelevant sein, ob man bereits erste Programmiererfahrungen besitzt oder noch nie eine Zeile Code geschrieben hat. Analytisches und logisches Denkvermögen sowie fehlende Berührungsängste mit Mathematik sind um einiges wichtiger als Wissen zu aktuellen Programmiersprachen, denn Programmierung ist selbst eher ein Werkzeug der Informatik, als zentraler Lehrinhalt eines universitären Studiums. Genauso wenig ist ein sonderlich profundes Vorwissen über Computer notwendig, wie bereits ein bekannter niederländischer Informatiker sagte:

„Computer science is no more about computers than astronomy is about telescopes."
Edsger Dijkstra

Trotzdem muss man natürlich lernen, seine Werkzeuge beherrschen zu können. Und leider haben erfahrungsgemäß Studierende im ersten Semester ohne Programmiererfahrungen einen zusätzlichen Aufwand dadurch, parallel zu den Vorlesungen, die eben keinen Programmierkurs darstellen, sondern eher abstrakte Konzepte vermitteln, auch noch das ganz praktische und angewandte Programmieren zu erlernen.

Aus diesem Grund wurde an der Uni Ulm vor einem Jahr auf Initiative von uns, der Fachschaft Informatik, ein aus Studiengebühren finanzierter Kurs eingeführt, der in die Java-Programmierung einführt und wirklich im wahrsten Sinne des Wortes bei null anfängt. Bei diesem freiwilligen Kurs werden Studierende intensiv bei ihren ersten Programmierschritten begleitet, was vor allem durch ein hohes Betreuungsverhältnis mit vielen Tutoren möglich ist. Neben Übungsblättern entstand nun bei der zweiten Durchführung der sogenannten „Programmierstarthilfe“ auch ein Skript als Einführung in die Java-Programmierung. Da ich als Tutor diese Veranstaltung in ihrem ersten Jahr mitbetreut habe, war ich auch an der Entstehung dieses Skripts beteilgt, an dem ansonsten vor allem Guido und Marcus gearbeitet haben, aber auch die übrige Team. Wir haben uns dazu entschlossen, das entstandene Werk unter einer Creative Commons-Lizenz der Öffentlichkeit zugänglich zu machen. Es entstand zwar in oben genanntem Kontext, kann aber auch völlig losgelöst zum Selbststudium gelesen werden. Es richtet sich weder ausschließlich an InformatikerInnen, noch sind irgendwelche Vorkenntnisse notwendig. Somit sollte es mit diesem Skript für quasi jeden möglich sein, erste Erfahrungen mit der Programmierung und dem Programmieren in Java zu machen

Auf 90 Seiten werden unter anderem grundlegende Konzepte wie Datentypen, Kontrollstrukturen, Schleifen, Arrays, Methoden, Rekursion oder einfache Objektorientierung erklärt. Ein weiteres Kapitel zeigt außerdem auf, in welche Richtungen es noch weitergeht. Hier werden Themen wie Vererbung, Interfaces, Autoboxing, Enum-Typen, Generics, Collections, Multithreading und GUI-Programmierung angerissen. Dieses weiterführende Kapitel sowie die Kapiel über abstrakte Datenstrukturen und über API-Dokumentation stammen übrigens von mir.

Download: Skript: Java Grundlagen - Programmierstarthilfe (PDF)

Das Skript steht unter der Creative Commons Attribution-NonCommercial-ShareAlike 2.0 Lizenz und kann in der Version vom April 2009 heruntergeladen werden.

Seit Version 6 Update 7 besitzt das Java Development Kit ein weiteres hilfreiches Entwicklungstool, nämlich VisualVM. Die Anwendung ermöglicht das Überwachen und Profiling laufender Java-Anwendungen (auch entfernter) virtueller Maschinen. Neben Merkmalen wie dem aktuellen Verbrauch an Speicher, der Größe des Heaps, Anzahl von Threads und geladener Klassen laufender Prozesse lassen sich zusätzlich aus einem erzeugbaren Heapdump zur Laufzeit Informationen über instanziierte Objekte erfragen, wie es vom Eclipse-Debugger bekannt ist. Auch die Garbage Collection kann hier manuell ausgelöst werden. Threads werden inklusive ihrer Zustände chronologisch visualisiert. Dies ist insbesondere beim Debugging von Anwendungen interessant, die intensiv Gebrauch von Multithreading machen. Durch die Anzeige der Zustände der Threads werden Monitore (Locks) sichtbar gemacht. Außerdem können über einen Threadump die einzelnen Callstacks der Threads inspiziert werden.

Im CPU-Profiling können die Anwendungen in Echtzeit daraufhin untersucht werden, welche Methoden wie oft aufgerufen werden und wieviel CPU-Zeit sie benötigen, was bei der Suche nach möglichen Optimierungsansätzen hilfreich sein könnte. Das Memory-Profiling zeigt die Anzahl von Instanzen, den Speicherverbrauch, sowie den prozentualen Anteil am gesamten Speicherplatz von Klassen und primitiven Datentypen an sowie Informationen zur Garbage Collection.

Durch Plugins lässt sich das Programm noch um weitere Funktionen ergänzen. Entstanden ist das Projekt aus der Sun-eigenen NetBeans-IDE und basiert auch heute noch auf dessen NetBeans-RCP Framework. Zu finden ist es bei jeder JDK Installation ab 6u7 im Ordner bin/jvisualvm. Es lässt sich für ältere JDK-Versionen über einen Download von der Projektseite separat installieren .

Automaten sind nicht nur in der theoretischen Informatik ein wichtiges Werkzeug im Bereich der formalen Sprachen zur Überprüfung von Sprachzugehörigkeiten. Eine davon abgeleitete Anwendung ist die Mustererkennung in Zeichenketten mithilfe regulärer Ausdrücke. Aber auch viele Protokolle verteilter Systeme (z.B. TCP) greifen das Konzept von Zustandsautomaten auf, um abhängig von verschiedenen internen Zuständen auf Ereignisse differenziert zu reagieren. Natürlich müssen diese Zustandsautomaten bei der Implementierung von Protokollen auch in Software abgebildet werden. In diesem Artikel möchte ich anhand eines einfachen DFAs aufzeigen, wie solche Zustandsautomaten unter Anwendung des State Patterns in Java realisierbar sind.

In diesem Beispiel soll ein DFA konstruiert werden, der aus allen möglichen Zeichenfolgen bestehend aus Einsen und Nullen genau diejenigen akzeptiert, in denen die Teilworte 01 und 10 gleich oft vorkommen. Der nebenstehende Graph verdeutlicht die Funktionsweise des Automaten. Neben dem Startzustand (S) gibt es zwei gültige Endzustände (A,X) mit gleicher Anzahl von Vorkommen, sowie zwei Zustände (B,Y) die keinen gültigen Endzustand darstellen.

Möchte man nun eine solche Konstruktion implementieren, so muss man Zustände, Übergänge und gültige Kombinationen abbilden. Das State Pattern der GoF als Verhaltensmuster bietet sich bei objektorientierten Sprachen an, da es übersichtlicher, sauberer und erweiterbarer ist als Kaskaden von If-Abfragen oder Switch-Statements-Konstrukten. Die Grundidee hierbei ist, Zustände mit zugehörigen Übergängen in eigene Objekte auszulagern und dem zustandsbehafteten Objekt die entsprechende Referenz auf seinen aktuellen Zustand zu übergeben. Änderungen delegiert dieses zustandsbehaftete Objekt dann an sein aktuelles Zustandsobjekt, welches eventuell nach dem Übergang ersetzt wird. In Java bietet es sich an, die Zustände als Enum-Instanzen zu realisieren und diese ein Interface implementieren zu lassen, welches die Übergange definiert. Zusätzlich lassen sich die Zustände, also Enum-Instanzen, darauf hin abfragen, ob sie einen gülitgen finalen Zustand darstellen.
Die Automaton-Klasse stellt nun das eigentliche Objekt dar, was zustandsbehaftet ist, jedoch mit ausgelagerter Behandlung der Zustände:

Transitions.java - Auflistung der Übergänge als Interface

/**
 * Interface listing possible transitions to be implemented by states
 */
public interface Transitions
{
	public void readZero(Automaton a);

	public void readOne(Automaton a);
}

State.java - Zustände als Enum-Typen

/**
 * Enum type for states
 */
public enum State implements Transitions
{
	/**
	 * Initial State - S
	 */
	S
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(X);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(A);
		}

		@Override
		public boolean isFinal()
		{
			return true;
		}
	},

	/**
	 * Final State - A
	 */
	A
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(B);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(A);
		}

		@Override
		public boolean isFinal()
		{
			return true;
		}
	},

	/**
	 * State -B
	 */
	B
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(B);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(A);
		}

		@Override
		public boolean isFinal()
		{
			return false;
		}
	},

	/**
	 * Final State - X
	 */
	X
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(X);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(Y);
		}

		@Override
		public boolean isFinal()
		{
			return true;
		}
	},

	/**
	 * State -Y
	 */
	Y
	{
		@Override
		public void readOne(Automaton a)
		{
			a.setState(X);
		}

		@Override
		public void readZero(Automaton a)
		{
			a.setState(Y);
		}

		@Override
		public boolean isFinal()
		{
			return false;
		}
	};

	/**
	 * Is state final?
	 * @return true if final
	 */
	abstract public boolean isFinal();
}

Automaton.java - Das zustandsbehaftete Objekt inklusive Test in der Main-Methode.

/**
 * Automaton class
 */
public class Automaton
{
	//Initial state
	private State state = State.S;

	public void setState(State s)
	{
		this.state = s;
	}

	public void readZero()
	{
		//Delegate...
		state.readZero(this);
	}

	public void readOne()
	{
		//Delegate...
		state.readOne(this);
	}

	public boolean isInFinalState()
	{
		//Delegate...
		return state.isFinal();
	}

	public static void main(String[] args)
	{
		Automaton a = new Automaton();
		String s1 = "11010101";
		for (char c : s1.toCharArray())
		{
			switch (c)
			{
				case '1':
					a.readOne();
					break;
				case '0':
					a.readZero();
					break;
			}
		}
		System.out.println(a.isInFinalState()); //true...
	}
}

Dieses Beispielprogramm mit einem DFA habe ich zum leichteren Verständis gewählt, natürlich lassen sich mit diesem Pattern weit aus komplexere Abläufe modellieren. So könnte der Automat zum Beispiel ein Buch-Objekt einer Bücherei sein und die Übergänge Aktionen wie das Ausleihen, Verlängeren oder Zurückgeben des Buches. Die Zustände als Enum-Typen würden dann auch mehr Geschäftslogik enthalten als das bloße Verändern das Zustands wie hier in diesem Beispiel.

Hier eine kleine Java-Methode, um Weiterleitungen des URL-Dienstes TinyURL aufzulösen. Der Methode wird die ID der URL als String übergeben, zurückgegeben wird ein URI-Objekt mit der entsprechenden Weiterleitung. Existiert die ID nicht, so wird eine IllegalArgumentException geworfen. Die Abfrage wird direkt auf HTTP-Ebene über die Methode HEAD durchgeführt. Aus diesem Grund sollte bei einem unsicheren Einsatz die ID zuvor überprüft werden, um Injektionen in den HTTP-Request zu verhindern.

	/**
	 * Resolves a TinyUrl redirect
	 * @author Benjamin Erb
	 * @param id http://tinyurl.com/{id}
	 * @return Redirected URI
	 * @throws IOException on network problems
	 * @throws IllegalArgumentException on unknown id 
	 */
	public static URL resolveTinyUrl(String id) throws IOException, IllegalArgumentException
	{
		Socket s = new Socket(InetAddress.getByName("tinyurl.com"),80);
		BufferedWriter w = new BufferedWriter(new OutputStreamWriter(s.getOutputStream()));
		BufferedReader r = new BufferedReader(new InputStreamReader(s.getInputStream()));
		w.append("HEAD /"+id+" HTTP/1.0\r\nHost: tinyurl.com\r\n\r\n").flush();
		String response;
		Matcher m;
		Pattern p = Pattern.compile("^Location:\\s([^\\r\\n]+)"); 
		while((response = r.readLine())  != null)
		{
			if((m = p.matcher(response)).find())
			{
				w.close();
				r.close();
				s.close();
				return new URL(m.group(1)); 
			}
		}		
		w.close();
		r.close();
		s.close();
		throw new IllegalArgumentException("Unknown TinyURL id");
	}

Das Singleton-Pattern ist ein Erzeugungsmuster aus dem Klassiker Design Patterns der Gang of Four. Es beschreibt, wie man von einer Klasse gezielt nur eine einzige Instanz erzeugt und darauf einen einfachen Zugriff möglich ist. Typische Einsatzzwecke des Patterns sind zum Beispiel Logger, die von überall im Programm Ereignisse protokollieren sollen oder Manager-Klassen, wie dem Toolkit.getDefaultToolkit(), das bei java.awt eine betriebssystemspezifische Instanz zurückgibt. Das Pattern ist nicht ganz unumstritten, da es Ähnlichkeiten mit unliebsamen globalen Variablen aufweist und außerdem die Testbarkeit von Klassen erschwert, doch hierum soll es an dieser Stelle nicht gehen, sondern viel mehr darum, wie man dieses Pattern in Java implementiert. Vollständigen Artikel lesen...