Оптимизация. Списки и последовательный доступ
Страница 2.

Что же тут неправильного? Ничего. Все сделано, вроде бы, достаточно логично. Тем не менее, показательно сделать несколько запусков и полюбоваться результатами (для измерения затраченного времени буду использовать команду bash time):
 
alk:~$ g++ -O5 t1.cpp -o t1
alk:~$ time t1
Iterations: 7485181
 
real 0m0.559s
user 0m0.549s
sys 0m0.001s
alk:~$ time t1
Iterations: 7485586
 
real 0m0.556s
user 0m0.555s
sys 0m0.001s
alk:~$ time t1
Iterations: 7486098
 
real 0m0.558s
user 0m0.549s
sys 0m0.001s
alk:~$ time t1
Iterations: 7480581
 
real 0m0.556s
user 0m0.548s
sys 0m0.000s
 
На самом деле, единственное что можно поставить в упрек написанной выше программе, это расход на каждый элемент (целое число) два раза больше оперативной памяти, чем надо --- еще столько же тратится на указатель для организации списка. Несложно придумать реализацию подобного списка на массиве, когда указатели не нужны:
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
struct hash_item
{
int* keys;
size_t alloc;
size_t used;
};
 
#define HASH_TABLE_SIZE 511
#define HASH_ALLOC_DELTA 16
 
hash_item hash[HASH_TABLE_SIZE];
 
#define COUNT 1000000
 
struct {
unsigned int iterations;
} stat;
 
int main()
{
unsigned int i, j;
 
int k;
hash_item* ptr;
 
bzero((char*)hash, sizeof(hash));
bzero((char*)&stat, sizeof(stat));
 
srandom(time(NULL));
 
for(i = 0; i < COUNT; i++)
{
 
k = random() & 8191;
 
ptr = hash + (k%HASH_TABLE_SIZE);
 
for(j = 0; j < ptr->used && ptr->keys[j] != k;
j++, stat.iterations++)
;
 
if(j >= ptr->used)
{
 
if(ptr->used == ptr->alloc)
{
int* temp = ptr->keys;
 
ptr->keys = (int*)calloc(ptr->alloc += HASH_ALLOC_DELTA,
sizeof(int));
if(ptr->used)
{
memcpy(ptr->keys, temp, ptr->used*sizeof(int));
free(temp);
}
}
 
ptr->keys[ptr->used++] = k;
}
}
 
printf("Iterations: %u\n", stat.iterations);
}