tag:blogger.com,1999:blog-84714509614117563992024-02-17T09:51:04.009+01:00Daniel's BlogMore Is DifferentDaniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.comBlogger52125tag:blogger.com,1999:blog-8471450961411756399.post-443247102530979882021-01-21T20:33:00.008+01:002023-05-31T11:52:51.719+02:00The Explore/Exploit Strategy in EngineeringThe explore/exploit strategy is an iterative approach to systems engineering and team formation.</br>
It starts out with an exploration phase and scales both system and team size during the exploitation phase.</br>
Later on, the strategy is repeated for either product improvements, disruptive changes, or new projects and teams.</br>
</br>
A general introduction to the explore/exploit strategy is described in Brian Christian's and Tom Griffiths' book named <a href="https://algorithmstoliveby.com/">"Algorithms to Live By"</a>.</br>
The advice divides the time you spend on tasks into an exploration and an exploitation phase.
Exploration is gathering knowledge, and exploitation is using the knowledge.</br>
The idea is to explore things when you will have time to use the resulting knowledge, and exploit it when your are ready to cash in.</br>
</br>
Another example of the explore/exploit startegy is given in <a href="https://en.wikipedia.org/wiki/Richard_Hamming">Richard Hamming</a>'s book "Learning to Learn".
He concluded one should have a plan to first explore things in a research phase, and then exploit that knowledge to build something.</br>
The exploration phase is best described by scientific research:</br>
<ul><i>In science, if you know what you are doing, you should not be doing it.</ul></i>
While the exploitation phase maps well to engineering:</br>
<ul><i>In engineering, if you do not know what you are doing, you should not be doing it.</ul></i>
Of course, both exploration and exploitation as well as science and engineering are tightly coupled with each other in an iterative process to make progress.
<ul><i>Change does not mean progress, but progress requires change.</ul></i>
Progress is achieved then by repeating the explore/exploit cycle over and over again with the results of an exploitation phase fueling new exploration phases.</br>
From time to time, this repeating process ends up in <a href=https://en.wikipedia.org/wiki/Disruptive_innovation>disruption</a> and disruptive technology, a terminology defined by Clayton Christensen in his book <a href="https://en.wikipedia.org/wiki/The_Innovator%27s_Dilemma">"The Innovator's Dilemma"</a>.</br>
</br>
The explore/exploit startegy helps to understand and boost various aspects in both software engineering and team formation.</br>
</br>
<h3>Explore</h3>
The exploration phase must be started by a small, motivated and joyful team with common sense that focuses on the hardest problems first.</br>
<a href="https://en.wikipedia.org/wiki/Louis_Pasteur">Louis Pasteur</a>'s remark, "Luck favors the prepared mind", perfectly summarizes the purpose of this phase.</br>
It both admits there is an element of luck and yet claims to a great extent it is up to you.
You prepare yourself and your team to succeed or not.</br>
</br>
Good advice for how to master the exploration phase can be found in <a href="https://en.wikipedia.org/wiki/Fred_Brooks">Frederick Brooks</a>' book on "The Design of Design".</br>
A quick summary can be found in one of my older blog posts about <a href="http://himmele.blogspot.com/2017/06/fred-brooks-software-design.html">"Frederick Brooks on Software Design"</a>.</br>
The few designers who do the exploration phase, build up a plan in mind for later execution.
According to Brooks, the outcome of the exploration should be a plan with conceptual integrity - unity, economy, clarity, delight.</br>
The plan is partly implemented during the exploration phase to learn fast from mistakes and other aspects of the design.
Another, bigger part of the plan is done during the exploitation phase while the team grows in size.</br>
</br>
An important fact, according to both Richard Hamming and Clayton Christensen, is that most of the great innovations come from outside the field, not from the insiders or experts.</br>
Probably because experts tend to neglect or shorten the exploration phase and immediately rush into the exploitation phase.</br>
</br>
Another remark from Richard Hamming is that some, not all experts rely too much on their own knowledge bubble:
<ul><i>
Working with one's door closed lets you get more work done per year than if you had an open door, but I have observed repeatedly that later those with closed doors,
while working just as hard as others, seem to work on slightly the wrong problems, while those who have let their door stay open got less work done but tend to work
on the right problem! I suspect the open mind leads to the open door, and the open door tends to lead to the open mind.
</ul></i>
A further good source of advice about the exploration phase is Richard Hamming's talk about "You and your research":</br>
</br>
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/a1zDuOPkMSw?hd=1&wmode=transparent" width="420"></iframe></span>
<br />
If you prefer text, have a look on Hamming's paper on <a href="https://www.cs.virginia.edu/~robins/YouAndYourResearch.pdf">"You and your research"</a>.</br>
</br>
<h3>Exploit</h3>
The interaction with harsh reality tends to push you into significant discoveries which otherwise you would never have thought about while doing pure research in a vacuum of your private interests.</br>
That means it is very important to start exploiting the knowledge garthered during exploration alongside scaling the team, not too early and not too late.</br>
</br>
The most important step during exploitation is team formation as well as building a common mindset and language within your team.</br>
Therefore, defining a few basic architectural building blocks during the design phase and documenting them with a software development kit and examples is crucial.</br>
While scaling your team always assure to build up many experts, not just a single or few knowledge towers, as explained by <a href="https://richardsheridan.com/books/joy-inc">Richard Sheridan</a> in his book "Joy, Inc.".
Otherwise such superstars will hoard knowledge without sharing it, and ultimatively wreck the overall team results and morale.</br>
Keeping high quality results while expanding the team requires a balanced team without a central superstar, a team which truly and authentically cares about things.</br>
Also see one of my older blog posts about the <a href="https://himmele.blogspot.com/2017/03/characteristics-of-efficient.html">Characteristics of an efficient engineering team</a>.
</br>
The leader of such a team is best when people barely know he/she exists. As Laozi said, that when the work is done, the aim fulfilled, they will say: we did it ourselves.</br>
</br>
Keep in mind that there is never time to do the job right, but there is always time to fix it later.</br>
As mentioned by <a href="https://en.wikipedia.org/wiki/Alan_Kay">Alan Kay</a>: <a href="https://himmele.blogspot.com/2010/11/alan-kay-on-object-oriented-programming.html">"The key in making great and growable systems is much more to design how its modules communicate rather than what their internal properties and behaviors should be."</a></br>
So as long as the overall system design has conceptual integrity, you and your team will have plenty of room for future improvements and refactorings, hopefully without changing public interfaces.</br>
</br>
<h3>Repeat/Iterate</h3>
Great designers grow with their challenges. They need a constant flow of exciting challenges for mastery.</br>
Therefore, you will repeat the explore/exploit startegy over and over again for product improvements or new projects.</br>
Success means you and your team will get better problems to work on.
But what you did to become successful is likely to be counter-productive when applied at a later date.</br>
For that reason you have to iterate to a new exploration phase with some of your team not to get stuck in exploitation.</br>
Being an expert all the time is not what you should aim for. Be a hungry and foolish beginner from time to time.</br>
</br>Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com4tag:blogger.com,1999:blog-8471450961411756399.post-77699310348321023442020-11-15T22:19:00.003+01:002020-11-15T22:26:21.984+01:00The four paradigm shifts for the connected car of the futureThe automotive industry is undergoing substantial changes as new technologies for connected cars, autonomous vehicles and electric vehicles are creating new customer expectations.
In this webinar, Dominik Obermaier (CTO of HiveMQ) and me discuss four key paradigm changes that need to happen for the automotive industry to remain competitive and deliver on the customer experience of the future.
<ul>
<li>Software Platforms and Software Development Kits</li>
<li>Publish/Subscribe Messaging on both Edge and Cloud Side</li>
<li>Domain Modelling</li>
<li>Pragmatic Software Development Processes</li>
</ul>
In this video you will learn how modern software technologies like publish/subscribe messaging using MQTT and Kafka, domain modeling, as well as edge and cloud computing will accelerate time to market for new automotive features and improve customer experience.
<br />
<br />
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/_M6bRX8gWtI?hd=1&wmode=transparent" width="420"></iframe></span>
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-29720207527193556482020-03-23T09:24:00.001+01:002020-03-23T09:53:46.226+01:00The Soul of Erlang and ElixirSaša Jurić talks about the Erlang runtime, the BEAM virtual machine.<br />
Since years I planned to write a post about "Why can Erlang have this 'let it crash' methodology and all others can't?".
Now, Saša Jurić shows exactly that along with other runtime features of the BEAM VM is his talk about the Soul of Erlang and Elixir.<br />
His talk perfectly extends my last post about <a href="https://himmele.blogspot.com/2019/05/whats-next-for-our-programming.html">What's Next for Our Programming Languages and Operating Systems?</a> and gives a glimpse on the future.
<br />
<br />
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/JvBT4XBdoUE?hd=1&wmode=transparent" width="420"></iframe></span>
<br />
I love simplicity!<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com1tag:blogger.com,1999:blog-8471450961411756399.post-86209031520029069262019-05-21T21:28:00.001+02:002019-05-21T22:49:05.273+02:00What's Next for Our Programming Languages and Operating Systems?Joe Duffy (previous Microsoft Director of Engineering for Languages and Compilers), Richard Feldman (Elm Software Engineer), Brian Goetz (Java Language Architect at Oracle) and Sylvan Clebsch (Designer of the Pony Programming Language) discuss the future of programming languages. <br />
<br />
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/q3XcQh0cNZM?hd=1&wmode=transparent" width="420"></iframe></span>
<ul>
<li>02:49 Brian Goetz: When I am working on a programming problem and not making progress the root cause usually is that I am not thinking clearly about the data flows. Once you get the data flows right then the code pretty much writes itself.</li>
<li>05:23 Joe Duffy: Operating systems of the future should provide <a href="http://joeduffyblog.com/2015/11/03/a-tale-of-three-safeties/">type, memory and concurrency-safety (no data races)</a>. We should use languages that solve the problems by construction.</li>
<li>07:37 Focus on writing simple code!</li>
<li>28:29 Richard Feldman: Immutability rules out a lot of concurrency related problems. Will programmers adapt and use different programming paradigms where these problems (concurrency, data-safety, etc.) cannot happen anymore?</li>
<li>39:15 Brian Goetz: There is the programming language you program in. And then there is the runtime which really is the important part. That's where all your deployment, debuggability, monitorability, serviceability comes from. Developers (who are focused on code) often think the surface language is the important part. But in a lot of ways the runtimes matter way more than programming languages do.</li>
<li>46:53 Sylvan Clebsch: The Actor model programming paradigm makes OOP vs. FP discussions unnecessary.</li>
<li>49:22 Sylvan Clebsch: The programming language is a UI to the runtime.</li>
</ul>
<br />
<h3>My Comments</h3>
I think that software architects and engineers focus way too much on code instead of data flows. Understanding the data flows in a system and arranging them efficiently usually points you to the best and simplest architectures.<br />
<br />
Brian Goetz definition of programming language runtimes and Sylvan Clebsch comment that we should regard programming languages just as user interfaces to their runtime systems is so true. I would even say that most languages I like, I do that mostly because of their runtime system and not so much for the language itself.
<ul>
<li>The <a href="http://www.erlang.org/">Erlang</a> runtime system (programming language) provides me a really nice Actor model paradigm I love to program in, and perfect abstractions how to build reliable, fault-tolerant distributed systems.</li>
<li>The <a href="https://developer.android.com/guide">Android</a> framework to me is a superb runtime on the Java VM that provides much more fun and simplicity for writing correct programs than the standard Java runtime system abstractions. Their Actor model implementation (Handler/Looper/MessageQueue) is far more easy and fun to work with than Java's pure Thread and Executor stuff. Having callbacks run in the application thread (actor) without introducing concurrency issues is just great and must be the norm!</li>
<li>The main reason for building the <a href="https://github.com/Himmele/Mindroid.java">Mindroid</a> frameworks/runtimes for Java, C++ and embedded C++ is due to the fact that the standard Java and C++ runtimes do not provide neat, slim and consistent application models (Erlang guys would say behaviors) to work with. Mindroid provides a consistent way to develop Java, C++ and embedded C++ applications using the Actor model design pattern. It bridges language boundaries and helps in building correct, fault-tolerant (distributed) systems.</li>
<li>Both operating systems and/or programming systems (languages) can provide runtimes that are fun to work with. Besides Erlang, I really loved to work with the <a href="http://www.qnx.com/developers/docs/7.0.0/index.html#com.qnx.doc.neutrino.sys_arch/topic/about.html">QNX operating system</a> since it provides nice, yet easy to understand, abstractions for building modular (distributed) systems using inter-process communication (<a href="https://en.wikipedia.org/wiki/Communicating_sequential_processes">CSP-style IPC</a>) and resource managers (kind of an Actor model).</li>
<li>Runtimes standardize ways of doing things and behaviors so that not everybody needs to reinvent the wheel. I think nobody ever tried to implement her/his own Actor model implementation or distribution transparency mechanism on top of Erlang or <a href="https://elixir-lang.org/">Elixir</a>.</li>
<li>Operating systems and language runtimes should align on basic building blocks like fast message passing as well as inexpensive processes (for isolation) and fast process switching. Furthermore, both should have first-class support for distributed systems including distribution transparency, supervision trees and (topic-based) publish/subscribe messaging.</li>
</ul>
Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-40161145609822838732017-07-09T23:27:00.000+02:002017-07-10T00:33:30.863+02:00Schnelles Denken, langsames Denken von Daniel Kahneman<a href="https://de.wikipedia.org/wiki/Schnelles_Denken,_langsames_Denken"><b>Schnelles Denken, langsames Denken</b></a> (englischer Originaltitel: Thinking, Fast and Slow) ist ein Buch von Daniel Kahneman, das seine oft gemeinsam mit Amos Tversky durchgeführten Forschungen aus mehreren Jahrzehnten zusammenfasst.<br />
Die zentrale These ist die Unterscheidung zwischen zwei Arten des Denkens: Das schnelle, instinktive und emotionale <b><i>System 1</b></i> und das langsamere, Dinge durchdenkende und logischere <b><i>System 2</b></i>. Das Buch schildert kognitive Verzerrungen im Denken von System 1, und bietet dabei einen breiten Querschnitt von Forschungsergebnissen der sogenannten Heuristics-and-biases-Schule, die von Tversky und Kahneman in den 1970er Jahren begründet wurde.<small> [Quelle: Wikipedia "Schnelles Denken, langsames Denken" vom 9. Juli 2017].</small><br />
<br />
Die Psychologie zählt für mich neben der Biologie und der Informatik zu den spannendsten Wissenschaften. Als Informatiker finde ich es sehr beeindruckend, dass sich die Psychologie der <a href="https://de.wikipedia.org/wiki/Abstraktion">Abstraktion</a> bedient, um das Denken mittels zweier Systeme zu beschreiben. Dieser Beitrag soll mir als Zusammenfassung und Nachschlagewerk von Daniel Kahneman's Buch dienen; einem Buch das jeder mehrmals lesen sollte.<br />
<br />
<h3>System 1</h3>
<ul>
<li>Schnell, automatisch, immer aktiv, emotional, stereotypisierend, unbewusst.</li>
<li>Das assoziative Gedächtnis, der Kern von System 1, konstruiert fortwährend eine kohärente Interpretation dessen, was zu jedem beliebigen Zeitpunkt in unserer Welt geschieht.</li>
<li>System 1 ist nicht für statistisches Denken ausgelegt, da wir tendenziell unser Wissen über die Welt überschätzen und wir unterschätzen welche Rolle der Zufall bei Ereignissen spielt.</li>
<li>System 1 ist so gestaltet, dass es aus dürftigen Informationen automatisch weitreichende Schlussfolgerungen zieht - es ist aber nicht imstande, zu ermessen, wir groß die Sprünge sind, die es beim Folgern macht. Wegen der WYSIATI-Regel zählen nur die verfügbaren Informationen.</li>
<li>System 1 ist leichtgläubig und neigt dazu Aussagen für wahr zu halten.</li>
</ul>
<h3>System 2</h3>
<ul>
<li>Langsam, anstrengend, selten aktiv (faul), logisch, berechnend, bewusst.</li>
<li>Zielgerichtetes, strukturiertes und konzentriertes Denken.</li>
<li>Eine der Hauptfunktionen von System 2 besteht darin, von System 1 "vorgeschlagene" Gedanken und Handlungen zu überwachen und zu kontrollieren; einigen davon erlaubt es, sich direkt im Verhalten auszudrücken, während es andere unterdrückt oder modifiziert.</li>
<li>Die Arbeitsteilung zwischen System 1 und System 2 ist höchsteffizient, da sie Aufwände minimiert und die Leistung optimiert.</li>
<li>Oftmals folgt das faule System 2 den Vorschlägen von System 1, was unser Denken anfällig für systhematische Fehler macht.</li>
<li>System 2 wird durch kognitive Beanspruchung mobilisiert.</li>
<li>System 2 ist dafür zuständig Aussagen anzuzweifeln, aber System 2 ist manchmal beschäftigt und oft faul.</li>
</ul>
<h3>Heuristiken und kognitive Verzerrungen</h3>
<ul>
<li><a href="https://de.wikipedia.org/wiki/M%C3%BCller-Lyer-Illusion">Müller-Lühr-Illusion</a> ist eine sehr bekannte geometrisch-optische Täuschung.</li>
<li><a href="https://de.wikipedia.org/wiki/Flow_(Psychologie)">Flow</a> bezeichnet das als beglückend erlebte Gefühl eines mentalen Zustandes völliger Vertiefung (Konzentration) und restlosen Aufgehens in einer Tätigkeit.</li>
<li><a href="https://de.wikipedia.org/wiki/Priming_(Psychologie)">Priming Effekt</a> bezeichnet eine Beeinflussung einer Handlung durch eine Vorstellung.</li>
<li>Kognitive Leichtigkeit beschreibt ein Konzept, nach welchem entschieden wird, ob die Aufmerksamkeit neu ausgerichtet werden muss (Aktivierung von System 2) oder ob den Antworten von System 1 geglaubt werden kann.</li>
<li><a href="https://de.wikipedia.org/wiki/Halo-Effekt">Halo-Effekt</a>: Unter dem Effekt wird die Tendenz verstanden, faktisch unabhängige oder nur mäßig korrelierende Eigenschaften von Personen oder Sachen fälschlicherweise als zusammenhängend wahrzunehmen.</li>
<li><a href="https://de.wikipedia.org/wiki/Kognitive_Verzerrung">Kognitive Verzerrung</a> ist ein kognitionspsychologischer Sammelbegriff für systematische fehlerhafte Neigungen beim Wahrnehmen, Erinnern, Denken und Urteilen.</li>
<li>WYSIATI - What You See Is All There Is: Voreilige Schlussfolgerungen aufgrund unvollständiger oder falscher Informationen.</li>
<li><a href="https://de.wikipedia.org/wiki/Ankereffekt">Ankereffekt</a> ist ein Begriff aus der Kognitionspsychologie für die Tatsache, dass Menschen bei bewusst gewählten Zahlenwerten von momentan vorhandenen Umgebungsinformationen beeinflusst werden, ohne dass ihnen dieser Einfluss bewusst wird.</li>
<li>Basisrate: Die Basisratenvernachlässigung, d. h. die Überschätzung der bedingten Wahrscheinlichkeit von Ereignissen mit niedriger Basisrate, erklären Kahneman und Tversky mit der Anwendung der Repräsentativitätsheuristik. Wahrscheinlichkeitsurteile sollten sich daher an der Basisrate orientieren.</li>
<li>Die <a href="https://de.wikipedia.org/wiki/Satz_von_Bayes">Bayessche Regel</a> gibt genau an, wie bestehende Überzeugungen (Basisraten) mit der Aussagekraft der Erkenntnisse - dem Ausmaß, in dem sie die Hypothese gegenüber der Alternative begünstigen - kombiniert werden sollten. Somit handelt es sich um die Verankerung eines Urteils über die Wahrscheinlichkeit eines Ereignisses in einer plausiblen Basisrate.</li>
<li><a href="https://de.wikipedia.org/wiki/Regression_zur_Mitte">Regression zum Mittelwert</a> ist ein Begriff der Statistik; er bezeichnet das Phänomen, dass nach einem extrem ausgefallenen Messwert die nachfolgende Messung wieder näher am Durchschnitt liegt, falls der Zufall einen Einfluss auf die Messgröße hat.</li>
</ul>
<h3>Selbstüberschätzung</h3>
<ul>
<li>Die Kompetenzillusion ist nicht nur ein individueller Urteilsfehler; sie ist tief in der Kultur der Wirtschaft verwurzelt.</li>
<li>Checklisten und einfache Regeln: Einfache statistische Regeln sind meistens intuitiven Urteilen überlegen. (Paul Meehl)</li>
<li>Intuition ist nicht mehr und nicht weniger als Wiedererkennen.</li>
<li>Voraussetzungen für Expertise sind eine hinreichend regelmäßige Umgebung um vorhersagbar zu sein sowie eine Gelegenheit diese Regelmäßigkeit durch langjährige Übung zu erlernen. Wenn es keine stabilen Regelmäßigkeiten in der Umgebung gibt, kann man der Intuition nicht vertrauen.</li>
</ul>
<h3>Entscheidungen</h3>
<ul>
<li>Der <a href="https://de.wikipedia.org/wiki/Planungsfehlschluss">Planungsfehlschluss</a> ist die Tendenz von Leuten und Organisationen, zu unterschätzen, wie viel Zeit sie zur Vollendung einer Aufgabe benötigen. Wir konzentrieren uns auf unser Zeil, verankern uns in unserem Plan und vernachlässigen relevante Basisraten.</li>
<li>Prä-mortem-Methode überwindet übermäßigen Optimismus indem sie Zweifel zulässt und nach möglichen nicht betrachteten Gefahren sucht.</li>
<li><a href="https://de.wikipedia.org/wiki/Verlustaversion">Verlustaversion</a> bezeichnet in der Psychologie und Ökonomie die Tendenz, Verluste höher zu gewichten als Gewinne. Die Verlustaversion ist ein Bestandteil der Prospect Theory (deutsch: Neue Erwartungstheorie), die 1979 von Kahneman und Tversky aufgestellt wurde.</li>
<li>Die Außensicht ist ein sehr wichtiges Monitoring-Instrument, da die Innensicht zum WYSIATI-Effekt neigt.</li>
<li><a href="https://de.wikipedia.org/wiki/Framing-Effekt">Framing-Effekt</a> bezeichnet die Tendenz, dass unterschiedliche Formulierungen einer Botschaft – bei gleichem Inhalt – das Verhalten des Empfängers unterschiedlich beeinflussen.</li>
</ul>
<h3>Zwei Selbste</h3>
<ul>
<li>Erlebendes Selbst vs. erinnerndes Selbst: Ich bin mein erinnerndes Selbst, und das erlebende Selbst, das mein Leben lebt, ist für mich wie ein Fremder.</li>
</ul>
<br />
<b>Gedankenexperiment</b><br />
Möglicherweise ist die Idee der Abstraktion unseres Denkens mittels System 1 und System 2 ein ideales Design bzw. eine vielversprechende Architektur für KI-Systeme wie etwa autonome Roboterautos.<br />
<br />
<br />
Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-54078388968677506322017-06-05T22:52:00.000+02:002017-06-05T23:03:23.022+02:00Frederick Brooks on Software DesignSoftware design and architecture always has been my foremost interest and fun part in computer science. Frederick Brooks' book <a href="https://www.amazon.com/Design-Essays-Computer-Scientist-ebook/dp/B003DKG5H6/ref=sr_1_3?ie=UTF8&qid=1496694673&sr=8-3&keywords=The+Design+of+Design">"The Design of Design"</a> summarizes a lot of useful facts and topics all system designers will learn about sooner or later. This post contains some few excerpts from his excellent book.</br>
</br>
<b><i>The Design Question</i></b>
<ul>
<li>Design is to plan in mind for later execution.</li>
<li>For most human makers of things, the incompletenesses and inconsistencies of our ideas become clear only during implementation. Thus it is that writing, experimentation, "working out" are essential disciplines for the theoretician.</li>
<li>Great designers have <b>conceptual integrity</b> - unity, economy, clarity, delight.<li>
</ul>
Frederick Brooks in his classic book "The Mythical Man-Month" about <b>conceptual integrity</b>:</br>
<i>"I will contend that conceptual integrity is the most important consideration in system design. It is better to have a system omit certain anomalous features and improvements, but to reflect one set of design ideas, than to have one that contains many good but independent and uncoordinated ideas."</i></br>
<i>"Conceptual integrity in turn dictates that the design must proceed from one mind, or from a very small number of agreeing resonant minds."</i></br>
Conceptual integrity does not emerge from democracy. The result of a democratic approach is a compromise that does not meet the needs of any single person or the customer.</br>
<i>"The separation of architectural effort from implementation is a very powerful way of getting conceptual integrity on very large projects."</i></br>
</br>
<b><i>Design Models</i></b>
<ul>
<li>The theory of design is the general theory of search through large combinatorial spaces of possibilities.</li>
<li>Sometimes the problem is to discover what the problem is.</li>
<li>Goal iteration must be considered an inherent part of the design process.</li>
<li>The most potent reason to study design history is to learn what <i>doesn't work</i>, any <i>why</i>.</li>
<li>Ask yourself: <i>Am I doing the right thing?</i> or am I just <i>doing the thing right?</i></li>
<li>Study failure examples even more carefully than you study successes.</li>
<li>Any attempt to formulate all possible requirements at the start of a project will fail and would cause considerable delays.</li>
</ul>
<b><i>Collaboration in Design</i></b>
<ul>
<li>Most great works have been made by one mind. The exceptions have been made by two minds.</li>
<li>Great designs often arise in physical isolation, small teams, intense concentration, and leadership by one mind.</li>
<li>Great designers most have a clear vision of and for the system and must really <i>care</i> about its conceptual integrity.</li>
<li>Clean interfaces make a big difference in the error rate of the design.</li>
<li>Clean interfaces give multiple designers each the joy of ownership, of the privilege of signing a piece of work. They also facilitate sequential ownership, as small components flow together into larger subsystems.</li>
<li>The telephone provides an even bigger collaboration breakthrough than email.</li>
</ul>
<b><i>Constraints are Friends</i></b>
<ul>
<li>A general-purpose product is harder to design well than a special-purpose product.</li>
<li>Constrains shrink the search space of possibilities.</li>
<li>The hardest part of designing is deciding exactly <i>what to design</i>.</li>
<li>Any design process begins with the designer elaborating and particularizing the objectives and constraints. The first task is to narrow the design space.</li>
</ul>
<b><i>Esthetics and Style in Design</i></b>
<ul>
<li>Style is the dress of thought, and a well-dresses thought, like a well-dressed man, appears to great advantage.</li>
<li>Definition of style: Those features of literary composition that belong to form or expression rather than to the substance of the thought or matter expressed.</li>
<li>Computer design clearly must place a high value on parsimony, the use of few elements (building blocks).</li>
<li>Consistency is reinforcing and self-teaching, because it confirms and encourages our expectations.</li>
<li>Uniform style aids comprehensibility of a design.</li>
</ul>
<b><i>Great Design and Great Designers</i></b>
<ul>
<li>Good design is top-down.</li>
<li>Great designers, even the most iconoclastic, rarely start from scratch - they build on the rich inheritance from their predecessors. This is why you must know about design (computer science) history.</li>
<li>Great designs come from great designers, not from great design processes.</li>
<li>Very good programmers are <i>ten times</i> as productive as poor ones.</li>
<li>Give the system architect full authority over the design.</li>
<li>Every man who rises above the common level has received two educations: the first from his teachers; the second, more personal and important, from himself.</li>
<li>Design productivity requires <a href="https://himmele.blogspot.de/2017/02/psychology-and-behavioral-science-not.html"><i>flow</i></a>, an uninterrupted mental state of high creativity and concentration.</li>
</ul>
<b><i>The Mythical Man-Month</i></b>
<ul>
<li>Lean, sparse, fast programs are almost always the result of <i>strategic breakthrough</i>, rather than tactical cleverness.</br>
Often such breakthrough will be a new <i>algorithm</i>.</br>
More often, the breakthrough will come from redoing the <i>representation</i> of the data or tables. <b><i>Representation is the essence of programming.</i></b></li>
<li>You can never plan the future by the past.</li>
<li>Be careful how you fix what you don't understand.</li>
</ul>
<b><i>One addition from my side</i></b>
<ul>
<li>Great designers grow with their challenges. They need a constant flow of exciting challenges for <a href="https://himmele.blogspot.de/2017/02/psychology-and-behavioral-science-not.html">mastery</a>.</li>
</ul>
</br>Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-26322153346322580722017-04-17T21:13:00.002+02:002017-05-15T15:49:30.347+02:00Alan Kay on Computer ScienceAlan Kay is a computer scientist and pioneer who was part of the Xerox PARC team of about 30 researchers that developed many of the key concepts of today's hardware and software technologies.<br />
This post contains some famous keynotes and other talks by Alan Kay including quotes and comments.<br />
<br />
See also: <a href="https://himmele.blogspot.com/2010/11/alan-kay-on-object-oriented-programming.html">Alan Kay on Object-Oriented Programming</a><br />
<br />
<h3>Normal Considered Harmful</h3>
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/FvmTSpJU-Xc?hd=1&wmode=transparent" width="420"></iframe></span>
<ul>
<li>05:00 We must know about the past (the pioneers of computing) to invent the future.</li>
<li>13:53 We cannot invent the future by using vendor computer hardware and software.</li>
<li>34:29 Knowledge almost always trumps IQ. A change in perspective is worth a lot of IQ points.</li>
<li>36:31 Clever hacks don't scale well and worse keep broken things around for too long.</li>
<li>39:45 Learning a new idea requires almost as much creativity as the original invention.</li>
<li>49:27 Wayne Gretzsky theory of hockey: <i>Why are you a so much better hockey player than everybody else? Everybody else just goes where the puck is, I go where it is going to be.</i></li>
<li>1:01:08 All understanding begins with our not accepting the world as it appears (Susan Sontag).</li>
<li>1:02:17 Brains were designed for survival and coping, not for great inventions. Science is a way to get around that limitation.</li>
</ul>
<br />
<h3>Programming and Scaling</h3>
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/YyIQKBzIuBY?hd=1&wmode=transparent" width="420"></iframe></span>
<ul>
<li>06:50 The biggest problem we have as human beings is that we confuse our beliefs with reality.</li>
<li>08:21 Make-and-fix paradigm: Nowadays, computing is mostly tinkering and not engineering.</li>
<li>18:03 The internet is one of the few human artifacts that behaves like a living organism.</li>
<li>25:11 Smalltalk (OO) mistake: Objects are too small! The scale jump from molecules to a living organism is incredible compared the scale jump when trying to make objects. <i>Idea</i>: Make much more capable universal objects and try to build things out of that.</li>
<li>33:11 Most people can only experience the present in terms of the past. (Marshall McLuhan)</li>
<li>30:05 Our strain of humanity is on the planet for about 192.000 years (tracing mother's mitochondrial DNA) and we only invented science 400 years ago. That's why IQ does not count that much.</li>
<li>37:00 Past, Present, Future: The past is enormous!</li>
<li>42:43 Computing is mostly tinkering at this time, there's not much engineering, math, or science.</li>
</ul>
<br />
<h3>Is it really "Complex"? Or did we just make it "Complicated"?</h3>
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/ubaX1Smg6pY?hd=1&wmode=transparent" width="420"></iframe></span>
<ul>
<li>1:13:10 Next generation publish/subscribe systems in UI/UX design: Widgets communicating by a publish/subscribe methodology to announcements of events.</li>
<li><b>1:38:00 Computer science is the science of processes. It is about thinking, reasoning, and talking of processes as well as representing, constructing and debugging them both in hardware and software.</b></li>
</ul>
<br />
<h3>@ SAP</h3>
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/vXjpA9gFX5c?hd=1&wmode=transparent" width="420"></iframe></span>
<ul>
<li>12:47 Our perception of the future is mostly just a little increment on the present.</li>
<li>13:01 Innovation is just taking an idea or invention that already exists into the marketplace.</li>
<li>19:19 Problem finding is much harder than problem solving in order to make progress.</li>
<li><b>21:14 You are doing research only so long as you can change your mind. Making decisions consolidates one's mind.</b></li>
<li>21:53 Most software in the world is absolutely not designed!</li>
<li>25:01 Thinking is not remembering!</li>
<li>37:50 Big data: What we need is <i>not</i> big data but big meaning (including descriptions for processes, relationships and constraints).</li>
<li>40:33 Building with gears does not scale (< 1000 gears)! Biology scales!</li>
<li>42:58 The internet is one of the few human artifacts that behaves like a living organism.</li>
<li>44:19 Learning how to code is like the last thing you wonna learn about computing. Computing is about systems, not about algorithms, not about if-statements; it is about powerful ideas that are made into descriptions computers can interpret.</li>
<li>56:55 <i>How do you learn how to bike?</i> Using a low bike without pedals. Bicycle training wheels are actually anti-learning! Lessons learned: Software called "user-friendly" very often isn't.</li>
</ul>
<br />
<h3>Power of Simplicity</h3>
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/NdSD07U5uBs?hd=1&wmode=transparent" width="420"></iframe></span>
<ul>
<li><b>10:01 You get simplicity by finding a slightly more sophisticated building block to build your theories out of.</b> The inability to fix the existing building blocks is one of the largest problems that computing has today. The building blocks (abstractions) help in putting stuff into the right context.</li>
<li>14:33 <a href="https://en.wikipedia.org/wiki/Thinking,_Fast_and_Slow">WYSIATI</a>: What you see is all there is.</li>
<li><b>23:53 You need to solve the context, not just a problem!</b></li>
<li>24:14 Finding out about the real problem is the big deal and it may be much harder than solving the problem itself.</li>
<li>32:39 What is your company's 10 year plan? Umm...</li>
<li>49:27 Wayne Gretzsky: A good hockey player is going to where the puck is, and a great hockey player is going to where the puck is going to be.</li>
<li>50:11 "Better" and "Perfect" are the two enemies of "What Is Actually Needed".</li>
</ul>
<br />
<h3>The Future Doesn't Have to Be Incremental</h3>
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/gTAghAJcO1o?hd=1&wmode=transparent" width="420"></iframe></span>
<ul>
<li>21:55 Human universals by anthropologist <a href="https://en.wikipedia.org/wiki/Donald_Brown_(anthropologist)">Donald Brown</a> (e.g. coping, social, language, culture, fantasies, stories, news, art, etc.). Most popular software products work as technological amplifiers for at least one such human universal.</li>
<li>28:15 Linux is a budget of bad ideas.</li>
<li>29:12 Real inventions: E.g. writing and reading, abstract math, model-based science, democracy, equal rights, slow deep thinking, etc.</li>
<li>30:48 Isaac Newton changed the way of how people think.</li>
<li>35:23 Wayne Gretzsky: <i>You miss 100% of the shots you don't take.</i></li>
</ul>
<br />
<h3>The computer revolution hasn't happened yet</h3>
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/oKg1hTOQXoY?hd=1&wmode=transparent" width="420"></iframe></span>
<ul>
<li>16:45 OOP architecture: As complexity starts becoming more and more important architecture is always going to dominate material.</li>
<li>24:11 It only takes about 50 cell divisions (iterations) to make a baby.</li>
<li>35:11 In contrast to biology computers are slow, small and stupid.</li>
<li>37:01 Cell membrane acts like a pattern matcher and it keeps most of the things out as much as it keeps certain things in.</li>
</ul>
<br />
<h3>The Best Way to Predict the Future is to Invent It</h3>
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="https://www.youtube.com/embed/yVw42wWZWrg?hd=1&wmode=transparent" width="420"></iframe></span>
<ul>
<li>11:39 We all have a duty to the next generation, whether or not we have children!</li>
<li>13:26 Our brain is mostly set up for reacting (System 1) and it tries to avoid real thinking (System 2).</li>
<li>27:31 <i>"We must ensure that human wisdom exceeds human power"</i> (Vi Hart)
</ul>
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-62605342648977362032017-04-16T22:38:00.001+02:002017-04-16T22:48:54.484+02:00Operating System 101From Andrew S. Tanenbaum's <a href="https://www.cs.vu.nl/~ast/reliable-os/">"Tanenbaum-Torvalds Debate - Part II"</a>.<br />
No flame wars, just operating system and distributed system architecture.<br />
<br />
<i>My view is that you want to avoid shared data structures as much as possible. Systems should be composed of smallish modules that completely hide their internal data structures from everyone else. They should have well-defined ‘thin’ interfaces that other modules can call to get work done. That’s what object-oriented programming is all about – hiding information – not sharing it. I think that hiding information (a la Dave Parnas) is a good idea. It means you can change the data structures, algorithms, and design of any module at will without affecting system correctness, as long as you keep the interface unchanged. Every course on software engineering teaches this. In effect, Linus is saying the past 20 years of work on object-oriented programming is misguided. I don’t buy that.</i><br />
<br />
<i>Once you have decided to have each module keep its grubby little paws off other modules' data structures, the next logical step is to put each one in a different address space to have the MMU hardware enforce this rule. When applied to an operating system, you get a microkernel and a collection of user-mode processes communicating using messages and well-defined interfaces and protocols. Makes for a much cleaner and more maintainable design. Naturally, Linus reasons from his experience with a monolithic kernel and has arguably been less involved in microkernels or distributed systems. My own experience is based on designing, implementing, and releasing multiple such operating systems myself. This gives us different perspectives about what is hard and what is not.</i><br />
<br />
See also: <a href="http://blog.darknedgy.net/technology/2016/01/01/0/">Microkernels are slow and Elvis didn’t do no drugs</a><br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-81155427186019037192017-04-07T14:01:00.002+02:002023-04-19T10:38:31.888+02:00On Building Reliable Automotive Software SystemsDuring the last years me and my team built various automotive software systems in the <a href="https://en.wikipedia.org/wiki/Connected_car">connected car</a> domain as well as in the <a href="https://en.wikipedia.org/wiki/Body_control_module">body</a> domain.<br />
Before that, we built Android-based infotainment systems, mobile internet routers and some kind of wireless display like <a href="https://en.wikipedia.org/wiki/Miracast">Miracast</a>.<br />
Over time, our work became highly inspired by two software platforms and their characteristics: <a href="https://www.erlang.org/">Erlang</a> and <a href="https://developer.android.com/guide/components/fundamentals.html">Android</a>.<br />
Erlang's influence came mostly from its reliability characteristics and its shared-nothing methodology.
Android provides a modular, component-based application framework including a software development kit and documentation which we wanted to have for all kinds of automotive software systems as well.<br />
This led to the developement of the Mindroid application frameworks.<br />
<br />
<h3>What is Mindroid?</h3>
In short, Mindroid is a component-based application framework similar to Google's Android, including a software development kit and documentation.
It builds upon the <a href="https://en.wikipedia.org/wiki/Actor_model">Actor model</a> as core system architecture building block and provides an event-based programming paradigm.<br />
Currently, there are three variants of Mindroid.
<ul>
<li><a href="https://github.com/Himmele/Mindroid.java">Mindroid.java</a> targets the Java platform</li>
<li><a href="https://github.com/Himmele/Mindroid.cpp">Mindroid.cpp</a> targets native platforms, like Linux or QNX Neutrino RTOS</li>
<li><a href="https://github.com/Himmele/Mindroid.ecpp">Mindroid.ecpp</a> targets deeply embedded systems without dynamic memory management, like AUTOSAR OS, <a href="http://www.keil.com/pack/doc/CMSIS/RTOS/html/index.html">CMSIS RTOS</a> or even bare metal</li>
</ul>
One of Mindroid's main goals is to provide a slim platform to develop highly reliable (distributed) software systems. Other goals and their prerequisites are:
<ul>
<li>Modularity: Components with clear interfaces, threading and dependencies</li>
<li>Reuse: Set of reusable components across projects and platforms</li>
<li>SDK: Sustainable, public APIs crafted by an API first design approach (Finding good abstractions and truly care about naming things)</li>
<li>Reliability, testability and refactorings: No shared state between components</li>
<li>Software quality highly benefits from Actor model design approach
<ul>
<li>No complex critical sections</li>
<li>Callbacks run in right thread contexts</li>
<li>Low energy, CPU time and memory requirements</li>
</ul>
</li>
<li>Logging (No long-lasting debugging sessions)</li>
<li>Slim platform: Simplicity is prerequisite for reliability</li>
<li>Scalability: Distributed systems running multiple Mindroid instances on different nodes</li>
</ul>
Mindroid relies on the Erlang-style actor process model to achieve that goals. The core Actor model is mainly based on the Android <i>Thread</i>, <i>Looper</i>, <i>Message</i>, <i>MessageQueue</i>, <i>Handler</i> and <i>Binder</i> classes. Together with the <i>Process</i> class Mindroid implements deployable components and component isolation comparable to Erlang-style process isolation.
The component isolation assures that there is no shared state across component boundaries. This is done by exchanging only <a href="https://en.wikipedia.org/wiki/Passive_data_structure">POD types</a> a.k.a. plain old data structures and component interfaces (actor endpoints) on component interface level. Using such component interfaces one can access further components.
Furthermore, each component clearly defines its own threading behavior within the hosting process to achieve true component isolation regarding data (no shared state) and the runtime environment (process and actor).<br />
<br />
Slide 5 below illustrates the Erlang-style actor process model using a CarFinder component that relies on a LocationManager for location updates.
<span style="display: block; text-align: center;"><br />
<iframe frameborder="0" height="560px" src="https://drive.google.com/file/d/0B_UbcMNexKaIUnAyMDYtNVJKRzg/preview?usp=sharing&resourcekey=0-BoOP9VHT4q9Mnp8R8zWD3Q" width="100%"></iframe><br />
</span>
<br />
For future, we plan to implement Erlang-style distribution transparency for services and service discovery.
And we would love to have a <a href="https://www.rust-lang.org/">Rust</a> variant of Mindroid.<br />
<br />
See also:
<ul>
<li><a href="https://himmele.blogspot.de/2015/10/building-car-as-pragmatic-software.html">Building a car (from the perspective of a pragmatic software engineer)</a></li>
<li><a href="https://www.infoq.com/presentations/concurrency-distributed-computing?utm_campaign=infoq_content&utm_source=twitter&utm_medium=feed&utm_term=architecture-design">Our Concurrent Past; Our Distributed Future</a></li>
<li><a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/acrobat-17.pdf">Butler Lampson's Hints for Computer System Design</a></li>
</ul>
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-42697458310511793312017-03-11T13:48:00.002+01:002017-03-11T14:29:27.995+01:00Characteristics of an efficient engineering teamAn efficient engineering team offers a fun and challenging place to work at.
From my personal experience the following mindset forms the basis of such a team.
<br />
<br />
<b><i>We truly care about things</i></b>
<ul>
<li>Caring means acting</li>
<li>Caring means pushing things forward</li>
<li>Caring means questioning ideas, concepts and decisions</li>
<li>Caring means listening to customer feedback</li>
<li>Caring means answering questions and providing feedback in time</li>
<li>Caring means continually monitoring project progress</li>
<li>We are pragmatic while caring about things</li>
</ul>
<b><i>Failures happen, but we are able to quickly analyze, find and fix them</i></b>
<ul>
<li>Logging helps us in analyzing and finding bugs quickly (without long-lasting debugging sessions)</li>
<li>Simple and elegant design help us in fixing problems instantly as well as in maintaining and refactoring our code base without fear</li>
<li>Tooling is very important to achieve fast bug fixing turnaround times</li>
</ul>
<b><i>We communicate openly</i></b>
<ul>
<li>Open communication means keeping others informed</li>
<li>Open communication works like a push system, not like a pull system</li>
<li>Open communication must no result in overstimulation by steady interruptions</li>
</ul>
<b><i>To understand is to invent</i></b>
<ul>
<li>We keep asking <i>why</i> and question until we understand all the stuff</li>
<li>Understanding all the code and technologies is a prerequisite to quality</li>
</ul>
<b><i>Best Practices</i></b>
<ul>
<li>Strive for simplicity</li>
<li>Keep an eye out for beauty and aesthetics in your code base no matter if it is about architecture, naming or something else</li>
<li>Reduce risk by integrating early and often</li>
<li>Read code, review code! By reading code one learns so much, both from the good and the bad parts of the code base</li>
<li>Fail fast, but don't give up too easily</li>
</ul>
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-48381897447900739802017-02-24T23:03:00.001+01:002017-02-25T09:26:46.424+01:00Psychology and Behavioral Science (not just) for Computer ScientistsThis post contains some few excerpts from the book <a href="http://www.danpink.com/books/drive/">Drive: The Surprising Truth About What Motivates Us</a> from <a href="https://en.wikipedia.org/wiki/Daniel_H._Pink">Daniel H. Pink</a>.<br />
The field of psychology and behavioral science currently preoccupies me a lot mostly due to personal struggles in seeking purpose.<br />
<br />
<h3>Societal Operating Systems</h3>
Societies have operating systems: the laws, social customs and economic arrangements sit atop a layer of instructions, protocols and suppositions about how the world works.<br />
A big part of our societal operating system consists of a set of assumptions about human behavior.<br />
<br />
<b><i>Societal OS v1.0</i></b> code name "Try to survive" was the operating system in place at the beginning of human mankind<br />
<ul>
</ul>
<b><i>Societal OS v2.0</i></b> code name "Humans are more than the sum of their biological urges" is the operating system that currently has the biggest installed base<br />
<ul>
<li>Supports more complex societies</li>
<li>Cooperation</li>
<li>Rewards and punishments to build and scale complex economies</li>
<li>Profit maximization</li>
<li>Enabler for the industrial revolution</li>
<li>Algorithmic, rule-based work</li>
</ul>
<b><i>Societal OS v3.0</i></b> code name "Intrinsic motivation" currently has a small but growing installed base out there<br />
<ul>
<li>Purpose maximization</li>
<li>Social benefit principle</li>
<li>Supports really complex societies</li>
<li>Powerful, new business models: Open-source</li>
<li>Humans have a drive to learn, to create and to make to world a better place</li>
<li>Effectiveness</li>
<li>Heuristic tasks</li>
</ul>
<br />
<h3>Intrinsic motivation</h3>
Intrinsic motivation depends on autonomy, mastery and purpose.<br />
To develop intrinsic motivation an undertaking itself must provide <b><i>freedom</i></b>, <b><i>challenge</i></b> and <b><i>purpose</i></b> to the people.<br />
<br />
<b><i>Self-Determination Theory</i></b><br />
The <a href="https://en.wikipedia.org/wiki/Self-determination_theory">self-determination theory</a> describes three innate human needs: competence, autonomy and relatedness.
Satisfying these needs results in motivation, productivity and happiness.<br />
<br />
<b><i>The Open-Source Movement</i></b><br />
<ul>
<li>Enjoyment-based intrinsic motivation is the strongest and most pervasive driver</li>
<li>The fun of mastering a given software problem and the desire to give a gift to the community</li>
<li>Social benefit principle replaces maximum profit principle</li>
<li>Open-source people are mostly intrinsically motivated purpose maximizers</li>
<li>Open-source people love creativity, interest and self-direction</li>
</ul>
<b><i>Flow</i></b><br />
<a href="https://en.wikipedia.org/wiki/Flow_(psychology)">Flow</a> in positive psychology is the mental state of operation in which a person performing an activity is fully immersed in a feeling of energized focus, full involvement, and enjoyment in the process of the activity. People can frequently reach "flow" in case of optimal challenges.<br />
<ul>
<li>Flow, the deep sense of engagement, is the oxygen of the soul we need to survive</li>
<li>People are much more likely to reach a flow state at work than in leisure</li>
<li>Why at work? Maybe due to clear goals, immediate feedback, challenges matching to our abilities</li>
<li>This way, organizations can enrich people's lives</li>
</ul>
<b><i>Autonomy and Self-Direction</i></b>
<ul>
<li>Autonomy over 4 aspects of work: what people do, when they do it, how they do it and whom they do it with</li>
<li>People should focus on the undertaking itself rather than on the time to do it</li>
<li>People should contribute rather than just show up and grind out the day</li>
<li>The opposite of autonomy is control. Control leads to compliance, autonomy leads to engagement</li>
<li>The billable hour is a relic of societal OS 2.0</li>
</ul>
<b><i>Mastery</i></b>
<ul>
<li>Mastery is the desire to get better and better at something that matters</li>
<li>Only engagement produces mastery</li>
<li>The modern workplace's most notable feature may be its lack of engagement and its disregard for mastery</li>
<li>Flow is essential to mastery</li>
<li>Grit may be as essential as talent to high accomplishment</li>
<li>Mastery is an asymptote. You can approach it without ever reaching it</li>
<li>Mastery can be an ethic for living</li>
<li>Mastery is a mindset! -> Intelligence is something you can develop</li>
<li>Mastery is a pain! -> Mastery requires effort over a long time</li>
<li>Does your company or team have and share a mastery mindset?</li>
</ul>
<i>Carol Dweck</i>: What people believe shapes what people achieve.
<ul>
<li>Our believes about ourselves and the nature of our abilities (our self-fears) determine how we interpret our experiences and can set the boundaries on what we accomplish</li>
<li>Effort is one of the things that gives meaning to life. Effort means you care about something, that something is important to you and you are willing to work for it</li>
<li>It would be an impoverished existence if you were not willing to value things and commit yourself to working toward them</li>
</ul>
<b><i>Purpose</i></b>
<ul>
<li>It is in our nature to seek purpose</li>
<li>The secret to high performance isn't our biological drive or our reward and punishment drive but our third drive: our deep-seated desire to direct our own lives, to extend and expand our abilities, and to live a life of purpose</li>
<li>Societal OS 3.0 is built for purpose maximization</li>
<li>Purpose maximization is about seeking the right goals</li>
<li>A healthy society or healthy organization needs sustainable purpose</li>
<li>"They" and "we" companies are very different places</li>
<li>What is your company's purpose?</li>
<li>What gets you up at morning? What keeps you up at night?</li>
</ul>
<br />
<h3>Extrinsic motivation</h3>
<ul>
<li>Good for algorithmic, rule-based tasks</li>
<li>If-then rewards require people to forfeit some of their autonomy and therefore undermining the intrinsic motivation toward the activity</li>
<li>Try to offer now-that rewards instead of if-then rewards by praising and providing positive feedback with useful information</li>
<li>Rewards narrow people's focus</li>
<li>Goals may narrow people's focus, decrease cooperation and decrease intrinsic motivation</li>
</ul>
<br />
See also:
<ul>
<li>Book summary from <a href="http://www.samuelthomasdavies.com/book-summaries/business/drive/">Samuel Thomas Davies</a></li>
<li>RSA ANIMATE: The surprising truth about what motivates us</li>
</ul>
<span style="display: block; text-align: center;">
<object height="346" width="420"><param name="movie" value="https://www.youtube.com/v/u6XAPnuFjJc&hl=en_US&fs=1&color1=0x3a3a3a&color2=0x999999"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="https://www.youtube.com/v/u6XAPnuFjJc&hl=en_US&fs=1&color1=0x3a3a3a&color2=0x999999" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="420" height="346"></embed></object>
</span>
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-79821041094671041682016-08-06T18:29:00.002+02:002016-08-06T18:31:00.567+02:00Danny Hillis: The Pattern on the Stone"The greatest achievement of our technology may well be the creation of tools that allow us to go beyond engineering - that allow us to create more than we can understand."
<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-66643150168715947702016-01-26T23:49:00.002+01:002016-01-27T00:24:59.815+01:00Unsere Art zu leben - Eine ehrliche Gesellschaftskritik<section class="header" style="background-color: white; color: #333333; font-family: 'SZ Sans', 'Neue Helvetica', Helvetica, sans-serif; font-size: 13.3333px; line-height: 16px; position: relative;">
</section><section class="body" id="article-body" style="background-color: white; color: #333333; font-family: 'SZ Text', Georgia, Times, serif; font-size: 13.3333px; line-height: 16px; position: relative;"><div class="article-sidebar-wrapper" id="article-sidebar-wrapper" style="font-family: 'SZ Sans', 'Neue Helvetica', Helvetica, sans-serif; font-size: 1.5em; height: 2421.16px; left: -91px; margin: 0px; padding: 0px; position: absolute;">
</div>
<div class="article entry-summary" style="font-family: 'SZ Sans', 'Neue Helvetica', Helvetica, sans-serif; font-size: 1.15em; font-weight: 700; line-height: 1.4em; margin-bottom: 1.4em; padding: 0px;">
Es gibt Menschen, die die freien Gesellschaften mit Gewalt bekämpfen. Und es gibt Menschen, denen diese freien Gesellschaften Gewalt antun - ohne dass dies hier groß auffallen würde.</div>
<section class="authors" style="margin: 0px 0px 2em;"><div class="authorContainer" style="font-family: 'SZ Sans', 'Neue Helvetica', Helvetica, sans-serif; margin: 0px; padding: 0px; position: relative;">
<div class="authorProfileContainer" style="margin: 0px; padding: 0px;">
<ul class="authorProfiles" style="float: left; margin: 0px; max-width: 47%; padding: 0px;"></ul>
<span class="moreInfo" style="color: #888888; float: none; font-size: 1.15em; width: auto;"><span style="font-family: "sz text" , "georgia" , "times" , serif; font-style: italic; font-weight: inherit; padding-top: 0.4em;">Von <span data-abbr="de" id="abbr-de" style="cursor: pointer; text-decoration: underline;"><a href="http://www.sueddeutsche.de/politik/wohlstand-unsere-art-zu-leben-1.2819588">Detlef Esslinger (Süddeutsche Zeitung)</a></span></span></span></div>
</div>
</section><span class="opc-anchor"></span><span id="sharingbaranchor"></span><div style="font-size: 1.15em; line-height: 1.4em; margin-bottom: 1.4em; padding: 0px;">
Immer, wenn irgendwo auf der Welt Terroristen gemordet haben, müssen Regierungschefs vor Kameras treten und einige Sätze dazu erklären. Eine traurige Routine ist das geworden; Angela Merkel bewältigt sie mit Variationen ein und derselben Bemerkung. Die Terroristen zielten auf "unser freies Leben in freien Gesellschaften", sagte sie nach dem Anschlag von Istanbul. Sie griffen "unsere Art zu leben" an, sagte sie nach dem Horror von Paris, vor zwei Monaten. Es sind Worte des Trotzes und des Beharrens - was in dem Moment auch angemessen ist. Doch in ihnen verbirgt sich viel mehr, als das Floskelhaftige in ihnen zum Ausdruck zu bringen scheint.</div>
<div style="font-size: 1.15em; line-height: 1.4em; margin-bottom: 1.4em; padding: 0px;">
Dass Gesellschaften sich von Terroristen nicht intellektuell herausfordern (oder gar einschränken) lassen, ist eine Binsenweisheit, die nur Terroristen nie kapieren. Wer andere in die Luft sprengt oder erschießt, mit dem diskutiert man nicht, den bekämpft man. Dennoch steckt in einer Formulierung wie "unsere Art zu leben" nicht allein eine Kampfansage an Mörder. Denn zum einen mag sie die Freiheit beschreiben, nach Istanbul zu reisen und dort die Hagia Sophia zu besichtigen; oder den Besuch von Kneipen, Restaurants und Konzerten in Paris, München, Kopenhagen. Sie mag zum Ausdruck bringen, dass in freien Gesellschaften jeder nach seiner Façon leben darf; Männer, Frauen, Schwule, Heteros, Fleischesser, Vegetarier, Gläubige, Atheisten.</div>
<div style="font-size: 1.15em; line-height: 1.4em; margin-bottom: 1.4em; padding: 0px;">
Das ist das eine, das von dem Begriff umfasst wird. Das andere ist das, worauf ausgerechnet Angela Merkel einmal hingewiesen hat, und zwar ganz und gar nicht im Zusammenhang mit Terror. Es ist einige Jahre her, es war die Neujahrsansprache kurz nach dem gescheiterten Weltklimagipfel von <span class="nowrap" style="white-space: nowrap;">2009</span>. Da dachte sie laut darüber nach, "wie wir unseren Wohlstand erhalten" - nämlich "indem wir unsere Art zu leben und zu wirtschaften ändern".</div>
<div style="font-size: 1.15em; line-height: 1.4em; margin-bottom: 1.4em; padding: 0px;">
Es wäre geboten, die Lebensart in den reichen, freien Gesellschaften als beides wahrzunehmen: als Errungenschaft und als gigantisches Problem. Gelebt wird hier ein Freiheitsverständnis, das absolut ist. Nichts ist den Menschen hier fremder als Beschränkung im persönlichen Alltag. Freiheit ist erstens der Kneipenbesuch und zweitens, dass der Wirt Heizpilze auf den Gehsteig stellt, damit man auch im Januar den Wein und den Barsch draußen genießen kann. Freiheit ist, dass Amerikaner 6,6 Milliarden Kilowattstunden Strom allein für Weihnachtsbeleuchtung aufwenden, mehr als Tansania im gesamten Jahr verbraucht. Freiheit ist, ein Auto zu bauen (und zu kaufen), das pro Kilometer 224 Gramm Kohlendioxid ausstößt. Benedikt XVI. war ein Papst, der nicht mit Beispielen erklärte, sondern der lieber grundsätzlich formulierte. So gelang ihm der Satz, "dass Materie nicht nur Material für unser Machen ist" - den Menschen des <span class="nowrap" style="white-space: nowrap;">21</span>. Jahrhunderts muss man an eine solche Banalität erinnern. Denn der macht und macht; und wer denkt schon über Terrorismus, Klimawandel und Flüchtlinge nach, wenn er unterm Heizpilz sitzt.</div>
<div style="font-size: 1.15em; line-height: 1.4em; margin-bottom: 1.4em; padding: 0px;">
Das ist in Wahrheit die größte Herausforderung: die Auseinandersetzung mit einem so alltäglich gewordenen Lebensstil. Das Nachdenken darüber, ob zum Beispiel aus Westafrika auch deshalb so viele Flüchtlinge kommen, weil europäische Kutter den Einheimischen dort die Barsche weggefischt haben? Wie viele ökonomische und kulturelle Konflikte künftig allein deshalb drohen, weil Menschen ihre Heimat für unbewohnbar erklären und nach Europa aufbrechen; mal der Armut wegen, mal um einem Krieg zu entkommen, immer aus Perspektivlosigkeit? "Wir haben unseren Wohlstand auf dem Rücken der Entwicklungsländer aufgebaut. Das wird nicht mehr lange gut gehen. Diese Spannungen entladen sich." Hört sich nach Brot-für-die-Welt-Sätzen an. Ihr Urheber kommt aber aus der CSU, es ist der Entwicklungsminister Gerd Müller. Er fügt noch hinzu, dass man sich nur nichts von Obergrenzen für Flüchtlinge versprechen soll: "Die Menschen werden uns nicht fragen, ob sie kommen können."</div>
<div style="font-size: 1.15em; line-height: 1.4em; margin-bottom: 1.4em; padding: 0px;">
Die Klima-Apokalypse wird zwar nicht dadurch verhindert, dass Politiker im Dezember in Paris eine Vereinbarung dazu getroffen haben. Doch ohne eine solche Vereinbarung würde sie ganz gewiss eines Tages zur Realität. So wie der Vereinbarung erst noch Taten folgen müssen, so werden Menschen zu ebenjenen Taten nur bereit sein, wenn es eine Instanz gibt, die sie orchestriert. Niemand gibt auch nur Teile seiner Lebensweise auf, also von Freiheit, solange er mit Recht sagen kann: "Nützt ja doch nichts." Solange bleibt die Menschheit ein Gewusel aus Räuberbanden - und in dem trachtet jeder nach Beute, solange es noch Beute gibt. In diesem Gewusel wird es immer einen Unterschied geben zwischen abstrakten Einsichten und konkretem Handeln. Ausgerechnet ein katholischer Bischof lebt diesen Unterschied auf unübertreffliche Art vor. Erst schrieb er neulich einen Aufsatz, in dem er "die Industrienationen" aufforderte, die Emissionen zu reduzieren. Dann schaffte er als Dienstwagen einen VW Phaeton an, das Auto, das <span class="nowrap" style="white-space: nowrap;">224</span> Gramm Kohlendioxid pro Kilometer ausstößt. Typisch Bischof? Typisch Mensch.</div>
<div id="iq-artikelanker" style="margin: 0px; padding: 0px;">
</div>
<div style="font-size: 1.15em; line-height: 1.4em; margin-bottom: 1.4em; padding: 0px;">
Die Frage des <span class="nowrap" style="white-space: nowrap;">21</span>. Jahrhunderts ist, ob der Mensch lernen wird, dass Wohlstand nur durch Verzicht zu sichern ist - siehe Merkels Neujahrsansprache von <span class="nowrap" style="white-space: nowrap;">2009</span> -, und ob er bereit ist, sich diesen Verzicht organisieren zu lassen. Jeder Gemeinschaft geht es schlecht, wenn der Einzelne alle Freiheiten haben darf; sei es eine Nation oder eine Weltgemeinschaft. Jeder Staat beschneidet - zum Beispiel durch Steuern - die Freiheit seiner Bürger. Wenn die Einzelnen weniger haben, haben alle zusammen mehr. Das ist der Gedanke dabei. Lässt sich dieses Prinzip auf die Welt als Ganzes übertragen?</div>
<div style="font-size: 1.15em; line-height: 1.4em; padding: 0px;">
Es gibt Menschen, die "unsere Art zu leben" mit Gewalt bekämpfen, und es gibt Menschen, denen diese Lebensart ihrerseits Gewalt antut. Auf einen "sozialen Klimawandel" stimmt der Essener Bischof Franz-Josef Overbeck die Deutschen deshalb ein (der mit dem Phaeton, übrigens). Er meint damit, dass Zuwanderung kein vorübergehendes Phänomen sein wird. Nur welches Ausmaß sie bekommen wird, das können die Menschen in den reichen Ländern mitbestimmen - noch.<br />
<br /></div>
</section>Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-21969939146240764282015-10-07T00:21:00.000+02:002017-05-13T22:22:36.386+02:00Building a car (from the perspective of a pragmatic software engineer)The ideas for building a car from the perspective of a pragmatic software engineer came up during the series development of an Internet of Things (IoT) platform and control unit for a German automaker.<br />
The automotive industry is currently undergoing a disruptive technology change mainly driven by software. The self-driving (electric) car will not only change the automotive industry but also society and urban life.<br />
To enable this technology change, the automotive industry finally needs sustainable software platforms that allow for building reliable and scalable software systems in a very short time. (And I am definitely not talking about <a href="https://en.wikipedia.org/wiki/AUTOSAR">AUTOSAR</a> here.)<br />
Hence, the automotive industry needs to build software platforms including software development kits (SDK), great APIs, documentation and tools.
The automakers must design for simplicity, modularity and security. This requires them to look at the car as a (classical) distributed system of computers and to find good <a href="https://en.wikipedia.org/wiki/Abstraction_(computer_science)">abstractions</a> to easily manage each system and the whole system of systems.<br />
Today, I often see a lot of bad abstractions or no abstractions at all in automotive software systems. That results in slow development cycles, way to much (unreadable) code which is hard to maintain, and at worst, unhappy developers.<br />
Having some good fundamental abstractions would allow for building applications from a set of reusable components that form the basic building blocks of this new software platforms. (And no, I don't have AUTOSAR Software Components in mind.)<br />
<br />
So what kinds of software platforms do you need to build a car?<br />
<ul>
<li>Deeply embedded (body) domain (engine, powertrain, light, etc.)</li>
<li>Infotainment domain (Head units, dashboards and head-up displays)</li>
<li>Internet of Things domain (secure cloud connectivity, eCall, WiFi hotspot, car sharing, over-the-air updates)</li>
<li>Driver assistance systems for self-driving cars (highly reliable, real-time number crunchers)</li>
<li>Private cloud (machine learning platforms to teach your self-driving cars, data mining to analyse customer behavior, online services like roadside assistance, etc.)</li>
</ul>
<b>Deeply embedded (body) domain</b><br />
Automotive real-time software systems of this domain run on embedded controllers with little CPU power and few memory. Therefore, application frameworks and libraries for these kinds of systems avoid or lack dynamic memory allocation and many other well-known abstractions. We have built our own application framework for this kind of deeply embedded systems, called <a href="https://github.com/Himmele/Mindroid.ecpp">Mindroid.ecpp</a>.<br />
<br />
<b>Infotainment domain</b><br />
Systems in this category are often the same as today's high-end smartphones. So why not use today's smartphone platforms for these kinds of system, or at least parts of it.<br />
<br />
<b>Internet of Things domain</b><br />
Systems in this category are often the same size as today's mid-range smartphones. So why not use today's IoT application frameworks and smartphone platforms for these kinds of systems.<br />
<br />
<b>Driver assistance systems (for self-driving cars)</b><br />
Hardware and software systems in this category are really big computing beasts. Due to its reliability and safety (<a href="https://en.wikipedia.org/wiki/Automotive_Safety_Integrity_Level">ASIL</a>) requirements, these are the most challenging and interesting automotive software platforms of the future.<br />
<br />
<b>Private clouds</b><br />
Well, private clouds. Let's do it with Erlang technologies! (Or with any other well-known open source infrastructure.)<br />
To be honest, building a machine learning and data mining platform really is some work to do. Today, only IT giants like Google, Facebook, Amazon, Apple, Microsoft, etc. own and operate such platforms. Hopefully, this will change.<br />
<br />
Now let's bring the various car domains (yes, also the private cloud) together. As we <a href="http://himmele.blogspot.de/2010/11/alan-kay-on-object-oriented-programming.html">learned from Alan Kay</a>, the key in making great and growable systems is much more to design how its modules communicate rather than what their internal properties and behaviors should be. Hence, the connected car needs a simple, clean and robust messaging paradigm.<br />
Choosing form the classical messaging paradigms of distributed systems, I think <a href="https://en.wikipedia.org/wiki/Publish%E2%80%93subscribe_pattern">topic-based publish-subscribe messaging</a> fits best for most use-cases. It allows us to build loosely coupled, flexible, scalable and easy to test (asynchronous) software systems. And it avoids dependencies, something that is really important when evolving systems.
Furthermore, a publish-subscribe messaging infrastructure should support quality of service levels for at-most-once, at-least-once and exactly-once delivery to simplify the overall software architecture.<br />
One can also add synchronous messaging systems, like <a href="https://en.wikipedia.org/wiki/Remote_procedure_call">Remote procedure calls</a>. I always try to keep synchronous remote procedure calls to a minimum in order to avoid some of the dependencies (and shared state) they often introduce into distributed systems.<br />
What data to exchange with the publish-subscribe messaging between the domains? Well, let's define a <a href="https://en.wikipedia.org/wiki/Domain_model">domain model</a> for representing real-world (domain-specific) objects, processes and rules.<br />
E.g. speed, mileage, door states, window states, sequences to safely open the car by a smartphone app, and so on.<br />
Applications must only know about the application framework, the publish-subscribe mechanism and the domain model. They should definitely not know about which protocol to use for domain model exchange, serialization, model binding and many other things. This has to happen within the application framework and a publish-subscribe messaging service.<br />
To evolve the domain model over time, protocols like Google's protocol buffers that allow for changing message formats without breaking backwards-compatibility provide great flexibility.<br />
Using a publish-subscribe messaging mechanism abstracts away all the quirks of automotive bus systems and protocols like CAN, LIN, FlexRay, MOST or even Ethernet.<br />
And of course you never have the "one size fits all" abstraction. E.g. besides publish-subscribe messaging you still need H.264 video streaming over RTP to connect your cameras to a driver assistance system, and others.<br />
<br />
To sum up, the automotive industry should build application frameworks with a few simple building blocks for each domain and provide a variety of system services on top of it, e.g. logging, publish-subscribe messaging, power management (using wake locks and leases), etc. - just like Google did with the Open Handset Alliance.<br />
<br />
<b>Advice for ambitious system architects and application framework engineers</b><br />
<ul>
<li>The most dangerous enemy of a better solution is an existing codebase that is just good enough - Eric S. Raymond.</li>
<li>Seriously think about threading and message-passing. Get the damn threading right <i>by</i> the application framework <i>for</i> the application developers. You are developing an application framework for developers, not against them!</li>
<li>Modularity is there for reusability of components and to ease refactorings within software systems while trying to minimize dependencies between the components. Try to minimize the number of control units within a car!</li>
<li>Keep an eye out for beauty and aesthetics in software systems. This has to do with software architecture and naming. Naming is so important!</li>
</ul>
<b>Links</b><br />
<ul>
<li><a href="http://www.wsj.com/articles/SB10001424053111903480904576512250915629460">Software is eating the world, by Marc Andreessen</a></li>
<li><a href="https://himmele.blogspot.com/2017/04/on-building-reliable-automotive.html">On Building Reliable Automotive Software Systems</a></li>
<li><a href="https://youtu.be/NdSD07U5uBs">Power of Simplicity, by Alay Kay</a></li>
<li><a href="https://himmele.blogspot.com/2010/11/alan-kay-on-object-oriented-programming.html">Alan Kay on Object-Oriented Programming</a></li>
</ul>
<br />
<span style="font-size: x-small;">This is my personal opinion about software engineering in the automotive sector, not that of the company I am working for, nor of anybody else in that company.
</span>
<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-40708876522851676472014-05-02T18:10:00.000+02:002014-05-02T18:12:55.272+02:00RISC design principles for project managementWhen David A. Patterson and Carlo H. Sequin designed the first RISC processors in the beginning of the 80s they soon realized that designing instructions that could be issued (started) quickly was the key to good performance. While the initial emphasis was on simple instructions that could be executed quickly, they learned, that how long an instruction actually took mattered less than how many could be started per second.<br />
I learned that the same principles apply to good project management in the last few years. Thanks RISC designers!<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-58139191004416849652013-10-01T00:04:00.001+02:002015-09-29T22:55:04.372+02:00Mindroid - Android everywhereMindroid is an application framework that lets you create applications using a set of reusable components - just like Android.
The name Mindroid has two different meanings. On one hand Mindroid is a minimal set of core Android classes and on the other hand these classes also form Android's mind (at least in my opinion).
There are three versions of Mindroid focusing on different domains.<br />
<br />
The feature-richest version is <b><a href="https://github.com/Himmele/Mindroid.java">Mindroid.java</a></b>. It is a complete application framework intended for machine-to-machine (M2M) communication projects and the Internet of Things. It is almost completely Android API-compliant with minor exceptions since Mindroid even runs on Java v1.4 (Java SE and Jave ME CDC) platforms like IBM's J9 Java virtual machine on Qualcomm's modem chipsets running an L4 microkernel OS. Mindroid.java also includes an application framework <a href="http://esrlabs.com/Mindroid">documentation</a>. For the future, I plan to make Mindroid run on Java ME 8.<br />
<br />
Another version of Mindroid is <b><a href="https://github.com/Himmele/Mindroid.cpp">Mindroid.cpp</a></b>. It is written in C++ using reference counting and other nice gimmicks. Currently, Mindroid.cpp is not really a complete application framework but focuses on Android's messaging and concurrency features. Nevertheless, it provides all messaging abstractions for implementing a lot of applications - the <a href="https://github.com/Himmele/AndroidTransporterPlayer">Android Transporter Player</a> is one such example. At the moment Mindroid.cpp runs on POSIX operating systems like Linux, Android or QNX Neutrino RTOS and it uses dynamic memory allocations.<br />
<br />
The third version is <b><a href="https://github.com/Himmele/Mindroid.ecpp">Mindroid.ecpp</a></b>. This deeply embedded version of Mindroid is similar to Mindroid.cpp but it runs on tiny embedded operating systems like <a href="http://www.keil.com/pack/doc/CMSIS/RTX/html/index.html">CMSIS-RTOS</a> for ARM Cortex-M processors and it also runs on <a href="http://de.wikipedia.org/wiki/OSEK-OS">AUTOSAR-OS</a> for various embedded processors. Such deeply embedded environments often lack dynamic memory allocation which is also not required by Mindroid.ecpp.<br />
<br />
<h3>Why?</h3>
One of the main reasons for building Mindroid is the fantastic <a href="http://en.wikipedia.org/wiki/Actor_model">Actor</a> implementation of Google's Android operating system. This actor model is the core building block of Android's whole software architecture.
In all versions of Mindroid (and Android) an Actor is implemented by the <a href="http://esrlabs.com/Mindroid/reference/mindroid/os/Looper.html">Looper</a> and <a href="http://esrlabs.com/Mindroid/reference/mindroid/os/Handler.html">Handler</a> classes. A Looper has a thread and a message queue. The threads blocks on the message queue waiting for something to do. To put something into a message queue there is the <a href="http://esrlabs.com/Mindroid/reference/mindroid/os/Handler.html">Handler</a> class. Each Handler also has a handleMessage method for processing messages. An example of this scenario is given in the documentation of the <a href="http://esrlabs.com/Mindroid/reference/mindroid/os/Looper.html">Looper</a> class.
Each Handler is attached to exactly one message queue (and thus to one Looper) at creation time. A message object always refers to its Handler that will process it later.
Now think of software components in terms of Handlers. Software components (Handlers) talk to each other by passing messages. For example, you can run each Handler on its own Looper (thread) if you like. But you are also allowed to put multiple Handlers on the same Looper. (Android is also able to put multiple Handlers in different operating system processes that communicate with each other using the Binder IPC.) This behavior (software architecture) is changeable at will without a need to change the inner workings of a software component.<br />
<br />
<h3>How?</h3>
Here are "Hello World" examples (using two Handlers) for all versions of Mindroid. One Handler prints "Hello " and the other one "World!" once in a second resulting in "Hello World!" outputs.<br />
<br />
<b><a href="https://github.com/Himmele/Mindroid.java/blob/master/src/examples/HelloWorld.java">Mindroid.java</a></b><br />
<pre class="brush:java">
public class HelloWorld extends Service {
private static final String LOG_TAG = "HelloWorld";
private static final int SAY_HELLO = 0;
private static final int SAY_WORLD = 1;
private Handler mHelloHandler = new Handler() {
public void handleMessage(Message message) {
switch (message.what) {
case SAY_HELLO:
System.out.print("Hello ");
mWorldHandler.obtainMessage(SAY_WORLD)
.sendToTarget();
break;
}
}
};
private Handler mWorldHandler = new Handler() {
public void handleMessage(Message message) {
switch (message.what) {
case SAY_WORLD:
System.out.println("World!");
Message hello = mHelloHandler
.obtainMessage(SAY_HELLO);
mHelloHandler.sendMessageDelayed(hello, 1000);
break;
}
}
};
public void onCreate() {
mHelloHandler.obtainMessage(SAY_HELLO)
.sendToTarget();
}
public void onDestroy() {
mHelloHandler.removeMessages(SAY_HELLO);
mWorldHandler.removeMessages(SAY_WORLD);
}
public IBinder onBind(Intent intent) {
return null;
}
}
</pre>
<b><a href="https://github.com/Himmele/Mindroid.cpp/blob/master/tests/HelloWorld.cpp">Mindroid.cpp</a></b><br />
<pre class="brush:cpp">
static const int SAY_HELLO = 0;
static const int SAY_WORLD = 1;
class HelloHandler : public Handler {
public:
HelloHandler(const sp<Handler>& worldHandler) :
mWorldHandler(worldHandler) {
}
virtual void handleMessage(const sp<Message>& msg) {
switch (msg->what) {
case SAY_HELLO:
printf("Hello ");
sp<Message> message = mWorldHandler
->obtainMessage(SAY_WORLD);
message->metaData()->putObject("Handler", this);
message->sendToTarget();
break;
}
}
private:
sp<Handler> mWorldHandler;
};
class WorldHandler : public Handler {
public:
WorldHandler() {
}
virtual void handleMessage(const sp<Message>& msg) {
switch (msg->what) {
case SAY_WORLD:
printf("World!\n");
sp<Handler> helloHandler = msg->metaData()
->getObject<Handler>("Handler");
sp<Message> message = helloHandler
->obtainMessage(SAY_HELLO);
helloHandler->sendMessageDelayed(message, 1000);
break;
}
}
};
int main() {
Looper::prepare();
sp<Handler> worldHandler = new WorldHandler();
sp<Handler> helloHandler =
new HelloHandler(worldHandler);
helloHandler->obtainMessage(SAY_HELLO)
->sendToTarget();
Looper::loop();
return 0;
}
</pre>
<b><a href="https://github.com/Himmele/Mindroid.ecpp/blob/master/examples/HelloWorld.cpp">Mindroid.ecpp</a></b><br />
<pre class="brush:cpp">
static const int SAY_HELLO = 0;
static const int SAY_WORLD = 1;
class HelloHandler : public Handler {
public:
HelloHandler(Handler& worldHandler) :
mWorldHandler(worldHandler) {
}
virtual void handleMessage(const Message& msg) {
switch (msg.what) {
case SAY_HELLO:
printf("Hello ");
mWorldHandler.obtainMessage(mMessage,
SAY_WORLD);
mMessage.obj = this;
mMessage.sendToTarget();
break;
}
}
private:
Handler& mWorldHandler;
Message mMessage;
};
class WorldHandler : public Handler {
public:
WorldHandler() {
}
virtual void handleMessage(const Message& msg) {
switch (msg.what) {
case SAY_WORLD:
printf("World!\n");
Handler* helloHandler = (Handler*) msg.obj;
helloHandler->obtainMessage(mMessage,
SAY_HELLO);
helloHandler->sendMessageDelayed(mMessage,
1000);
break;
}
}
private:
Message mMessage;
};
static uint8_t sHelloHandler[sizeof(HelloHandler)];
static uint8_t sWorldHandler[sizeof(WorldHandler)];
int main() {
Message message;
Looper::prepare();
Handler* worldHandler =
new (sHelloHandler) WorldHandler();
Handler* helloHandler =
new (sWorldHandler) HelloHandler(*worldHandler);
helloHandler->obtainMessage(message, SAY_HELLO);
message.sendToTarget();
Looper::loop();
return 0;
}
</pre>
<br />
For more information on Mindroid please consult the <a href="https://github.com/Himmele/Mindroid.java">Mindroid.java</a> <a href="http://esrlabs.com/Mindroid">documentation</a> and the examples provided with the application frameworks on <a href="https://github.com/Himmele?tab=repositories">GitHub</a>.<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-37798038210683065942013-04-18T23:46:00.000+02:002013-04-27T19:07:46.183+02:00Concurrency: A single human body cell versus the internetThis week I asked <a href="http://en.wikipedia.org/wiki/Alan_Kay">Alan Kay</a> (the inventor of <a href="http://en.wikipedia.org/wiki/Object-oriented_programming">OOP</a>, <a href="http://en.wikipedia.org/wiki/Smalltalk">Smalltalk</a>, the <a href="http://en.wikipedia.org/wiki/Dynabook">Dynabook</a>, and much more)<b> if there are more concurrent activities going on inside a single human body cell than on the whole internet?</b> Since he is a computer scientist as well as a molecular biologist he seemed to be the right person to answer this question. Here is a summary of the short conversation:<br />
<div style="background-color: transparent; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<span style="font-size: 12px; line-height: 18px; white-space: pre-wrap;"><br /></span></div>
<div style="background-color: transparent; color: #222222; font-family: arial, sans-serif; font-size: 13px;">
<div style="font-family: 'times new roman', 'new york', times, serif; font-size: 14pt;">
Hi Daniel</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<br /></div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
Good question -- and we have to work on the question some more in order to get a reasonable comparison.</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<br /></div>
<div style="font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
Since matter is concurrently active at the subatomic level, the more mass we have the more concurrent activities -- so the Internet wins here because it has much more mass.</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<br /></div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
Things get a lot more tricky at the "cell mechanics" level. Typical human body cells have about 80 billion large molecules of about 10,000 types <span style="background-color: transparent;">(the other 70% is water and other small molecules), and these are concurrently active. </span></div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<span style="background-color: transparent;">There are several billion computers on the Internet (plus many nuts and bolts computers such as routers) and we can guess that most of these have a few hundred processes each (and each with some number of threads) -- all of which are pseudo-concurrent (it's really how many CPU type things are operating).</span></div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<br /></div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
So at the hardware level with real CPU like things, there are likely ~ 10 in each computer, and now more with multiples cores, so that gives us an estimate of around 20 billion real concurrent processes not counting routers and other infrastructure.</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<br /></div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
If we count pseudo-processes (which are logically concurrent), then I think in the Internet we've exceeded a single cell at the active large molecule as a process level of concurrency.</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<br /></div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
We have about 10 Trillion cells in our body that have our DNA (and about 90 Trillion that are microorganisms of many different kinds).</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<br /></div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
I think we are safe to say that the concurrent activities in one human body completely dominate the Internet.</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<br /></div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
However, I have not looked below the CPU level to processes at the hardware level .... perhaps you'd like to take a shot at estimating that!</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<br /></div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
Cheers,</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
Alan</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
</div>
</div>
<br />
<br />
Hi Alan,<br />
<br />
thanks for your detailed answer. I really appreciate that you took the time to think about this.
I came up with this question when thinking about concurrency (maybe also parallelism and message passing) as measurement unit for complex systems.
There is no measurement unit for concurrency, I think. But its quite hard to define one, just like comparing the incomparable :-).
<br />
...<br />
I also tried to google the answer to this question but since I am a software engineer and only a hobbyist in biology, I wasn't quite sure if I can count all proteins as concurrently active entities or if I should only count ribosomes, motor proteins etc. as concurrently active. On the internet I found that there are about 15.000 ribosomes in one single cell. If only counting ribosomes (which I think is not correct) would reduce the concurrency within a human body cell enormously. Hard to compare...<br />
<br />
Thank you very much and best regards,<br />
Daniel<br />
<br />
<br />
<div style="font-family: arial, sans-serif; font-size: 13px;">
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 18px;">
<div style="font-size: 19px;">
<div style="font-family: 'times new roman', 'new york', times, serif; font-size: 14pt;">
Hi Daniel</div>
<div style="background-color: transparent; font-family: 'times new roman', 'new york', times, serif; font-size: 19px;">
<br /></div>
You have to at least count proteins that are acting as enzymes -- they are continuously active. Also, you will be interested (and amazed) if you look at the dynamics of biochemistry (i.e. why does it work? How do the molecules "find" each other). These processes are happening concurrently.</div>
<div style="background-color: transparent; font-size: 19px;">
<br /></div>
<div style="background-color: transparent; font-size: 20px;">
I think it is hard to compare -- but mainly for "level" not for estimating how many entities are actually "in process" concurrently.</div>
<div style="background-color: transparent; font-size: 20px;">
<br /></div>
<div style="background-color: transparent; font-size: 20px;">
Cheers,</div>
<div style="background-color: transparent; font-size: 20px;">
Alan</div>
</div>
</div>
<br />
<br />
Really impressive, isn't it? And we software engineers think that today's multi-core computers provide concurrency and parallelism. |-O
<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com2tag:blogger.com,1999:blog-8471450961411756399.post-24944398132611110972012-11-04T13:25:00.001+01:002015-09-29T16:02:27.463+02:00Concurrent Hello World in Go, Erlang and C++This week I started taking a deeper look at the Go programming language since I am somewhat addicted to scalability, reliability, concurrency and message passing :-).
The first thing I always do when playing around with a new software platform is to write a concurrent "Hello World" program. The program works as follows: One active entity (e.g. thread, Erlang process, Goroutine) has to print "Hello " and another one "World!\n" with the two active entities synchronizing with each other so that the output always is "Hello World!\n". Here is the concurrent Hello World program in Go, Erlang and in C++ using the Mindroid framework.
<br />
<br />
<b><a href="http://golang.org/">Go</a></b>
<pre class="brush:cpp">
package main
import "fmt"
func main() {
sayHello := make(chan string)
sayWorld := make(chan string)
quitter := make(chan string)
go func() {
for i := 0; i < 1000; i++ {
fmt.Print("Hello ")
sayWorld <- "Do it"
<-sayHello
}
sayWorld <- "Quit"
}()
go func() {
for {
var reply string
reply = <- sayWorld
if (reply == "Quit") {
break
}
fmt.Print("World!\n")
sayHello <- "Do it"
}
quitter <- "Done"
}()
<-quitter
}
</pre>
<br />
<b><a href="http://www.erlang.org/">Erlang</a></b>
<pre class="brush:erl">
-module(hello_world).
-export([start/0, say_hello/2, say_world/0]).
say_hello(0, WorldPid) ->
WorldPid ! quit;
say_hello(N, WorldPid) ->
io:format("Hello ", []),
WorldPid ! {sayWorld, self()},
receive
sayHello ->
say_hello(N - 1, WorldPid)
end.
say_world() ->
receive
quit ->
quit;
{sayWorld, HelloPid} ->
io:format("World!~n", []),
HelloPid ! sayHello,
say_world()
end.
start() ->
WorldPid = spawn(hello_world, say_world, []),
spawn(hello_world, say_hello, [1000, WorldPid]).
</pre>
<br />
<b>C++ (<a href="https://github.com/Himmele/Mindroid">Mindroid</a>)</b>
<pre class="brush:cpp">
#include <stdio.h>
#include "mindroid/os/Message.h"
#include "mindroid/os/Handler.h"
#include "mindroid/os/LooperThread.h"
using namespace mindroid;
static const int SAY_HELLO = 0;
static const int SAY_WORLD = 1;
static const int QUIT = 2;
class HelloHandler : public Handler
{
public:
HelloHandler(const sp<Handler>& worldHandler) :
mWorldHandler(worldHandler), mCounter(0) {}
virtual void handleMessage(const sp<Message>& msg) {
switch (msg->what) {
case SAY_HELLO:
mCounter++;
if (mCounter <= 1000) {
printf("Hello ");
sp<Message> sayWorld =
mWorldHandler->obtainMessage(SAY_WORLD);
sayWorld->metaData()->putObject("SayHello",
obtainMessage(SAY_HELLO));
sayWorld->sendToTarget();
} else {
mWorldHandler->obtainMessage(QUIT)
->sendToTarget();
Looper::myLooper()->quit();
}
break;
}
}
private:
sp<Handler> mWorldHandler;
int mCounter;
};
class WorldHandler : public Handler
{
public:
virtual void handleMessage(const sp<Message>& msg) {
switch (msg->what) {
case SAY_WORLD:
printf("World!\n");
msg->metaData()
->getObject<Message>("SayHello")
->sendToTarget();
break;
case QUIT:
Looper::myLooper()->quit();
break;
}
}
};
int main() {
sp< LooperThread<WorldHandler> > wlt =
new LooperThread<WorldHandler>();
wlt->start();
Looper::prepare();
sp<Handler> hh =
new HelloHandler(wlt->getHandler());
hh->obtainMessage(SAY_HELLO)->sendToTarget();
Looper::loop();
return 0;
}
</pre>
<br />
I think I really like Go (although Erlang is a bit more crafty :-)).
Go eases developing scalable and reliable distributed systems while being a good to read language. Since you can also handle much more concurrent activities with one machine using Goroutines (compared to plain operating system threads) it also helps in saving energy.
<br />
<br />
<b>Links</b>
<ul>
<li><a href="http://golang.org/doc/go_faq.html#goroutines">Why goroutines instead of threads?</a>
<li><a href="https://groups.google.com/forum/?fromgroups=#!topic/golang-nuts/tGvuvc8Z2IQ">How does goroutine scheduling work?</a></li>
<li><a href="http://erlang.org/pipermail/erlang-questions/2001-April/003132.html">How does Erlang process scheduling work?</a>
<li><a href="https://github.com/Himmele/Mindroid">Mindroid @ GitHub</a></li>
<li><a href="http://himmele.blogspot.de/2010/11/alan-kay-on-object-oriented-programming.html">Alan Kay on Object-Oriented Programming</a></li>
<li><a href="http://news.ycombinator.com/item?id=4739600">Some more concurrent Hello World's at Hacker News (I like the implementation using Boost fibers)</a></li>
</ul>Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com5tag:blogger.com,1999:blog-8471450961411756399.post-74006683185805219892012-06-21T23:09:00.000+02:002012-09-29T09:20:27.642+02:00Android Transporter on the Raspberry PiThe Android Transporter which we have developed at <a href="http://esrlabs.com/">E.S.R.Labs</a> now also runs on the <a href="http://www.raspberrypi.org/">Raspberry Pi</a>. It allows you to easily share and display the contents of an Android gadget wirelessly with a television set or a beamer.<br />
<br />
<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="http://www.youtube.com/embed/lyoZoNA8U24?hd=1&wmode=transparent" width="420"></iframe></span>
The demo video shows how the Android Transporter turns your smartphone or tablet together with the Raspberry Pi into a powerful media hub to watch movies, play games, or do slideshows.<br />
This way, the Raspberry Pi becomes the cheapest gaming console or set-top box :-).<br />
<br />
The Android Transporter for the Raspberry Pi is based on my <a href="http://himmele.blogspot.de/2011/08/android-messaging-and-concurrency-for.html?">Android messaging and concurrency (a.k.a. Mindroid)</a> C++ library. The source code of this library is available on <a href="https://github.com/Himmele/Mindroid">GitHub</a>.<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-73297086172481978122012-05-08T21:21:00.000+02:002012-05-17T11:10:10.503+02:00Android Transporter WiFi Display<span style="display: block; text-align: center;">
<iframe allowfullscreen="" frameborder="0" height="346" src="http://www.youtube.com/embed/wLEeZ9zU7yI?hd=1&wmode=transparent" width="420"></iframe><br />
</span><br />
The video above shows the <a href="http://esrlabs.com/android-transporter/">Android Transporter</a>, a realtime <a href="http://www.androidauthority.com/wifi-display-to-make-your-life-easier-in-2012-47153/">WiFi Display</a> for Android which I and some other guys have implemented during the last few days. We have done this for our new software startup company called <a href="http://esrlabs.com/">E.S.R.Labs</a>, which is short for Embedded Software Research Labs.<br />
The WiFi Display mirror mode beams the display contents of your smartphone or tablet onto other gadgets, TVs, beamers, or other devices. Soon, there will also be a dual screen mode with an accompanying SDK.<br />
I think WiFi Displays will find their firm place for interconnecting devices to make the world around you a bit smarter :-).<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-58638176026613374572012-03-31T18:32:00.000+02:002015-09-29T22:48:57.183+02:00Android's C++ reference counting<pre class="brush:cpp">#include <stdio.h>
#include "android/os/Ref.h"
using namespace android::os;
class RefTest : public Ref {
public:
RefTest(int32_t id) : mID(id) {
printf("RefTest ctor: %d\n", mID);
}
virtual ~RefTest() {
printf("RefTest dtor: %d\n", mID);
}
int32_t id() const {
return mID;
}
private:
int32_t mID;
};
int main() {
sp<RefTest> ref1 = new RefTest(1);
{
sp<RefTest> ref2 = new RefTest(2);
}
wp<RefTest> ref3 = ref1;
sp<RefTest> ref4 = ref3.toStrongRef();
if (ref4 == NULL) {
printf("RefTest object is destroyed\n");
} else {
printf("RefTest object %d is still around\n",
ref4->id());
}
ref4 = NULL;
ref1 = NULL;
ref4 = ref3.toStrongRef();
if (ref4 == NULL) {
printf("RefTest object is destroyed\n");
} else {
printf("RefTest object %d is still around\n",
ref4->id());
}
return 0;
}
</pre>
<br />
To use the reference counting mechanism for (non Android) C++ projects check out the <span style="font-family: 'Courier New', Courier, monospace;"><b><a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Google%20Android/Android%20Messaging%20and%20Concurrency%20(with%20Automatic%20Reference%20Counting)/include/android/os/Ref.h">Ref</a></b></span> class of my <a href="http://himmele.blogspot.de/2011/08/android-messaging-and-concurrency-for.html">native Android messaging and concurrency framework</a>. It contains Google's C++ reference counting class from the Android project along with some fixes and refactorings for code readability.<br />
<br />
To get started you have to inherit (<span style="font-family: 'Courier New', Courier, monospace;"><b>virtual</b></span>) <span style="font-family: 'Courier New', Courier, monospace;"><b>public</b></span> from the <span style="font-family: 'Courier New', Courier, monospace;"><b><a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Google%20Android/Android%20Messaging%20and%20Concurrency%20(with%20Automatic%20Reference%20Counting)/include/android/os/Ref.h">Ref</a></b></span> base class so that each object of a particular class that derives from <span style="font-family: 'Courier New', Courier, monospace;"><b><a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Google%20Android/Android%20Messaging%20and%20Concurrency%20(with%20Automatic%20Reference%20Counting)/include/android/os/Ref.h">Ref</a></b></span> contains reference counters and the necessary management methods to increment and decrement them.<br />
Afterwards you are able to create instances of types like <span style="font-family: 'Courier New', Courier, monospace;"><b>RefTest</b></span> as in the example above and assign them to strong (smart) pointers of type <span style="font-family: 'Courier New', Courier, monospace;"><b>sp<RefTest></b></span>. There also is a <span style="font-family: 'Courier New', Courier, monospace;"><b>wp<></b></span> template class for weak pointers when you have to get around circles of strong references.<br />
<br />
Each <span style="font-family: 'Courier New', Courier, monospace;"><b><a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Google%20Android/Android%20Messaging%20and%20Concurrency%20(with%20Automatic%20Reference%20Counting)/include/android/os/Ref.h">Ref</a></b></span> object has a <span style="font-family: 'Courier New', Courier, monospace;"><b><a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Google%20Android/Android%20Messaging%20and%20Concurrency%20(with%20Automatic%20Reference%20Counting)/src/android/os/Ref.cpp">WeakRefImpl</a></b></span> object that keeps two reference counters, one for weak references and one for strong references. Whenever the strong reference counter is incremented or decremented then the weak reference counter also gets incremented or decremented. But when you create a <span style="font-family: 'Courier New', Courier, monospace;"><b>wp<></b></span> to some object only the object's weak reference counter is incremented. Therefore, managed objects live as long as there is some strong pointer referring to it. However, the managed object's <b style="font-family: 'Courier New', Courier, monospace;"><a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Google%20Android/Android%20Messaging%20and%20Concurrency%20(with%20Automatic%20Reference%20Counting)/src/android/os/Ref.cpp">WeakRefImpl</a></b> object may live longer than the object itself because it lives as long as there is some weak pointer referring to the object. If that is the case and the object itself is already destroyed the weak pointer's <span style="font-family: 'Courier New', Courier, monospace;"><b>toStrongRef</b></span> method returns <span style="font-family: 'Courier New', Courier, monospace;"><b>NULL</b></span> to indicate that the object is not available anymore.<br />
<br />
The <span style="font-family: 'Courier New', Courier, monospace;"><b><a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Google%20Android/Android%20Messaging%20and%20Concurrency%20(with%20Automatic%20Reference%20Counting)/include/android/os/Ref.h">Ref</a></b></span> base class is thread-safe without needing expensive locks. It completely synchronizes the access to the reference counters using atomic operations. The <span style="font-family: 'Courier New', Courier, monospace;"><b>sp<></b></span> and <span style="font-family: 'Courier New', Courier, monospace;"><b>wp<></b></span> template classes are not thread-safe. So always make sure you copy the strong and weak pointers when you share managed objects with different threads.<br />
<br />
The C++0x <span style="font-family: 'Courier New', Courier, monospace;"><b>shared_ptr</b></span> class is similar to Android's C++ reference counting class but there are also some differences. E.g. while C++0x keeps the reference counter outside of the managed object in the <span style="font-family: 'Courier New', Courier, monospace;"><b>shared_ptr</b></span> class Android's reference counting mechanism keeps the counter in the object itself.<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com9tag:blogger.com,1999:blog-8471450961411756399.post-53757618055506730722012-02-04T12:45:00.000+01:002015-09-29T22:43:56.967+02:00The Erlang Design PatternOver the last couple of weeks I did an OO programming experiment. I call it the Erlang design pattern. It is based on the <a href="http://en.wikipedia.org/wiki/Actor_model">Actor model</a> but goes some steps further. At its core just like the Actor model there are active entities (objects) that have a thread and a message queue with the thread waiting on the message queue to do some stuff.<br />
<br />
The Erlang design pattern extends the Actor model by first dividing the software program into active (actors, that have their own thread) and passive (objects, whose methods are called by other actors) objects.<br />
Second, I enforced that all methods of an active or passive object are always called by the same thread context (e.g. actor). So for each object there is no shared state between different thread contexts anymore. Two different objects of the same class could as a matter of course be used by two different actors.<br />
Third, if two or more actors want to share data they have to explicitly do this via message passing. To avoid a lot of copying I shared data using smart pointers in C++ and references in Java and C#. When one actor sends such a data structure to another actor it loses its reference to that data structure to make sure that it is only owned by one actor at a time (see also <a href="http://research.microsoft.com/en-us/um/people/larus/talks/upenn_singularity.pdf">Microsoft Singularity's exchange heap</a>).<br />
<br />
Building software systems using the Erlang design pattern was very interesting because it helped to write concurrent, modular, scalable and readable code :-). Maybe you will try it at your next <a href="http://coderetreat.com/">code retreat</a>.<br />
Of course there also were some quirks. E.g. I couldn't use my <a href="https://github.com/Himmele/Mindroid.cpp/blob/master/mindroid/os/Closure.h">C++ closures</a> (which I really like) anymore because they delegate methods of an object from one thread context to another.<br />
To sum this up, the Erlang design pattern was an interesting experiment which I will most probably not use every day in its pure form. But it helps to better understand how ideas of functional programming result in modular, scalable and readable (OO) software systems.<br />
<br />
For C++, I used my <a href="http://himmele.blogspot.com/2011/08/android-messaging-and-concurrency-for.html">Android messaging and concurrency (a.k.a. Mindroid) framework</a> to play around with the Erlang design pattern and for Java I just used the <a href="http://developer.android.com/index.html">Android SDK</a>.<br />
<br />
Of Joe Armstrong's Erlang design principles, the Actor model "solves" the first and third point. The Erlang Design pattern also "solves" the second point and goes a step further on the third one.<br />
<ul>
<li>The world is concurrent.</li>
<li>Things in the world don't share data.</li>
<li>Things communicate with messages.</li>
<li>Things fail.</li>
</ul>
To achieve to same degree of concurrency as Erlang does with its lightweight processes one definitely needs to build its own virtual machine, OS thread abstractions and libraries.<br />
But for smartphone and tablet software development one will most probably not need that degree of concurrency and is able to stick with OS threads :-).<br />
<br />
See also:<br />
<ul>
<li><a href="http://himmele.blogspot.com/2010/11/alan-kay-on-object-oriented-programming.html">Alan Kay on Object-Oriented Programming</a></li>
<li><a href="http://c2.com/cgi/wiki?AlanKaysDefinitionOfObjectOriented">Alan Kay's Definition of OOP</a></li>
<li><a href="http://c2.com/cgi/wiki?AlanKayOnMessaging">Alan Kay on Messaging</a></li>
<li><a href="http://himmele.blogspot.com/2011/01/why-are-we-building-so-much-software.html">Why are we building so much software technologies that will eventually fail?</a></li>
</ul>Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-19218847438335880952012-01-01T18:52:00.001+01:002012-05-30T10:00:37.761+02:00How do you read source code?If <a href="http://online.wsj.com/article/SB10001424053111903480904576512250915629460.html">software is eating the world</a> as Marc Andreessen and I think, how do you [r]ea(d|t) source code?<br />
Well, let's first answer why you should be good at reading source code at all.<br />
First it's always great fun to figure out how things work. By reading source code one is exactly doing that to learn about interesting software systems and projects.<br />
Another reason for reading source code may be to get better (and faster) at reading and writing software by learning from others and sometimes also from their mistakes.<br />
If you join a new software company or an open source project you are probably going to work on a huge existing codebase and therefore you should be able to get into it quickly, e.g. to implement tests and features or to fix bugs.<br />
The primary goal of reading source code always is to be able to think and reason about all aspects of a software system's codebase. In this article I put together some advise and patterns for reading source code which made my life as software engineer a lot easier :-).<br />
<br />
Now the big question is: <b>How do you read source code?</b><br />
Before you begin to dive deep into the source code of a software project you should make sure to have enough domain specific knowledge to understand the particular piece of software. Hence, you should start to get the big picture by reading documentation and computer science literature about the software platform/product or field of computer science (e.g. Windows apps, Mac OS X and iOS apps, Android apps, operating systems, computer networks, browsers, search engines, databases, etc.).<br />
You don't have to know everything about the topic, but you have to <b>understand the core abstractions and the basic building blocks</b> of the software platform/product. E.g. you should know what processes, threads, semaphores, etc. are before you write your own scheduling algorithm for Linux (see <a href="http://www.amazon.com/Modern-Operating-Systems-Andrew-Tanenbaum/dp/0136006639/ref=sr_1_1?ie=UTF8&qid=1323008055&sr=8-1">Modern Operating Systems</a> by Andrew S. Tanenbaum). You should also know about Linux specific process management before doing this (see <a href="http://www.amazon.com/Linux-Kernel-Development-Robert-Love/dp/0672329468/ref=sr_1_1?s=books&ie=UTF8&qid=1323008100&sr=1-1">Linux Kernel Development</a> by Robert Love and <a href="http://www.amazon.com/Professional-Linux-Kernel-Architecture-Programmer/dp/0470343435/ref=sr_1_1?s=books&ie=UTF8&qid=1323008158&sr=1-1">Linux Kernel Architecture</a> by Wolfgang Mauerer).<br />
But most probably you have already done this before investigating a particular piece of software. So let's get started...<br />
<br />
For starters, all software systems or at least all subsystems of huge software systems have some basic building blocks and core abstractions that you will notice all over the place. These components (e.g. classes, modules, actors, data structures, etc.) are also known as <b>hubs</b>. The hubs are simultaneously part of various aspects or subsystems of the whole codebase. <b>Therefore the hubs interlink the subsystems and yet make huge codebases look like small worlds</b>.<br />
<b>Hubs form the contexts around which software engineers build the software architecture</b>. They also implement quite a lot of the core features and functionality. As software systems grow, more and more other components will depend on the hubs. Therefore look for the hubs first and learn about their responsibilities. Usually even huge software systems only have a relatively small number of hubs. Hence, you don't have to fear millions of lines of source code because the hubs will guide you through the codebase. E.g. if we take a look at Google's Android OS, I would say that the following classes (active objects and processes) are the hubs: Zygote, ActivityManagerService, WindowManagerService, PackageManagerService, ConnectivityService and the SurfaceFlinger. You see, just 6 components :-).<br />
You can also repeat the game at a smaller scale, e.g. for Android's widget framework where the View, ViewGroup and ViewRoot classes are the hubs upon which a lot of other UI components build.<br />
This <a href="http://en.wikipedia.org/wiki/Reductionism">reductionist</a> approach also works for other software systems such as operating systems, filesystems, networking stacks, web backend platforms, etc.<br />
For more details on hubs and network theory I suggest Albert-Laszlo Barabasi's book <a href="http://www.amazon.com/Linked-Everything-Connected-Else-Means/dp/0452284392">Linked</a>.<br />
<br />
Next, after identifying the hubs you should try to <b>understand the interaction patterns between the hubs</b>. The interactions may rely on different mechanisms like pure API calls or <a href="http://en.wikipedia.org/wiki/Message_passing">message passing</a> (e.g. message queues or IPC calls). To get the idea of how hubs depend on each other I suggest to just <b>draw some pictures of the hubs, their dependencies and their interactions</b>.<br />
As an example just take a look at one of my previous blog posts about <a href="http://himmele.blogspot.com/2010/02/android-architecture-patterns.html">Andoid Architecture Patterns</a>.<br />
On the 7th slide there is a picture about how Android starts activities, services and content providers within their own Linux OS processes. It does so by several interactions between the ActivityManagerService, the Zygote process and the app's process.<br />
<br />
As you see, getting the big picture is done by identifying the hubs and understanding their interactions using a top-down approach. To dig deep into specific parts or aspects of software systems we have to change our source code reading patterns. Therefore we will switch to a bottom-up approach to inspect modules, classes, data structures, methods, functions, etc. Later we are able to combine both code reading approches. <b>This strategy of summarizing the findings of the top-down and the bottom-up approach is called <a href="http://pespmc1.vub.ac.be/DOWNCAUS.html">downward causation</a></b>.<br />
<div>
<br /></div>
I think the bottom-up approach works best by starting with the active entities (threads, actors, processes) that breathe life into the hubs. This is because to be able to think and reason about some piece of source code you really need to understand the environment in which the hubs run.<br />
So <b>always make sure which active entities run which parts of a system's source code</b> and try to understand how and when they interact with each other. This will help you to achieve the primary goal of reading source code, that is to be able to think and reason about all aspects of a software system's codebase (solely with your brain and without the help of external tools like a debugger :-)).<br />
Getting into the details of some piece of source code always starts with <b>trying things out</b>. I do that by adding some logging code or by making assumptions about the code's behavior which I verify with tests afterwards. Another method is to do modifications to the source code just to check how the code behaves under the new circumstances. Breaking or damaging the code may also help you to learn about it ;-).<br />
While reading source code always ask yourself: "How does it work?" and "Why have the developers done it that way?". This will most probably cause you some sleepless nights but it will also make you a better software engineer and software architect.<br />
Everything you do to get better at thinking and reasoning about the source code will help you to develop stronger debugging and analytical skills which in turn enable you to implement new features, fix bugs or do refactorings.<br />
<br />
By thinking and reflecting about the source code you are reading you will learn a lot about how to write software systems and platforms. Besides, from bad software you will also learn what to avoid when developing software systems.<br />
Furthermore, there are two great articles about <b>how to write great source code and software systems</b>. Rich Hickey's talk about <a href="http://www.infoq.com/presentations/Simple-Made-Easy">"Simple made easy"</a> at InfoQ and <a href="http://www.erlang.se/doc/programming_rules.shtml">Erlang's programming rules and conventions</a>. These two guides are outstanding no matter which programming language you use.<br />
So, reading code really is fun. Maybe next time instead of reading another software engineering book just read some source code. (GitHub is really great for that.)<br />
<br />
Since you need some staying power to get into a huge codebase I suggest to pick a software project that provides some fun and purpose along the way :-). Maybe the list below contains an interesting software project for you...<br />
<br />
<b>Software projects</b><br />
<ul>
<li><a href="http://source.android.com/source/downloading.html">Google Android</a></li>
<li><a href="http://git.minix3.org/?p=minix.git;a=tree">Minix</a> (Monolithic OSes are not here to stay forever :-))</li>
<li><a href="http://www.kernel.org/">Linux Kernel</a></li>
<li><a href="http://singularity.codeplex.com/releases/view/19428">Microsoft Singularity</a></li>
<li><a href="https://github.com/erlang/otp">Erlang</a></li>
<li><a href="https://github.com/apache/couchdb">CouchDB</a></li>
<li><a href="http://src.chromium.org/viewvc/chrome/">Google Chrome</a></li>
<li><a href="http://aspnet.codeplex.com/SourceControl/changeset/view/72551">Microsoft ASP.NET MVC</a></li>
<li><a href="https://github.com/GenTiradentes/tinyvm">TinyVM</a></li>
<li><a href="http://git.kernel.org/?p=linux/kernel/git/torvalds/linux.git;a=tree;f=fs/ext4;h=10fc5796018ce1f8611a94eb3801c33119b185f1;hb=HEAD">Ext4 FS</a></li>
<li>TCP/IP networking stacks: <a href="http://www.netbsd.org/">NetBSD</a>, <a href="http://git.savannah.gnu.org/cgit/lwip.git/tree/">lwIP</a></li>
<li><a href="http://lucene.apache.org/java/docs/developer-resources.html#source">Apache Lucene</a></li>
<li><a href="http://hadoop.apache.org/mapreduce/version_control.html#Anonymous+Access+%28read-only%29">Apache Hadoop</a></li>
<li><a href="http://bio.codeplex.com/documentation">Microsoft .NET Bio</a></li>
<li><a href="http://llvm.org/">LLVM</a></li>
<li><a href="http://www.qnx.com/developers/docs/6.4.1/neutrino/sys_arch/about.html">QNX Neutrino RTOS</a> (Sadly the QNX Neutrino RTOS is not shared source anymore, but hopefully a great software company will buy QNX Software Systems some day and make this great OS really huge :-))</li>
<li>...</li>
</ul>Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com4tag:blogger.com,1999:blog-8471450961411756399.post-48643191262259936562011-11-05T10:50:00.000+01:002015-09-29T22:40:29.047+02:00Apple's Siri and the Semantic Web<span style="display: block; text-align: center;"><br />
<iframe allowfullscreen="" frameborder="0" height="346" src="http://www.youtube.com/embed/OGg8A2zfWKg?wmode=transparent" width="420"></iframe><br />
</span><br />
Maybe not Google will start to build the semantic web as I thought in one of my previous blog posts about <a href="http://himmele.blogspot.com/2010/12/internet-of-things.html">"The Internet of Things"</a> but Apple will do so with <a href="http://www.apple.com/iphone/features/siri.html">Siri</a>.<br />
<br />
Some interesting links:<br />
<a href="http://semanticweb.com/tag/siri">Siri at semanticweb.com</a><br />
<a href="http://semanticweb.com/siri-is-live-and-points-the-way-to-next-level-of-semantic-web-apps_b526">Siri points the way to next level of semantic web apps</a><br />
<a href="http://semanticweb.com/new-research-helps-executives-get-engaged-with-the-semantic-web_b518">New research helps people to get engaged with the semantic web</a><br />
<a href="http://visionscapers.net/freddysnijder/posts/will-siri-and-her-offspring-bring-the-semantic-web-to-life/">Will Siri and her offspring bring the semantic web to life?</a><br />
<a href="http://vimeo.com/9216789">Siri - the do engine</a><br />
<a href="http://goo.gl/Bsbmr">Siri internals</a><br />
<br />
Siri was born out of SRI’s CALO Project, the largest AI project in U.S. history:<br />
<ul>
<li><a href="https://pal.sri.com/Plone/framework">DARPA PAL program</a> (Personal Assistant that Learns)</li>
<li><a href="http://www.ai.sri.com/project/CALO">Cognitive Assistant that Learns and Organizes</a></li>
</ul>
<br />
Siri is “Search” as it should be: Ask a question, receive an answer or get things done.<br />
...great, Siri is what I wanted <a href="https://github.com/Himmele/Quickdroid">Quickdroid</a> to be :-).<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com0tag:blogger.com,1999:blog-8471450961411756399.post-36093795324850893742011-11-02T23:10:00.000+01:002015-09-29T22:36:39.388+02:00Algorithms and Data Structures<b>Topics:</b>
<br />
<ul>
<li><a href="#Binary_search">Binary search</a></li>
<li><a href="#Quicksort">Quicksort</a>,
<a href="#Heapsort">Heapsort</a>,
<a href="#Introsort">Introsort</a>,
<a href="#Mergesort">Mergesort</a></li>
<li><a href="#Random_number_generators">Random number generators</a></li>
<li><a href="#Array">Array</a>,
<a href="#Linked_list">Linked List</a>,
<a href="#Stacks_and_queues">Stacks and queues</a>,
<a href="#Hashtable">Hashtable</a></li>
<li><a href="#Binary_search_tree">Binary search tree</a>,
<a href="#Red_black_tree">Red-black tree</a>,
<a href="#AVL_tree">AVL tree</a>,
<a href="#B_tree">B-tree</a>,
<a href="#B_plus_tree">B+ tree</a></li>
<li>See also <a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures-part-2.html">Algorithms and Data Structures - Part 2</a></li>
</ul>
<br />
<b>Approaches and strategies:</b><br />
The <a href="http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm" style="font-weight: bold;">divide-and-conquer</a> algorithm design paradigm divides the problem into a number of subproblems. Then it conquers the subproblems by solving them recursively. Finally, it combines the solutions to the subproblems into a solution for the original problem.<br />
This algorithm design method is e.g. used by <a href="#Quicksort">Quicksort</a> and <a href="#Mergesort">Mergesort</a>.<br />
<br />
<b><a href="http://en.wikipedia.org/wiki/Recursion">Recursion</a></b> in computer engineering is a method where the solution to a problem depends on solutions to smaller instances of the same (self-similar) problem.<br />
A classic example of recursion is the definition of the factorial function, given here in Java:<br />
<pre class="brush:java">public static int factorial(int n) {
if (n <= 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
</pre>
<br />
<b>Search algorithms:</b><br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Binary_search"></a>
<a href="http://en.wikipedia.org/wiki/Binary_search"><b>Binary search</b></a> finds the position of a specified value within a sorted array.<br />
Worst case performance: O(log n)<br />
<br />
<a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Algorithms%20and%20Data%20Structures/BinarySearch/src/BinarySearch.java">Java source code:</a><br />
<pre class="brush:java">public static int search(final char character,
final char[] alphabet) {
int leftIndex = 0;
int rightIndex = alphabet.length - 1;
while (leftIndex <= rightIndex) {
final int middleIndex = leftIndex +
((rightIndex - leftIndex) / 2);
if (alphabet[middleIndex] < character) {
leftIndex = middleIndex + 1;
} else if (alphabet[middleIndex] > character) {
rightIndex = middleIndex - 1;
} else {
return middleIndex;
}
}
return -1;
}
</pre>
<br />
<b>Sorting algorithms:</b><br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Quicksort"></a>
<a href="http://en.wikipedia.org/wiki/Quicksort"><b>Quicksort</b></a> is a divide-and-conquer sorting algorithm developed by Tony Hoare that, <u>on average, makes O(n log n) comparisons</u> to sort n items. In the worst case, it makes O(n^2) comparisons, though this behavior is rare. Quicksort is often faster in practice than other O(n log n) algorithms. Quicksort can be implemented as an <u>in-place sort</u>, requiring only O(log n) additional space. The recursion call stack has height <i>n</i> in the worst case and height <i>log n</i> in the best case.<br />
<br />
Quicksort selects a random pivot element from the n items to sort. (Here the pivot element is always the rightmost element of the pile.) Then Quicksort separates the n - 1 other elements into two piles: a low pile containing all elements that appear before the pivot element and a high pile that contains all elements that appear after the pivot element. By doing that recursively for smaller and smaller piles the whole pile is being sorted.<br />
<br />
<a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Algorithms%20and%20Data%20Structures/Quicksort/src/Quicksort.java">Java source code:</a><br />
<pre class="brush:java">public static void quicksort(char[] string,
int leftIndex, int rightIndex) {
if (leftIndex < rightIndex) {
int pivotIndex = partition(string,
leftIndex, rightIndex);
quicksort(string, leftIndex, pivotIndex-1);
quicksort(string, pivotIndex+1, rightIndex);
}
}
static int partition(char[] string, int leftIndex,
int rightIndex) {
int pivotIndex = rightIndex;
// divider index for the pivot element
int storageIndex = leftIndex;
for (int i = leftIndex; i < rightIndex; i++) {
if (string[i] < string[pivotIndex]) {
swap(string, i, storageIndex);
storageIndex++;
}
}
swap(string, pivotIndex, storageIndex);
return storageIndex;
}</pre>
<br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Heapsort"></a>
<a href="http://en.wikipedia.org/wiki/Heapsort"><b>Heapsort</b></a> is a comparison-based sorting algorithm. Although somewhat slower in practice on most machines than a well implemented <a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort</a>, it has the advantage of a more favorable <u>worst-case O(n log n) runtime</u>. Heapsort is an <u>in-place algorithm</u>, but is <u>not a stable sort</u>. The Java source code for Heapsort is available <a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Algorithms%20and%20Data%20Structures/Heapsort/src/BinaryHeap.java">here</a>.<br />
<br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Introsort"></a>
<a href="http://en.wikipedia.org/wiki/Introsort"><b>Introsort</b></a> or introspective sort is a sorting algorithm designed by David Musser in 1997. It begins with <a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort</a> and switches to <a href="http://en.wikipedia.org/wiki/Heapsort">Heapsort</a> when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. It is the best of both worlds, with a worst-case O(n log n) runtime and a practical performance comparable to Quicksort on typical data sets. Introsort is used by the GCC C++ STL and the SGI C++ STL.<br />
<br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Mergesort"></a>
<a href="http://en.wikipedia.org/wiki/Mergesort"><b>Mergesort</b></a> is an <u>O(n log n) divide-and-conquer sorting algorithm</u>. Most implementations produce a <u>stable sort</u>, meaning that the implementation preserves the input order of equal elements in the sorted output. Mergesort was invented by John von Neumann in 1945.<br />
<u>Mergesort does not sort in place</u> but it has the advantage that it may be distributed across multiple machines to sort parts of really huge data set. <a href="http://himmele.blogspot.com/2011/05/build-your-own-internet-search-engine.html">Therefore mergesort is used a lot by web search engines</a>. Mergesort is a typical recursive algorithms that reduces large problems into smaller ones. The recursion call stack always has height <i>log n</i>.<br />
<br />
<a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Algorithms%20and%20Data%20Structures/Mergesort/src/Mergesort.java">Java source code:</a><br />
<pre class="brush:java">public static void mergesort(char[] string,
int leftIndex, int rightIndex) {
if (leftIndex < rightIndex) {
int middleIndex = (leftIndex + rightIndex) / 2;
mergesort(string, leftIndex, middleIndex);
mergesort(string, middleIndex + 1, rightIndex);
merge(string, leftIndex, middleIndex,
rightIndex);
}
}
static void merge(char[] string, int leftIndex,
int middleIndex, int rightIndex) {
Queue<Character> string1 =
new LinkedList<Character>();
Queue<Character> string2 =
new LinkedList<Character>();
for (int i=leftIndex; i<=middleIndex; i++) {
string1.add(string[i]);
}
for (int i=middleIndex+1; i<=rightIndex; i++) {
string2.add(string[i]);
}
int i = leftIndex;
while (!string1.isEmpty() && !string2.isEmpty()) {
if (string1.peek() <= string2.peek()) {
string[i++] = string1.poll();
} else {
string[i++] = string2.poll();
}
}
while (!string1.isEmpty()) {
string[i++] = string1.poll();
}
while (!string2.isEmpty()) {
string[i++] = string2.poll();
}
}
</pre>
<br />
<b>Random numbers</b><br />
<b><a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Random_number_generators"></a>
<a href="http://en.wikipedia.org/wiki/Random_number_generation">Random number generators</a></b><br />
x(t+1) = R * x(t) * (1 - x(t))<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgg1f4K_XlSgeCiq9YHVA0l_mCkVL0VsfkRwk8mh-Ru5l32PCNv4LnGbN4-OSzTxz46s2KAZaZYi88l5IomdpGhCg4t3Mo_8zVvCan3Gv_TyMWJ3aRvK1fTJeYKKw8IpX4bc_dTu-793_0/s1600/Chaos+Attractor.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="203" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgg1f4K_XlSgeCiq9YHVA0l_mCkVL0VsfkRwk8mh-Ru5l32PCNv4LnGbN4-OSzTxz46s2KAZaZYi88l5IomdpGhCg4t3Mo_8zVvCan3Gv_TyMWJ3aRvK1fTJeYKKw8IpX4bc_dTu-793_0/s320/Chaos+Attractor.png" width="320" /></a></div>
With the initial values of R = 4.0 and x(0) = 0.2 you will get the chaotic trajectory as shown in the map above. The values for x(t+1) are chaotic and therefore like random numbers.<br />
Dynamical systems theory characterizes the behavior of the above equation as chaotic <a href="http://en.wikipedia.org/wiki/Attractor">attractor</a>.<br />
For more details see chapter 2 of <a href="http://www.amazon.com/Complexity-Guided-Tour-Melanie-Mitchell/dp/0199798109/ref=sr_1_2?ie=UTF8&qid=1320173815&sr=8-2">"Complexity: A Guided Tour"</a> by Melanie Mitchell.<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<b>Data Structures</b><br />
<b><a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Array"></a>
<a href="http://en.wikipedia.org/wiki/Array_data_structure">Array</a></b><br />
Indexing performance: O(1)<br />
Adding or deleting values: O(1)<br />
Search performance (unsorted array): O(n)<br />
<br />
<b><a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Linked_list"></a>
<a href="http://en.wikipedia.org/wiki/Linked_list">Linked list</a></b><br />
Indexing performance: O(n)<br />
Adding or deleting items: O(1)<br />
Search performance: O(n)<br />
<br />
<a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Algorithms%20and%20Data%20Structures/LinkedList/src/LinkedList.java">Java source code (singly-linked list):</a><br />
<pre class="brush:java">public class LinkedList<T> {
public void put(T item) {
Node node = new Node(item);
Node curNode = mHeadNode;
if (curNode == null) {
node.nextNode = curNode;
mHeadNode = node;
} else {
Node prevNode = null;
while (curNode != null) {
prevNode = curNode;
curNode = curNode.nextNode;
}
node.nextNode = prevNode.nextNode;
prevNode.nextNode = node;
}
}
public T take() {
Node node = getHeadNode();
if (node != null) {
T item = node.item;
return item;
} else {
return null;
}
}
class Node
{
public T item;
public Node nextNode;
public Node(T t) { item = t; }
};
Node getHeadNode() {
Node node = mHeadNode;
if (node != null) {
mHeadNode = node.nextNode;
return node;
}
return null;
}
private Node mHeadNode;
}
</pre>
<br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Stacks_and_queues"></a>
<b><a href="http://en.wikipedia.org/wiki/Stack_(data_structure)">Stacks</a> (LIFO) and <a href="http://en.wikipedia.org/wiki/Queue_(data_structure)">queues</a> (FIFO)</b><br />
Stacks support retrieval of data items by last-in, first-out (LIFO) order.<br />
Queues support retrieval of data items in first-in, first out (FIFO) order.<br />
Both stack and queue implementations are normally based on arrays or linked lists.<br />
<br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Hashtable"></a>
<a href="http://en.wikipedia.org/wiki/Hashtable"><b>Hashtable / Dictionary</b></a><br />
In computer science, a hash table or dictionary is a data structure that uses a hash function to map identifying values, known as keys (e.g., a person's name), to their associated values (e.g., their telephone number). Thus, a hash table implements an associative array. The <a href="http://en.wikipedia.org/wiki/Hash_function">hash function</a> is used to transform the key into the index (the hash) of an array element (the slot or bucket) where the corresponding value is to be sought. For further details also see <a href="http://en.wikipedia.org/wiki/Hashtable#Separate_chaining">hashing with chaining</a>, <a href="http://en.wikipedia.org/wiki/Hashtable#Open_addressing">hashing with open addressing</a> and <a href="http://en.wikipedia.org/wiki/Hash_function">hash functions</a>.<br />
The <u>best case performance for adding or deleting items into or from hash tables is O(1)</u>. <u>The search (indexing) performance is also O(1)</u>. You get the best case performance e.g. if the hash table is implemented using an array and if there are no collisions when inserting items.<br />
If there are collisions the performance depends on the data structure that is used for managing the data items of a hash table. E.g. if a self-balancing tree is used to manage them you will get a <u>worst-case performance of O(log n) for adding, deleting and searching items</u>.<br />
For more details about which underlying data structure should be used to implement hash tables see Skiena's <a href="http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693/ref=sr_1_1?ie=UTF8&qid=1320265682&sr=8-1">"The Algorithm Design Manual"</a> page 368.<br />
<br />
<a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Algorithms%20and%20Data%20Structures/Hashtable/src/Hashtable.java">Java source code (simple Hashtable with open addressing):</a><br />
<pre class="brush:java">public class Hashtable {
private static final int SIZE = 16;
private Object mKeys[] = new Object[SIZE];
private Object mObjects[] = new Object[SIZE];
public void add(Object key, Object object)
throws Exception {
int i = 0;
int index;
do {
index = hashCode(key, i);
if (mKeys[index] == null) {
mKeys[index] = key;
mObjects[index] = object;
return;
} else {
i++;
}
} while (i < SIZE);
throw new Exception("hash table overflow");
}
public Object get(Object key) {
int i = 0;
int index;
do {
index = hashCode(key, i);
if (mKeys[index].equals(key)) {
return mObjects[index];
}
i++;
} while (i < SIZE);
return null;
}
int hashCode(Object key, int i) {
int k = Math.abs(key.hashCode());
int hashCode1 = k % 701;
int hashCode2 = 1 + (k % 700);
int hastCode =
(hashCode1 + i * hashCode2) % 701;
return hastCode % SIZE;
}
}
</pre>
<br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Binary_search_tree"></a>
<b><a href="http://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree</a></b><br />
A <a href="http://en.wikipedia.org/wiki/Binary_search_tree">binary search tree</a> is a node-based binary tree data structure which has the following properties:<br />
<ul>
<li>The left subtree of a node contains only nodes with keys less than the node's key.</li>
<li>The right subtree of a node contains only nodes with keys greater than the node's key.</li>
<li>Both the left and right subtrees must also be binary search trees.</li>
</ul>
Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.<br />
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.<br />
Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays.<br />
<br />
<u>Adding or deleting items: O(h)</u>, where h is the height of the tree.<br />
<u>Search performance: O(h)</u>, where h is the height of the tree.<br />
<br />
<a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Algorithms%20and%20Data%20Structures/BinarySearchTree/src/BinarySearchTree.java">Java source code</a> (see also <a href="http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1319920104&sr=8-1">"Introduction to Algorithms"</a>, chapter 12):<br />
<pre class="brush:java">public class BinarySearchTree {
class Node {
public int mKey;
public Object mObject;
public Node mParentNode;
public Node mLeftNode;
public Node mRightNode;
}
private Node mRootNode;
// Recursive add method.
public void add(Node node, Node parentNode,
int key, Object object) {
if (node == null) {
Node newNode = new Node();
newNode.mKey = key;
newNode.mObject = object;
newNode.mParentNode = parentNode;
if (parentNode != null) {
if (key < parentNode.mKey) {
parentNode.mLeftNode = newNode;
} else {
parentNode.mRightNode = newNode;
}
} else {
mRootNode = newNode;
}
return;
}
if (key < node.mKey) {
add(node.mLeftNode, node, key, object);
} else {
add(node.mRightNode, node, key, object);
}
}
public void add(int key, Object object) {
add(mRootNode, null, key, object);
}
// Iterative add method.
public void add2(Node node, int key,
Object object) {
Node prevNode = null;
while (node != null) {
prevNode = node;
if (key < node.mKey) {
node = node.mLeftNode;
} else {
node = node.mRightNode;
}
}
Node newNode = new Node();
newNode.mKey = key;
newNode.mObject = object;
newNode.mParentNode = prevNode;
if (prevNode == null) {
mRootNode = newNode;
} else {
if (key < prevNode.mKey) {
prevNode.mLeftNode = newNode;
} else {
prevNode.mRightNode = newNode;
}
}
}
public void add2(int key, Object object) {
add2(mRootNode, key, object);
}
// Recursive search method.
public Object search(Node node, int key) {
if(node == null) {
return null;
}
if (node.mKey == key) {
return node.mObject;
}
if (key < node.mKey) {
return search(node.mLeftNode, key);
} else {
return search(node.mRightNode, key);
}
}
public Object search(int key) {
return search(mRootNode, key);
}
// Iterative search method.
public Object search2(Node node, int key) {
if(node == null) {
return null;
}
while (node != null && node.mKey != key) {
if (key < node.mKey) {
node = node.mLeftNode;
} else {
node = node.mRightNode;
}
}
if (node != null) {
return node.mObject;
} else {
return null;
}
}
public Object search2(int key) {
return search2(mRootNode, key);
}
// Inorder walk over the tree.
String printBST(Node node) {
String string = "";
if (node != null) {
string += printBST(node.mLeftNode);
string += node.mObject + ", ";
string += printBST(node.mRightNode);
}
return string;
}
public String toString() {
return printBST(mRootNode);
}
}
</pre>
<br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="Red_black_tree"></a>
<a href="http://en.wikipedia.org/wiki/Red%E2%80%93black_tree"><b>Red-black tree</b></a> is a type of self-balancing binary search tree, a data structure that is typically used to implement associative arrays. The original structure was invented in 1972 by Rudolf Bayer and named "symmetric binary B-tree," but acquired its modern name in a paper in 1978 by Leonidas J. Guibas and Robert Sedgewick. It is complex, but has good worst-case running time for its operations and is efficient in practice: <u>it can search, insert, and delete in O(log n) time</u>, where n is the total number of elements in the tree. Put very simply, a red–black tree is a binary search tree that inserts and deletes in such a way that the tree is always reasonably balanced. For further details on red-black trees I suggest chapter 13 of the <a href="http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1319920104&sr=8-1">"Introduction to Algorithms"</a> book.<br />
<br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="AVL_tree"></a>
<a href="http://en.wikipedia.org/wiki/AVL_tree"><b>AVL tree</b></a> is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. <u>Lookup, insertion, and deletion all take O(log n) time</u> in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.<br />
The AVL tree is named after its two Soviet inventors, G.M. Adelson-Velskii and E.M. Landis, who published it in their 1962 paper "An algorithm for the organization of information."<br />
AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, <a href="http://www.stanford.edu/~blp/papers/libavl.pdf">they are faster than red-black trees for lookup intensive applications</a>. However, red-black trees are faster for insertion and removal.<br />
<br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="B_tree"></a>
<b><a href="http://en.wikipedia.org/wiki/B-tree">B-tree</a></b><br />
A <a href="http://en.wikipedia.org/wiki/B-tree">B-tree</a> is a tree data structure that <u>keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time [O(log n)]</u>. <u>The B-tree is a generalization of a binary search tree in that a node can have more than two children</u>. <u>Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data</u>. <u>It is commonly used in databases and filesystems</u>.<br />
In B-trees, nodes can have a variable number of keys (elements) and children. The keys of a node are stored in non-decreasing order. Each node either is a leaf node or it has some associated children that are the root nodes of subtrees. The left child node of a node's element contains all nodes (elements) with keys less than or equal to the node element's key but greater than the preceding node element's key. When data is inserted to or removed from a node, its number of keys (elements) or child nodes changes. In order to maintain the pre-defined range, nodes may be joined or split. Because a range of child nodes is permitted, B-trees do not need re-balancing as frequently as other self-balancing search trees, but may waste some space, since nodes are not entirely full. The lower and upper bounds on the number of child nodes are typically fixed for a particular implementation.<br />
Each node of a B-tree will contain a number of keys. Usually, the number of keys is chosen to vary between t-1 and 2t-1. In practice, the keys (elements) take up the most space in a node. The factor of 2 will guarantee that nodes can be split or combined. If a node has 2t-1 keys, then adding a key to that node can be accomplished by splitting the 2t-1 key node into two t-1 key nodes and adding the median (middle) key of the original node to the parent node. Each splitted node has the required minimum number of keys.<br />
<u>If a new element is added into a B-tree it will always be inserted into a leaf node while the median key of the original node is shifted up into the parent node when the original node is already full</u>.<br />
A B-tree is kept balanced by requiring that all leaf nodes are at the same depth. This depth will increase slowly as elements are added to the tree, but an increase in the overall depth is infrequent, and results in all leaf nodes being one more node further away from the root.<br />
B-trees have substantial advantages over alternative implementations when node access times far exceed access times within nodes, because then the cost of accessing the node may be amortized over multiple operations within the node. This usually occurs when the nodes are in secondary storage such as disk drives. By maximizing the number of child nodes within each internal node, the height of the tree decreases and the number of expensive node accesses is reduced. In addition, rebalancing the tree occurs less often. The maximum number of child nodes depends on the information that must be stored for each child node and the size of a full disk block or an analogous size in secondary storage. Practical B-trees using secondary storage want a large number of child nodes to improve performance.<br />
<br />
<a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Algorithms%20and%20Data%20Structures/BTree/src/BTree.java">Java source code (including delete)</a> (see also <a href="http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1319920104&sr=8-1">"Introduction to Algorithms"</a>, chapter 18):<br />
<pre class="brush:java">public class BTree {
class Node {
public int mNumKeys = 0;
public int[] mKeys = new int[2*T-1];
public Object[] mObjects = new Object[2*T-1];
public Node[] mChildNodes = new Node[2*T];
public boolean mIsLeafNode;
}
private Node mRootNode;
private static final int T = 4;
public BTree() {
mRootNode = new Node();
mRootNode.mIsLeafNode = true;
}
public void add(int key, Object object) {
Node rootNode = mRootNode;
if (rootNode.mNumKeys == (2 * T - 1)) {
Node newRootNode = new Node();
mRootNode = newRootNode;
newRootNode.mIsLeafNode = false;
mRootNode.mChildNodes[0] = rootNode;
// Split rootNode and move its median
// key up into newRootNode.
splitChildNode(newRootNode, 0, rootNode);
// Insert the key into the B-Tree
// with root newRootNode.
insertIntoNonFullNode(newRootNode, key,
object);
} else {
// Insert the key into the B-Tree
// with root rootNode.
insertIntoNonFullNode(rootNode, key, object);
}
}
// Split the node, node, of a B-Tree into
// two nodes that both contain T-1 elements
// and move node's median key up
// to the parentNode. This method will
// only be called if node is full; node is the
// i-th child of parentNode.
void splitChildNode(Node parentNode, int i,
Node node) {
Node newNode = new Node();
newNode.mIsLeafNode = node.mIsLeafNode;
newNode.mNumKeys = T - 1;
// Copy the last T-1 elements of node
// into newNode.
for (int j = 0; j < T - 1; j++) {
newNode.mKeys[j] = node.mKeys[j + T];
newNode.mObjects[j] = node.mObjects[j + T];
}
if (!newNode.mIsLeafNode) {
// Copy the last T pointers of node
// into newNode.
for (int j = 0; j < T; j++) {
newNode.mChildNodes[j] =
node.mChildNodes[j + T];
}
for (int j = T; j <= node.mNumKeys; j++) {
node.mChildNodes[j] = null;
}
}
for (int j = T; j < node.mNumKeys; j++) {
node.mKeys[j] = 0;
node.mObjects[j] = null;
}
node.mNumKeys = T - 1;
// Insert a (child) pointer to node newNode
// into the parentNode, moving other keys
// and pointers as necessary.
for (int j = parentNode.mNumKeys; j >= i + 1;
j--) {
parentNode.mChildNodes[j + 1] =
parentNode.mChildNodes[j];
}
parentNode.mChildNodes[i + 1] = newNode;
for (int j = parentNode.mNumKeys - 1; j >= i;
j--) {
parentNode.mKeys[j + 1] =
parentNode.mKeys[j];
parentNode.mObjects[j + 1] =
parentNode.mObjects[j];
}
parentNode.mKeys[i] = node.mKeys[T - 1];
parentNode.mObjects[i] = node.mObjects[T - 1];
node.mKeys[T - 1] = 0;
node.mObjects[T - 1] = null;
parentNode.mNumKeys++;
}
// Insert an element into a B-Tree. (The element
// will ultimately be inserted into a leaf node).
void insertIntoNonFullNode(Node node, int key,
Object object) {
int i = node.mNumKeys - 1;
if (node.mIsLeafNode) {
// Since node is not a full node insert the
// new element into its proper place
// within node.
while (i >= 0 && key < node.mKeys[i]) {
node.mKeys[i + 1] = node.mKeys[i];
node.mObjects[i + 1] = node.mObjects[i];
i--;
}
i++;
node.mKeys[i] = key;
node.mObjects[i] = object;
node.mNumKeys++;
} else {
// Move back from the last key of node until
// we find the child pointer to the node
// that is the root node of the subtree
// where the new element should be placed.
while (i >= 0 && key < node.mKeys[i]) {
i--;
}
i++;
if (node.mChildNodes[i].mNumKeys ==
(2 * T - 1)) {
splitChildNode(node, i,
node.mChildNodes[i]);
if (key > node.mKeys[i]) {
i++;
}
}
insertIntoNonFullNode(node.mChildNodes[i],
key, object);
}
}
// Recursive search method.
public Object search(Node node, int key) {
int i = 0;
while (i < node.mNumKeys && key >
node.mKeys[i]) {
i++;
}
if (i < node.mNumKeys && key ==
node.mKeys[i]) {
return node.mObjects[i];
}
if (node.mIsLeafNode) {
return null;
} else {
return search(node.mChildNodes[i], key);
}
}
public Object search(int key) {
return search(mRootNode, key);
}
// Iterative search method.
public Object search2(Node node, int key) {
while (node != null) {
int i = 0;
while (i < node.mNumKeys && key >
node.mKeys[i]) {
i++;
}
if (i < node.mNumKeys && key ==
node.mKeys[i]) {
return node.mObjects[i];
}
if (node.mIsLeafNode) {
return null;
} else {
node = node.mChildNodes[i];
}
}
return null;
}
public Object search2(int key) {
return search2(mRootNode, key);
}
}
</pre>
<br />
<a href="http://himmele.blogspot.com/2011/11/algorithms-and-data-structures.html" name="B_plus_tree"></a>
<a href="http://en.wikipedia.org/wiki/B%2B_tree"><b>B+ tree</b></a> or B plus tree is a type of <u>balanced tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key</u>. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment (usually called a "block" or "node"). <u>In a B+ tree, in contrast to a B-tree, all records are stored at the leaf level of the tree; only keys are stored in interior nodes</u>.<br />
<u>The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context—in particular, filesystems</u>. This is primarily because unlike binary search trees, <u>B+ trees have a very high fanout (typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree</u>.<br />
The NTFS, XFS, and JFS filesystems all use this type of tree for metadata indexing. Relational database management systems such as IBM DB2, Microsoft SQL Server, MySQL and SQLite support this type of tree for table indices. Key-value database management systems such as <a href="http://guide.couchdb.org/draft/btree.html">CouchDB</a> support this type of tree for data access.<br />
The leaves of the B+ tree are often linked to one another in a linked list; this makes range queries or an (ordered) iteration through the blocks simpler and more efficient.<br />
<br />
<a href="https://github.com/Himmele/My-Blog-Repository/blob/master/Algorithms%20and%20Data%20Structures/BPlusTree/src/BPlusTree.java">Java source code</a> (for differences to the B-tree data structure take a look at the <span class="Apple-style-span" style="font-family: monospace; white-space: pre;">splitChildNode</span> method):<br />
<pre class="brush:java">public class BPlusTree {
class Node {
public int mNumKeys = 0;
public int[] mKeys = new int[2*T-1];
public Object[] mObjects = new Object[2*T-1];
public Node[] mChildNodes = new Node[2*T];
public boolean mIsLeafNode;
public Node mNextNode;
}
private Node mRootNode;
private static final int T = 4;
public BPlusTree() {
mRootNode = new Node();
mRootNode.mIsLeafNode = true;
}
public void add(int key, Object object) {
Node rootNode = mRootNode;
if (rootNode.mNumKeys == (2 * T - 1)) {
Node newRootNode = new Node();
mRootNode = newRootNode;
newRootNode.mIsLeafNode = false;
mRootNode.mChildNodes[0] = rootNode;
// Split rootNode and move its median
// key up into newRootNode.
splitChildNode(newRootNode, 0, rootNode);
// Insert the key into the B+-Tree
// with root newRootNode.
insertIntoNonFullNode(newRootNode, key,
object);
} else {
// Insert the key into the B+-Tree
// with root rootNode.
insertIntoNonFullNode(rootNode, key, object);
}
}
// Split the node, node, of a B+-Tree into two
// nodes that contain T-1 (and T) elements
// and move node's median key up to the
// parentNode.
// This method will only be called if node is full;
// node is the i-th child of parentNode.
// All internal keys (elements) will have
// duplicates within the leaf nodes.
void splitChildNode(Node parentNode, int i,
Node node) {
Node newNode = new Node();
newNode.mIsLeafNode = node.mIsLeafNode;
newNode.mNumKeys = T;
// Copy the last T elements of node
// into newNode. Keep the median key
// as duplicate in the first key of newNode.
for (int j = 0; j < T; j++) {
newNode.mKeys[j] = node.mKeys[j + T - 1];
newNode.mObjects[j] = node.mObjects[j + T - 1];
}
if (!newNode.mIsLeafNode) {
// Copy the last T + 1 pointers of node
// into newNode.
for (int j = 0; j < T + 1; j++) {
newNode.mChildNodes[j] =
node.mChildNodes[j + T - 1];
}
for (int j = T; j <= node.mNumKeys; j++) {
node.mChildNodes[j] = null;
}
} else {
// Manage the linked list that is used e.g.
// for doing fast range queries.
newNode.mNextNode = node.mNextNode;
node.mNextNode = newNode;
}
for (int j = T - 1; j < node.mNumKeys; j++) {
node.mKeys[j] = 0;
node.mObjects[j] = null;
}
node.mNumKeys = T - 1;
// Insert a (child) pointer to node newNode
// into the parentNode, moving other keys
// and pointers as necessary.
for (int j = parentNode.mNumKeys; j >= i + 1;
j--) {
parentNode.mChildNodes[j + 1] =
parentNode.mChildNodes[j];
}
parentNode.mChildNodes[i + 1] = newNode;
for (int j = parentNode.mNumKeys - 1; j >= i;
j--) {
parentNode.mKeys[j + 1] =
parentNode.mKeys[j];
parentNode.mObjects[j + 1] =
parentNode.mObjects[j];
}
parentNode.mKeys[i] = newNode.mKeys[0];
parentNode.mObjects[i] = newNode.mObjects[0];
parentNode.mNumKeys++;
}
// Insert an element into a B-Tree. (The element
// will ultimately be inserted into a leaf node).
void insertIntoNonFullNode(Node node, int key,
Object object) {
int i = node.mNumKeys - 1;
if (node.mIsLeafNode) {
// Since node is not a full node insert the
// new element into its proper place
// within node.
while (i >= 0 && key < node.mKeys[i]) {
node.mKeys[i + 1] = node.mKeys[i];
node.mObjects[i + 1] = node.mObjects[i];
i--;
}
i++;
node.mKeys[i] = key;
node.mObjects[i] = object;
node.mNumKeys++;
} else {
// Move back from the last key of node until
// we find the child pointer to the node
// that is the root node of the subtree
// where the new element should be placed.
while (i >= 0 && key < node.mKeys[i]) {
i--;
}
i++;
if (node.mChildNodes[i].mNumKeys ==
(2 * T - 1)) {
splitChildNode(node, i,
node.mChildNodes[i]);
if (key > node.mKeys[i]) {
i++;
}
}
insertIntoNonFullNode(node.mChildNodes[i],
key, object);
}
}
// Recursive search method.
public Object search(Node node, int key) {
int i = 0;
while (i < node.mNumKeys && key >
node.mKeys[i]) {
i++;
}
if (i < node.mNumKeys && key ==
node.mKeys[i]) {
return node.mObjects[i];
}
if (node.mIsLeafNode) {
return null;
} else {
return search(node.mChildNodes[i], key);
}
}
public Object search(int key) {
return search(mRootNode, key);
}
// Iterative search method.
public Object search2(Node node, int key) {
while (node != null) {
int i = 0;
while (i < node.mNumKeys && key >
node.mKeys[i]) {
i++;
}
if (i < node.mNumKeys && key ==
node.mKeys[i]) {
return node.mObjects[i];
}
if (node.mIsLeafNode) {
return null;
} else {
node = node.mChildNodes[i];
}
}
return null;
}
public Object search2(int key) {
return search2(mRootNode, key);
}
// Inorder walk over the tree.
public String toString() {
String string = "";
Node node = mRootNode;
while (!node.mIsLeafNode) {
node = node.mChildNodes[0];
}
while (node != null) {
for (int i = 0; i < node.mNumKeys; i++) {
string += node.mObjects[i] + ", ";
}
node = node.mNextNode;
}
return string;
}
// Inorder walk over parts of the tree.
public String toString(int fromKey, int toKey) {
String string = "";
Node node = getLeafNodeForKey(fromKey);
while (node != null) {
for (int j = 0; j < node.mNumKeys; j++) {
string += node.mObjects[j] + ", ";
if (node.mKeys[j] == toKey) {
return string;
}
}
node = node.mNextNode;
}
return string;
}
Node getLeafNodeForKey(int key) {
Node node = mRootNode;
while (node != null) {
int i = 0;
while (i < node.mNumKeys &&
key > node.mKeys[i]) {
i++;
}
if (i < node.mNumKeys &&
key == node.mKeys[i]) {
node = node.mChildNodes[i + 1];
while (!node.mIsLeafNode) {
node = node.mChildNodes[0];
}
return node;
}
if (node.mIsLeafNode) {
return null;
} else {
node = node.mChildNodes[i];
}
}
return null;
}
}
</pre>
<br />
<b>Books about algorithms and data structures:</b><br />
<ul>
<li><a href="http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693/ref=sr_1_1?ie=UTF8&qid=1320265682&sr=8-1">The Algorithm Design Manual</a> by Steven S. Skiena.</li>
<li><a href="http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844/ref=sr_1_1?s=books&ie=UTF8&qid=1320267208&sr=1-1">Introduction to Algorithms</a> by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.</li>
</ul>
<br />
The source code of the examples above can be found <a href="https://github.com/Himmele/My-Blog-Repository/tree/master/Algorithms%20and%20Data%20Structures">here</a> in the blog repository.<br />
<br />
A lot of texts have been taken from <a href="http://en.wikipedia.org/wiki/Main_Page">Wikipedia</a>, the free encyclopedia.<br />
<br />Daniel Himmeleinhttp://www.blogger.com/profile/13947784031669126669noreply@blogger.com3