Esta pregunta en realidad podría ser separada en dos partes:
- ¿Cómo debo gestionar la memoria de datos de matriz plana ?
- ¿Cómo debo acceder a los elementos de una matriz plana?
Yo personalmente prefiero utilizar std :: vector para la gestión de la memoria, excepto en los casos en que necesito para mantener la compatibilidad con el código que no utiliza STL (es decir, cuando interfaz con el código C recta). Es mucho más difícil hacer código de excepción con matrices en bruto asignadas a través de nuevo o malloc (en parte porque es muy fácil olvidar que debe preocuparse por ello). Vea cualquier artículo en RAII por las razones.
En la práctica, std :: vector se implementa como una matriz plana. Como tal, siempre es posible extraer la matriz sin procesar y usar patrones de acceso al estilo C. Normalmente comienzo con la sintaxis del operador del subíndice vectorial. Para algunos compiladores, cuando se produce una versión de depuración, los vectores proporcionan una verificación de límite automática . Esto es lento (a menudo una ralentización de 10 veces para bucles apretados), pero útil para encontrar ciertos tipos de errores.
Si el perfilado en una plataforma en particular indica que el operador [] es un cuello de botella, entonces cambio a acceder directamente a la matriz sin procesar. Curiosamente, según el compilador y el sistema operativo, a veces puede ser más rápido utilizar un vector STL que un conjunto sin formato.
Aquí hay algunos resultados de una aplicación de prueba simple. Se compiló con Visual Studio 2008 en modo de lanzamiento de 32 bits utilizando optimizaciones de/O2 y se ejecutó en Vista x64. Se obtienen resultados similares con una aplicación de prueba de 64 bits.
Binary search...
fill vector (for reference) : 0.27 s
array with ptr math : 0.38 s <-- C-style pointers lose
array with int index : 0.23 s <-- [] on raw array wins
array with ptrdiff_t index : 0.24 s
vector with int index : 0.30 s <-- small penalty for vector abstraction
vector with ptrdiff_t index : 0.30 s
Counting memory (de)allocation...
memset (for reference) : 2.85 s
fill malloc-ed raw array with [] : 2.66 s
fill malloc-ed raw array with ptr : 2.81 s
fill new-ed raw array with [] : 2.64 s
fill new-ed raw array with ptr : 2.65 s
fill vector as array : 3.06 s \ something's slower
fill vector : 3.05 s/with vector!
NOT counting memory (de)allocation...
memset (for reference) : 2.57 s
fill malloc-ed raw array with [] : 2.86 s
fill malloc-ed raw array with ptr : 2.60 s
fill new-ed raw array with [] : 2.63 s
fill new-ed raw array with ptr : 2.78 s
fill vector as array : 2.49 s \ after discounting the
fill vector : 2.54 s/(de)allocation vector is faster!
Código:
#define WINDOWS_LEAN_AND_MEAN
#include <windows.h>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;
__int64 freq; // initialized in main
int const N = 1024*1024*1024/sizeof(int)/2; // 1/2 GB of data
int const nIter = 10;
class Timer {
public:
Timer(char *name) : name(name) {
QueryPerformanceCounter((LARGE_INTEGER*)&start);
}
~Timer() {
__int64 stop;
QueryPerformanceCounter((LARGE_INTEGER*)&stop);
printf(" %36s : % 4.2f s\n", name.c_str(), (stop - start)/double(freq));
}
private:
string const name;
__int64 start;
};
template <typename Container, typename Index>
int binarySearch_indexed(Container sortedArray, Index first, Index last, int key) {
while (first <= last) {
Index mid = (first + last)/2; // NOT safe if (first+last) is too big!
if (key > sortedArray[mid]) first = mid + 1;
else if (key < sortedArray[mid]) last = mid - 1;
else return mid;
}
return 0; // Use "(Index)-1" in real code
}
int Dummy = -1;
int const *binarySearch_ptr(int const *first, int const *last, int key) {
while (first <= last) {
int const *mid = (int const *)(((unsigned __int64)first + (unsigned __int64)last)/2);
if (key > *mid) first = mid + 1;
else if (key < *mid) last = mid - 1;
else return mid;
}
return &Dummy; // no NULL checks: don't do this for real
}
void timeFillWithAlloc() {
printf("Counting memory (de)allocation...\n");
{
Timer tt("memset (for reference)");
int *data = (int*)malloc(N*sizeof(int));
for (int it=0; it<nIter; it++) memset(data, 0, N*sizeof(int));
free(data);
}
{
Timer tt("fill malloc-ed raw array with []");
int *data = (int*)malloc(N*sizeof(int));
for (int it=0; it<nIter; it++) for (size_t i=0; i<N; i++) data[i] = (int)i;
free(data);
}
{
Timer tt("fill malloc-ed raw array with ptr");
int *data = (int*)malloc(N*sizeof(int));
for (int it=0; it<nIter; it++) {
int *d = data;
for (size_t i=0; i<N; i++) *d++ = (int)i;
}
free(data);
}
{
Timer tt("fill new-ed raw array with []");
int *data = new int[N];
for (int it=0; it<nIter; it++) for (size_t i=0; i<N; i++) data[i] = (int)i;
delete [] data;
}
{
Timer tt("fill new-ed raw array with ptr");
int *data = new int[N];
for (int it=0; it<nIter; it++) {
int *d = data;
for (size_t i=0; i<N; i++) *d++ = (int)i;
}
delete [] data;
}
{
Timer tt("fill vector as array");
vector<int> data(N);
for (int it=0; it<nIter; it++) {
int *d = &data[0];
for (size_t i=0; i<N; i++) *d++ = (int)i;
}
}
{
Timer tt("fill vector");
vector<int> data(N);
for (int it=0; it<nIter; it++) for (size_t i=0; i<N; i++) data[i] = (int)i;
}
printf("\n");
}
void timeFillNoAlloc() {
printf("NOT counting memory (de)allocation...\n");
{
int *data = (int*)malloc(N*sizeof(int));
{
Timer tt("memset (for reference)");
for (int it=0; it<nIter; it++) memset(data, 0, N*sizeof(int));
}
free(data);
}
{
int *data = (int*)malloc(N*sizeof(int));
{
Timer tt("fill malloc-ed raw array with []");
for (int it=0; it<nIter; it++) for (size_t i=0; i<N; i++) data[i] = (int)i;
}
free(data);
}
{
int *data = (int*)malloc(N*sizeof(int));
{
Timer tt("fill malloc-ed raw array with ptr");
for (int it=0; it<nIter; it++) {
int *d = data;
for (size_t i=0; i<N; i++) *d++ = (int)i;
}
}
free(data);
}
{
int *data = new int[N];
{
Timer tt("fill new-ed raw array with []");
for (int it=0; it<nIter; it++) for (size_t i=0; i<N; i++) data[i] = (int)i;
}
delete [] data;
}
{
int *data = new int[N];
{
Timer tt("fill new-ed raw array with ptr");
for (int it=0; it<nIter; it++) {
int *d = data;
for (size_t i=0; i<N; i++) *d++ = (int)i;
}
}
delete [] data;
}
{
vector<int> data(N);
{
Timer tt("fill vector as array");
for (int it=0; it<nIter; it++) {
int *d = &data[0];
for (size_t i=0; i<N; i++) *d++ = (int)i;
}
}
}
{
vector<int> data(N);
{
Timer tt("fill vector");
for (int it=0; it<nIter; it++) for (size_t i=0; i<N; i++) data[i] = (int)i;
}
}
printf("\n");
}
void timeBinarySearch() {
printf("Binary search...\n");
vector<int> data(N);
{
Timer tt("fill vector (for reference)");
for (size_t i=0; i<N; i++) data[i] = (int)i;
}
{
Timer tt("array with ptr math");
int sum = 0;
for (int i=-1000000; i<1000000; i++) {
sum += *binarySearch_ptr(&data[0], &data[0]+data.size(), i);
}
}
{
Timer tt("array with int index");
int sum = 0;
for (int i=-1000000; i<1000000; i++) {
sum += data[binarySearch_indexed<int const *, int>(
&data[0], 0, (int)data.size(), -1)];
}
}
{
Timer tt("array with ptrdiff_t index");
int sum = 0;
for (int i=-1000000; i<1000000; i++) {
sum += data[binarySearch_indexed<int const *, ptrdiff_t>(
&data[0], 0, (ptrdiff_t)data.size(), -1)];
}
}
{
Timer tt("vector with int index");
int sum = 0;
for (int i=-1000000; i<1000000; i++) {
sum += data[binarySearch_indexed<vector<int> const &, int>(
data, 0, (int)data.size(), -1)];
}
}
{
Timer tt("vector with ptrdiff_t index");
int sum = 0;
for (int i=-1000000; i<1000000; i++) {
sum += data[binarySearch_indexed<vector<int> const &, ptrdiff_t>(
data, 0, (ptrdiff_t)data.size(), -1)];
}
}
printf("\n");
}
int main(int argc, char **argv)
{
QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
timeBinarySearch();
timeFillWithAlloc();
timeFillNoAlloc();
return 0;
}
También podría usar boost :: array o tr1 :: array. – Anonymous
¿En qué se diferencia la copia de sobrecarga de una matriz? La única situación en la que puedo pensar donde las matrices serían más eficientes es si tuvieras "Foo arr [] = {Foo (...), Foo (...), ...};" –
@Mr Fooz: Sí, tienes razón ... no hay diferencia. Edité mi respuesta. – Naveen