Often you can get optimal performance with unusual combinations of
operations by combining data structures. Here you can get O(1) for all
operations by combining a hash table and a bag of pointers in an
array. The hash table references bag elements by index, and the bag
elements point back at hash table entries. Random lookups occur in
the bag array. Here is a quick C toy to show what I mean. There are
other possible implementations.
#include <stdio.h>
#include <stdlib.h>
typedef struct key_pair_s {
struct key_pair_s *next;
unsigned value, bag_index;
} KEY_PAIR;
typedef struct table_s {
KEY_PAIR *buckets[1007], *bag[10000];
unsigned size;
} TABLE;
#define ARRAY_SIZE(A) (sizeof A/sizeof *A)
void init_table(TABLE *table)
{
unsigned i;
for (i = 0; i < ARRAY_SIZE(table->buckets); i++)
table->buckets[i] = NULL;
table->size = 0;
}
unsigned hash(unsigned key)
{
return key % ARRAY_SIZE(((TABLE*)42)->buckets);
}
int Remove(TABLE *table, int value)
{
KEY_PAIR *p, *q;
unsigned h = hash(value);
for (q = NULL, p = table->buckets[h]; p; q = p, p = p->next)
if (p->value == value) {
if (q)
q->next = p->next;
else
table->buckets[h] = p->next;
// Move last element into hole in bag. Update hash table.
q = table->bag[--table->size];
table->bag[p->bag_index] = q;
q->bag_index = p->bag_index;
free(p);
return 1;
}
return 0;
}
void Insert(TABLE *table, int value)
{
// Put a new key pair in the hash table.
KEY_PAIR *p = malloc(sizeof *p);
unsigned h = hash(value);
p->next = table->buckets[h];
table->buckets[h] = p;
p->value = value;
// Allocate a new bag element for this pair.
p->bag_index = table->size++;
table->bag[p->bag_index] = p;
}
#define N_RAND (RAND_MAX + 1)
unsigned unbiased_rand(unsigned n)
{
unsigned r, m = N_RAND - N_RAND % n;
do r = rand(); while (r >= m);
return r % n;
}
void GetRandomElement(TABLE *table, unsigned *value)
{
if (table->size > 0)
*value = table->bag[unbiased_rand(table->size)]->value;
}
void Print(TABLE *table)
{
unsigned i;
printf("table:");
for (i = 0; i < table->size; i++)
printf(" %u", table->bag[i]->value);
printf("\n");
}
int main(void)
{
TABLE table[1];
unsigned i, values[10];
char cmd;
init_table(table);
for (i = 0; i < ARRAY_SIZE(values); i++) {
values[i] = rand();
Insert(table, values[i]);
}
for (;;) {
Print(table);
printf("cmd [arg]> ");
scanf(" %c", &cmd);
switch(cmd) {
case 'i':
scanf("%u", &i);
Insert(table, i);
printf("Inserted %u\n", i);
break;
case 'r':
scanf("%u", &i);
if (Remove(table, i))
printf("Removed %u\n", i);
else
printf("Couldn't find %u\n", i);
break;
case 'g':
i = 0;
GetRandomElement(table, &i);
printf("Random element: %u\n", i);
break;
case 'q':
return 0;
default:
printf("Unknown command\n");
break;
}
}
}
On Nov 2, 4:52 pm, shady <sinv...@gmail.com> wrote:
> does anyone knows how much is the complexity of operations erase and
> pop_back in case of Vector(STL)
> what would you choose :
>
> Design a data structure where the following 3 functions are optimised:
>
> 1. Insert(n)
> 2. GetRandomElement()
> 3. Remove(n)
>
> Write a class, and implement the functions. Give complexity of each of these
>
> what would you choose, insertion can always be done in O(1), but what about
> getrandomelement().... if we use simple arrays than for those
>
> 1. -> O(1)
>
> 2. -> O(1)
>
> 3. -> O(n)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
