Привет ребята.
Пришло ко мне сегодня желание навелосипедить по полной.
Навелосипедил:
struct node_s {
void *value;
struct node_s *children[256];
};
typedef struct node_s node_t;
node_t *
create_node()
{
return calloc(1, sizeof(node_t));
}
node_t *
create_storage()
{
return create_node();
}
int
insert(node_t *root, char *key, void *value)
{
node_t *curr_node = root;
size_t k;
size_t c;
for (k = 0; key[k]; k++) {
c = (size_t) key[k];
if (NULL == curr_node->children[c]) {
curr_node->children[c] = create_node();
}
curr_node = curr_node->children[c];
}
if (NULL != curr_node->value) {
return 0;
}
curr_node->value = value;
return 1;
}
void *
get(node_t *root, char *key)
{
node_t *curr_node = root;
size_t k;
size_t c;
for (k = 0; key[k]; k++) {
c = (size_t) key[k];
if (NULL == curr_node->children[c]) {
return NULL;
}
curr_node = curr_node->children[c];
}
return curr_node->value;
}
...
...
...
node_t *storage = create_storage();
// тут вставили 1113 тестовых элементов
// по строковым ключам разной длины (от 1 до 39 символов),
// каждый из них уникален,
// но большая часть не уникальна по префиксам
insert(storage, "blahblah", "A_LA_POINTER");
// типа ищем
clock_t tic = clock();
size_t i;
for (i = 0; i < 500000; i++) {
get(storage, "blahblah_not_found_key");
}
clock_t toc = clock();
printf("test time : %f\n", (double) (toc - tic) / CLOCKS_PER_SEC);
// ~0.000207Ну, это, конечно, швах. Да хрен с ним. Дело не в этом.
А вот в этом:
Мне нужна какая-то, внешне вот стаким интерфейсом хреновина, контейнер для данных.
Я посмотрел на хеш таблицу, но:
1) Хеш таблица, перед тем как искать, в цикле по строке получает хеш сумму строкового ключа, и только потом ищет по заявленному O(1). У меня же тут сразу во время цикла по строке происходит поиск. Хеширование ключа не требуется.
2) Доступная мне реализация хеш таблицы «искаропки» требует кучу каких-то танцеваний при инициализации. Так ещё и просит указать хотябы примерное количество элементов, которые в ней будут храниться. А я не знаю!!! Поставишь много — пожрёт много. Поставишь мало — в какой-то момент изза перестройки при выделении дополнительного куска памяти для индексов просядет скорость. Опять же у меня в велосипеде, кажется, такой проблемы нет — скорость (наверное) всегда примерно средняя, каллочит почуть и ладно.
Ну, размер выделенной памяти, конечно, ужас. 1.6 метра на 1.1к строчек. Или не ужас?
Нет, не хочу использовать свой велосипед. Он просто получился.
А вы, господа гуру, подскажите-ка немощному страдальщику какой мне контейнер правильно выбрать под свои хотелки?
