Herramientas de usuario

Herramientas del sitio


algoritmos-oia:problemas-con-queries:offline-vs-online

¡Esta es una revisión vieja del documento!


Qué son las queries

Las queries son preguntas que hay que resolver. Un problema con muchas queries, requiere, dada una situación fijada generalmente, hallar un respuesta que concierne a una parte de ese escenario. Por ejemplo, dado un conjunto de números, una query puede consistir en preguntar cuántos números de un número dado hay. O un poco más difícil, dado un conjunto de intervalos, una query puede consistir en dado un número averiguar cuántos intervalos del conjunto lo contienen.

Ejemplos de problemas:

PROBLEMAS

Con las queries, hay que tener cuidado con cuántas hay. Si hay muchas queries (del orden de $10^5 van a ser en general, más no porque hay que leer cada una), y las queries consisten de varios números, o palabras, hay que tener mucho cuidado con el método de input/output utilizado. Habrá que usar el método más rápido posible para que esto no sea un problema. FIXME link a i/o

Una vez leídas las queries, hay que responderlas. Para esto, hay distintos problemas que requieren distintos métodos.

Queries offline

Son queries, que pueden responderse al final, todas juntas. Esto es en general en un escenario que no va cambiando con el tiempo (es decir con el avance de las queries). Si es el escenario está siempre fijo, no importa cuándo nos den una query, ni cuándo la respondamos, la respuesta siempre será la misma. Aprovechando esto, podremos por ejemplo, al recibir todas las queries, ordenarlas, y en base a eso elaborar un algoritmo eficiente que resuelva el problema con las queries ordenadas. Un algoritmo conocido para estos casos es el algoritmo de Mo. FIXME link

El problema de arriba de ......... por ejemplo, puede resolverse con este algoritmo. Veámoslo.

CODIGO

Queries online

Hay problemas, en cambio, que pueden hacer variar nuestro escenario con las queries. Por ejemplo, puede haber dos tipos de query, uno que nos pida una respuesta a alguna pregunta, y otra que modifique algo, por ejemplo que agregue un número a un conjunto, o lo elimine. En estos casos, tendremos que resolver el problema con algo más elaborado que ordenando las queries al final, ya que la respuesta dependerá de en qué momento se efectuó cada query.

Estructuras que pueden resultar útiles para este tipo de problemas son FIXME linkssss!

Por ejemplo, en el problema de .......... de arriba:

Solución Código

algoritmos-oia/problemas-con-queries/offline-vs-online.1525416677.txt.gz · Última modificación: 2018/05/04 06:51 por sebach