¿Qué estructura de datos usar?

necesito una estructura de datos con las siguientes propiedades:¿Qué estructura de datos usar?

El acceso a elementos debe ser muy rápido
elementos, que no se añadió, no debe tener memoria (como el ideal, el tamaño de la estructura vacía cerca de cero)
cada elemento tiene dos coordenadas enteras (x, y) (acceso a elementos solamente por ellos)
recuento Max de elementos conocidos en el momento de la creación (más de 10^3)
Element contiene valores pocos flotador

Sería bueno si también se dirigió a una implementación de esta estructura en C o C++.

2010-10-25 Pavel

¿Es esta una tarea para hacer? –

Elija su idioma. No existe C/C++, y las implementaciones para estos 2 idiomas serían muy diferentes. –

@R ... tu punto es tomado, pero ese argumento está REALMENTE cansado. Me refiero a C/C++ todo el tiempo. ¿Por qué? Porque nuestros paquetes generalmente terminan siendo contenedores de C++ alrededor de los paquetes C. No creo que nadie esté terriblemente ofendido, salvo los puristas de ambos bandos que tienen el lujo de elegir un idioma u otro. –

Compruébalo: puedes modificar el tipo de elemento a float si esto hace todo lo que quieres.

Concise Sparse Matrix Package in C

para C++ se puede utilizar Boost.uBLAS - detalles sparse_matrix here.

Fuente

2010-10-25 14:17:19

¿Está buscando un sparse matrix?

Fuente

2010-10-25 14:11:46

Buen punto. Excepto que, si la observación del OP "más de 10^3" realmente significa "unos pocos miles", recomendaría una matriz simple de 2 d. –

Si su X e Y son relativamente pequeñas, una matriz bidimensional de punteros funcionaría. 10000 punteros serían 40K en código de 32 bits.

Fuente

2010-10-25 14:16:30

Incluso en modo de 64 bits, puede usar índices de 32 bits. –

typdef ElementAccessor std::pair<int, int>; 

struct Element 
{ 
    float f1; 
    float f2; 
    //etc. 

}; 

std::map< ElementAccessor, Element > myElementMap;

Ahora puede utilizar este mapa como una matriz. ElementAccessor se refiere a x, y. Solo asegúrate de ver si el elemento existe en el mapa antes de intentar acceder a él, o si se crea uno por defecto.

http://www.cplusplus.com/reference/std/utility/pair/ http://www.cplusplus.com/reference/stl/map/find/

edición: los soportes de plantilla se están presentando para el mapa. el tipo de clave del mapa es ElementAccessor, el valor es Element. Además, para el par, la creación de plantillas es int, int.

Fuente

2010-10-25 14:18:40

Los accesos a estos elementos son tiempo logarítmico. Entonces, si coloca 1 millón de elementos en el mapa, todavía no se necesitarían muchas operaciones para acceder a sus datos. No es una referencia de matriz de tiempo constante, sino un gran ahorro de espacio. –

marcado fijo. Hay (o solía ser, no revisé) un error irritante en SO que la sangría del código no funciona en la primera línea, de ahí el nbsp. –

@steve ¡gracias! –

Respuesta

Cuestiones relacionadas