Прошу совета.

Пишу обработчик, который считывает из файлов собранную информацию о вызванных в процессе работы программы функциях и обрабатывает ее. С каждой функцией идет информация о том, где она была вызвана: файл, строка и т.п. — это регион. Одна и та же функция может быть вызвана несколько раз. Чтобы сократить размер структур данных в памяти, информация о регионах записывается в отдельный массив, а из массива с функциями делается ссылка на массив регионов.

Я не знаю заранее сколько у меня будет регионов, поэтому массив должен быть динамическим. Кроме того, т.к. регионы не могут дублироваться, при добавлении региона в массив я каждый раз должен делать поиск по всему массиву, на предмет нет ли уже такого региона.

1. Что делать с динамикой? realloc — это медленно и вообще я полагаю дурной тон. Писать самому структуру типа "список", где линковать друг с другом элементы ссылками?
2. Поиск перебором — медленно. Писать продвинутый алгоритм поиска?

Парсер должен быть быстрым + не очень хочется заморачиваться со всеми этими списками и сортировками. Контейнера типа map, как в C++ у меня нет. Есть элегантный выход из ситуации или все-таки придется заморачиваться?

Подход с ссылками из функции на регион — данность. Изменить нельзя. Что-то придумать можно только с тем как заполнять массивы.

Здравствуйте, _Lestat_, Вы писали:
_L_>Парсер должен быть быстрым + не очень хочется заморачиваться со всеми этими списками и сортировками. Контейнера типа map, как в C++ у меня нет. Есть элегантный выход из ситуации или все-таки придется заморачиваться?

... я когда однажды устраивался на работу и обсуждал разрабатываемый ими продукт, узнал, что они его делают юникодовым причём без использования макросов типа _T() или TEXT(), а посему мультибайтовое приложение не выпускают в принципе. Я спросил: "... а как же поддержка Win95/98?" на что они мне сказали, она есть и заключается в сообщении "выкинь своё старое гавёное железо, купи помощнее и поставь себе свежую винду!" ... это шутка, про сообщение, ... но что-то в таком роде типа фига ли мы должны поддерживать кареты с деревянными колёсами, когда по улицам иномарки с безкамерками уже вовсю шныряют ... и без этого хватает всякого повседневного гемора

... подобное хочется посоветовать и тебе ... ты будто в 80-х застрял ... весь мир уже давно имеет реализации разнообразнейших структур данных, решающих те или иные задачи, в том числе и задачи наподобие твоей. И решение такой задачи сводится исключительно к выбору правильной структуры данных и правильного алгоритма. Поэтому, ИМХО, обзаведись С++ и контейнером std::map ... либо ищи подобную реализацию для своего Языка/Фреймворка ... либо страдай с массивами

Здравствуйте, _Lestat_, Вы писали:

_L_>Парсер должен быть быстрым + не очень хочется заморачиваться со всеми этими списками и сортировками. Контейнера типа map, как в C++ у меня нет. Есть элегантный выход из ситуации или все-таки придется заморачиваться?

На Си, что ли, пишешь? Посмотри тогда на гномовскую библиотеку контейнеров GLib. Чтобы не велосипедировать.

"Регион" в твоей терминологии — это кортеж (имя файла, номер строки, ...), да?
То есть, у нас не стоит вопрос о поиске диапазонов, а тем более каких-то многомерных фигур.
Это просто точки в хитром пространстве, над которыми определён линейный порядок. (Грубо говоря: можно отсортировать по имени файла, а в пределах одного файла — по номерам строк).

Таким образом, тебе нужен ассоциативный контейнер с быстрым доступом. Это или дерево, или хеш-таблица.

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

Спасибо за полезный совет. Думаю что GHashTable из GLib вполне подойдет. Только я пока не до конца понимаю детали.

К>Таким образом, тебе нужен ассоциативный контейнер с быстрым доступом. Это или дерево, или хеш-таблица.

Хэш-таблице нужен ключ. У меня в одном файле может быть много вызовов функций и вызов в одной и той же строке может происходить в разных файлах. Т.о. уникальность региона дает пара (файл, строка в файле). Т.к. стандартные функции вычисления хэша работают с простыми типами, то мне придется писать свою хэш-функцию?

Я не очень силен в этом. Объясните на пальцах, какие должны быть хэш-таблицы и что у них будет ключ, а что значение. По идее по кортежу (файл, строка, имя_фунции, и т.п....), должен возвращаться id региона. Как это провернуть? Через две хэш-таблицы?

Здравствуйте, _Lestat_, Вы писали:

Сперва дисклаймер.
Я никогда практически не использовал GLib. Так что прошу считать следующий код эскизом, а не готовым рецептом.


_L_>Хэш-таблице нужен ключ. У меня в одном файле может быть много вызовов функций и вызов в одной и той же строке может происходить в разных файлах. Т.о. уникальность региона дает пара (файл, строка в файле). Т.к. стандартные функции вычисления хэша работают с простыми типами, то мне придется писать свою хэш-функцию?

Хэш от строки — зачастую тупо сумма символов. Если коллизий слишком много, то можно взять CRC. Можно и MD5, но это уже паранойя.
Чтобы не мучаться с рукодельным управлением строками — используй GString. Для него, кстати, и хэш-функция есть: g_string_hash

_L_>Я не очень силен в этом. Объясните на пальцах, какие должны быть хэш-таблицы и что у них будет ключ, а что значение. По идее по кортежу (файл, строка, имя_фунции, и т.п....), должен возвращаться id региона. Как это провернуть? Через две хэш-таблицы?

Как я уже сказал, имён файлов немного, и для каждой записи повторять имя файла — это трата и памяти, и времени.
Поэтому отдельно заводишь таблицу (имя файла) -> (регистрационный номер файла).

static GHashTable* filenames;
static uint        last_file_id;

static void delete_filename(gpointer p)
{
    g_string_free((GString*)p, TRUE);
}

void init_filenames()
{
    filenames = g_hash_table_new_full(g_string_hash, g_string_equal, delete_filename, NULL);
    last_file_id = 0;
}
void destroy_filenames()
{
    g_hash_table_destroy(filenames);
    filenames = NULL;
    last_file_id = 0;
}

uint file_id(g_string* name)
{
    gpointer key, value; // key - это имя файла (GString*), value - счётчик (uint)
    if(g_hash_table_lookup_extended(filenames, name, &key, &value))
        return (uint)value;
    else
        g_hash_table_insert(filenames, g_string_new_len(name.str, name.len), (gpointer)(last_file_id++));
}

И отдельно — таблицу (номер файла, номер строки) -> (указатель на регион). Здесь, пожалуй, удобнее будет дерево — GTree.

struct RegionId { uint file, line; };
struct RegionInfo
{
    RegionId id; // не должно меняться в течение всего времени существования объекта
    // и дальше - всякая полезная информация
};

RegionInfo* new_region(........);
void delete_region(RegionInfo* p);

gint compare_region_ids(RegionId* x, RegionId* y, gpointer userdata)
{
    if(x->file < y->file) return -1;
    if(x->file > y->file) return +1;
    
    if(x->line < y->line) return -1;
    if(x->line > y->line) return +1;
    
    return 0;
}

static GTree* regions;

void init_regions()
{
    regions = g_tree_new_full(compare_region_ids, NULL, NULL, delete_region);
}

RegionInfo* lookup_region(uint file, uint line)
{
    RegionId id = { file, line };
    return g_tree_lookup(regions, &id);
}
void add_region(RegionInfo* region) // не копирует, а захватывает этот объект
{
    g_tree_insert(regions, region->id, region);
}

_L_>>Хэш-таблице нужен ключ. У меня в одном файле может быть много вызовов функций и вызов в одной и той же строке может происходить в разных файлах. Т.о. уникальность региона дает пара (файл, строка в файле). Т.к. стандартные функции вычисления хэша работают с простыми типами, то мне придется писать свою хэш-функцию?

К>Хэш от строки — зачастую тупо сумма символов. Если коллизий слишком много, то можно взять CRC. Можно и MD5, но это уже паранойя.
К>Чтобы не мучаться с рукодельным управлением строками — используй GString. Для него, кстати, и хэш-функция есть: g_string_hash

_L_>>Я не очень силен в этом. Объясните на пальцах, какие должны быть хэш-таблицы и что у них будет ключ, а что значение. По идее по кортежу (файл, строка, имя_фунции, и т.п....), должен возвращаться id региона. Как это провернуть? Через две хэш-таблицы?

К>Как я уже сказал, имён файлов немного, и для каждой записи повторять имя файла — это трата и памяти, и времени.
К>Поэтому отдельно заводишь таблицу (имя файла) -> (регистрационный номер файла).

Классная идея. Мне бы в голову, за неимением большого опыта программировния, такое не пришло. Кодт, ты молодец, что находишь время помогать людям.

Я хоть и computer science окончил, тем не менее мне вот что интересно стало. Имя файла свернули в хэш. Функцию сравнения для дерева сделали сами с сортировкой сначала по имени файла, а потом строке. (Дерево кстати сбалансированное, оно это потом балансировать будет). С точки зрения работы алгоритмов совершенно пофигу какое у нас условие сортировки и какие данные мы сортируем и с каким условием? Пусть даже у нас там будет десять условий в функции сортировки? Все равно ведь искать мы будем потом согласно тому же алгоритму?

Здравствуйте, _Lestat_, Вы писали:

_L_>Я хоть и computer science окончил, тем не менее мне вот что интересно стало. Имя файла свернули в хэш. Функцию сравнения для дерева сделали сами с сортировкой сначала по имени файла, а потом строке. (Дерево кстати сбалансированное, оно это потом балансировать будет). С точки зрения работы алгоритмов совершенно пофигу какое у нас условие сортировки и какие данные мы сортируем и с каким условием? Пусть даже у нас там будет десять условий в функции сортировки? Все равно ведь искать мы будем потом согласно тому же алгоритму?

Ну, во-первых, там не хэш, а регистрационный номер имени файла.
Если тебе важно, чтобы эти номера шли в определённом порядке, — собери все имена файлов, отсортируй и скорми реестру имён.

При работе со строками хэш-таблица даёт выигрыш перед двоичным деревом поиска, поскольку многократное сравнение строк дороже однократного нахождения хэша и доступа по хэшу. (Но если уж будут коллизии — тут никуда не денешься, последуют сравнения строк).

А вот придумать хороший хэш для пары чисел — сложнее. Хотя можно, наверное.
Да и записей в таблице регионов куда больше, чем в таблице имён.
Поэтому в хэш-таблице была бы куча коллизий и, как следствие, линейный поиск.

Для двоичного дерева поиска, разумеется, нам всё равно, какое условие сортировки. Лишь бы оно удовлетворяло аксиоматике строгого порядка, то есть обладало свойствами транзитивности (x<y<z => x<z), антикоммутативности (x<y <=> y>x) и (анти)рефлексивности (x=x).
Но из всего бесконечного многообразия таких условий проще всего взять лексикографическое: сравнение первых элементов (номеров файлов), затем в случае равенства сравнение вторых элементов (номеров строк).
Кроме всего прочего, это и для тебя удобно: регионы одного файла оказываются сгруппированными вместе и упорядоченными по номерам строк.

Естественно, что у существующего экземпляра дерева условие жёстко зафиксировано. И, как следствие, порядок обхода тоже заранее известен. Это инвариант дерева. Чтобы поменять условие сортировки, нужно заодно перестроить всё дерево. Так проще сделать новое дерево с новым условием и перетащить старые данные туда.


Если тебе, помимо поиска по ключу (файл,строка) хочется искать ещё как-то — то здесь есть 3 варианта
0. осознать тщетность этого хотения и отказаться
1. завести параллельно ещё один контейнер, в котором те же самые элементы упорядочены иным, нужным тебе способом (естественно, что эти вторичные ключи не могут изменяться! либо, при изменении ключа нужно сперва удалить элемент из контейнера, а затем изменить ключ и вставить элемент обратно)
2. линейный обход с проверкой условия

К>Как я уже сказал, имён файлов немного, и для каждой записи повторять имя файла — это трата и памяти, и времени.
К>Поэтому отдельно заводишь таблицу (имя файла) -> (регистрационный номер файла).

Вместо того, чтоб рукодельничать — можно взять уже существующий кэш GCache.
По сути, это ровно то же самое! Только вместо последовательных номеров у нас будут непрозрачные хэндлы (gpointer value)
Но тут на вкус и цвет.
Главное, что у тебя получится обратная функция — по хэндлу получить строку обратно.

А вот ещё я подумал: можно же завести коллекцию (хэш-таблицу) строк самих на себя — т.е. ключ и значение одинаковы.
А в дереве регионов договориться, что RegionId содержит указатели не на какие попало строки (имена файлов), а только на зарегистрированные. И ни в коем случае не дубликаты.
Тогда функция сравнения регионов тупо сравнивает указатели на строки: если указатели не равны, то, очевидно, и содержимое не равно (мы же договорились!)
Конечно, порядок получится весьма и весьма произвольным — как эти строки в памяти разместятся. Зато очень быстрым. И при работе с одним регионом не нужно будет ещё куда-то в соседние таблицы лезть.

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


Тут ещё один вопрос на заднем плане: что делать при удалении регионов.
Если у тебя предполагается какая-то текучка, то может сложиться ситуация, когда не осталось ни одного региона для данного файла, и строка его имени болтается в таблице без дела, занимая память.
Если множество файлов за всё время работы приложения невелико, то и фиг с ней, пусть болтается. А если ещё и файлы приходят и уходят, то потребуется подсчёт ссылок.
Т.е. со строкой имени будет связан не только указатель (либо хэндл, либо номер), но и счётчик её регионов. Как только он обнулится — строку из памяти долой!

К>Тут ещё один вопрос на заднем плане: что делать при удалении регионов.
К>Если у тебя предполагается какая-то текучка, то может сложиться ситуация, когда не осталось ни одного региона для данного файла, и строка его имени болтается в таблице без дела, занимая память.
К>Если множество файлов за всё время работы приложения невелико, то и фиг с ней, пусть болтается. А если ещё и файлы приходят и уходят, то потребуется подсчёт ссылок.
К>Т.е. со строкой имени будет связан не только указатель (либо хэндл, либо номер), но и счётчик её регионов. Как только он обнулится — строку из памяти долой!

Невнимательно читал документацию. GCache уже реализует эту функциональность.
g_cache_insert(key) инкрементирует счётчик, если такой же ключ уже был вставлен, и возвращает тот же хэндл.
g_cache_remove(handle) декрементирует счётчик, и при обнулении удаляет ключ.
А внутренне оно устроено как хэш-таблица.

К>Тут ещё один вопрос на заднем плане: что делать при удалении регионов.
К>Если у тебя предполагается какая-то текучка, то может сложиться ситуация, когда не осталось ни одного региона для данного файла, и строка его имени болтается в таблице без дела, занимая память.
К>Если множество файлов за всё время работы приложения невелико, то и фиг с ней, пусть болтается. А если ещё и файлы приходят и уходят, то потребуется подсчёт ссылок.
К>Т.е. со строкой имени будет связан не только указатель (либо хэндл, либо номер), но и счётчик её регионов. Как только он обнулится — строку из памяти долой!

А если текучки нет — то другой контейнер, Кварки (GQuark). В лиспе и виндоузе эти сущности называются атомами.
Кварки глобальны, т.е. существуют от рассвета до заката программы.
Если тебя это устраивает — можешь ими воспользваться.

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