Itchy programmiert Blog

Eine Katze, die über Programmierung spricht, gibt es nicht? Gibt es doch!


Ein Zeichen aus einem String entfernen

Algorithmus Java char string

Strings werden intern als array von chars repräsentiert *(jedenfalls war das bis JDK7 so). Das heißt, es müsste doch relativ einfach möglich sein, ein Zeichen aus einem String entfernen zu können. Genau das werde ich euch heute vorstellen. Es gibt verschiedene Umsetzungsmöglichkeiten und wir werden diese im Hinblick auf Performanz beurteilen. Als erstes nutzen wir die Methode public String replace(char oldChar, char newChar), die uns mit der String-Klasse zur Verfügung gestellt wird. String str = "hallo Welt"; str.replace("l",""); Wie lange dauert das Entfernen des Zeichens? Und ist es tatsächlich die optimale Lösung oder gibt es noch eine andere Möglichkeit? Schauen wir uns die Zeiten mal an. Um ein einigermaßes sinnvolles Ergebnis zu erhalten, machen wir ein Warmup, damit der Hotspot-Compiler drüber schauen und gegebenenfalls Optimierungen vornehmen kann. Dafür führen wir die jeweilige Methode etwa 10000 Mal aus, bevor wir die Zeit messen. Das Ergebnis: 6966ns. Ist das jetzt wirklich das beste Ergebnis? Schauen wir uns mal die Alternativen an. Wir könnten die Zeichen ja auch mit einer Methode ersetzen. Hierfür wandeln wir den String in ein Array von char um und hängen die Buchstaben zeichenweise an, solange wir nicht das zu entfernende Zeichen gefunden haben. Das würde dann wie folgt aussehen: public String entferneZeichen(String str, char c) { char[] array = str.toCharArray(); StringBuilder sb = new StringBuilder(); for(char ch : array) { if(ch != c) { sb.append(ch); } } return sb.toString(); } Ist das wohl schneller? Laut ermittelter Zeit bei gleichem Warmup ist es fast doppelt so langsam; nämlich: 13868ns. Wir könnten jetzt die Methode auch rekursiv aufbauen und schauen, ob das nicht vielleicht die optimale Lösung ist. public static String entferneZeichenRec(String str, char c) { int index = str.indexOf(c); if(index == -1) { return str; } return entferneZeichenRec(str.substring(0, index) + str.substring(index +1, str.length()), c); } Die Messung sagt, dass der rekursive Aufruf 4838ns dauert. Also nur minimal schneller als die replace-Methode, die uns zur Verfügung gestellt wird. Sollte man sich da wirklich die Mühe machen, eine eigene Methode zu schreiben? Man könnte doch genausogut die gewonnene Zeit durch Einsatz von replace mit Sonnen und Katzenleckerlies verbringen. Nun, schauen wir uns das Ganze doch mal näher an. Wir haben beim Warmup 10000 Durchläufe vorgenommen. Was passiert wohl, wenn wir das Ganze auf 20000 hochsetzen? Schauen wir uns da doch mal die Messungen an. Wuhuuuuuu, replace dauert plötzlich 78296ns, gefolgt von der Methode ersetzeZeichen(String str, char c) mit 19318ns. Aber die Nummer 1 ist plötzlich die rekursive Methode. Die braucht nach wie vor nur sehr kurz: 5809ns. Wie konnte das passieren??? Vorhin war doch replace noch schneller und die rekursive Methode nur unwesentlich schneller als die replace-Methode. Tja, des Rätsels Lösung liegt in der Behandlung von Strings. Strings sind unveränderlich und damit wird immer ein String-Objekt erzeugt. Je mehr Durchläufe, desto mehr String-Objekte und desto langsamer die Methode. Wir sagen ja auch str = str.replace("l","");. Würden wir nur str.replace("l",""); ausführen, wäre in str immernoch hallo Welt gespeichert. Ihr seht also, dass man gerade bei der Nutzung von Strings sehr vorsichtig sein muss. Im schlimmsten Fall kann es passieren, dass wir eine OutOfMemoryException erhalten, obwohl unser Heap eigentlich noch fast leer ist. Grund dafür sind vermutlich die String-Objekte, die rumschwirren. Apropos schwirren.. Ich habe vorhin hier eine Fliege entdeckt. Ich geh mal spielen. Viel Spaß noch.

27. September 2016 13:41

Itchy in Itchy programmiert

Fehlende Zahl in einer linearen Zahlenreihe finden

reihe suche Algorithmus Array Java

// 13 fehlt int[] zahlenreihe = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16}; Es gilt die fehlende Zahl herauszukriegen. Um das zu tun, gehen wir wie folgt vor. Wir nutzen die Gauss'sche Summenformel. Man sagt, dass Gauss in der Schule die Zahlen 1 bis 100 addieren sollte. Als er viel früher fertig wurde, war der Lehrer so erstaunt, dass er fragte, wie er das in so einer kurzen Zeit lösen konnte. Gauss' Antwort war einfach. Er bildete die Summe von der ersten und der letzten Zahl und multiplizierte sie dann mit 50. Also: 1 + 100 = 101 2 + 99 = 101 3 + 98 = 101 Folglich: 101 * 50 = 5050 Die allgemeine Formel von der Errungenschaft Gauss lautet: n * (n + 1) / 2 Genau diese Erkenntnis nutzen wir bei der Suche nach der fehlenden Zahl. Denn wir können damit sicherstellen, dass die Differenz der mittels der Formel berechneten Summe und der berechneten Summe aus dem Array der gesuchten Zahl entspricht. 1) n * (n + 1) / 2 2) Die Summe aller Zahlen in der Reihe. 3) fehlende Zahl = 1) - 2) Das heißt, das ist unsere Referenzsumme. Wenn eine Addition nicht dieser Zahl entspricht, fehlt da etwas. int[] zahlenreihe = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16}; int mittel = ((zahlenreihe.length + 1) * ((zahlenreihe.length + 1) + 1)) / 2; int summeAllerZahlen = Arrays.stream(zahlenreihe).sum(); System.out.println(zahlenreihe.length); System.out.println("Die fehlende Zahl ist " + (mittel - summeAllerZahlen)); Das ist die Lösung in Java 8. In Java 7 müsste man mit einer foreach-Schleife durch das Array iterieren. Puuh, das ganze Schreiben hat mich doch sehr angestrengt. Guckt nicht so erstaunt: Ihr habt 10 Finger, ich dagegen 2 Pfoten. Ich gehe mal an mein Napf, um zu schauen, welche Köstlichkeiten serviert wurden. Mahlzeit! Itchy

20. August 2016 13:41

Itchy in Itchy programmiert

Nutzung von prismjs in Pelican

Python site generator pelican syntax highlighting prismjs

Da ich als Informatiker-Katze öfters Code bereitstellen möchte, wollte ich etwas haben, womit ich unkompliziert Syntax Highlighting in markdown aktivieren kann. Dabei bin ich zufällig auf prismjs gestoßen. Hier könnt ihr weitere Informationen zu prism finden. Wenn die Dateien nun vorliegen, muss noch die Datei base.html angepasst werden: <link href="{{ SITEURL }}/theme/css/prism.css" rel="stylesheet" /> <script src="{{ SITEURL }}/theme/css/prism.js"></script> Jetzt steht jeder Menge Input nichts mehr im Wege. Na ja, vielleicht doch! Diese WG-Mitglieder können doch echt manchmal stören. Immer verlangen sie Aufmerksamkeit und Liebe. Nun, ich komme mal meinen Pflichten nach und werfe mich gleich auf sie. Mit Milchtritten im Gesicht kann ich damit rechnen, dass sie mich den Tag über in Ruhe lassen. Itchy

2. April 2016 00:42

Itchy in Itchy programmiert

Wie man Bilder in Pelican verkleinert

Python site generator pelican pic verkleinern Bilder

Das Bild, das ihr hier seht, entspricht nicht der Originalgröße. Ich habe mir hierzu überlegt, standardmäßig die Option für mich bereitzustellen, Bilder einheitlich in einer angemessenen Größe darzustellen. Als Beispiel zeig ich euch mal ein Bild. Dieses Bild ist in Originalgröße wesentlich größer. Das könnt ihr gerne überprüfen, indem ihr ein Rechtsklick auf das Bild ausführt, und es euch so anzeigen lasst. Übrigens bin ich an dem Tag beim Lesen von einem der Dosenöffner erwischt worden, aber ein Glück sind Dosenöffner doch so naiv, dass sie nicht davon ausgegangen ist, dass ich weitergelesen habe. Hierzu habe ich die main.css angepasst: /***** Picture ****/ img[alt="pic"] { max-width: 200px; display: block; Um jetzt ein Bild kleiner einzufügen, muss man lediglich in der md-Dateiauf das Bild verweisen: ![pic]({attach}img/itchy.png) Itchy

31. März 2016 00:42

Itchy in Itchy programmiert

Hallo Welt

katze katzen nerd willkommen Hello World Itchy

Ich bin Itchy. Eine Katze, die schon früh mit Computern in Berührung kam, weil einer meiner Dosenöffner sich damit beschäftigt. Da standen überall diese Kästen rum, und wenn man mit der Pfote reingehackt hat, gab es auch ein Ergebnis (nicht immer das Erhoffte). Herrlich! Ich fing also an, mir das Spielen mit dem Gerät anzueignen. Da ich im Laufe meiner Beobachtungen jede Menge Erfahrungen sammeln konnte, habe ich beschlossen, mein Wissen mit Euch zu teilen. Natürlich alles ohne das Wissen meiner Mitbewohner, glauben sie doch tatsächlich, dass Katzen nur am Essen und Schlafen wirklich interessiert sind. Stimmt aber nicht! Wir tun nur so. Eins noch an all die Menschen, die mit geringem Aufwand viel Geld verdienen wollen: ja genau, damit meine ich die Menschen, die gerne Seiten abmahnen, weil kein Impressum vorhanden ist. Dies ist absolut privater Bereich. Der ganze Inhalt steht Jedem vollumfänglich zur Verfügung und kann nach Belieben ausgedruckt und weitergegeben werden. Ich wünsche euch auf jeden Fall viel Spaß auf meiner Seite und hoffe, an der einen oder anderen Stelle behilflich gewesen zu sein. Paws in the air! Hier noch ein Kunstwerk von Krümel (einer der beiden Dosenöffner). Itchy

28. März 2016 00:42

Itchy in Itchy programmiert