Vitalik opublikował nowy artykuł „Memory access is O(N^[1/3])”: analiza złożoności dostępu do pamięci i efektywności systemów blockchain

5 października, Vitalik opublikował nowy artykuł „Memory access is O(N^(1/3))”, w którym analizuje złożoność dostępu do pamięci, omawiając problem złożoności „dostępu do pamięci” w strukturach danych i algorytmach. Zasugerował, że w niektórych architekturach lub modelach koszt dostępu do pamięci może mieć górną granicę O(N^(1/3)). Zwrócił uwagę, że klasyczna złożoność czasowa algorytmów sortowania wynosi O(N log N), jednak przy uwzględnieniu wąskich gardeł związanych z dostępem do pamięci konieczna jest ponowna analiza efektywności dla dużych zbiorów danych. Temat ten ma istotne znaczenie dla projektowania systemów bazowych blockchain, zwłaszcza przy obsłudze dużych stanów, synchronizacji węzłów oraz mechanizmów dostępności danych (DA / losowe próbkowanie dostępności danych), gdzie należy szczególnie ostrożnie rozważać wąskie gardła efektywności związane z „odczytem i zapisem pamięci”.