Eine klassische Algorithmusfrage, die durch einen häufig in Projekten verwendeten Linux-Befehl verursacht wird

　　小时候家里定了《读者》的月刊，里面记录一个故事：说有有个偏僻的乡村一日突然来了一个美女，她携着万贯家财子女在当地安家落户，成了当地的乡绅。她让她的子女世世代代的保守这个秘密，直到这个秘密不会再对家族带来灾难。她就是陈圆圆。当年吴三桂领清兵入关，冲冠一怒为红颜，改写了中国的历史，自己却能全身而退的那个人。

　　周五例行公事的查看一下离线数据推送项目的数据和log。将log用awk分段之后，我想知道实时数据前10个被重复发送的数据ID都被重复发送了几次，从而找到进一步优化的入手点，天知道我对这个项目已经进行了多少次优化了。于是linux命令就是

 cat transmission.log |grep 'IncrementAlbumService.java:146'|awk '{print $6}'|awk -F ',' '{print $1}'| sort |uniq -c| sort -nr |head

Die Ergebnisse, die ich erhalten habe, lösten in mir ein großes Schuldgefühl aus

(Datensicherheit, der ID-Regelteil unseres Projekts wird nicht angezeigt)

Obwohl dies mit ihrem Betrieb zusammenhängt, Ursprünglich ist es an der Zeit, die Daten zu senden, wenn die Änderung erkannt wird, aber die Rate der erneuten Übertragungen ist so hoch. Unabhängig von der Schnittstelle des Update-Dienstes oder des Offline-Dienstes gibt es noch Punkte, die optimiert werden können. Mädchen, mein Denken war schon immer anders als das dieser männlichen Idole, die Haartrockner und künstliche Gießkannen verwenden, um ein Bild zu erzeugen, wenn sie auftauchen. Zusätzlich zu diesem Ergebnis denke ich auch über ein weiteres klassisches Algorithmusproblem nach: Es gibt eine Textdatei mit etwa 10.000 Zeilen, ein Wort in jeder Zeile, und es ist erforderlich, die zehn am häufigsten vorkommenden Wörter zu zählen.

Für dieses Algorithmusproblem lautet der obige Linux-Befehl sort|uniq -c |sort -nr |. Die Zeitkomplexität ist die größte der folgenden:

1> Führen Sie zuerst eine Sortierung durch,

Direkte Einfügungssortierung: Fügen Sie kontinuierlich Elemente in die geordnete Liste ein, die schlechteste Zeit ist komplex. Der Grad ist O (n²)

Shell-Sortierung: Einfügungssortierung mit reduziertem Inkrement, instabil, abhängig von der Auswahl der Inkrementfaktorsequenz, die schlechteste Zeitkomplexität ist O(n ²)

Einfache Auswahlsortierung: Wählen Sie die kleinste oder größte Zahl unter den zu sortierenden Zahlen aus und tauschen Sie sie gegen die erste unsortierte Position aus. Die schlechteste Zeitkomplexität ist O(n² ).

Binäre Auswahlsortierung: Jede einfache Auswahlsortierung bestimmt zwei Elemente, wodurch der Zyklus um die Hälfte verkürzt werden kann.

Heap-Sortierung: Baumauswahlsortierung, großer Wurzelhaufen, kleiner Wurzelhaufen. Die schlechteste Zeitkomplexität ist O(N*logN)

Blasensortierung: Jedes Mal, wenn zwei benachbarte Zahlen verglichen und ausgetauscht werden, ist die schlechteste Zeitkomplexität O(n² )

Schnelle Sortierung: Wählen Sie das Basiselement aus und teilen Sie die zu sortierenden Elemente jedes Mal auf. Die schlechteste Zeitkomplexität ist O(n²)

Sortierung zusammenführen: Teilen Sie die beiden Elemente in geordnete Listen werden zu einer neuen geordneten Liste synthetisiert. Die Komplexität im schlimmsten Fall ist O(N*logN)

. Die Komplexität liegt nahe bei O(n)

Radix-Sortierung: Ordnen und sammeln Sie nach Hunderttausenden von Ziffern, die Zeitkomplexität ist O(dn)

　 2>Uniq-Zeitkomplexität ist O(n)

3> ; Der Grad der Sortierzeit ist derselbe wie 1>

4>Die Zeitkomplexität nach der Sortierung beträgt O(1)

Der verwendete Algorithmus hängt auch von der Größe der Datei ab Die Datei ist zu groß. Wenn zu viele Daten vorhanden sind, müssen die Dateien aufgeteilt, separat sortiert und dann auf verschiedene Arten zusammengeführt werden. Daher wird hier die Anzahl der Wörter angegeben.

Ohne Linux-Befehle besteht die klassische Lösung darin, zunächst einen Wörterbuchbaum zum Zählen der Worthäufigkeiten zu verwenden und dann einen großen Root-Heap zu verwenden. Lassen Sie uns zunächst den Wörterbuchbaum vorstellen, der auch Reifenbaum genannt wird. Da Suchmaschinen dies häufig verwenden, um Statistiken zur Worthäufigkeit von Texten zu erstellen, und Wortsegmentierungsalgorithmen dies auch als grundlegende Datenstruktur verwenden, weiß ich ein wenig darüber. Seine Vorteile sind: Minimierung unnötiger Zeichenfolgenvergleiche und höhere Abfrageeffizienz als bei Hash-Tabellen. Die Kernidee besteht darin, Raum gegen Zeit auszutauschen und öffentliche Präfixe zu verwenden, um den Zeitaufwand für Abfragen zu reduzieren. Wenn man also über Statistiken spricht, fällt einem als Erstes der Wörterbuchbaum ein. Wenn Sie beim Zählen der Worthäufigkeiten ein Array der zehn höchsten Worthäufigkeiten verwalten, ist die zeitliche Komplexität im Vergleich zur Schleifenverarbeitung zehnmal höher. Daher ist es sinnvoller, zunächst Statistiken zu erstellen und dann die Top 10 in Bezug auf Zeiteffizienz auszuwählen.

Eigentlich weiß ich nicht viel über Algorithmen, ich weiß nur, wie man sie verwendet. Ein ehemaliger Kollege von mir las einen Artikel, den ich auf WeChat geschrieben hatte, und fragte mich: „Ist Feed-Streaming ein sehr technischer Job?“ Seine Frage erinnerte mich an Li Xiaoyao in „Sword of Immortals“, der darauf bestand, so zu tun, als wäre er groß, reich und gutaussehend Als er im Restaurant sagte, er wolle das teuerste Gericht bestellen: „Gebratenes Rindfleisch mit Gemüse“, fragten alle Li Xiaoyao: „Bruder Xiaoyao, ist gebratenes Rindfleisch mit Gemüse ein sehr teures Gericht?“ Obwohl mein Kollege mich ernsthaft nach meiner Meinung fragte, weil er bei JD.com war und überlegte, ob er zu Momo gehen sollte, fühlte ich mich wie der Li Xiaoyao, der noch nie die Welt gesehen hatte. Die Geschäftslogik des Feed-Flows kann auf beliebige Weise erfolgen. Ob sie technischen Inhalt hat, hängt davon ab, wie sie durchgeführt wird. Ich habe ein Patent geschrieben, um eine Methode zur Zusammenstellung von Zufuhrströmen einzuführen. Der Prozess ist noch nicht abgeschlossen, daher werde ich die Berechnungsmethode bis dahin nicht offenlegen. Wenn Sie jedoch genau nachdenken, gibt es noch viele Optimierungspunkte. Im vorletzten Jahr, als ich gerne Moments spielte, stellte ich oft fest, dass die Moments, die ich gelöscht hatte, wieder auftauchten oder dass alle aktuellen Daten in meinen Moments oder denen anderer Leute plötzlich verschwanden und nur noch sehr alte Daten übrig blieben, z. B. die Daten von vor zwei Monaten von vor einem Jahr wird nach einem Tag automatisch wiederhergestellt. Es ist alles eine Frage der Strategie. Es gibt viele Probleme mit WeChat Moments. Da eines unserer Produkte, mm, ein Familienmitglied des WeChat-Architekten ist, werde ich mich nicht allzu sehr beschweren.

Auch wenn heute Sonntag ist, können Sie Ihrer Fantasie ein wenig freien Lauf lassen, aber Sie müssen auch ein Thema haben. Das vorherige Beispiel hat ein klassisches Top-K-Problem. Da Suchmaschinen oft die beliebtesten Abfragezeichenfolgen zählen müssen, ist die Top-K-Frage die Grundlage. TopK-Probleme verwenden kleine Root-Heaps. Behalten Sie einen kleinen Root-Heap der K-Größe bei, durchlaufen Sie die zu vergleichenden Elemente und vergleichen Sie sie jeweils mit den folgenden Elementen. Wenn es kleiner als das Root-Element ist, bedeutet dies, dass es definitiv nicht in das obere K gelangt und eliminiert wird. Wenn es größer als das Wurzelelement ist, entfernen Sie das Wurzelelement. Passen Sie dann den Baum auf den minimalen Heap an und fahren Sie mit dem Vergleich fort.

Der minimale Heap ist ein vollständiger Binärbaum, und der Wert jedes Nicht-Blattknotens ist nicht größer als der Wert seines untergeordneten Knotens. Wenn diese Regel verletzt wird, müssen Anpassungen vom ersten Nicht-Blattknoten bis zum Wurzelknoten in einer Reihenfolge von unten nach oben vorgenommen werden.

Ich habe beschlossen, nächste Woche ein Vorstellungsgespräch auf Hulu zu führen, habe es aber noch nicht getan, also werde ich es wahrscheinlich nicht tun. Vor zwei Jahren hat mein ehemaliger Kollege Amazon empfohlen, aber ich wurde nicht zu einem Vorstellungsgespräch eingeladen. Zu meiner Beruhigung muss ich sagen, dass sie zu diesem Zeitpunkt keine Mitarbeiter eingestellt haben. Ich war noch nie bei einem solchen Vorstellungsgespräch bei einem ausländischen Unternehmen dabei und weiß daher nicht, wie die Routine abläuft. Wenn wir jetzt mit den Vorbereitungen beginnen, werden wir es wahrscheinlich nach dem Nationalfeiertag schaffen. Ich denke, es wäre sehr nachteilig für mich, alleine zum Vorstellungsgespräch zu gehen. Es wird überhaupt nicht schlimm sein, es wird sehr instabil sein. Freunde, die meine Artikel gelesen haben, denken vielleicht, dass meine Artikel sehr chaotisch und kompliziert sind. Das ist bei mir im Leben tatsächlich der Fall. Ich verfüge über ein breites Wissensspektrum, bin sehr skurril und habe keine Skrupel. Das ist einerseits die Grundlage für meine Kreativität, andererseits aber auch nicht förderlich für meine Ausdrucksfähigkeit Stelle. Das Gehirn ist wie ein Computer. Ich habe viele parallele Programme, der Speicher ist nicht groß genug und es gibt viele Daten. Speicher-Paging führt zu einem ständigen Festplattenaustausch. Zeitkritische Aktionen wie Vorstellungsgespräche können leicht zu Timeout-Retouren führen. Ich habe so viele Patente für technische Erfindungen und jetzt denke ich, dass ich mich nicht einmal daran erinnern kann, was ich erfunden habe. Da nur sehr wenige Leute da waren, fragte mich der Fahrer, wo ich aussteigen solle. Er meinte, dass er dort anhalten würde, wo niemand ausstieg. Es hat lange gedauert, bis ich mich daran erinnerte. Mein Gehirn läuft eher im asynchronen, nicht blockierenden Modus. Tatsächlich wäre synchrones Blockieren für Dinge wie Interviews besser. Es gibt jedoch für alles eine Lösung. Wenn Sie keine Lösung finden, fehlt Ihnen einfach die Fähigkeit. Daran ist nichts auszusetzen. Im Vorstellungsgespräch sollen jedoch umfassende Fähigkeiten wie Teamfähigkeit, Gesprächsgeschick usw. geprüft werden. Ich glaube, dass niemand in unserer Abteilung Einwände gegen den Satz „Xiaojing ist sehr schlau“ haben wird. Ich glaube auch, dass Kollegen, mit denen ich in der Abteilung zusammenarbeite oder arbeite, nicht denken werden, dass es schwierig sei, mit mir zu kommunizieren oder mit mir auszukommen. Aber ich neige dazu, bei Vorstellungsgesprächen zu vergessen, wie man spricht. Aber wenn ich aufgrund dieses Problems bei einem Vorstellungsgespräch durchfalle, habe ich keine Beschwerden. Da der Interviewer Ihr zukünftiger Kollege und Leiter ist, können Sie Ihre Fähigkeiten in Zukunft möglicherweise nicht nutzen, wenn Sie nicht mit dem Interviewer im Einklang sind. Wenn Sie in Vorstellungsgesprächen nicht gut abschneiden und dennoch das Gefühl haben, dass Ihre Fähigkeiten ausreichen, ist es wahrscheinlich, dass Sie nicht hoch genug qualifiziert sind und noch nie gesehen haben, wie wirklich herausragende Menschen aussehen. Allerdings gehöre ich zu der Art von Person, die auch dann weitermacht, wenn ich fest entschlossen bin, gegen eine Wand zu stoßen. Wenn ich mich entscheide, etwas aufzugeben, dann deshalb, weil es sich nicht lohnt.

Ich arbeite gerne. Mein Ziel ist es, auch mit 60 Jahren noch einen kreativen Job zu haben. Deshalb habe ich Angst, dass inländische Internetunternehmen mich mit 40 Jahren in den Ruhestand gehen lassen. Es gibt noch etwas Wichtiges: Ich möchte meine eigene Suchmaschinen-Middleware entwickeln. Inländische Internetunternehmen konzentrieren sich hauptsächlich auf Benutzer, daher befürchte ich, dass es für mich schwierig sein wird, die Energie dafür aufzubringen. Wenn Sie nicht zu Hulu gehen können, muss die Suchmaschine dies natürlich trotzdem tun. Es ist nur eine Frage, wie Sie Ihre Zeit einteilen.

Eigentlich mag ich es, gegen die Wand zu stoßen, vielleicht weil ich nicht so schnell erwachsen werden möchte. Wenn Sie sich jeden Tag erwachsen und elegant verhalten, müssen Sie einige Dinge verbergen, in denen Sie nicht gut sind oder die schief gehen könnten. Dadurch werde ich jeden Tag glücklich sein, aber vielleicht bleibe ich auch für den Rest meines Lebens so. Es gibt viele berühmte Persönlichkeiten in der Geschichte, die ursprünglich Playboys waren, später aber nach dem Niedergang ihrer Familie zu großen Männern wurden. In dem Buch gibt es zwei Arten von Wendepunkten im Leben: die Begegnung mit edlen Menschen und das Erleben von Rückschlägen. Wenn Sie jung und aufgeschlossen sind, können Sie eine Offenbarung erleben, wenn Sie eine edle Person treffen und Ihren Geist öffnen. Mit zunehmender Erfahrung nehmen die Menschen die Informationen um sie herum selektiver wahr. In dieser Zeit müssen sie möglicherweise große Rückschläge erleiden, bevor sie ihr Leben überdenken können. Wenn ich eine bessere Zukunft sehen kann, bin ich bereit, einen Alleingang zu machen und das Boot niederzubrennen. Es ist besser, Höhen und Tiefen zu haben, als einen Tag nach dem anderen. Wenn du leben willst, lebe ein wundervolles Leben~~

Das obige ist der detaillierte Inhalt vonEine klassische Algorithmusfrage, die durch einen häufig in Projekten verwendeten Linux-Befehl verursacht wird. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!