Technologieaustausch

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Wie sieht die zugrunde liegende ArrayList-Datenstruktur aus?

Die unterste Ebene von ArrayList wird basierend auf Arrays implementiert. Dies geschieht durch dynamisches Erweitern oder Verringern der Größe des Arrays. Wenn die Kapazität nicht ausreicht, wird ein größeres Array erstellt, dann die Originaldaten kopiert und schließlich die neuen Daten hinzugefügt.

Der Mechanismus der ArrayList-Erweiterung ist: Wenn das erste Element hinzugefügt wird, beträgt die Kapazität von ArrayList jedes Mal 10. Wenn die Kapazität überschritten wird, wird die ursprüngliche Kapazität verdoppelt, dh die ursprüngliche Kapazität * 2 Wenn die ursprüngliche Kapazität 0 ist, ist die neue Kapazität 1.

Vor- und Nachteile des ArrayList-Erweiterungsmechanismus:

Vorteil:

1. Der ArrayList-Erweiterungsmechanismus ist einfach zu verstehen und leicht zu implementieren.
2. Die erweiterte Kapazität muss größer sein als die ursprüngliche Kapazität, wodurch die Anzahl der Array-Kopien beim Hinzufügen neuer Elemente verringert und die Effizienz beim Hinzufügen von Elementen verbessert werden kann.

Mangel:

1. Der ArrayList-Erweiterungsmechanismus führt zu einer Verschwendung von Speicher und kann leicht zu einer Verschwendung von Speicherplatz führen.
2. Wenn die Kapazität groß ist, erfordert jede Erweiterung eine große Menge an Speicher- und CPU-Ressourcen, was sich auf die Leistung auswirkt. Daher muss bei Verwendung von ArrayList die Anfangskapazität entsprechend eingestellt werden.

ArrayList ist nicht threadsicher

Die interne Implementierung von ArrayList basiert auf Arrays. Wenn mehrere Threads gleichzeitig auf dieselbe ArrayList zugreifen, kann es zu Dateninkonsistenzen kommen, wenn beispielsweise ein Thread die Daten der ArrayList liest und ein anderer Thread Daten hinzufügt/löscht In der ArrayList kann es sein, dass die Daten in der ArrayList geändert werden, sodass der Thread, der die ArrayList-Daten liest, möglicherweise falsche Daten liest, was zu einem Programmfehler führt.

Zu den gängigen Methoden zur Behebung der ArrayList-Thread-Unsicherheit gehören:

1. Verwenden Sie Vector anstelle von ArrayList: Vector ist synchronisiert und alle Methoden werden durch synchronisiert geändert, sodass es threadsicher ist.
2. ArrayList in Thread-Sicherheit umwandeln: Verwenden Sie die Methode Collections.synchronizedList(list), um ArrayList in Thread-Sicherheit umzuwandeln;
3. Verwenden Sie CopyOnWriteArrayList: Es handelt sich um eine threadsichere und effiziente Sammlung. Der Schreibvorgang erfolgt durch Kopieren des zugrunde liegenden Arrays. Die Kosten für diese Implementierung liegen in einem akzeptablen Bereich.
4. Verwenden Sie Sperren, um Thread-Sicherheit zu erreichen: Sie können Sperrmechanismen wie ReentrantLock verwenden, um eine thread-sichere ArrayList zu implementieren.

Der Unterschied zwischen Stapel und Heap

• Der Stapel ist eine spezielle lineare Tabelle. Seine Besonderheit besteht darin, dass Daten nur an einem Ende eingefügt und gelöscht werden können, basierend auf dem First-In-Last-Out-Last-In-First-Out-Prinzip. Es handelt sich um eine Speicherstruktur, die zum Speichern von Funktionsparameterwerten, lokalen Variablen usw. verwendet werden kann.

• Ein Heap ist eine spezielle Baumstruktur, die dadurch gekennzeichnet ist, dass die Werte aller Knoten größer oder gleich den Werten ihrer untergeordneten Knoten sind und der Wert des Wurzelknotens der größte oder kleinste ist. Der Heap ist eine dynamische Speicherstruktur, die zum Speichern großer Datenmengen wie Sortieren, Suchen usw. verwendet werden kann.

Unterste Schicht der Coroutine

Die Essenz einer Coroutine ist ein leichter Thread. Jede Coroutine verfügt über einen Stapel zum Speichern von Funktionen und ihren Parametern, lokalen Variablen usw. Die Coroutine kann so angehalten, fortgesetzt und umgeschaltet werden.

C# GC-Prinzip (Garbage Collection).

1. Referenzzählung: Wenn auf ein Objekt verwiesen wird, wird sein Referenzzähler um 1 erhöht. Wenn die Referenz ungültig wird, wird sein Referenzzähler um 1 verringert. Wenn der Referenzzähler eines Objekts 0 wird, wird das Objekt vom Garbage Collector zurückgefordert.
2. Mark-and-Clear: Wenn der Garbage Collector ausgeführt wird, durchläuft er Objekte gemäß Referenzbeziehungen, markiert zugängliche Objekte als „lebendig“, markiert unzugängliche Objekte als „tot“ und löscht dann alle als „tot“ markierten Objekte.
3. Kopieralgorithmus: Der Garbage Collector teilt den verfügbaren Speicher in zwei Blöcke auf und verwendet jeweils nur einen Block. Wenn der Speicherplatz nicht ausreicht, werden die verbleibenden Objekte in einen anderen Speicherplatzblock kopiert und dann die kopierten Objekte aus dem Original gelöscht Raum.
4. Mark-Complement-Algorithmus: Wenn der Garbage Collector ausgeführt wird, markiert er zunächst alle überlebenden Objekte und verschiebt dann alle überlebenden Objekte an ein Ende, um ungenutzte Speicherplatzfragmente zu löschen.

Der Unterschied zwischen Statussynchronisation und Framesynchronisation

Zustandssynchronisation Es bezieht sich auf die Übertragung des Status (z. B. Position, Geschwindigkeit, Beschleunigung usw.) jeder Maschine im Mehrmaschinensystem an andere Maschinen in jedem Steuerzyklus, sodass jede Maschine synchronisiert bleibt. Durch die Zustandssynchronisierung kann eine Echtzeitleistung der kollaborativen Steuerung mehrerer Maschinen erreicht werden. Da jedoch in jedem Steuerungszyklus eine große Datenmenge übertragen werden muss, ist die Genauigkeit möglicherweise relativ gering.

Frame-Synchronisation Dies bedeutet, dass in jedem Steuerzyklus die Steuerbefehle jeder Maschine im Mehrmaschinensystem an andere Maschinen übertragen werden, sodass jede Maschine synchronisiert bleibt. Durch die Rahmensynchronisation kann die Genauigkeit einer kollaborativen Steuerung mehrerer Maschinen erreicht werden. Da jedoch in jedem Steuerungszyklus nur eine geringe Anzahl von Steuerbefehlen übertragen wird, ist die Echtzeitleistung möglicherweise relativ gering.

Gängige Designmuster

Singleton-Muster

Fabrikmuster

Zusammengesetztes Muster

Proxy-Muster

Eigenschaften verknüpfter Listen, Binärbäume und Hashtabellen

1. Verlinkte Liste:

• Es handelt sich um eine lineare Listenstruktur, die dadurch gekennzeichnet ist, dass jeder Knoten einen Zeiger hat, der auf den nächsten Knoten zeigt, wodurch eine verknüpfte Liste entsteht.
• Unabhängig davon, ob ein Knoten eingefügt oder gelöscht wird, müssen Sie nur die Ausrichtung des Zeigers ändern, und die zeitliche Komplexität beträgt O (1).
• Die Zeitkomplexität zum Auffinden eines Knotens beträgt O(n), und Sie müssen die Suche der Reihe nach beginnend mit dem Kopfknoten durchführen.
• Bei verknüpften Listen müssen Probleme bei der Speicherplatzzuweisung nicht berücksichtigt werden. Im Allgemeinen wird die dynamische Speicherzuweisung verwendet, um eine flexible Speicherverwaltung zu erreichen.

2. Binärbaum:

• Ein Binärbaum ist eine Baumstruktur, bei der jeder Knoten höchstens zwei untergeordnete Knoten hat.
• Die zeitliche Komplexität der Such-, Einfügungs- und Löschvorgänge des Binärbaums beträgt O(log2n), O(log2n) bzw. O(log2n);
• Da jeder Knoten des Binärbaums nicht kontinuierlich, sondern hierarchisch gespeichert wird und jeder Knoten nur zwei untergeordnete Knoten haben kann, kann der Speicherplatz effizienter genutzt werden.

3. Hash-Tabelle:

• Eine Hash-Tabelle ist eine Datenstruktur, die einen Schlüssel einer Position in einer Tabelle zuordnet, um auf Datensätze zuzugreifen und Suchvorgänge zu beschleunigen.
• Die Suchzeitkomplexität der Hash-Tabelle beträgt O(1) und die Einfüge- und Löschzeitkomplexität beträgt O(n);
• Die Implementierung einer Hash-Tabelle erfordert zusätzlichen Speicherplatz zum Speichern der Hash-Tabelle selbst und das Problem der Hash-Kollisionen muss gelöst werden.

Das zugrunde liegende Prinzip von HashMap

Die unterste Ebene von HashMap wird mithilfe einer Array-verknüpften Liste (Rot-Schwarz-Baum) implementiert. Sie speichert Daten entsprechend dem HashCode-Wert des Schlüssels. Sie kann die Position der Daten im Array (Hash-Konflikt) basierend auf dem Hash berechnen Code und verwendet eine verknüpfte Liste (Rot-Schwarz-Baum), um Konflikte zu speichern. HashMap Wenn in Java 8 die Länge der verknüpften Liste den Schwellenwert überschreitet (Standard ist 8), wird sie in einen rot-schwarzen Baum konvertiert, um die Abfrageeffizienz zu verbessern.Wenn die Kapazität nicht ausreicht, wird sie automatisch erweitert. Der Standardlastfaktor beträgt 0,75 und die Erweiterungsmethode beträgt das Zweifache der Kapazität.

So ermitteln Sie, ob eine verknüpfte Liste einen Zyklus hat

1. Verwenden Sie eine Hash-Tabelle, um jeden Knoten in der verknüpften Liste zu durchlaufen und die Adresse des Knotens in der Hash-Tabelle zu speichern. Wenn der aktuelle Knoten bereits in der Hash-Tabelle vorhanden ist, bedeutet dies, dass die verknüpfte Liste einen Zyklus hat.
2. Definieren Sie zwei Zeiger: Ein langsamer Zeiger bewegt sich jeweils um einen Schritt und ein schneller Zeiger bewegt sich jeweils um zwei Schritte. Wenn der schnelle Zeiger auf den langsamen Zeiger trifft, bedeutet dies, dass die verknüpfte Liste einen Zyklus hat.

Was sind die Nutzungsszenarien von Stapeln und Warteschlangen?

Die Vorwärts- und Rückwärtsfunktionen des Browsers: Die vom Browser besuchten Webseiten können die Vorwärts- und Rückwärtsfunktionen über die Stapeldatenstruktur realisieren.

Wissen Sie etwas über das TCP-Sticky-Problem?

Das TCP-Sticky-Problem bezieht sich auf die Tatsache, dass das TCP-Protokoll die Daten beim Übertragen von Daten nicht fragmentiert, was dazu führt, dass die vom empfangenden Ende empfangene Datenmenge größer ist als die vom sendenden Ende gesendete Datenmenge.

Es gibt folgende Möglichkeiten, das TCP-Sticky-Problem zu lösen:

1. Fügen Sie auf der sendenden Seite ein Trennzeichen hinzu: Nachdem die empfangende Seite das Trennzeichen erhalten hat, kann sie die Daten basierend auf dem Trennzeichen aufteilen.
2. Fügen Sie einen Header auf der sendenden Seite hinzu: Der sendende Teil fügt einen Header hinzu, bevor er die Daten sendet. Der empfangende Teil teilt die Daten basierend auf den Längeninformationen im Header auf.
3. Fügen Sie auf der sendenden Seite einen Puffer hinzu: Vor dem Senden von Daten legt die sendende Seite die Daten zunächst in den Puffer und sendet jedes Mal nur einen Teil der Daten im Puffer. Nach dem Empfang der Daten bestimmt die empfangende Seite, ob sie gesendet werden soll Daten basierend auf der Gesamtlänge der Daten vollständig.

So implementieren Sie ein einfaches TCP mithilfe von UDP

Erstens können UDP-Datagramme dabei helfen, den Drei-Wege-Handshake-Prozess im TCP/IP-Protokoll zu implementieren. Beim ersten Handshake sendet ein Client ein UDP-Datagramm mit einer Handshake-Anfrage. Wenn der Server diese Nachricht empfängt, antwortet er mit einer Bestätigungsnachricht, die angibt, dass der Server die Handshake-Anfrage des Clients erhalten hat und bereit ist, Dienste bereitzustellen. Beim zweiten Handshake sendet der Client erneut ein UDP-Datagramm. Diesmal enthält die Nachricht einige nützliche Informationen, wie z. B. die IP-Adresse des Clients, die Portnummer usw., damit der Server den Client identifizieren kann. Beim dritten Handshake sendet der Server ein UDP-Datagramm, das anzeigt, dass die Verbindung hergestellt wurde und der Client mit dem Senden von Daten beginnen kann.

Zweitens können UDP-Datagramme auch dabei helfen, den Datenübertragungsprozess im TCP/IP-Protokoll zu realisieren. Wenn der Client Daten an den Server senden muss, werden die Daten in ein UDP-Datagramm gekapselt und an den Server gesendet. Nachdem der Server das UDP-Datagramm empfangen hat, analysiert er die in der Nachricht enthaltenen Daten und führt die entsprechende Verarbeitung durch.

Schließlich können UDP-Datagramme auch dabei helfen, den Terminierungsprozess im TCP/IP-Protokoll zu implementieren.Wenn der Client nicht mehr mit dem Server kommunizieren muss, kann er ein UDP-Datagramm senden, um anzuzeigen, dass der Client die Verbindung beendet. Nachdem der Server diese Nachricht erhalten hat, gibt er die entsprechenden Ressourcen frei und vervollständigt so das gesamte TCP/IP-Protokoll . Verbindungsprozess

Haben Sie Coroutinen verwendet? Warum Coroutinen verwenden?Warum Coroutinen schneller sind

Coroutinen ermöglichen es Programmen, zwischen verschiedenen Aufgaben zu wechseln, wodurch die Programmeffizienz verbessert und die Programmlaufzeit verkürzt wird. Coroutinen ermöglichen es einem Programm, zwischen mehreren Aufgaben zu wechseln, anstatt auf den Abschluss einer Aufgabe zu warten, bevor es eine andere startet. Außerdem können Variablen zwischen verschiedenen Threads gemeinsam genutzt werden, wodurch die Laufzeit des Programms verkürzt wird. Bei Multitasking-Anwendungen kann der Einsatz von Coroutinen die Leistung erheblich verbessern, was zu schnelleren Ausführungsgeschwindigkeiten führt.

Ist es schneller, ein Array oder eine verknüpfte Liste gleicher Länge zu durchlaufen? Warum?

Arrays sind schneller, da die Adresse jedes Elements des Arrays kontinuierlich und fest ist und die Adresse des nächsten Elements schnell ermittelt werden kann, während die Adresse jedes Elements der verknüpften Liste diskontinuierlich ist und Sie den Zeiger durchlaufen müssen Um die Adresse des nächsten Elements zu erhalten, ist die Durchquerung des Arrays schneller.

Sprechen wir über virtuelle Funktionen. Warum brauchen wir virtuelle Funktionen?

Eine virtuelle Funktion ist eine spezielle Funktion, die sich von gewöhnlichen Funktionen dadurch unterscheidet, dass sie automatisch vom Compiler definiert wird und zur Kompilierungszeit aufgerufen werden kann. Das Merkmal einer virtuellen Funktion besteht darin, dass ihre Implementierung zur Laufzeit und nicht zur Kompilierungszeit bestimmt wird.
Der Hauptzweck virtueller Funktionen besteht darin, Polymorphismus zu erreichen. Eine abstrakte Klasse kann mehrere virtuelle Funktionen definieren und ihre Unterklassen können diese Funktionen dann implementieren.

Kann der Destruktor eine virtuelle Funktion sein? Muss es eine virtuelle Funktion sein? Warum? Was ist das Problem, wenn es sich nicht um eine virtuelle Funktion handelt?

Es muss keine virtuelle Funktion sein, es wird jedoch im Allgemeinen empfohlen, eine virtuelle Funktion zu verwenden, da eine virtuelle Funktion von einer abgeleiteten Klasse überschrieben werden kann, sodass der Destruktor der abgeleiteten Klasse korrekt ausgeführt werden kann Wird es nicht verwendet, wird der Destruktor der abgeleiteten Klasse nicht aufgerufen, was zu Problemen wie Speicherverlusten führen kann.

Einführung in die Rendering-Pipeline

Die Rendering-Pipeline besteht aus einer Reihe von Schritten, mit denen Spielszenendaten von Eingabeinformationen in auf dem Bildschirm angezeigte Bilder umgewandelt werden.

Der Prozess der Rendering-Pipeline ist in drei Hauptphasen unterteilt: Vorbereitungsphase, Geometriephase und Beleuchtungsphase.

In der Vorbereitungsphase lädt die Spiel-Engine die Modelle und Texturen der Spielszene in die Grafikverarbeitungseinheit (GPU) und organisiert die Daten für die Verwendung in nachfolgenden Phasen.

Während der Geometriephase werden Matrixtransformationen verwendet, um das Modell im dreidimensionalen Raum zu platzieren und das Modell in eine Form umzuwandeln, die von Pixeln auf dem Bildschirm unterstützt werden kann.

In der Beleuchtungsphase werden die Lichtquelle und das Beleuchtungsmodell verwendet, um den Farbwert jedes Pixels zu berechnen, und das resultierende Bild wird schließlich auf dem Bildschirm angezeigt.

Lassen Sie uns über die Einfüge-, Abfrage- und Löschvorgänge binärer Suchbäume sprechen. Wie hoch ist die zeitliche Komplexität?

1. einfügen:

• Zeitkomplexität: O(log n)
• Schritte:

1. Behandeln Sie den einzufügenden Knoten als neuen Blattknoten, beginnend mit dem Wurzelknoten.
2. Wenn der einzufügende Knotenwert kleiner als der aktuelle Knotenwert ist, wechseln Sie zum linken untergeordneten Knoten des aktuellen Knotens.
3. Wenn der einzufügende Knotenwert größer als der aktuelle Knotenwert ist, wechseln Sie zum rechten untergeordneten Knoten des aktuellen Knotens.
4. Wenn der aktuelle Knoten keine untergeordneten Knoten hat, ist der einzufügende Knoten der untergeordnete Knoten des aktuellen Knotens.
5. Andernfalls wiederholen Sie die Schritte 2 bis 4, bis ein Knoten ohne untergeordnete Knoten gefunden wird und der einzufügende Knoten als untergeordneter Knoten dieses Knotens verwendet wird.

Unter welchen Bedingungen erhält der Greedy-Algorithmus die optimale Lösung?

Die Bedingungen dafür, dass der Greedy-Algorithmus die optimale Lösung erhält, sind die „optimale Unterstruktur“ und die „Greedy-Selection-Eigenschaft“:

1. Optimale Unterstruktur: Die optimale Lösung eines Problems enthält die optimalen Lösungen für die Teilprobleme des Problems;
2. Eigenschaft der gierigen Auswahl: Bei jedem Schritt wird eine lokal optimale Auswahl getroffen, und das Endergebnis ist die globale optimale Lösung.