Vitalik pubblica un nuovo articolo "Memory access is O(N^[1/3])": analisi della complessità dell’accesso alla memoria e dell’efficienza dei sistemi blockchain

Il 5 ottobre, Vitalik ha pubblicato un nuovo articolo intitolato "Memory access is O(N^(1/3))" in cui esplora la complessità dell'accesso alla memoria, discutendo il problema della complessità dell’“accesso alla memoria” nelle strutture dati e negli algoritmi, e suggerendo che, in alcune architetture o modelli, il costo di accesso alla memoria potrebbe avere un limite superiore di O(N^(1/3)). Ha sottolineato che la complessità temporale degli algoritmi di ordinamento classici è O(N log N), ma quando si considera il collo di bottiglia dell’accesso alla memoria, è necessario riconsiderare l’analisi dell’efficienza per dataset di grandi dimensioni. Questo argomento è di particolare ispirazione per la progettazione dei sistemi di base della blockchain, soprattutto nella gestione di stati su larga scala, sincronizzazione dei nodi e meccanismi di disponibilità dei dati (DA / campionamento della disponibilità dei dati, ecc.), dove è necessario prestare maggiore attenzione ai colli di bottiglia dell’efficienza di “lettura e scrittura della memoria”.