About Frogs, tales and poems
Designing an efficient algorithm is certainly a scientific endeavor to maximize utility (and minimize cost). However, greeNsort® believes that algorithms also have an aesthetic dimension that should be considered. What connects truth, beauty and the good is simplicity. Epistemology tends to favor simple theories over complicated ones (Occam’s razor), simplicity is an important aesthetic dimension and simplicity serves robustness and resilience. In a way, writing an algorithm is like writing a poem: the result may be ugly or beautiful. In what follows, you find a rather poetic perspective on Frogsort
About the name Frogsort
FROG is an acronym describing the core innovation of Frogsort (and Geckosort):
Flip Recursive Organized Gaps
The Gecko is a relative of the Frog which is not only left-right-symmetric but also more rear-front-symmetric
At the very least, we didn’t name our language after a snake
– Alan Edelman, creator of the Julia language which outperforms Python
About the Holy Sorting Grail
The challenge
the “Holy Sorting Grail” would be to find a practically usable stable inplace mergesort with a \(\mathcal{O}(N\log{N})\) worst-case and best-case.
– Robert Sedgewick (2008 or earlier)
The algorithmic solution
Fast Stable Merging and Sorting in Constant Extra Space: we devise a relatively simple strategy by which this efficient merge can be made stable, and extend our results in a nontrivial way to the problem of stable sorting by merging
– Huang & Langston (1992)
The implementation proof
Grailsort: Stable In-place sorting in worst time.
– Andrej Astrelin (2013/2014)
The superior practical algorithm
Sqrtsort: GrailSortWithBuffer uses fixed buffer of 512 elements (allocated in the stack). GrailSortWithDynBuffer uses dynamiclly allocated buffer less than \(2*\sqrt{N}\) elements (allocated in heap).
– Andrej Astrelin (2013/2014)
Sedgewick’s reaction: not honoring the winners, but redefining the challenge
the “Holy Sorting Grail” would be to find a practically usable stable inplace mergesort with a \(\mathcal{O}(N\log{N})\) worst-case and a \(\mathcal{O}(N)\) best-case.
– Robert Sedgewick (2014 and later)
greeNsort® approach: rational analysis and superior solutions
Inplace sorting has been an academic obsession for decades. Buffer-extremism is suboptiomal. Neither \(0\%\) nor \(100\%\) buffer give the most sustainable sorting algorithm. The most sustainable buffer size is between \(\mathcal{O}(\sqrt{N})\) (Walksort, Jumpsort) and \(50\%\) buffer (Frogsort)
– Jens Oehlschlägel (2010 - 2024)
About beauty and simplicity
To the true, the beautiful and the good
— Old Opera Frankfurt1
The height of sophistication is simplicity
― Clare Boothe Luce
Simplicity carried to the extreme becomes elegance.
― Jon Franklin
To iterate is human, to recurse divine
― L. Peter Deutsch
Hardware eventually fails. Software eventually works.
― Michael Hartung
Beauty is more important in computing than anywhere else in technology because software is so complicated. Beauty is the ultimate defence against complexity.
— David Gelernter
The process of preparing programs for a digital computer is especially attractive, not only because it can be economically and scientifically rewarding, but also because it can be an aesthetic experience much like composing poetry or music.
— Donald Knuth
Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it.
— Brian Kernighan
Ugly programs are like ugly suspension bridges: they’re much more liable to collapse than pretty ones, because the way humans (especially engineer-humans) perceive beauty is intimately related to our ability to process and understand complexity. A language that makes it hard to write elegant code makes it hard to write good code.
— Eric Raymond
A good programmer is someone who always looks both ways before crossing a one-way street
— Doug Linder
Manufacturing, science and engineering are … incredibly creative. I’d venture to say more so than creative advertising agencies and things that are known as the creative industries.
— Sir James Dyson
I have always imagined that Paradise will be a kind of library — Jorge Luis Borges
That’s about how art can foreshadow politics, offering glimpses of a future that we can then work in more mundane ways to turn into reality. That’s the concrete utopia concept that I dearly love. — Benjamin Tallis2
About efficiency and preparation
Being cold-blooded, frogs make efficient use of the food they eat with little energy being used for metabolic processes, while the rest is transformed into biomass.
— Wikipedia
Cold-blooded research digested publications and biases since 1945 bit by bit, and puts the irrational search for the holy sorting grail onto the compost heap of history.
— greeNsort®
A wild boar was whetting his tusks against a tree when a fox came by and asked why he did so. “For,” said he, “I see no reason for it; there is neither hunter nor hound in sight, nor any other danger that I can see at hand.” “True,” replied the boar, “but when that danger does arise, I shall have something else to do than to sharpen my weapons.”
— Aesop, The Wild Boar and the Fox
The secret of getting ahead is getting started
— Mark Twain
About transformation and hope
At the end of the tadpole stage, a frog undergoes metamorphosis into the adult form.
— Wikipedia
After all, realism offers no guide to a better life. In contrast, Idealism, by putting morals into play and also focusing on economic benefit, centres everything on the well-being of people.
— Benjamin Tallis
A futurism that, instead of just moving fast and breaking things, moves fast and creates something, looks forward, looks to the new, pushes those frontiers, and experiments—but takes people with it, too.
— Benjamin Tallis
Perhaps all the dragons in our lives are princesses who are only waiting to see us act, just once, with beauty and courage
— Rainer Maria Rilke3
Then she felt beside herself with rage, and picking him up, she threw him with all her strength against the wall, crying: “Now will you be quiet, you horrid frog!”. But as he fell, he ceased to be a frog, and became all at once a prince with beautiful kind eyes.
— Brothers Grimm, The frog king or Iron Henry4
The future enters into us, in order to transform itself in us, long before it happens
— Rainer Maria Rilke5
But the second frog did not give up hope. He swam and pedaled on all night. When morning finally came and the sun shone into the chamber, the frog sat on a lump of butter. He gathered all his strength, jumped out of the jar and was saved.
— unknown
Why is it that we rejoice at a birth and grieve at a funeral? It is because we are not the person involved.
— Mark Twain
The best way to predict the future is to create it.
― Alan Kay
About resilience and perseverence
“Who shall pluck me up by the roots or bow my head to the ground?” But it soon had to repent of its boasting, for a hurricane arose which tore it up from its roots, and cast it a useless log on the ground, while the little Reed, bending to the force of the wind, soon stood upright again when the storm had passed over.
— Aesop, The Oak And The Reeds
Some frogs inhabit arid areas, such as deserts, and rely on specific adaptations to survive. […] Members of the Australian genus Cyclorana bury themselves underground where they create a water-impervious cocoon in which to aestivate during dry periods. Once it rains, they emerge, find a temporary pool, and breed […] The wood frog (Rana sylvatica), whose habitat extends into the Arctic Circle, buries itself in the ground during winter. Although much of its body freezes during this time, it maintains a high concentration of glucose in its vital organs, which protects them from damage.
— Wikipedia
Frogsorts compile robustly under various compiler versions on different CPUs, they adapt to divers inputs without tuning and are resilient in minimum memory contexts, hence on old hardware.
— greeNsort®
That something is difficult must be one more reason for us to do it.
― Rainer Maria Rilke6
In the beginner’s mind there are many possibilities; in the expert’s mind there are few.
― Shunryu Suzuki
Giving up smoking is the easiest thing in the world. I know because I’ve done it thousands of times.
― Mark Twain
About innovation and meaning
I live my life in widening rings,
which spread over earth and sky.
I may not ever complete the last one,
but that is what I will try.
— Rainer Maria Rilke7
At first sight, frogs seem rather defenceless because of their small size, slow movement, thin skin, and lack of defensive structures, such as spines, claws or teeth. Many use camouflage to avoid detection, the skin often being spotted or streaked in neutral colours that allow a stationary frog to merge into its surroundings. Some can make prodigious leaps, often into water, that help them to evade potential attackers, while many have other defensive adaptations and strategies. […] Poisonous frogs tend to advertise their toxicity with bright colours, an adaptive strategy known as aposematism.
— Wikipedia
Frogsorts are a new species of algorithms that combine beauty and efficiency.
— greeNsort®
Art means not to know that the world already exists, and to make a world
— Rainer Maria Rilke8
The greatest invention in the world is the mind of a child.
― Thomas Edison
Inventors are honorable not because they make a difference, but because they want to make a difference against all odds
― Kalyan C. Kankanala
The Patent Office is the mother-in-law of invention — Anonymous
They did not know it was impossible so they did it
― Mark Twain
A pile of rocks ceases to be a rock pile when somebody contemplates it with the idea of a cathedral in mind.
— Antoine Saint-Exupery
Two roads diverged in a wood … I took the one less travelled by, and that has made all the difference.
— Robert Frost
A good scientist is a person with original ideas. A good engineer is a person who makes a design that works with as few original ideas as possible.
— Freeman Dyson
About science and truth
The first principle is that you must not fool yourself — and you are the easiest person to fool
― Richard Feynman
Measuring programming progress by lines of code is like measuring aircraft building progress by weight
― Bill Gates
A big computer, a complex algorithm and a long time does not equal science. ― Robert Gentleman
The combination of some data and an aching desire for an answer does not ensure that a reasonable answer can be extracted from a given body of data ― John Tukey
There are no routine statistical questions, only questionable statistical routines. ― D.R. Cox
He uses statistics like a drunken man uses a lamp post, more for support than illumination. ― Andrew Lang
It’s easy to win forgiveness for being wrong; being right is what gets you into real trouble
― Bjarne Stroustrup
The way we organize the modern American university fragments our knowledge badly
― Elinor Ostrom
He thought the term “workshop” conveyed a sense closer to his philosophical view of science as a form of artisanship
― Elinor Ostrom
The limits of my language mean the limits of my world
― Ludwig Wittgenstein
Sapere aude – Have the courage to use your own reason!
― Immanuel Kant
The reason why I give no sources is that it is a matter of indifference to me whether the thoughts that I have had have been anticipated by someone else
― Ludwig Wittgenstein
Genius is the ability to independently arrive at and understand concepts that would normally have to be taught by another person
― Immanuel Kant
I believe that the extraordinary should be pursued. But extraordinary claims require extraordinary evidence.
— Carl Sagan
Absence of evidence is not evidence of absence. ― Martin Rees
The weight of evidence for an extraordinary claim must be proportioned to its strangeness. ― Pierre Simon Laplace
Mathematics is a place where you can do things which you can’t do in the real world
— Marcus du Sautoy
A good mathematical joke is better, and better mathematics, than a dozen mediocre papers
— J. E. Littlewood
The subjectivist (i.e. Bayesian) states his judgements, whereas the objectivist sweeps them under the carpet by calling assumptions knowledge, and he basks in the glorious objectivity of science. ― Irving John Good
Those who ignore Statistics are condemned to reinvent it. ― Brad Efron
To find out what happens when you change something, it is necessary to change it. ― Box, Hunter, and Hunter, Statistics for Experimenters (1978).
The surprising thing about this paper is that a man who could write it would
— J. E. Littlewood
Only that scientist proves, negatively, his fidelity to the aesthetic who in general resists language and instead of degrading the word to a mere paraphrase of his calculations prefers the charts that uninhibitedly admit the reification of consciousness
— Theodor W. Adorno9]
About sustainability and eternity
The biologist passes,
the frog remains.
— Jean Rostand10
Frogs are generally recognized as exceptional jumpers and, relative to their size, the best jumpers of all vertebrates.
— Wikipedia
Sustainability means that Frogs jump faster with less muscles using less energy and that Frogsorts sort faster with less RAM using less CPU.
— greeNsort®
The old pond
A frog leaps in.
Sound of the water.
— Matsuo Basho11
When I was younger I could remember anything, whether it happened or not.
— Mark Twain
About the tragedy of the commons
Frogs are also seen as environmental bellwethers, with declines in frog populations often viewed as early warning signs of environmental damage.
— Wikipedia
The tragedy of the commons is a situation in a shared-resource system where individual users, acting independently according to their own self-interest, behave contrary to the common good of all users by depleting or spoiling the shared resource through their collective action.
— Wikipedia
However, there are large and important parts of the world that are “unmanaged” or “unmanageable.”
— William D. Nordhaus
If Frogsort is patented and sold to cover the innovators expenses, potential annual savings of 51 TWh resp. 30 MtCO2e resp. 7.1 Billion EUR are lost for the public good.
— greeNsort®
A frog was fighting with a rat over a swamp. The frog claimed that he owned it with the greatest right; the rat, on the other hand, claimed that it belonged to him and that the frog had to give it to him. But the frog wouldn’t hear of it, and so they clashed violently in this quarrel. How much better they would have done if they had compared themselves, for in the heat of the quarrel they had not paid attention to the consecration, which had lurked in the distance, and now came upon the fighters and tore them both apart.
— Aesop, The Rat And The Frog
Go to Heaven for the climate, Hell for the company.
— Mark Twain
About the tragedy of the horizon
The boiling frog is a fable describing a frog being slowly boiled alive. The premise is that if a frog is put suddenly into boiling water, it will jump out, but if the frog is put in tepid water which is then brought to a boil slowly, it will not perceive the danger and will be cooked to death. The story is often used as a metaphor for the inability or unwillingness of people to react to or be aware of sinister threats that arise gradually rather than suddenly.
— Wikipedia
If you put a frog in boiling water, it won’t jump out. It will die. If you put it in cold water, it will jump before it gets hot - they don’t sit still for you.
— Douglas Melton, 1995
The truth appears to be that if the heating be sufficiently gradual, no reflex movements will be produced even in the normal frog
— William Thompson Sedgwick, 1888
In this paper, we investigate how humans respond to a very slow versus a very steep increase of a subsidy on contributions to a public good. […] When the subsidy was raised to a substantial level, a clear boiling frog effect emerged. Subjects hardly responded to the subsidy when it was introduced gradually while they reacted strongly when it was introduced in one shot. […] Subjects who did not play the public good game […] predicted the effect of the subsidy more or less correctly when it was introduced at once […] predictors failed to predict that the subsidy would not have an effect on the contributions when the subsidy was introduced gradually […] people simply fail to respond to tiny changes in the environment.
— Offermann & van der Veen, 201512
These days, the problem isn’t how to innovate; it’s how to get society to adopt the good ideas that already exist.
— Douglas Engelbart
There is a risk that everyone with the ability to sponsor greeNsort® is hoping for someone else to carry the cost, and that finally none of the potential annual savings of 51 TWh resp. 30 MtCO2e resp. 7.1 Billion EUR are realized.
— greeNsort®
All you need in this life is ignorance and confidence, and then success is sure.
— Mark Twain
If I had asked people what they wanted, they would have said faster horses.
— Henry Ford
For peace to reign on Earth, humans must evolve into new beings who have learned to see the whole first
– Immanuel Kant
About climate action and outcome
Three weeks ago the frog was so sick!
Now he smokes again. Thank God!
— Wilhelm Busch13
If it’s your job to eat a frog, it’s best to do it first thing in the morning.
— Mark Twain
Star of Lithuanian diplomacy, Neo-Idealism. The resurgence of a radical centre↩︎
Vielleicht sind alle Drachen unseres Lebens Prinzessinnen, die nur darauf warten, uns einmal schön und mutig zu sehen
— Rainer Maria Rilke↩︎Da ward sie erst bitterböse, holte ihn herauf und warf ihn aus allen Kräften wider die Wand: “Nun wirst du Ruhe haben, du garstiger Frosch.” Als er aber herabfiel, war er kein Frosch, sondern ein Königssohn mit schönen und freundlichen Augen.
— Gebrüder Grimm, Der Froschkönig oder der eiserne Heinrich↩︎Aber es sprechen viele Anzeichen dafür, dass die Zukunft in solcher Weise in uns eintritt, um sich in uns zu verwandeln, lange bevor sie geschieht.
— Rainer Maria Rilke↩︎daß etwas schwer ist, muß uns ein Grund mehr sein, es zu tun.
― Rainer Maria Rilke↩︎Ich lebe mein Leben in wachsenden Ringen,
die sich über die Dinge zieh’n.
Ich werde den letzten vielleicht nicht vollbringen,
aber versuchen will ich ihn.
— Rainer Maria Rilke↩︎Kunst heißt, nicht wissen, daß die Welt schon ist, und eine machen.
— Rainer Maria Rilke↩︎“.. der Forscher bewährt, negativ, am ehesten ästhetische Treue, der gegen Sprache überhaupt sich sträubt und, anstatt das Wort zur bloßen Umschreibung seiner Zahlen zu erniedrigen, die Tabelle vorzieht, welche die Verdinglichung des Bewußtseins ohne Rückhalt einbekennt …” — Theodor W. Adorno (1958). Der Essay als Form. In: Noten zur Literatur, S. 17, Suhrkamp↩︎
Le biologiste passe,
la grenouille reste.
— Jean Rostand↩︎古池や 蛙飛び込む 水の音
Furuike ya
Kawazu tobikomu
Mizu no oto
— Matsuo Basho↩︎Theo Offerman & Ailko van der Veen (2015) How to subsidize contributions to public goods Does the frog jump out of the boiling water? European Economic Review, Volume 74, Pages 96-108↩︎
Drei Wochen war der Frosch so krank!
Jetzt raucht er wieder. Gott sei Dank!
— Wilhelm Busch↩︎
Copyright © 2010 - 2024 Dr. Jens Oehlschlägel - All rights reserved - Terms - Privacy - Impressum