Condivisione della tecnologia

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

Che aspetto ha la struttura dei dati ArrayList sottostante?

Il livello inferiore di ArrayList è implementato in base agli array. Lo fa espandendo o riducendo dinamicamente la dimensione dell'array. Quando la capacità non è sufficiente, creerà un array più grande, quindi copierà i dati originali e infine aggiungerà i nuovi dati.

Il meccanismo di espansione dell'ArrayList è: quando viene aggiunto il primo elemento, la capacità di ArrayList è 10 ogni volta che viene aggiunto un nuovo elemento, se la capacità viene superata, la capacità originale verrà raddoppiata, ovvero la capacità originale * 2; , se la capacità originale è 0, la nuova capacità è 1.

Vantaggi e svantaggi del meccanismo di espansione ArrayList:

vantaggio:

1. Il meccanismo di espansione di ArrayList è semplice da comprendere e facile da implementare.
2. La capacità espansa deve essere maggiore della capacità originale, il che può ridurre il numero di copie dell'array quando si aggiungono nuovi elementi e migliorare l'efficienza dell'aggiunta di elementi.

discordanza:

1. Il meccanismo di espansione dell'ArrayList porta ad uno spreco di memoria e può facilmente causare uno spreco di spazio di memoria.
2. Quando la capacità è elevata, ogni espansione richiede una grande quantità di risorse di memoria e CPU, che influiranno sulle prestazioni. Pertanto, quando si utilizza ArrayList, la capacità iniziale deve essere impostata in modo appropriato.

ArrayList non è thread-safe

L'implementazione interna di ArrayList è basata su array. Quando più thread accedono allo stesso ArrayList contemporaneamente, può verificarsi un'incoerenza dei dati, ad esempio quando un thread legge i dati di ArrayList e un altro thread aggiunge/elimina dati nell'ArrayList, potrebbero esserci modifiche ai dati nell'ArrayList, in modo che il thread che legge i dati dell'ArrayList possa leggere dati errati, causando un errore del programma.

I metodi comuni per risolvere l'insicurezza del thread ArrayList includono:

1. Usa Vector invece di ArrayList: Vector è sincronizzato e tutti i metodi vengono modificati da sincronizzato, quindi è thread-safe;
2. Avvolgi ArrayList nella sicurezza del thread: utilizza il metodo Collections.synchronizedList(list) per convertire ArrayList nella sicurezza del thread;
3. Utilizza CopyOnWriteArrayList: è una raccolta thread-safe ed efficiente. La sua operazione di scrittura viene implementata copiando l'array sottostante. Il costo di questa implementazione rientra in un intervallo accettabile. È adatta a scenari simultanei con più letture e meno scritture.
4. Utilizzare i blocchi per ottenere la sicurezza del thread: è possibile utilizzare meccanismi di blocco come ReentrantLock per implementare un ArrayList thread-safe.

La differenza tra stack e heap

• Lo stack è una speciale tabella lineare la cui caratteristica è che i dati possono essere inseriti e cancellati solo ad un'estremità, secondo il principio first-in, last-out, last-in-first-out. È una struttura di archiviazione che può essere utilizzata per memorizzare valori di parametri di funzione, variabili locali, ecc.

• Un heap è una struttura ad albero speciale caratterizzata dal fatto che i valori di tutti i nodi sono maggiori o uguali ai valori dei rispettivi nodi figli e il valore del nodo radice è il più grande o il più piccolo. L'heap è una struttura di archiviazione dinamica che può essere utilizzata per archiviare grandi quantità di dati, ad esempio per l'ordinamento, la ricerca, ecc.

Strato inferiore di coroutine

L'essenza di una coroutine è un thread leggero. Ogni coroutine ha uno stack per memorizzare le funzioni e i relativi parametri, variabili locali, ecc. La coroutine può essere sospesa, ripresa e cambiata. Ecco come implementare una coroutine.

Principio C# GC (garbage collection).

1. Conteggio dei riferimenti: quando viene fatto riferimento a un oggetto, il relativo conteggio dei riferimenti viene aumentato di 1. Quando il riferimento diventa non valido, il relativo conteggio dei riferimenti viene diminuito di 1. Se il conteggio dei riferimenti di un oggetto diventa 0, l'oggetto verrà recuperato dal Garbage Collector.
2. Mark-and-clear: quando il Garbage Collector è in esecuzione, attraversa gli oggetti in base alle relazioni di riferimento, contrassegna gli oggetti accessibili come "vivi", contrassegna gli oggetti inaccessibili come "morti" e quindi cancella tutti gli oggetti contrassegnati come "morti".
3. Algoritmo di copia: il garbage collector divide la memoria disponibile in due blocchi e utilizza solo un blocco alla volta. Quando lo spazio è insufficiente, gli oggetti sopravvissuti vengono copiati in un altro blocco di spazio, quindi gli oggetti copiati vengono cancellati dall'originale. spazio.
4. Algoritmo di complemento del contrassegno: quando il Garbage Collector è in esecuzione, contrassegnerà prima tutti gli oggetti sopravvissuti, quindi sposterà tutti gli oggetti sopravvissuti a un'estremità per eliminare i frammenti di spazio inutilizzati.

La differenza tra la sincronizzazione dello stato e la sincronizzazione dei frame

Sincronizzazione degli stati Si riferisce alla trasmissione dello stato (come posizione, velocità, accelerazione, ecc.) di ciascuna macchina nel sistema multi-macchina ad altre macchine in ciascun ciclo di controllo, in modo che ciascuna macchina rimanga sincronizzata. La sincronizzazione degli stati può ottenere prestazioni in tempo reale del controllo collaborativo di più macchine, ma poiché è necessario trasmettere una grande quantità di dati in ciascun ciclo di controllo, la sua precisione potrebbe essere relativamente bassa.

Sincronizzazione dei fotogrammi Ciò significa che in ogni ciclo di controllo, i comandi di controllo di ciascuna macchina nel sistema multi-macchina vengono trasmessi ad altre macchine in modo che ciascuna macchina rimanga sincronizzata. La sincronizzazione dei frame può raggiungere la precisione del controllo collaborativo su più macchine, ma poiché in ciascun ciclo di controllo viene trasmesso solo un numero limitato di comandi di controllo, le sue prestazioni in tempo reale potrebbero essere relativamente basse.

Modelli di progettazione comuni

Modello Singleton

Modello di fabbrica

Modello composito

Modello proxy

Caratteristiche di elenchi concatenati, alberi binari e tabelle hash

1. Elenco collegato:

• Si tratta di una struttura di lista lineare, caratterizzata dal fatto che ogni nodo ha un puntatore che punta al nodo successivo, formando così una lista concatenata;
• Indipendentemente dall'inserimento o dall'eliminazione di un nodo, è sufficiente modificare solo il puntamento del puntatore e la complessità temporale è O(1);
• La complessità temporale per trovare un nodo è O(n), ed è necessario cercare in ordine partendo dal nodo testa;
• Gli elenchi collegati non devono considerare i problemi di allocazione dello spazio In genere, l'allocazione dinamica della memoria viene utilizzata per ottenere una gestione flessibile della memoria.

2. Albero binario:

• Un albero binario è una struttura ad albero in cui ciascun nodo ha al massimo due figli;
• La complessità temporale delle operazioni di ricerca, inserimento e cancellazione dell'albero binario è rispettivamente O(log2n), O(log2n) e O(log2n);
• Poiché ogni nodo dell'albero binario non viene memorizzato in modo continuo, ma gerarchicamente, e ogni nodo può avere solo due figli, lo spazio di archiviazione può essere utilizzato in modo più efficiente.

3. Tabella hash:

• Una tabella hash è una struttura dati che mappa una chiave in una posizione in una tabella per accedere ai record e velocizzare le ricerche;
• La complessità del tempo di ricerca della tabella hash è O(1) e la complessità del tempo di inserimento e cancellazione è O(n);
• L'implementazione di una tabella hash richiede spazio aggiuntivo per memorizzare la tabella hash stessa e deve essere risolto il problema delle collisioni degli hash.

Il principio alla base di HashMap

Il livello inferiore di HashMap è implementato utilizzando un elenco collegato di array (albero rosso-nero). Memorizza i dati in base al valore hashCode della chiave. Può calcolare la posizione dei dati nell'array (conflitto hash) in base all'hash codice e utilizza un elenco collegato (albero rosso-nero) per memorizzare i conflitti. HashMap In Java 8, quando la lunghezza dell'elenco collegato supera la soglia (il valore predefinito è 8), verrà convertito in un albero rosso-nero per migliorare l'efficienza delle query.Quando la capacità non è sufficiente, si espanderà automaticamente. Il fattore di carico predefinito è 0,75 e il metodo di espansione è 2 volte la capacità.

Come determinare se un elenco collegato ha un ciclo

1. Utilizzare una tabella hash per attraversare ciascun nodo nell'elenco collegato e memorizzare l'indirizzo del nodo nella tabella hash Se il nodo corrente esiste già nella tabella hash, significa che l'elenco collegato ha un ciclo;
2. Definisci due puntatori, un puntatore lento si muove un passo alla volta e un puntatore veloce si muove due passi alla volta. Se il puntatore veloce incontra il puntatore lento, significa che l'elenco collegato ha un ciclo.

Quali sono gli scenari di utilizzo di stack e code?

Le funzioni avanti e indietro del browser: le pagine web visitate dal browser possono realizzare le funzioni avanti e indietro attraverso la struttura dei dati dello stack.

Sai qualcosa sul problema del tcp sticky?

Il problema del TCP sticky si riferisce al fatto che il protocollo TCP non frammenta i dati durante la trasmissione dei dati, facendo sì che la quantità di dati ricevuti dal lato ricevente sia maggiore della quantità di dati inviati dal lato mittente.

I modi per risolvere il problema persistente del TCP sono:

1. Aggiungi un delimitatore all'estremità di invio: aggiungi un delimitatore all'estremità di invio Dopo che l'estremità ricevente riceve il delimitatore, può dividere i dati in base al delimitatore.
2. Aggiungi un'intestazione all'estremità di invio: l'estremità di invio aggiunge un'intestazione prima di inviare i dati. L'intestazione contiene le informazioni sulla lunghezza dei dati correnti. L'estremità di ricezione divide i dati in base alle informazioni sulla lunghezza nell'intestazione.
3. Aggiungi un buffer all'estremità di invio: prima di inviare i dati, l'estremità di invio inserisce i dati nel buffer e ogni volta invia solo una parte dei dati nel buffer. Dopo aver ricevuto i dati, l'estremità di ricezione determina se inviare il file dati in base alla lunghezza totale dei dati completati.

Come implementare un semplice TCP utilizzando UDP

Innanzitutto, i datagrammi UDP possono aiutare a implementare il processo di handshake a tre vie nel protocollo TCP/IP. Nel primo handshake, un client invia un datagramma UDP contenente una richiesta di handshake. Quando il server riceve questo messaggio, risponderà con un messaggio di conferma, indicando che il server ha ricevuto la richiesta di handshake del client ed è pronto a fornire servizi. Nel secondo handshake, il client invierà nuovamente un datagramma UDP. Questa volta il messaggio contiene alcune informazioni utili, come l'indirizzo IP del client, il numero di porta, ecc., in modo che il server possa identificare il client. Nel terzo handshake, il server invierà un datagramma UDP indicando che la connessione è stata stabilita e il client può iniziare a inviare dati.

In secondo luogo, i datagrammi UDP possono anche aiutare a realizzare il processo di trasmissione dei dati nel protocollo TCP/IP. Quando il client deve inviare dati al server, i dati verranno incapsulati in un datagramma UDP e inviati al server dopo che il server ha ricevuto il datagramma UDP, analizzerà i dati contenuti nel messaggio ed eseguirà la relativa elaborazione;

Infine, i datagrammi UDP possono anche aiutare a implementare il processo di terminazione nel protocollo TCP/IP.Quando il client non ha più bisogno di comunicare con il server, può inviare un datagramma UDP per indicare che il client sta terminando la connessione. Dopo che il server ha ricevuto questo messaggio, rilascerà le risorse corrispondenti, completando così l'intero protocollo TCP/IP processo di connessione

Hai usato le coroutine? Perché usare le coroutine?Perché le coroutine sono più veloci

Le coroutine consentono ai programmi di passare da un compito all'altro, migliorando così l'efficienza del programma e riducendone il tempo di esecuzione. Le coroutine consentono a un programma di passare da un'attività all'altra invece di attendere il completamento di un'attività prima di avviarne un'altra. Può anche condividere variabili tra thread diversi, riducendo così il tempo di esecuzione del programma. Per le applicazioni multitasking, l'utilizzo delle coroutine può migliorare significativamente le prestazioni, con conseguente velocità di esecuzione più elevata.

È più veloce attraversare un array o un elenco collegato della stessa lunghezza? Perché?

Gli array sono più veloci, perché l'indirizzo di ciascun elemento dell'array è continuo e fisso e l'indirizzo dell'elemento successivo può essere ottenuto rapidamente, mentre l'indirizzo di ciascun elemento della lista concatenata è discontinuo ed è necessario attraversare il puntatore per ottenere l'indirizzo dell'elemento successivo, quindi l'array Traversing è più veloce.

Parliamo di funzioni virtuali. Perché abbiamo bisogno di funzioni virtuali?

Una funzione virtuale è una funzione speciale che differisce dalle funzioni ordinarie in quanto viene definita automaticamente dal compilatore e può essere chiamata in fase di compilazione. La caratteristica di una funzione virtuale è che la sua implementazione è determinata in fase di esecuzione, non in fase di compilazione.
Lo scopo principale delle funzioni virtuali è ottenere il polimorfismo. Una classe astratta può definire più funzioni virtuali e quindi le sue sottoclassi possono implementare queste funzioni.

Il distruttore può essere una funzione virtuale? Deve essere una funzione virtuale? Perché? Qual è il problema se non è una funzione virtuale?

Non deve essere necessariamente una funzione virtuale, ma in genere è consigliabile utilizzare una funzione virtuale, poiché una funzione virtuale può essere sovrascritta da una classe derivata, in modo che il distruttore della classe derivata possa essere eseguito correttamente se si tratta di una funzione virtuale non viene utilizzato, il distruttore della classe derivata non verrà chiamato, il che potrebbe causare problemi come perdite di memoria.

Presentazione della pipeline di rendering

La pipeline di rendering è una serie di passaggi utilizzati per convertire i dati della scena di gioco dalle informazioni di input alle immagini visualizzate sullo schermo.

Il processo della pipeline di rendering è suddiviso in tre fasi principali: fase di preparazione, fase di geometria e fase di illuminazione.

Nella fase di preparazione, il motore di gioco carica i modelli e le texture della scena di gioco nell'unità di elaborazione grafica (GPU) e organizza i dati per l'utilizzo nelle fasi successive.

Durante la fase geometrica, vengono utilizzate trasformazioni di matrice per posizionare il modello nello spazio tridimensionale e convertire il modello in una forma che può essere supportata dai pixel sullo schermo.

Nella fase di illuminazione, la sorgente luminosa e il modello di illuminazione vengono utilizzati per calcolare il valore del colore di ciascun pixel e l'immagine risultante viene infine visualizzata sullo schermo.

Parliamo delle operazioni di inserimento, interrogazione ed eliminazione degli alberi binari di ricerca e qual è la complessità temporale?

1. inserire:

• Complessità temporale: O(log n)
• Passaggi:

1. Trattare il nodo da inserire come un nuovo nodo foglia, a partire dal nodo radice;
2. Se il valore del nodo da inserire è inferiore al valore del nodo corrente, vai al nodo figlio sinistro del nodo corrente;
3. Se il valore del nodo da inserire è maggiore del valore del nodo corrente, vai al nodo figlio destro del nodo corrente;
4. Se il nodo corrente non ha nodi figli, il nodo da inserire sarà il nodo figlio del nodo corrente;
5. Altrimenti, ripetere i passaggi da 2 a 4 finché non viene trovato un nodo senza nodi figli e il nodo da inserire viene utilizzato come nodo figlio di questo nodo.

Quali sono le condizioni affinché l’algoritmo greedy ottenga la soluzione ottima?

Le condizioni affinché l'algoritmo greedy ottenga la soluzione ottima sono la "sottostruttura ottimale" e la "proprietà di selezione greedy":

1. Sottostruttura ottimale: la soluzione ottima a un problema contiene le soluzioni ottime ai sottoproblemi del problema;
2. Proprietà della selezione greedy: ad ogni passo viene effettuata una scelta ottima locale e il risultato finale è la soluzione ottima globale.