Inhaltsverzeichnis dieser Seite Schritt 1: Formatierung und Benennung    Schritt 2: Deklarationen Aufschieben    Schritt 3: temporäre Variable "inlinen" (siehe SprachPolizei)    Schritt 4: Methode Extrahieren I    Schritt 5: Vorbereitung für Methode Extrahieren II    Schritt 6: Methode Extrahieren II    Schritt 7: nocheinmal temporäre Variablen "inlinen"    Schritt 8: nochmal Umbenennen    Schritt 9: Und nocheinmal Methode extrahieren    Schritt 10: Methode "inlinen"    Schritt 11: Zugriffsmodifikatoren    Artikel    Ergebnis    Diskussion

Anmerkung: Im Allgemeinen sollte mit CodeRefactoring die intensive Nutzung von UnitTests einhergehen, die nach jedem Schritt die Korrektheit des veränderten Codes prüfbar machen. In diesem einfachen Fall, in dem die meisten CodeRefactorings automatisiert mit Hilfe eines RefactoringBrowsers durchgeführt wurden, habe ich mir das gespart und lediglich auf einen nicht-automatisierten Akzeptanztest zurückgegriffen (soll heißen: ich hab's einfach nach jedem Schritt an einem Beispiel ausprobiert). Wem ein Akzeptanztest nicht genug scheint, mag auch mal die /TestSuite begutachten und ergänzen.

public static int comlen(String s1,String s2) { int i; int checklen=Math.min(s1.length(),s2.length()); for(i=0; i<checklen; i++) { if(s1.charAt(i) != s2.charAt(i)) { return(i); } } return checklen; } private static String StringRetLongestRepeatingSubstring(String s) { int slen=s.length(); String [] list=new String[slen]; int i; int maxlen=0; int imax=-1; int curlen; for(i=0; i<slen; i++) { list[i]=s.substring(i,slen); } Arrays.sort(list); for (i=0; i<slen-1; i++) { curlen=comlen(list[i],list[i+1]); if(curlen>maxlen) { maxlen = curlen; imax=i; } } return list[imax].substring(0,maxlen); }

Schritt 1: Formatierung und Benennung

Zuerst geben wir den Variablen und Methoden aussagekräftigere Namen. Außerdem können wir die Formatierung an unseren CodingStandard angleichen (in diesem Fall wurden die Standard-Einstellungen von VisualAge for Java benutzt). Mit Hilfe von VisualAge und JFactor sieht der Code wenige Mausklicks später so aus:

private static String longestRepeatingSubstring(String string) { int stringLength = string.length(); String[] substrings = new String[stringLength]; int index; int maxlen = 0; int imax = -1; int currentLength; for (index = 0; index < stringLength; index++) { substrings[index] = string.substring(index, stringLength); } Arrays.sort(substrings); for (index = 0; index < stringLength - 1; index++) { currentLength = matchLength(substrings[index], substrings[index + 1]); if (currentLength > maxlen) { maxlen = currentLength; imax = index; } } return substrings[imax].substring(0, maxlen); } public static int matchLength(String string1, String string2) { int index; int minLength = Math.min(string1.length(), string2.length()); for (index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

Für maxlen und imax fand ich es schwer, einen wirklich aussagekräftigen und dennoch nicht allzu langen Namen zu finden. Warten wir ersteinmal ab, vielleicht fällt uns später etwas ein.

http://www.refactoring.com/catalog/renameMethod.html

(Komisch, dass es in dem Katalog keine anderen Umbenennungs-CodeRefactorings gibt. Ist das Umbenennen von Variablen so trivial, dass es keiner Erwähnung wert ist?)

Schritt 2: Deklarationen Aufschieben

Wir verschieben alle Deklarationen lokaler Variablen an die spätmöglichste Stelle. Auf diese Weise wird deutlicher, wo sie überhaupt benötigt werden, außerdem vereinfacht dies spätere CodeRefactorings, wie z.B. das Extrahieren von Methoden.

private static String longestRepeatingSubstring(String string) { int stringLength = string.length(); String[] substrings = new String[stringLength]; for (int index = 0; index < stringLength; index++) { substrings[index] = string.substring(index, stringLength); } Arrays.sort(substrings); int maxlen = 0; int imax = -1; for (int index = 0; index < stringLength - 1; index++) { int currentLength = matchLength(substrings[index], substrings[index + 1]); if (currentLength > maxlen) { maxlen = currentLength; imax = index; } } return substrings[imax].substring(0, maxlen); } public static int matchLength(String string1, String string2) { int minLength = Math.min(string1.length(), string2.length()); for (int index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

http://www.refactoring.com/catalog/replaceAssignmentWithInitialization.html

http://www.refactoring.com/catalog/reduceScopeOfVariable.html

Schritt 3: temporäre Variable "inlinen" (siehe SprachPolizei)

Einige der lokalen Variablen bekommen einmal einen Wert zugewiesen, der sich im Anschluss nicht mehr ändert. Im Falle von stringLength ist das wenig sinnvoll, da string.length() in jeder Hinsicht kaum einen Unterschied macht. currentLength und minLength hingegen machen den Sinn der Berechnung explizit und haben wohl auch einigen Einfluss auf die Performance (auch wenn es natürlich gefährlich ist, dies an dieser Stelle ohne Überprüfung zu raten). Auf jeden Fall sollten wir ihren Charakter jedoch mit Hilfe des Schlüsselwortes final explizit hervorheben.

private static String longestRepeatingSubstring(String string) { String[] substrings = new String[string.length()]; for (int index = 0; index < string.length(); index++) { substrings[index] = string.substring(index, string.length()); } Arrays.sort(substrings); int maxlen = 0; int imax = -1; for (int index = 0; index < string.length() - 1; index++) { final int currentLength = matchLength(substrings[index], substrings[index + 1]); if (currentLength > maxlen) { maxlen = currentLength; imax = index; } } return substrings[imax].substring(0, maxlen); } public static int matchLength(String string1, String string2) { final int minLength = Math.min(string1.length(), string2.length()); for (int index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

http://www.refactoring.com/catalog/inlineTemp.html

Schritt 4: Methode Extrahieren I

Es fällt auf, dass die Methode longestRepeatingSubstring offensichtlich aus zwei in sich geschlossenen Code-Blöcken besteht. In diesem Schritt können wir nun den ersten Block in eine eigene Methode extrahieren (dank JFactor mit wenigen Mausklicken).

private static String longestRepeatingSubstring(String string) { String[] substrings = sortedSubstrings(string); int maxlen = 0; int imax = -1; for (int index = 0; index < string.length() - 1; index++) { final int currentLength = matchLength(substrings[index], substrings[index + 1]); if (currentLength > maxlen) { maxlen = currentLength; imax = index; } } return substrings[imax].substring(0, maxlen); } private static String[] sortedSubstrings(String string) { String[] substrings = new String[string.length()]; for (int index = 0; index < string.length(); index++) { substrings[index] = string.substring(index, string.length()); } Arrays.sort(substrings); return substrings; } public static int matchLength(String string1, String string2) { final int minLength = Math.min(string1.length(), string2.length()); for (int index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

http://www.refactoring.com/catalog/extractMethod.html

Schritt 5: Vorbereitung für Methode Extrahieren II

Vor dem Extrahieren des zweiten Blocks wollen wir uns noch um zwei Kleinigkeiten kümmern:

Zum einen sind da immer noch die Variablen maxlen und imax. Deren Aufgabe ist es, sich die Länge des bisher gefundenen längsten Duplicats, sowie das Duplikat selber (hier in Form des Indizes im Array) zu merken. Es wäre schön, diese enge Zusammengehörigkeit dieser beiden Werte auch explizit auszudrücken. Dafür gibt es eine einfache Lösung: wir merken uns das Duplikat selber als String-Objekt.

Außerdem ist die Nutzung der String-Länge als Abbruch-Bedingung in der for-Schleife unschön: für die zu extrahierende Funktion ergibt dies einen zusätzlich zu übergebenden Parameter, der mit der eigentlichen Funktionalität eigentlich wenig zu tun hat. Was uns hier offensichtlich wirklich interessiert ist nicht die Länge des string, sonder die des substrings-Array (die aufgrund der Konstruktion 'zufällig' identisch sind).

private static String longestRepeatingSubstring(String string) { String[] substrings = sortedSubstrings(string); String currentLongest = ""; for (int index = 0; index < substrings.length - 1; index++) { final int currentLength = matchLength(substrings[index], substrings[index + 1]); if (currentLength > currentLongest.length()) { currentLongest = substrings[index].substring(0, currentLength); } } return currentLongest; } private static String[] sortedSubstrings(String string) { String[] substrings = new String[string.length()]; for (int index = 0; index < string.length(); index++) { substrings[index] = string.substring(index, string.length()); } Arrays.sort(substrings); return substrings; } public static int matchLength(String string1, String string2) { final int minLength = Math.min(string1.length(), string2.length()); for (int index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

(Auch dafür kein passender Eintrag in Fowlers Katalog. Hier könnte es sich vielleicht lohnen, einen entsprechenden Vorschlag zu diskutieren? z.B. ZusammengehörigeVariablenKapseln?)

Schritt 6: Methode Extrahieren II

Jetzt können wir den zweiten Block ebenfalls extrahieren.

private static String longestRepeatingSubstring(String string) { String[] substrings = sortedSubstrings(string); String currentLongest = longestConsecutiveMatch(substrings); return currentLongest; } private static String[] sortedSubstrings(String string) { String[] substrings = new String[string.length()]; for (int index = 0; index < string.length(); index++) { substrings[index] = string.substring(index, string.length()); } Arrays.sort(substrings); return substrings; } private static String longestConsecutiveMatch(String[] strings) { String currentLongest = ""; for (int index = 0; index < strings.length - 1; index++) { final int currentLength = matchLength(strings[index], strings[index + 1]); if (currentLength > currentLongest.length()) { currentLongest = strings[index].substring(0, currentLength); } } return currentLongest; } public static int matchLength(String string1, String string2) { final int minLength = Math.min(string1.length(), string2.length()); for (int index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

http://www.refactoring.com/catalog/extractMethod.html

Schritt 7: nocheinmal temporäre Variablen "inlinen"

Zum Abschluss noch die beiden temporären lokalen Variablen entfernt:

private static String longestRepeatingSubstring(String string) { return longestConsecutiveMatch(sortedSubstrings(string)); } private static String[] sortedSubstrings(String string) { String[] substrings = new String[string.length()]; for (int index = 0; index < string.length(); index++) { substrings[index] = string.substring(index, string.length()); } Arrays.sort(substrings); return substrings; } private static String longestConsecutiveMatch(String[] strings) { String currentLongest = ""; for (int index = 0; index < strings.length - 1; index++) { final int currentLength = matchLength(strings[index], strings[index + 1]); if (currentLength > currentLongest.length()) { currentLongest = strings[index].substring(0, currentLength); } } return currentLongest; } public static int matchLength(String string1, String string2) { final int minLength = Math.min(string1.length(), string2.length()); for (int index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

http://www.refactoring.com/catalog/inlineTemp.html

Schritt 8: nochmal Umbenennen

Die Diskussion mit einer Kollegin (ein schwacher Ersatz für das ProgrammierenInPaaren) hat gezeigt, dass einige Namen noch nicht so recht aussagekräftig (sogar ein wenig fehlleitend) sind. Wir zögern nicht lange und ändern das:

private static String longestRepeatingSubstring(String string) { return longestConsecutiveMatch(sortedTailstrings(string)); } private static String[] sortedTailstrings(String string) { String[] tailstrings = new String[string.length()]; for (int index = 0; index < string.length(); index++) { tailstrings[index] = string.substring(index, string.length()); } Arrays.sort(tailstrings); return tailstrings; } private static String longestConsecutiveMatch(String[] strings) { String currentLongest = ""; for (int index = 0; index < strings.length - 1; index++) { final int currentLength = headingMatchLength(strings[index], strings[index + 1]); if (currentLength > currentLongest.length()) { currentLongest = strings[index].substring(0, currentLength); } } return currentLongest; } public static int headingMatchLength(String string1, String string2) { final int minLength = Math.min(string1.length(), string2.length()); for (int index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

http://www.refactoring.com/catalog/renameMethod.html

Schritt 9: Und nocheinmal Methode extrahieren

HelmutLeitner merkt richtig an, dass sortedTailStrings eigentlich zwei Dinge tut: das String-Array erstellen und dies anschließend sortieren. Wir sollten dies voneinander trennen.

private static String longestRepeatingSubstring(String string) { return longestConsecutiveMatch(sortedTailstrings(string)); } private static String[] sortedTailstrings(String string) { String[] tailstrings = tailStrings(string); Arrays.sort(tailstrings); return tailstrings; } private static String[] tailStrings(String string) { String[] tailstrings = new String[string.length()]; for (int index = 0; index < string.length(); index++) { tailstrings[index] = string.substring(index, string.length()); } return tailstrings; } private static String longestConsecutiveMatch(String[] strings) { String currentLongest = ""; for (int index = 0; index < strings.length - 1; index++) { final int currentLength = headingMatchLength(strings[index], strings[index + 1]); if (currentLength > currentLongest.length()) { currentLongest = strings[index].substring(0, currentLength); } } return currentLongest; } public static int headingMatchLength(String string1, String string2) { final int minLength = Math.min(string1.length(), string2.length()); for (int index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

http://www.refactoring.com/catalog/extractMethod.html

Schritt 10: Methode "inlinen"

die Methode sortedTailStrings hat jetzt eigentlich keine rechte Daseinsberechtigung mehr - sie bläht den Code mehr auf, als dass sie zur Kommunikation beiträgt. Also hinfort mit ihr.

private static String longestRepeatingSubstring(String string) { String[] tailstrings = tailStrings(string); Arrays.sort(tailstrings); return longestConsecutiveMatch(tailstrings); } private static String[] tailStrings(String string) { String[] tailstrings = new String[string.length()]; for (int index = 0; index < string.length(); index++) { tailstrings[index] = string.substring(index, string.length()); } return tailstrings; } private static String longestConsecutiveMatch(String[] strings) { String currentLongest = ""; for (int index = 0; index < strings.length - 1; index++) { final int currentLength = headingMatchLength(strings[index], strings[index + 1]); if (currentLength > currentLongest.length()) { currentLongest = strings[index].substring(0, currentLength); } } return currentLongest; } public static int headingMatchLength(String string1, String string2) { final int minLength = Math.min(string1.length(), string2.length()); for (int index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

http://www.refactoring.com/catalog/inlineMethod.html

Schritt 11: Zugriffsmodifikatoren

JohannesDöbler? merkt zu recht an, dass die Wahl der Zugriffsmodifikatoren etwas willkürlich erscheint. Zwei offensichtliche Möglichkeiten bieten sich an: alle Methoden als public deklarieren, da ja jede auch durchaus auch alleine genutzt werden könnte; oder nur die Startmethode des Algorithmus in das öffentliche Interface übernehmen, um den Startpunkt des Algorithmus zu dokumentieren.

Wir wählen hier die zweite Variante, in dem Bewusstsein, dass wir die Zugriffsbeschränkungen jederzeit lockern können, sollte sich das später einmal als nützlich erweisen:

public static String longestRepeatingSubstring(String string) { String[] tailstrings = tailStrings(string); Arrays.sort(tailstrings); return longestConsecutiveMatch(tailstrings); } private static String[] tailStrings(String string) { String[] tailstrings = new String[string.length()]; for (int index = 0; index < string.length(); index++) { tailstrings[index] = string.substring(index, string.length()); } return tailstrings; } private static String longestConsecutiveMatch(String[] strings) { String currentLongest = ""; for (int index = 0; index < strings.length - 1; index++) { final int currentLength = headingMatchLength(strings[index], strings[index + 1]); if (currentLength > currentLongest.length()) { currentLongest = strings[index].substring(0, currentLength); } } return currentLongest; } private static int headingMatchLength(String string1, String string2) { final int minLength = Math.min(string1.length(), string2.length()); for (int index = 0; index < minLength; index++) { if (string1.charAt(index) != string2.charAt(index)) { return (index); } } return minLength; }

Ergebnis

Der resultierende Code ist gut in der Lage, die Idee hinter dem Algorithmus zu dokumentieren; er ist nur marginal langsamer, um etwa 2 Prozent (Java Hotspot Client VM 1.3.0, Windows).

Für einen Vortrag wurde das RefactoringBeispiel überarbeitet und ist als Foliensatz in pdf ( http://www.informatik.uni-bremen.de/~bschiff/vortraege/refactoring.pdf) oder ppt ( http://www.informatik.uni-bremen.de/~bschiff/vortraege/refactoring.ppt) verfügbar. -- bs

Diskussion

Frage:

Wo ist nun der richtige Platz für diesen Code. A. Im Rahmen eines Projektes? B. Bei der gemeinsamen Verwendung durch mehrere Projekte?

A:

Dort wo er benutzt wird. Wird er an mehreren Stellen benutzt, sollte er wahrscheinlich in die AlgorithmenSammlung?.

B:

In die AlgorithmenSammlung?.

Artikel

• BerndSchiffer, Karsten Violka, Spielzimmer aufräumen, CtMagazin 17/2003, S. 204. In diesem Artikel wird dieses (ein klein wenig abgewandelte) RefactoringBeispiel behandelt.