Quadrat- und Kubikwurzeln berechnen vor 30 Jahren und heute ;-)

Unsere Rechner können sehr viele Rechenoperationen schon auf der CPU erledigen, wenn es darum geht, mit den Standardtypen (z.b. double, dem gängigen 8-Byte-Fließkommaformat) zu rechnen. Das war gegen Anfang der 80er Jahre noch nicht so, da konnten typische CPUs nur gerade mit 8-Bit-Ganzzahlen addieren, subtrahieren und ein paar Bit-Operationen ausführen und doch ließ sich daraus alles aufbauen. Langzahladdition und -subtraktion waren trivial, Multiplikation und Division etwas schwieriger, aber noch gut machbar. Aber für die Quadratwurzeln musste man schon etwas genauer überlegen. Das mitgelieferte Basic konnte das für 5-Byte-Fließkommazahlen, aber das Verfahren war einfach nur dumm und langsam, den es wurde der Logarithmus genommen, halbiert und dann die Exponentialfuntion. Mathematisch völlig richtig, aber eben langsam und mit unnötigen Rundungsfehlern behaftet. Wer sich ein bisschen mit dem Thema auskennt, landet recht schnell bei dem Newton-Verfahren. Man schätzt die Quadratwurzel, z.B. von 2, dividiert 2 durch den Schätzwert und nimmt dann den Mittelwert von Schätzung und Quotient für die nächste Iteration. Zu offensichtlich, um es nicht so zu machen und in der Praxis auch ganz brauchbar. Es gibt aber ein Verfahren, wie man früher ähnlich wie die Division auch die Quadratwurzeln „handschriftlich“ berechnen konnte und dieses Verfahren lässt sich sehr gut verwenden, um eine Quadratwurzelberechnung zu schreiben. Hier ist eine Ruby-Implementierung, die von Ganzzahlen ausgeht:
Zu einer ganzen Zahl x \ge 0 werden ganze Zahlen r \ge 0 und s \ge 0 gesucht so dass x = r + s^2 und (s+1)^2 > x gilt.

  def check_is_int(x, name="x")
    raise TypeError, "#{name}=#{x.inspect} must be Integer" unless x.kind_of? Integer
  end

  #
  # helper method for internal use: checks if word_len is a reasonable
  # size for splitting a number into parts
  #
  def check_word_len(word_len, name="word_len")
    raise TypeError, "#{name} must be a positive number <= 1024" unless (word_len.kind_of? Fixnum) && word_len > 0 && word_len <= 1024
    word_len
  end

  #
  # split number (Integer) x into parts of word_len bits each such
  # that the concatenation of these parts as bit patterns is x
  # (the opposite of merge_from_words)
  #
  def split_to_words(x, word_len = 32)
    check_word_len(word_len)
    check_is_int(x, "x")
    m = x.abs
    s = (x <=> 0)
    bit_pattern = (1 << word_len) - 1
    words = []
    while (m != 0 || words.length == 0) do
      w = m & bit_pattern
      m = m >> word_len
      words.unshift(w)
    end
    if (s < 0) then
      words[0] = -words[0]
    end
    words
  end


  #
  # calculate the an integer s >= 0 and a remainder r >= 0 such that
  # x = s**2 + r and s**2 <= x < (s+1)**2
  # the wordwise algorithm is used, which works well for relatively
  # large values of x.  n defines the word size to be used for the
  # algorithm.  It is good to use half of the machine word, but the
  # algorithm would also work for other values.
  #
  def sqrtw_with_remainder(x, n = 16)
    check_is_int(x, "x")
    check_is_int(n, "n")

    n2 = n<<1
    n1 = n+1
    check_word_len(n2, "2*n")

    s = (x <=> 0)
    if (s == 0) then
      return [0, 0]
    elsif (s < 0)
      a = sqrtw_with_remainder(-x)
      return [ Complex(0, a[0]), a[1]]
    end

    xwords = split_to_words(x, n2)
    if (xwords.length == 1) then
      return sqrtb_with_remainder(xwords[0])
    end

    xi = (xwords[0] << n2) + xwords[1]
    a  = sqrtb_with_remainder(xi)
    yi = a[0]
    if (xwords.length <= 2) then
      return a
    end

    xi -= yi*yi
    2.upto(xwords.length-1) do |i|
      xi = (xi << n2) + xwords[i]
      d0 = (yi << n1)
      q  = (xi / d0).to_i
      q0 = q
      j  = 0
      was_negative = false
      while (true) do
        d = d0 + q
        r = xi - (q * d)
        break if (0 <= r && (r < d || was_negative))
        if (r < 0) then
          was_negative = true
          q = q-1
        else
          q = q+1
        end
        j += 1
        if (j > 10) then
          break
        end
      end
      xi = r
      yi = (yi << n) + q
    end
    return [ yi, xi ]
  end

  #
  # calculate an integer s >= 0 and a remainder r >= 0 such that
  # x = s**2 + r and s**2 <= x < (s+1)**2
  # the bitwise algorithm is used, which works well for relatively
  # small values of x.
  #
  def sqrtb_with_remainder(x)
    check_is_int(x, "x")

    s = (x <=> 0)
    if (s == 0) then
      return [0, 0]
    elsif (s < 0)
      a = sqrtb_with_remainder(-x)
      return [ Complex(0, a[0]), a[1]]
    end

    xwords = split_to_words(x, 2)
    xi = xwords[0] - 1
    yi = 1

    1.upto(xwords.length-1) do |i|
      xi = (xi << 2) + xwords[i]
      d0 = (yi << 2) + 1
      r  = xi - d0
      b  = 0
      if (r >= 0) then
        b  = 1
        xi = r
      end
      yi = (yi << 1) + b
    end
    return [yi, xi]
  end

Daraus lässt sich dann relativ einfach eine Quadratwurzelfunktion mit entsprechender Nachkommstellenberechnung bilden.

Witzerweise lässt sich das Verfahren auch für Kubikwurzeln sinngemäß anwenden.

Hier ein kleiner Test:

irb(main):138:0> sqrtw_with_remainder(2)
=> [1, 1]
irb(main):139:0> sqrtw_with_remainder(200)
=> [14, 4]
irb(main):140:0> sqrtw_with_remainder(20000)
=> [141, 119]
irb(main):141:0> sqrtw_with_remainder(2000000)
=> [1414, 604]
irb(main):142:0> sqrtw_with_remainder(200000000000000000000000000000000000000000000000000000000000)
=> [447213595499957939281834733746, 228299936041363866321288807484]
irb(main):143:0> sqrtw_with_remainder(2000000000000000000000000000000000000000000000000000000000000)
=> [1414213562373095048801688724209, 1974464361663955412145937324319]
irb(main):144:0> sqrtw_with_remainder(3000000000000000000000000000000000000000000000000000000000000)
=> [1732050807568877293527446341505, 3021967735564464902990914334975]
irb(main):145:0> sqrtw_with_remainder(3)
=> [1, 2]
irb(main):146:0> sqrtw_with_remainder(300)
=> [17, 11]
irb(main):147:0> sqrtw_with_remainder(30000)
=> [173, 71]
irb(main):148:0> sqrtw_with_remainder(3000000)
=> [1732, 176]
Share Button

Einmal entwickeln – überall installieren

Das ist eine der großen Versprechungen von Java gewesen. Nun gab es drei oder bei genauerem Hinschauen etwas mehr als drei Varianten von Java, also „Micro-Edition“ (JavaME) für Toaster, Radios und Mobiltelefone, „Enterprise-Edition“ (JavaEE, JEE oder J2EE) für die ganz großen Server, die Sun auch gerne selber verkauft hat und „Standard-Edition“ (JavaSE) für „normale“ Aufgaben. Diese Aufteilung hat sich ein bisschen relativiert. Von JavaME hört man heute weniger, weil die Mobiltelefone heute leistungsfähig genug für JavaSE wären, wenn man es sich antun wollte, sogar für JavaEE. Die Programmierung von Toastern, Radios und Waschmaschinen ist ein Spezialgebiet, „embedded-Entwicklung“, mit dem man auch in der Informatik nur selten zu tun hat und diese Dinge nimmt man auch im Alltag kaum als Software wahr. JavaEE war in den ersten 10 Jahren einfach nur ein Rezept, um Programme langsamer, größer, komplizierter, störanfälliger und schlechter wartbar zu machen. Und man hatte plötzlich Abhängigkeiten vom Applikationsserver, die zwar idealerweise nicht den Programmtext selbst, wohl aber die Tonnen von XML-Konfiguration und die Deployment-Prozesse betraf. Da haben sich dann andere Frameworks entwickelt, zum Beispiel Spring, die etwas weniger schwerfällig daherkamen. Und für die Persistenz in JavaEE etablierte sich Hibernate und Eclipselink, was auch in JavaSE verwendbar ist. Nennt man nun eine Applikation, die mit Spring und Hibernate arbeitet, JavaEE oder JavaSE? Ich habe beides gehört. Jetzt sollte man bitte nicht versuchen, eine Applikation so zu entwickeln, dass sie wahlweise mit Spring und dem „Original-JavaEE“ läuft.

In den späten 90er-Jahren hatten Browser JavaSE eingebaut, damit man Applets schreiben konnte. So zeichnete es sich ab, dass jeder Rechner, den man kauft, eine gewisse Ausstattung bekommt, zum Beispiel einen Browser und eine Java-Installation. Dann hätten Java-Programme auf allen Desktop-Rechnern laufen können. Vielleicht müsste die Version hoch genug sein, weil Java sich natürlich weiterentwickelt hat und gelegentlich auch auf JavaVM-Ebene Erweiterungen nötig waren. Mit einem gute Software-Update-Mechanismus, wie wir ihn heute bei Linux-Distributionen oder bei den meisten Mobiltelefonen finden, hätte sich das lösen lassen. Dumm war nur, dass es eine Zeit gab, wo noch viele Anwender ein Modem mit 56k hatten und wo eine Java-Installation 80 MB groß war. Dann ist aber irgendwann, etwa nach dem Jahr 2000, die Java-Installation auf gängigen PCs selten geworden und man musste Endkunden bei der Installation von Java (wohlgemerkt 80 MB über das Modem) supporten, um ihre Java-Installation zum Laufen zu bringen. Das konnte sich nur in wenigen Fällen lohnen und man hat lieber auf Web-Applikationen gesetzt, was sich weitgehend durchgesetzt hat. Und die Browser können heute JavaScript, aber kein Java.

Bei den Mobiltelefonen gab es einige vielversprechende Anläufe, um Software-Entwicklung für eine Vielzahl von Geräten auf einmal zu ermöglichen. JavaME war eigentlich keine schlechte Idee, weil das auch auf recht kleinen Telefonen lief und auf den dicksten Smartphone könnte man es auch haben. Ein anderer Ansatz, der vielleicht ein bisschen weniger bekannt ist, ist die Verwendung des Qt-Frameworks für C++. Das ermöglicht auch auf einer Vielzahl von Geräten vom Arbeitsplatzrechner mit Linux oder MS-Windows bis zum Mobiltelefon „dieselbe“ Software laufen zu lassen, natürlich mit kleinen Anpassungen, um dem Benutzerinterface Rechnung zu tragen, und mit einer Neucompilierung für die Zielplattform. Diesen Weg hat Nokia verfolgt, als sie noch ernsthaft Mobiltelefone entwickelt haben und Qt-Applikationen liefen auf Symbian und Linux-Geräten (N900, N9), womit die Umstellung von Symbian auf Meego-Linux innerhalb kürzester Zeit eine reiche Auswahl an Apps für die neue Plattform ermöglicht hätte. Da Nokia sich aus der Mobiltelefonieentwicklung weitgehend und aus Meego und Symbian ganz zurückgezogen hat, bietet sich hier die Chance für neue Anbieter, wie zum Beispiel Jolla, mit dem Knowhow der ehemaligen Nokia-Mitarbeiter und deren vielversprechenden Ideen in den Markt einzusteigen und einen Teil der Rolle, die Nokia einmal hatte, zu übernehmen. Für native Apps auf dem Mobiltelefon ist aber aus heutiger Sicht die Dalvik-Engine von Android das mit Abstand zukunftsträchtigste Modell. Das ist letztlich eine weitere Java-„Edition“ und ermöglicht immerhin eine Lauffähigkeit auf dem überwiegenden Teil der neu verkauften Smartphones. Neue Linux-basierte Mobiltelefon-Betriebssysteme haben zum Teil die Möglichkeit integriert, für Dalvik geschriebene Android-Apps auszuführen. Aber einige Anbieter fahren bewusst die Schiene der Inkompatibilität ihrer Geräte und verlangen so eine Eigeneentwicklung nur für diese. Das schöne daran ist, dass dieser Ansatz scheitern wird, sobald die Marktanteile nicht mehr so groß sind. Hier werden sich wahrscheinlich Web-Applikationen durchsetzen.

Was Java betrifft, ist dessen Domäne heute neben Android-Telefonen im Serverbereich. Tatsächlich laufen Java-Applikationen ja mit hinreichend neuen JavaVM-Installationen oft auf allen Servern, wenn bei der Entwicklung gewisse Einschränkungen beachtet wurden. Ein Java-Programm, das seine Konfiguration in „C:/Programme/myCoolApp/config.properties“ sucht, wird auf Linux-Servern eher nicht das gewünschte finden, obwohl die „forward-slashes“ in Java-Programmen auch unter MS-Windows empfehlenswert sind und funktionieren. Aber es gibt immer noch genug potentielle Probleme, zum Beispiel mit Bibliotheken, die von der Java-Applikation benötigt werden, aber die inkomptabil zu der gewünschten Tomcat-Version sind, weil dort eine ältere Version derselben Bibliothek integriert und verwendet wird. Bis zu einem gewissen Grade lassen sich solche Probleme lösen und man findet immer wieder coole Ideen, die das ganz vollständig lösen wollen, wie z.B. OSGi. Mit entsprechendem Aufwand geht es auch tatsächlich in vielen Fällen, aber gewisse Bibliotheks-Inkomptabilitäten lassen sich nicht so leicht aus der Welt schaffen. so bleibt das „write once – run everywhere“ ein Versprechen, an dem viel Wahres dran ist, das aber auch seine Grenzen hat.

Nebenbei bemerkt ist das gar nicht so sehr die Eigenheit von Java. Qt mit C++ wurde schon erwähnt. Aber auch Perl, Ruby, Python, Oracle, C# (mit Mono), Lua, TeX und viele andere können ein ähnliches Versprechen wie Java abgeben und dieses ähnlich gut und mit ähnlichen Einschränkungen halten. Vielleicht ist es in Java schwieriger, nicht-triviale Dinge zu tun, die spezifisch für eine Plattform sind. Und vielleicht reicht Java in gewissen Bereichen mit diesem Versprechen etwas weiter als andere, aber für typische Server-Applikationen stimmt das „write-once-run-everywhere“ für Ruby-on-Rails mindestens genauso wie für Java-Web-Applikationen.

Share Button

PDF mit Ruby erzeugen

Es gibt viele Libraries, die mit Ruby, Perl, Java oder was auch immer man so verwendet, PDF-Dateien erzeugen. Das Prinzip ist oft so, dass man eine Art Formular erstellt, in dem dann Platzhalter mit Daten aus dem Programm gefüllt werden. Im Prinzip sehr ähnlich wie das Generieren von HTML-Seiten in vielen Web-Applikationen.

Heute verwendet man für Webapplikationen mit Ruby on Rails HAML. Die älteren Rails-Entwickler erinnern sich aber noch teilweise daran, dass man früher einmal erb verwendet hat. Man hat also das HTML so hingeschrieben, wie es halt aussieht und die Platzhalter dann mit so etwas wie <%= some_ruby_code => ausgefüllt. Es war sogar möglich, Schleifen und Bedingte Codeteile zu haben, dafür hat man dann so etwas wie

<% number.times do |x| %>
...
<%= function(x) %>
...
<% end %>

geschrieben. In HAML ist das alles viel schöner, weil man eine Syntax hat, die den Ruby und den HTML-Code viel eleganter miteinander integriert. Aber HAML ist für HTML gemacht.

Um nun PDF-Dateien zu generieren, lohnt es sich, Text-Formate anzusehen, die zu PDF konvertiert werden können. Möglich wäre zum Beispiel PostScript, aber auch die Formate heutiger Office-Systeme wie MS-Office und LibreOffice und OpenOffice sind grundsätzlich dokumentiertes XML, also durchaus zugänglich, wenn man viel Zeit hat. Ob nun XML wirklich als Textformat zählt oder doch eher als Binärformat mit einzelnen Merkmalen eines Textformats, muss die Praxis zeigen. Viele XML-Formate sind fast so unzugänglich wie Binärdateien. Wer sich mit diesen Office-Systemen auskennt, kann auch Libraries verwenden, die diese direkt generieren oder die die APIs der entsprechenden Software ansprechen, wenn man eine entsprechende Installation erreichen kann. Auf typischen Serversystemen ist das schon eine gewisse Hürde.

Ein schönes Textformat ist LaTeX oder TeX. Das sind Satzsysteme, die das Layout in einer textbasierten Sprache, man kann sagen einer Programmiersprache, beschreiben. Text wird einfach so geschrieben, für mathematische und chemische Formeln gibt es sehr leistungsfähige Funktionen, die ich hier in diesem Blog auch regelmäßig für Formeln verwende, wenn es nötig ist. Und ansonsten gibt es Macros, die mit „\“ anfangen. Diese Macros machen TeX zu einer vollwertigen, aber nicht sehr zugänglichen Programmiersprache, aber für einfache Layouts kann man sich Muster im Internet oder von Kollegen oder aus Büchern holen und anpassen und das Lernen der Macrosprache weitgehend der Zukunft oder anderen überlassen. Weil das nun wirklich „plain“-Text ist, lässt sich sehr gut mit erb arbeiten und ein LaTeX-Template erstellen, in dem dann die Daten aus der Software eingefüllt werden, einschließlich Dingen wie Tabellen, bei denen z.B. die Anzahl der Zeilen dynamisch ist.

Mit diesem Ansatz generiere ich seit dem Bestehen der Firma IT Sky Consulting GmbH alle Rechnungen, die an Kunden verschickt werden. Es muss wohl funktioniert haben, denn ohne lesbare Rechnungen kann kaum eine Firma mehrere Jahre überleben. 😉

Share Button

Zeichenketten in Java, Ruby und Perl

Eigentlich sind die Zeichenketten in allen Programmiersprachen das gleiche, man kann sie als Literale angeben, irgend woher lesen oder zusammensetzen und dann vergleichen und ausgeben.

Aber es gibt einen großen Unterschied. In Java und in den JVM-Sprachen Scala und Clojure, die sich nicht speziell dagegen gewehrt haben, sind die normalen Zeichenketten unveränderlich. Das bedeutet, dass bei jeder Operation, die eine Zeichenkette zu verändern scheint, in Wirklichkeit jeweils eine neue Zeichenkette generiert wird. Das erschwert die Handhabung der Zeichenketten etwas, hat aber den Vorteil, dass man nicht durch Manipulationen an einer Zeichenkette anderen Programmteilen den Teppich wegziehen kann. Bei Multi-Thread-Programmen ist das besonders gefährlich, aber auch ohne mehrere Threads zu verwenden könnte das zu unerwarteten Fehlern führen, aber für Manipulationen kann es etwas unpraktischer sein, weil jedes Mal eine neue Zeichenkette generiert werden muss. Für diese Zwecke gibt es aber StringBuilder und StringBuffer, die explizit veränderliche Zeichenketten darstellen und für längere Manipulationen als Zwischenergebnis gut geeignet sind, aber man sollte diese am Schluss mit toString() in eine normale Zeichenkette umwandeln, die nicht mehr veränderlich ist. Da Scala und Clojure das Lied der unveränderlichen Objekte singen und als funktionale Sprachen oder teilweise funktionale Sprachen solche unveränderlichen Objekte der Normalfall sind, passt dieses Konzept dort sehr gut hinein.

In Perl und Ruby kann man sehr viele Manipulationen mit Zeichenketten machen, man könnte sogar fast sagen, dass diese Manipulationen von Zeichenketten mit regulären Ausdrücken die Stärke von Perl sind und deshalb auch sehr häufig vorkommen. Aber auch Perl und Ruby haben sich davor geschützt, dass man den Schlüssel (engl. key) einer Map verändert:

Beispiel in Ruby:

$ irb
irb(main):001:0> x="abc"
=> "abc"
irb(main):002:0> y="def"
=> "def"
irb(main):003:0> m={x=>3, y=>4}
=> {"abc"=>3, "def"=>4}
irb(main):004:0> x += "x"
=> "abcx"
irb(main):005:0> x
=> "abcx"
irb(main):006:0> m
=> {"abc"=>3, "def"=>4}
irb(main):007:0> y.gsub!(/d/, "x")
=> "xef"
irb(main):008:0> m
=> {"abc"=>3, "def"=>4}
irb(main):009:0>

Man sieht also, dass auch hier sichergestellt wird, dass das Verändern der Zeichenkette nicht die Schlüssel der Map verändert.

In Perl verhält es sich ähnlich:

$ perl
$x = "abc";
$y = "def";
%m = ($x, 3, $y, 4);
$x =~ s/a/A/;
print "x=$x y=$y\n";
print "m{x}=", $m{$x}, " m{'abc'}=", $m{'abc'}, " m(y)=", $m{$y},"\n";

Ctrl-D

x=Abc y=def
m{x}= m{'abc'}=3 m{y}=4

Die Zeichenketten werden beim Anlegen der Map %m kopiert und deshalb passiert nichts, wenn man nachträglich noch $x und $y ändert. Bei Ruby ist das entsprechend.

Man kann dies aber austricksen, zum Beispiel in Ruby:

$ irb
irb(main):001:0> class X
irb(main):002:1> attr_accessor :x
irb(main):003:1> def initialize(x)
irb(main):004:2> @x = x
irb(main):005:2> end
irb(main):006:1> end
=> nil
irb(main):007:0> x = X.new("abc")
=> #
irb(main):008:0> y = X.new("def")
=> #
irb(main):009:0> m={x=>3, y=>4}
=> {#=>3, #=>4}
irb(main):010:0> m
=> {#=>3, #=>4}
irb(main):011:0> x.x="abcd"
=> "abcd"
irb(main):012:0> x
=> #
irb(main):013:0> m
=> {#=>3, #=>4}
irb(main):014:0> y.x.gsub!(/d/, "D")
=> "Def"
irb(main):015:0> y
=> #
irb(main):016:0> m
=> {#=>3, #=>4}

Das lässt sich entsprechend in Perl und Java auch tun, führt eher zu überraschenden als erwünschten Ergebnissen und ist nicht zu empfehlen. In Ruby kann man die Schlüssel einer Map mit freeze() schützen:

irb(main):017:0> x.freeze
=> #
irb(main):018:0> x.x="u"
RuntimeError: can't modify frozen object
from (irb):18
from /usr/local/bin/irb:12:in `

'

Das ist ein recht eleganter Mechanismus, weil man ein Objekt mit einigen komplexeren Schritten initialisieren kann und dann durch freeze() schützen kann. Aber Vorsicht, es ist kein deepfreeze(), dies muss man explizit sicherstellen:

irb(main):019:0> x.x.gsub!(/a/, "u")
=> "ubcd"
irb(main):020:0> x
=> #
irb(main):021:0> x.x.freeze
=> "ubcd"
irb(main):022:0> x.x.gsub!(/a/, "u")
RuntimeError: can't modify frozen string
from (irb):22:in `gsub!'
from (irb):22
from /usr/local/bin/irb:12:in `
'

Eine interessante Frage ist oft, ob zwei Zeichenketten mit demselben Inhalt in Wirklichkeit dieselbe Zeichenkette sind oder ob es identische Kopien sind. Normalerweise ist das ja egal, aber es spielt eine Rolle bei Vergleichen. Diese sind billiger, wenn man sofort erkennt, ob es dasselbe Objekt ist und nicht erst zeichenweise vergleichen muss. Wenn große Datenmengen verarbeitet werden, ist es aber auch manchmal wegen des Speicherverbrauchs relevant.

Man kann in allen drei Sprachen beide Fälle haben. Mit zwei Variablen dieselbe Zeichenkette zu referenzieren ist in Java und Ruby einfach.

x = "abc";
y = x;

(in Ruby darf man die „;“ weglassen.)
In Perl sind die Variablen nicht Referenzen, sondern es werden wirklich Werte kopiert. Man muß dazu also explizit Referenzen verwenden:

$ perl
$x="abc";
$u=\$x;
$v=\$y;
print "x=$x u=$u v=$v\n";
$$u =~ s/a/A/;
print "x=$x u=$u v=$v\n";
print '$$u=', $$u, ' $$v=', $$v, ' $x=', $x,"\n";
Ctrl-D

x=abc u=SCALAR(0x8069820) v=SCALAR(0x80698ac)
x=Abc u=SCALAR(0x8069820) v=SCALAR(0x80698ac)
$$u=Abc $$v= $x=Abc

Umgekehrt kann man aber auch echte Kopien erzwingen, wenn man das will:
In Java geht das so:

String x = "abc";
String y = new String(x);

Oder in Ruby:

x = "abc"
y = String.new(x)

und in Perl ist es trivial:

$x = "abc";
$y = $x;

reicht schon aus.

Nun gewinnt man beim Vergleichen und beim Speicherverbrauch schon etwas, wenn man möglichst oft bei Vergleichen, die am Ende „true“ ergeben, schon an der Objektidentität und nicht erst am Vergleich aller Zeichen die Gleichheit erkennt. Aber wenn bei der Mehrheit der Vergleiche zwar die Länge gleich ist, aber die Zeichen sich irgendwo weit hinten unterscheiden, arbeitet das Programm vielleicht immer noch zu viel für diese Vergleiche. Wenn man also große Datenmengen verarbeiten will oder einfach nur meint, dass der Vergleich über die Objektidentität „richtiger“ ist, lässt sich das in Java und Ruby recht gut erzwingen.

In Java etwa mit

import java.util.IdentityHashMap;

public class MyMap extends IdentityHashMap {
public V put(String key, V value) {
assert key != null;
String uniqueKey = key.intern();
return super.put(uniqueKey, value);
}

public V get(Object key) {
if (key instanceof String) {
String str = (String) key;
return super.get(str.intern());
} else {
return null;
}
}
//..

public static void main(String args[]) {
MyMap map = new MyMap();
System.out.println(map.put("abc", "uvw"));
System.out.println(map.put(new String("abc"), "def"));
System.out.println(map.get("abc"));
System.out.println(map.get(new String("abc")));
}
}

ergibt die Ausgabe:

null
uvw
def
def

und verwendet intern nur die billigen Vergleiche mit == statt mit .equals(..).

In Ruby verwendet man dafür einfach „Symbole“ statt Zeichenketten, etwa

m = { :a => 3, :b => 4, :c => 5 }

Vorsicht ist aber geboten, sobald man Frameworks benutzt, die serialisieren, um Daten zu persistieren oder über das Netz zu schieben. Beim Deserialisieren geht diese Identität der Zeichenketten leider ganz schnell verloren, vor allem, wenn man „über das Netz“ vergleicht, was ja vorkommen kann.

Nun sei noch ein Grund erwähnt, warum man Java-Zeichenketten überhaupt mit so etwas wie y=new String(x) kopiert, wo sie doch unveränderbar (immutable) sind. Hier sollte man eine Optimierung in der Implementierung von String kennen. Wenn man substring() aufruft, wird ein neues String-Objekt für die Unterzeichenkette angelegt, dieses referenziert aber die Zeichensequenz der ursprünglichen Zeichenkette, nur mit anderen Anfangs- und Endzeigern. Dadurch wird in der Regel Speicher gespart und auch der Aufwand für das Allozieren von neuem Speicher vermieden. Wenn man nun aber von einer sehr langen, kurzlebigen Zeichenkette mit substring() eine sehr kurze, aber langlebige Zeichenkette extrahiert, verhindert man damit, dass der Speicher der eigentlichen Zeichensequenz der langen Zeichenkette freigegeben wird. So raffiniert und richtig es also in den allermeisten Fällen ist, die Optimierung der Library zu nutzen und zu schreiben

String y = x.substring(r, s);

so sollte man doch beachten, dass es in seltenen Fällen richtig und sogar wichtig ist, stattdessen

String y = new String(x.substring(r, s));

zu schreiben. Im Zweifelsfalls sollte man aber immer bei der ersten Schreibweise bleiben. Programme, die wegen ein paar Zeichenketten Memoryprobleme bekommen, die sich nicht durch Erhöhen der Speicherparameter leicht lösen lassen, sind zum Glück sehr selten.

Interessant ist sicher noch die Frage, in welcher Codierung die Zeichenketten gespeichert werden und wie man sie bei Ein- und Ausgabe richtig konvertiert. Das ist aber sicher genug Stoff für einen eigenen Artikel. Hier sei nur soviel gesagt: Java speichert die Zeichenketten mit utf-16, braucht also zwei Byte pro Zeichen, auch bei europäischen Sprachen.

Share Button

Ruby 2.0 ist seit 2013-02-24 verfügbar

Ruby 2.0 ist seit 2013-02-24 verfügbar:

Share Button