Идеальная структура данных для отображения целых чисел в целые числа?

Я не буду вдаваться в подробности, но я пытаюсь реализовать алгоритм, аналогичный алгоритму Бойера-Мура-Хорспула , только с использованием шестнадцатеричных значений цвета вместо символов (т. е. существует гораздо больший диапазон).

Следуя примеру Википедии, у меня изначально было следующее:

size_t jump_table[0xFFFFFF + 1];
memset(jump_table, default_value, sizeof(jump_table);

Однако, 0xFFFFFF, очевидно, является огромным числом, и это быстро приводит C к seg-ошибке (но не к переполнению стека, к сожалению).

В принципе, то, что мне нужно, - это эффективный ассоциативный массив, сопоставляющий целые числа целым числам. Я рассматривал возможность использования хэш-таблицы, но наличие структуры malloc'D для каждой записи кажется мне излишним (мне также не нужны хэши, поскольку каждый ключ является уникальным целым числом, и не может быть никаких повторяющихся записей).

Есть ли у кого-нибудь альтернативы, чтобы предложить? Может быть, я слишком прагматичен в этом вопросе?

Обновление

Для тех, кто заинтересован, я в конечном итоге использовал хэш-таблицу через библиотеку uthash.

7 4
algorithm data-structures

7 ответов:

0xffffff это довольно большой размер, чтобы поместить его в стек на большинстве систем, но вы абсолютно можете malloc буфер такого размера (по крайней мере, на текущих компьютерах; не так много на смартфоне). Стоит ли вам это делать для выполнения этой задачи-отдельный вопрос.

Edit: исходя из комментария, если вы ожидаете, что общий случай будет иметь относительно небольшое количество записей, кроме значения пропуска "этот цвет не отображается во входных данных", вам, вероятно, следует просто использовать хэш-карту (очевидно, только сохранение значений, которые на самом деле появляются во входных данных).

(игнорируйте предыдущее обсуждение других структур данных, которое было основано на неправильном запоминании обсуждаемого алгоритма - вы хотите использовать хэш-таблицу)

7

Если массив, который вы собирались сделать (размером 0xFFFFFF), будет разреженным, вы можете попробовать сделать меньший массив, чтобы он действовал как простая хэш-таблица, с размером 0xFFFFFF / N и хэш-функцией hexValue / N (или hexValue % (0xFFFFFF / N)). Однако вам придется проявить творческий подход, чтобы справиться с конфликтами.

Это единственный способ, который я могу предвидеть, чтобы выйти из malloc ing struct s.

3

Вы можете разместить в куче(для простоты) блоки 0xffffff из size_t и адресовать их так же, как и массив.

Что касается переполнения стека. В основном программа получает SIGSEGV,который может быть результатом переполнения стека или доступа к незаконной памяти или записи на сегмент только для чтения и т. д... Все они абстрагируются под одним и тем же сообщением об ошибке "ошибка сегментации".

Но почему бы вам не использовать язык более высокого уровня, такой как python, который поддерживает ассоциированные массивы?

1

Возможно, ценой некоторой скорости вы можете попробовать изменить алгоритм, чтобы найти только совпадения, выровненные по некоторой границе (каждые три или четыре символа), а затем выполнить поиск на байтовом уровне.

0

Вы можете создать разреженный массив видов, который имеет "страницы", как это (в этом примере используется 256 "страниц", поэтому самый верхний байт-это номер страницы): 

int *pages[256]; 

/* call this first to make sure all of the pages start out NULL! */
void init_pages(void) {
    for(i = 0; i < 256; ++i) {
        pages[i] = NULL;
    }
}

int get_value(int index) {
    if(pages[index / 0x10000] == NULL) {
        pages[index / 0x10000] = calloc(0x10000, 1); /* calloc so it will zero it out */
    }
    return pages[index / 0x10000][index % 0x10000];
}

void set_value(int index, int value) {
    if(pages[index / 0x10000] == NULL) {
        pages[index / 0x10000] = calloc(0x10000, 1); /* calloc so it will zero it out */
    }
    pages[index / 0x10000][index % 0x10000] = value;
}

Это выделит страницу при первом прикосновении, чтении или записи.

0

Чтобы избежать накладных расходов malloc, вы можете использовать хэш-таблицу, в которой записи в таблице являются вашими структурами, предполагая, что они малы. В вашем случае достаточно пары целых чисел со специальным значением, указывающим на пустоту ячейки в таблице.

0

Сколько значений есть в вашем выходном пространстве, т. е. сколько различных значений вы сопоставляете в диапазоне 0-0xFFFFF?

Используя рандомизированное универсальное хеширование , Вы можете получить безколлизионную хэш-функцию с таблицей, не превышающей в 2 раза число значений в вашем выходном пространстве (для статической таблицы)

0