Привет ребята.

Пришло ко мне сегодня желание навелосипедить по полной.

Навелосипедил:

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

И ещё я посчитал сколько места такая неэффективная страхолюдина занимает для всех этих индексов: 1697228 байт.

Ну, это, конечно, швах. Да хрен с ним. Дело не в этом.

А вот в этом:

Мне нужна какая-то, внешне вот стаким интерфейсом хреновина, контейнер для данных.

Я посмотрел на хеш таблицу, но:

1) Хеш таблица, перед тем как искать, в цикле по строке получает хеш сумму строкового ключа, и только потом ищет по заявленному O(1). У меня же тут сразу во время цикла по строке происходит поиск. Хеширование ключа не требуется.

2) Доступная мне реализация хеш таблицы «искаропки» требует кучу каких-то танцеваний при инициализации. Так ещё и просит указать хотябы примерное количество элементов, которые в ней будут храниться. А я не знаю!!! Поставишь много — пожрёт много. Поставишь мало — в какой-то момент изза перестройки при выделении дополнительного куска памяти для индексов просядет скорость. Опять же у меня в велосипеде, кажется, такой проблемы нет — скорость (наверное) всегда примерно средняя, каллочит почуть и ладно.

Ну, размер выделенной памяти, конечно, ужас. 1.6 метра на 1.1к строчек. Или не ужас?

Нет, не хочу использовать свой велосипед. Он просто получился.

А вы, господа гуру, подскажите-ка немощному страдальщику какой мне контейнер правильно выбрать под свои хотелки?








 , , , ,






URL записи