- Palima Aethera wirkt wie die Kandidatin, die Techaros chaotische Infrastruktur retten könnte, kippt aber beim Live-Coding die Stimmung im Interview, indem sie absichtlich eine skurrile Sortierlösung präsentiert
- Der Interviewer Jeff prüft zunächst die Aussprache ihres Namens und ob ihr Gesicht echt ist, und zeigt dann großes Interesse an Palimas Infrastruktur-Erfahrung bei MovieFlix und einem Fall, in dem sie FreeBSD gewählt hat
- Bei der Aufgabe, ein Zahlen-Array zu sortieren, implementiert Palima in Haskell sleepsort: Für jeden Wert erzeugt sie einen Thread, lässt ihn proportional zum Wert schlafen und gibt ihn dann aus
- Palima beharrt darauf, diese Lösung sei „Sortieren in konstanter Zeit“, und erklärt, sie habe sie um den Faktor 10 optimiert, indem sie die Verzögerung von
100000auf10000Mikrosekunden pro Einheit reduziert habe, was Jeff zum Lachen bringt - Nach dem Interview rechnet Palima mit einer Absage, doch Techaro schickt ein Angebot über eine beträchtliche Summe; Palima beschließt, schlafen zu gehen, weil sich die Dinge schon von selbst sortieren würden
Der Interviewtag beginnt im Traum
- Palima bemerkt im Traum, dass ihr Erwachens-Talisman am Handgelenk verschwunden ist, und erkennt daran, dass sie träumt
- Nachdem sie morgens durch die Vibration ihrer Armbanduhr aufwacht, erinnert sie sich daran, dass an diesem Tag ein wichtiger Termin ansteht
- Der Weg zur Arbeit ist in 30 Sekunden erledigt, und Palima setzt sich auf einen Stuhl, der so umgebaut ist, dass er Schwanz und Rückenflosse Platz bietet
- Die Workstation meldet, dass Firefox veraltet ist, und ein Skript baut die neue Version und startet sie
Beginn des Interviews bei Techaro
- Die Videokonferenz läuft über einen Dienst der E100-Reihe, und Palima schaltet die Kamerabeleuchtung ein
- Der erste Interviewer, Jeff, spricht Palimas Namen zunächst falsch aus und korrigiert sich sofort
- Palima erklärt, dass
Pa-lee-mahundAetheraalsAy-theer-ahausgesprochen werden - Jeff sagt, er werde sich das notieren, damit auch andere sie korrekt ansprechen können
- Palima erklärt, dass
- Als Jeff fragt, ob sie einen virtuellen Avatar verwende, antwortet Palima: „Das ist mein echtes Gesicht“
- Palima hat schon aus der Stellenausschreibung erkannt, dass Techaros Infrastruktur chaotisch ist und einen Helden braucht
Beruflicher Hintergrund und Infrastruktur-Erfahrung
- Palima beschreibt, dass sie viel daran gearbeitet hat, digitale Automaten zu bauen und in die Welt zu entlassen, damit sie Ziele erfüllen
- Bei MovieFlix trug sie zum Aufbau der Infrastruktur für gleichzeitiges Streaming populärer Filme und TV-Sendungen bei
- Sie fügt hinzu, dass es viele Projekte gebe, über die sie nicht sprechen dürfe, und dass Jeff derzeit von mindestens drei davon profitiere
- Der Grund, warum sie zu einem kleineren Unternehmen wechseln möchte, sei, dass sie die Menschen persönlicher kennenlernen wolle; der Reiz, wie ein anonymes Bauteil in einer Maschine zu arbeiten, halte nicht lange an
- Als bevorzugtes Infrastrukturprojekt nennt sie OS-Kernel-Benchmarks für das MovieFlix-Backend
- Palima hatte gehofft, dass Linux gewinnen würde, doch nach
epoll(7)lief FreeBSD schneller, weshalb sie FreeBSD wählte - Sie ergänzt, dass sie vermutlich noch Commit-Rechte für FreeBSD habe
- Palima hatte gehofft, dass Linux gewinnen würde, doch nach
Live-Coding: sleepsort
- Jeff erklärt, dass Palimas Hintergrund zu dem Typ passe, den Techaro suche, sie aber einen Coding-Challenge absolvieren müsse, damit alle nach denselben Kriterien bewertet werden
- Die Aufgabe besteht darin, auf der Website ein Zahlen-Array zu sortieren und auch die Sortiermethode zu erklären
- Die Sprache ist frei wählbar, und Palima schreibt Haskell-Code
- Die Implementierung erzeugt für jede Zahl einen eigenen Green Thread, wartet
threadDelay (100000 * time)und schreibt den Wert anschließend zur Ausgabe in einen Channel - Palima sagt, diese Sortierung verwende keine Vergleiche, und „manchmal braucht es eben nur ein bisschen Ruhe“
- Als Jeff fragt, ob die Laufzeit nicht vom Eingabewert abhänge, antwortet Palima, dass sich Zeitkomplexität nicht um Seiteneffekte wie Zeit kümmere
Optimierung und ein unerwartetes Ergebnis
- Als Jeff nach Optimierungsmöglichkeiten fragt, ändert Palima nur den Verzögerungsfaktor
- Sie reduziert
100000 * timeauf10000 * time - Palima erklärt, es sei nun 10-mal schneller
- Sie reduziert
- Jeff lacht schließlich laut, und auf die Frage, warum sie einen so seltsamen Sortieralgorithmus verwendet habe, kontert Palima: „Warum haben Sie so eine seltsame Frage gestellt?“
- Palima urteilt, dass Techaro nicht komplex genug sei, um sie zu fassen, und dass statt Kubernetes auch ein einzelner dedizierter Server von Typhoon Digital gereicht hätte
- Nach dem Interview erwartet sie, dass bald eine Absage-E-Mail eintreffen wird
- Doch Techaro schickt eine E-Mail, dass man sie für eine beträchtliche Summe einstellen möchte, und Palima fragt sich, ob sie wissen, worauf sie sich einlassen
- Palima beschließt, wieder schlafen zu gehen, denn bis zum Abend würden sich die Dinge schon von selbst sortieren
1 Kommentare
Hacker-News-Meinungen
Es ist weder konstante Zeit noch polynomielle Zeit, sondern pseudo-polynomielle Zeit. Bei negativen Zahlen dürfte es scheitern, und damit es linear in der Anzahl der Bits wird, die die Eingabe darstellen, bräuchte man etwas wie
10000 * log(time + min(time) + 1)In der Theorie der Berechnungskomplexität bedeutet, dass ein numerischer Algorithmus in pseudo-polynomieller Zeit läuft, dass seine Laufzeit ein Polynom im numerischen Wert der Eingabe ist, also in der größten in der Eingabe vorkommenden ganzen Zahl — nicht ein Polynom in der Eingabelänge (der Anzahl der Bits, die nötig sind, um diese Zahl darzustellen).
https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time
Berechnungskomplexität befasst sich mit der Anzahl der Schritte in einem Berechnungsmodell, nicht damit, wie viel Uhrzeit vergeht. Sleep Sort nutzt Eigenschaften des Betriebssystem-Schedulers, und in einer virtuellen Zeitumgebung springt die Zeit direkt zum nächsten geplanten Ereignis weiter. Wenn man so etwas als Berechnungsmodell annimmt, läuft es tatsächlich mit polynomieller Komplexität.
Und wenn man andere belehren will, sollte man zumindest pseudo-polynomial richtig schreiben.
1stehen, getrennt durch0.Das wieder in Ganzzahlen umzuwandeln ist linear; danach ruft man die alte Box auf und gibt das Ergebnis zurück, und schon ist es polynomielle Zeit in Bezug auf meine Eingabelänge. Ich habe zwar von Ganzzahlen gesprochen, aber der Kern ist die Kodierung: Man könnte für das Dezimalkomma ein einzelnes
0und zur Trennung der Eingaben00verwenden.Jedenfalls liegt der Kern des Witzes doch darin, dass die Schlafzeit nicht zählt, oder? Der Computer kann in der Zwischenzeit ja andere Dinge tun. Es hat ziemlich überzeugend diesen „dumm, aber ich mag es“-Charme.
Sleep Sort entstand auf /prog/ [0]. Es dürfte einige HN-Lurker geben, die damals im Sleep-Sort-Thread dabei waren; vielleicht gehört xena auch dazu :)
[0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...
<=>erfunden hatte, wenn er „kleiner als, gleich oder größer als“ prüfen wollte. Genial.Wie der Autor des Originals sagt, erinnert der Text stark an den Erzählstil von aphyrs Interview-Reihe, etwa „Rewriting the Technical Interview“. Das ist alles sehr unterhaltsam zu lesen.
[0] - https://aphyr.com/posts/353-rewriting-the-technical-intervie...
https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
Kostprobe:
Computersortierung muss die Eingabe lesen und braucht daher mindestens lineare Zeit. Umso mehr, wenn man keine weiteren Informationen über die Eingabe kennt, etwa eine Gleichverteilung.
Es gibt mehrere lineare Sortierverfahren wie Sleep Sort, Postman Sort, Counting Sort usw. Allerdings nur für begrenzte Zahlenmengen oder sortierbare Schlüssel.
Wenn man statt eines Computers aber einen Abakus verwendet, gibt es ein fast echtes Sortieren in konstanter Zeit: https://en.wikipedia.org/wiki/Bead_sort
Eine nette Geschichte, aber in keinem Sinn konstante Zeit
NThreads zu erstellen und sie alle in eine sortierte Wake-up-Liste einzutragen, dauert je nach Betriebssystem oder Sprach-Runtime zwischen O(N log N) und O(N^2)Irgendwo im Hintergrund steckt eine sortierte Liste, ein Heap oder ein N^2-Algorithmus. Ebenso braucht Sleep Sort selbst mindestens lineare Zeit, weil es N Threads aufwecken muss, um N sortierte Elemente auszugeben
Schlimmer noch: Auch die tatsächliche Uhrzeit wächst mit der Größe der Werte. Man könnte zuerst den Minimal- und Maximalwert finden und den Bereich komprimieren, aber auch das ist lineare Zeit
Es ist hier ein Wortspiel mit zwei miteinander kollidierenden Perspektiven auf das Wort „Zeit“. Aus Sicht der Komplexitätsanalyse ist es korrekt, dass es unmöglich ist, einen Sortieralgorithmus in konstanter Zeit zu haben
Die eigentliche Pointe zielte auf die Uhrzeit. In einem Vorstellungsgespräch ist diese Zeit relevanter, und realistisch gesehen verwendet kaum jemand nur Zahlen unter 100, wenn er etwas wie „Schreiben Sie eine Funktion zum Sortieren von Ganzzahlen“ vorgibt; dieses Programm läuft gefühlt also fast sofort
Es ist ein subtiler metasprachlicher Witz, der das Verständnis davon, wie Informatik funktioniert, auf den Kopf stellt. Schade, dass der Witz nicht gezündet hat
https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
sleepletztlich auf eine Ganzzahl hinauslaufen, also könnte man es mit so etwas wie Radix Sort in linearer Zeit verarbeitenEs gibt Problemräume, in denen sich das lohnt, auch wenn eine Abhängigkeit von der Größe des größten Werts entsteht
Natürlich gibt es in der Praxis kein solches System. System-Call-Timeouts sind normalerweise kein Bereich, in dem diese Methode vorteilhaft wäre. Und selbstverständlich ist es besser, Radix Sort direkt anzuwenden, der nur von
log(max_value)abhängt, statt von einer Methode, die linear vom Maximalwert abhängtNThreads und das Einfügen in eine sortierte Wake-up-Liste O(N log N) bis O(N^2) kostet, ist keine fundamentale Grenze von Scheduling-SystemenDas gilt erst recht, wenn man Spezialhardware einbezieht, die Scheduling in konstanter Zeit bezüglich der Thread-Anzahl ermöglicht. Man könnte zum Beispiel — praktisch völlig unwirtschaftlich — einen Scheduler bauen, der Informationspakete per Laser an einer riesigen Menge von Spiegeln in unterschiedlichen Entfernungen abprallen lässt und zu einem an den Computer angeschlossenen Sensor zurückführt
Dabei nutzt man die Lichtgeschwindigkeit, um um eine bestimmte Zeit zu verzögern. Sleep Sort hängt also nicht grundsätzlich von der versteckten algorithmischen Komplexität irgendeiner Thread-Scheduling-Methode ab und könnte theoretisch auf O(1) optimiert werden, auch wenn das unpraktisch ist
Wenn dir das gefällt, gibt es mit Protos eine Art Nachfolger: https://xeiaso.net/blog/protos
Ich schreibe noch mehr Geschichten in diesem „Universum“, aber es dauert etwas, bis sich genug satirische Energie aufgeladen hat. Der nächste Teil könnte vielleicht Spatial Computing werden
Trotzdem scheint dieses Universum besser im Benennen von Dingen zu sein
Der Teil, in dem
threadDelay (100000 * time)zuthreadDelay (10000 * time)geändert wird und es heißt „Jetzt ist es zehnmal schneller“, hängt mit diesem Artikel zusammen: https://thedailywtf.com/articles/The-Speedup-LoopIch habe den Artikel nicht gelesen, aber ich hasse solche Dinge. Ich hatte früher ein Remote-Vorstellungsgespräch bei Meta, und die Person am anderen Ende hat die ganze Zeit direkt ins Mikrofon gegessen
Das hat mich so abgelenkt, dass ich sogar vergessen habe, wie man eine for-Schleife schreibt
Wenn man angestellt war, musste man Urlaub nehmen, und es gab Stress wie „Verschwende ich hier meinen begrenzten Urlaub?“, „Werde ich parken können?“, „Komme ich rechtzeitig an?“. Dann hatte man ein 30-minütiges „Erstgespräch“, wartete wochenlang und wurde entweder zu einem richtigen Gespräch eingeladen oder hörte gar nichts mehr
Der ganze Prozess konnte einen Monat dauern und mindestens zwei Urlaubstage sowie erheblichen Reiseaufwand erfordern
Heute ruft ein Recruiter oder die Personalabteilung an, fragt, ob man für einen Videoanruf verfügbar ist, man spricht am selben Tag 15–20 Minuten, der Lebenslauf wird an die Entscheider weitergegeben, und es werden ein oder mehrere Video-Interviews oder technische Sessions angesetzt. Manche Firmen lassen einen bequem von zu Hause aus Persönlichkeits-/Techniktests machen
Wenn man remote arbeitet, kann man das alles in der Mittagspause erledigen. Die Kommunikationsbandbreite vor Ort ist zwar deutlich größer, aber nur remote kann man am selben Morgen bei einer Firma in Tel Aviv, mittags bei einer Firma in Warschau und abends bei einer Firma in Kalifornien ein Vorstellungsgespräch führen
1000 Threads zu erstellen ist doch mindestens lineare Zeit, oder? Vielleicht kann man es bis auf logarithmisch reduzieren, aber ich glaube nicht, dass dieser Code das automatisch tut
Damit Sleep Sort konstante Zeit wäre, bräuchte es eine obere Schranke für die Eingabe, also eine Begrenzung der größten Zahl, und man dürfte beliebige Arbeiten wie Eingabe lesen und verarbeiten oder Threads erstellen nicht mitzählen
Wenn man das erlaubt, werden aber alle anderen Sortierverfahren ebenfalls konstante Zeit. Ich glaube, schon eines von beidem würde reichen
Wenn die Thread-Runtime ihr eigenes Zeitkonzept pflegt, muss der Algorithmus nicht einmal in Echtzeit schlafen.
Nachdem alle Threads erzeugt wurden, kann die Runtime feststellen, dass alle Threads idle sind und der als Nächstes zu schedulende Thread der Thread zu Zeitpunkt N ist; sie kann also die aktuelle Zeit auf N setzen und diesen Thread ausführen. Wiederholt man das, erhält man ein sortiertes Array ganz ohne
sleep.Letztlich ist die Sortierarbeit bereits erledigt, wenn die Threads anfangen zu schlafen, und sie haben sich bei einem Koordinator registriert, der sie später aufweckt, zum Beispiel bei einem Timer Wheel. Tatsächlich schlafen müssen sie nicht.
Haskell kenne ich nicht, aber die tokio-Runtime von Rust ermöglicht das mit
start_paused: https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht...Lässt man mehrere Abstraktionsschichten und ausgelassene Implementierungsdetails beiseite, ist das Sortieren von Werten mit so einem Scheduler einfach Heapsort. :)