elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: ¿Eres nuevo? ¿Tienes dudas acerca del funcionamiento de la comunidad? Lee las Reglas Generales


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Estructura de datos ordenada y muy grande
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Estructura de datos ordenada y muy grande  (Leído 2,289 veces)
Distorsion

Desconectado Desconectado

Mensajes: 238


15Hz ~ 20Hz


Ver Perfil
Estructura de datos ordenada y muy grande
« en: 14 Febrero 2012, 13:09 pm »

Buenas,

pretendo hacer un 'juego naval' y situar los barcos como puntos en un mapa 2D por coordenadas X,Y.

Asta ahí bien, el problema es que pretendo hacer una estructura de datos que me ordene los barcos por proximidad (para saber
que barcos tiene más a tiro cada uno). Obviamente los barcos se van moviendo y modificando sus posiciones en el mapa.

Si fueran 20 barcos no habría problema, pero se trata de hacer un trabajo de optimización, vamos a suponer que hay un millón
de barcos.

Con este escenario se dan dos problemas:

1- Calcular la proximidad por X,Y. Si fueran números sueltos sería muy fácil, pero por coordenadas? Que función matematica me
   devolvería a que distancia se encuentra una coordenada de otra? El modulo entre dos puntos? En verdad esto es lo de menos
   eso es fácil de buscar, solo lo añado para entrar de lleno en materia y contar con que hay un tiempo de calculo extra.

2- Estructura de datos y metodos de busqueda.

   Había pensado en una busqueda dicotómica, una busqueda rápida (aunque no se yo si con un millón de entradas...).
   Pero para ello necesito una tabla con un millon de posiciones y para modificar la tabla para ordenarla necesito
   desplazar toda la tabla... mucho tiempo.

   Por otra banda para no desplazar los nodos de datos al ordenarlos, había pensado en una lista encadenada,
   pero ahí no puedo hacer busquedas, tengo que ir recorriendo toda la lista asta encontrar donde le toca ir...

Si suponemos que cada 30 segundos la mitad de los barcos se han movido... como lo hago para en
trenta segundos actualizar los datos??

Supongo que es mejor que lo implemente todo en una estructura de datos en memoria y no usar bases de datos, ya que se tardaría
tiempo en llamar funciones de la base de datos, a parte lo que tarde la base de datos en procesarlo, más que las bases de
datos lo pasan por disco, más tiempo aun...

Mejor C para que sea más rapido todo?


Como lo veis? Alguna solución, aportación o consejo?

 >:D


En línea

[Case]


Desconectado Desconectado

Mensajes: 474



Ver Perfil WWW
Re: Estructura de datos ordenada y muy grande
« Respuesta #1 en: 14 Febrero 2012, 20:46 pm »

Pues si tienes la estructura Set, creo que la mayoría de los lenguajes tienen esta estructura, si usas C, puedes hacer una estructura Barco, que tenga las coordenadas, tanto agregar como quitar barcos toma logn, y construir el Set ordenado te tomaría nlogn, imprimirlo siempre te tomara tiempo lineal.


En línea

ghastlyX
Ex-Staff
*
Desconectado Desconectado

Mensajes: 1.900



Ver Perfil
Re: Estructura de datos ordenada y muy grande
« Respuesta #2 en: 14 Febrero 2012, 21:10 pm »

Dependerá de la función distancia que quieras utilizar.

Si he entendido bien, necesitas actualizar las posiciones de los barcos cada 30 segundos y una vez están actualizados, necesitas una función que sea algo como proximos(B, k) que retorne los barcos que estén a distancia menor de k del barco B.

La solución que te plantean sirve para la primera parte perfectamente, pero para la segunda en general no funcionará. Con un set supongo que te refieres a lo que internamente suele ser o bien un árbol AVL o bien un Red-Black Tree.

Esto plantea un problema y es que según la distancia que utilice no puedes contestar la segunda función rápido. Por ejemplo, consideremos la distancia euclidiana estándar. No podemos usar ninguna ordenación de manera que los contiguos a un elemento sean los más próximos a él (según esa distancia) y esto implicaría que habría que mirar todos los barcos para poder contestar, es decir, demasiado lento. Si tomamos como distancia que sólo considere la primera coordenada, entonces funcionaría pero no es que sea una distancia muy normal (y de hecho, no es una distancia en el sentido matemático).

Lo que se me ocurre que te puede ir mejor a simple vista es un Burkhard-Keller Tree (BK-Tree). Cada vez que cambies las posiciones tendrás que construir un nuevo árbol (para un millón de barcos le debería dar tiempo de hacerlo en uno o dos segundos así a ojo, por lo que vas sobrado con 30) y gracias a eso podrás contestar rápido las preguntas de proximidad. Además, sirve para cualquier distancia, siempre que sea una distancia en el sentido matemático:
  • d(a, b) >= 0 y d(a, b) = 0 <=> a = b
  • d(a, b) = d(b, a)
  • d(a, b) <= d(a, c) + d(c, b), para cualquier c
En línea

Distorsion

Desconectado Desconectado

Mensajes: 238


15Hz ~ 20Hz


Ver Perfil
Re: Estructura de datos ordenada y muy grande
« Respuesta #3 en: 15 Febrero 2012, 14:16 pm »

Gracias por las respuestas.

La verdad es que es interesante el ver como manejar datos en grandes cantidades.
Buscando he visto que facebook, twiter y google usan NoSql, bases de datos no relacionales.

 ;D
En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Estructura de datos en NASM y/o MASM
ASM
Rozor 2 4,870 Último mensaje 12 Julio 2011, 22:01 pm
por Иōҳ
[aporte] Estructura de datos
Java
danielo- 1 2,382 Último mensaje 25 Julio 2010, 19:07 pm
por Aeros
Estructura de datos
Programación General
EFEX 1 2,553 Último mensaje 27 Junio 2011, 14:25 pm
por EFEX
Extraer datos con estructura
PHP
Shell Root 2 2,231 Último mensaje 12 Agosto 2011, 13:52 pm
por [u]nsigned
La base de datos de Hackers más grande de internet
Noticias
The_Mushrr00m 0 1,703 Último mensaje 8 Enero 2013, 12:27 pm
por The_Mushrr00m
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines