c++ - aprender - solidity español

Preguntas sin ordenar

Question

¿Alguien podría explicar cómo funciona un conjunto desordenado? Tampoco estoy seguro de cómo funciona un conjunto. Mi pregunta principal es cuál es la eficiencia de su función de búsqueda.

Por ejemplo, ¿cuál es el tiempo de ejecución de O grande total de esto?

 vector<int> theFirst;
vector<int> theSecond;
vector<int> theMatch;
theFirst.push_back( -2147483648 );
theFirst.push_back(2);
theFirst.push_back(44);
theSecond.push_back(2);
theSecond.push_back( -2147483648 );
theSecond.push_back( 33 );
//1) Place the contents into a unordered set that is O(m).
//2) O(n) look up so thats O(m + n).
//3) Add them to third structure so that''s O(t)
//4) All together it becomes O(m + n + t)
unordered_set<int> theUnorderedSet(theFirst.begin(), theFirst.end());
for(int i = 0; i < theSecond.size(); i++)
{
if(theUnorderedSet.find(theSecond[i]) != theUnorderedSet.end())
{
theMatch.push_back( theSecond[i] );
cout << theSecond[i];
}
}

Answer 1

Todos los tipos de datos std :: desordenados _ * () utilizan un hash para realizar búsquedas. Mira la documentación de Boost sobre el tema y creo que obtendrás un entendimiento muy rápido.

http://www.boost.org/doc/libs/1_46_1/doc/html/unordered.html

Answer 2

unordered_set y todas las otras estructuras de datos unordered_ usan hashing, como lo menciona @Sean. Hashing implica tiempo constante amortizado para la inserción, y cerca de tiempo constante para la búsqueda. Una función hash básicamente toma información y produce un número a partir de ella. Es una función en el sentido de que la misma entrada debe producir la misma salida. Sin embargo, diferentes entradas pueden dar como resultado el mismo resultado, lo que da como resultado lo que se denomina colisión. Se garantizaría que la búsqueda sea un tiempo constante para una "función hash perfecta", es decir, una sin colisiones. En la práctica, el número de entrada proviene del elemento que almacena en la estructura (digamos su valor, es un tipo primitivo) y lo mapea en una ubicación en una estructura de datos. Por lo tanto, para una tecla dada, la función lo lleva al lugar donde se almacena el elemento sin necesidad de recorridos o búsquedas (ignorando las colisiones aquí por simplicidad), por lo tanto, tiempo constante. Existen diferentes implementaciones de estas estructuras (direccionamiento abierto, encadenamiento, etc.) Ver tabla hash , función hash . También recomiendo la sección 3.7 de The Algorithm Design Manual de Skiena. Ahora, con respecto a la complejidad de la gran O, tienes razón de que tienes O (n) + O (n) + O (tamaño de superposición). Dado que la superposición no puede ser mayor que la menor de myn, la complejidad global puede expresarse como O (kN), donde N es el más grande entre m y n. Pronto). De nuevo, este es el "mejor caso", sin colisiones y con hash perfecto.

set y multi_set por otro lado utilizan árboles binarios, por lo que las inserciones y búsquedas suelen ser O (logN). El rendimiento real de una estructura hash frente a uno de árbol binario dependerá de N, por lo que es mejor probar los dos enfoques y perfilarlos en un escenario de ejecución realista.