[ Algoritmo de ejemplo 1 ]: tengo una matriz de estructuras ( PaymentReceipt[] paymentReceiptList;) e imagino que hay alrededor de 1000 elementos empujados y el tamaño de la matriz sigue aumentando. Cada elemento tiene un valor time_start y time_end. Dentro de la función de mi contrato, tengo que iterar todos esos miembros para verificar si dos intervalos se superponen entre un conjunto dado de intervalos , que es O (n) tiempo.
[ Algoritmo de ejemplo 2 ]: uso una función de algoritmo para calcular el número n de Fibonacci para encontrar el valor 1000. Esta es una función recursiva para calcular el n-ésimo número de Fibonacci y tiene un tiempo O(log(n)).
Para Algorithm_1 , con un conjunto pequeño, y para Algorithm_2 si el valor n-ésimo es pequeño, no debería haber problema. Pero el gran tamaño de la matriz en Algorithm_1 y el gran valor de n en Algorithm_2 , me pueden enfrentar con un problema de gas ineficiente. No estaba seguro si ambos algoritmos consumirán una gran cantidad de gas o no según lo dado n. Quiero averiguar cuál es el más alto nque puedo usar para ambos algoritmos en función de la cantidad de gas dada.
[P] ¿Se recomienda hacer algoritmos de tiempo O(n) y O(log(n)) dentro de la función de un contrato? En caso afirmativo, ¿hay alguna forma de estimar el gas requerido como algún tipo de función basada en lo dado npara el cada algoritmo?
=> Relacionado con la pregunta anterior; ¿Cambia el gas usado para cada algoritmo en la misma proporción con el tiempo O()?
Por ejemplo: Para el Algoritmo_1 : ¿Podemos decir que el gas usado tendrá la misma relación con el tiempo O(n)?
O((n=10)) usedGas=10
O((n=100)) usedGas=100
O((n=1000)) usedGas=1000
Para Algorithm_2 : ¿o podemos decir que el gas usado tendrá la misma relación con el tiempo O (log (n)).
O(log(n=10)) usedGas=10
O(log(n=100)) usedGas=20
O(log(n=1000)) usedGas=30
Gracias por su valioso tiempo y ayuda.
Algoritmo 1: debe implementarlo para que cuando se agregue un intervalo, se verifique inmediatamente si se superpone con los existentes. A continuación, guarda el resultado de esta verificación en el almacenamiento. No es fácil porque eso significaría mantener 1 o 2 listas ordenadas. Esto podría convertirse en O (log n) y, por lo tanto, debería ser posible sin explotar el gas.
Algo 2: el cálculo que vinculaste me parece O(n) debido al for (int i=2;i<n;i++)bucle. Por otro lado, parece que la gente tiene cálculos O(1) para Fibonacci: https://stackoverflow.com/questions/6037472/can-a-fibonacci-function-be-write-to-execute-in-o1- hora
No debe hacer ningún cálculo O(n) o, si lo hace, distribuirlos en varias transacciones. La forma de hacerlo es verificar si hay gas restante y guardar el estado intermedio si se agota.
O (log n) está bien.
Los cálculos de gas también dependerán de si tienes if then elsedentro del circuito. Estas declaraciones de bifurcación influirán en el costo del gas de cada ejecución del ciclo. Así que no veo un hermoso cálculo de gas antes de que realmente lo intentes...
alper
if then else. ¿Debo verificar el gas restante en el tiempo de ejecución del código? ¿A qué te refieres con estado intermedio? @Xavier Leprêtre B9lab. PD: actualicé el enlace para Algoritm_2 con O (log (n))Xavier Leprêtre B9lab