new literal initialize initial create cpp array performance

literal - inicializando una matriz de n elementos usando O(1) performance?



load array c (7)

Creo que es solo una simple pregunta de sintaxis. En C ++ puedes hacer esto:

int foo[1000] = {0};

Todos los valores en el conjunto ahora son 0

Si bien parece que está hecho en tiempo constante, sigue siendo O (n)

alguien tiene una idea de cómo puedo hacer eso?

Gracias

En realidad, es posible, pero solo con ayuda de hardware. En el software, deberá realizar una serie de pasos proporcionales a n , por lo tanto, es O(n) ; en hardware, sin embargo, puede cablear cosas para que todos los elementos de la matriz se configuren en paralelo.

Esto es de hecho una compensación de tiempo / espacio; mientras que antes uno necesitaba O(n) tiempo, ahora uno necesita O(n) elementos del circuito pero puede hacer la operación en O(1) tiempo.

Y en realidad es algo común de hacer. Una gran cantidad de hardware tiene una entrada de reinicio que, cuando se establece, establece todo el hardware a un estado conocido. Esto puede implicar, por ejemplo, poner a cero toda la memoria.

No. Es físicamente imposible. Sin embargo, puede usar instrucciones vectoriales para convertirlo en O (n * 1 / k) tiempo, donde k es el ancho de una instrucción de vector setter. Eso sigue siendo O (n), pero la constante se reduce.

Si quiere decir "inicializar una matriz densa de N elementos en un tiempo independiente de N", entonces es físicamente imposible. Una matriz densa tiene un espacio de almacenamiento que crece linealmente con la cantidad de elementos, y tomará una cantidad de tiempo lineal inicializar este espacio.

Puede tener una inicialización de tiempo constante usando una matriz dispersa. Eso es esencialmente una matriz asociativa (o hashmap, o diccionario, o tabla, dependiendo del idioma) que inicializa los elementos cuando se accede por primera vez.

Si necesita hacer algo para cada elemento de un conjunto de n elementos, no puede hacerlo con un rendimiento superior a O ( n ).

Puede hacerlo en O (1), si calcula el tiempo de ejecución con un Análisis Amortizado sobre todas las acciones de lectura futuras. Solo tiene que inicializar su elemento bajo demanda (la primera vez que se lee).