История изменений

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

Если «очередь» состоит чисто из целых чисел, которые надо расставить по дереву в правильном порядке - то да, выглядит красиво, хотя и так, по-моему, желательно увеличить количество потомков у узла (например 4), чтобы делать меньше перестановок.

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

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

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

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

Во вариантах 1 и 2а, если увеличить количество потомков у узла, можно заметно уменьшить описанные вредные эффекты.

Во варианте 2а, с хранением структур в индексированном статическом массиве, можно сделать например так: 4 байта на индекс, 4 байта на ключ сравнения, 8 потомков у узла, итого описание всех его потомков займёт 64 байта - размер кеш-линии проца (и надо выровнять чтобы оно на правильные адреса попадало), что наверно положительно скажется на скорости. При этом сравнение ключей будет без указателей, а в указатели лезть только для свапа одного из 8 потомков (в 3 раза реже чем с двоичной кучей).

Ну и всё-таки, сравнение с обычным b-tree (дерево с блоками размера процовой страницы т.е. 4кб): в нём указанных проблем с лишними хождениями по указателям почти нет, постоянно делать свапы не нужно, иногда приходится делать сплит или объединение блоков но это иногда - редко, и затрагиваются этой операцией обычно только 1-2 узла. И можно без проблем хранить структуры в самом btree без лишних указателей. Куча точно лучше?

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

Если «очередь» состоит чисто из целых чисел, которые надо расставить по дереву в правильном порядке - то да, выглядит красиво, хотя и так, по-моему, желательно увеличить количество потомков у узла (например 4), чтобы делать меньше перестановок.

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

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

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

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

Во вариантах 1 и 2а, если увеличить количество потомков у узла, можно заметно уменьшить описанные вредные эффекты.

Во варианте 2а, с хранением структур в индексированном статическом массиве, можно сделать например так: 4 байта на индекс, 4 байта на ключ сравнения, 8 потомков у узла, итого описание всех его потомков займёт 64 байта - размер кеш-линии проца (и надо выровнять чтобы оно на правильные адреса попадало), что наверно положительно скажется на скорости. При этом сравнение ключей будет без указателей, а в указатели лезть только для свапа одного из 8 потомков (в 3 раза реже чем с двоичной кучей).

Ну и всё-таки, сравнение с обычным b-tree: в нём указанных проблем с лишними хождениями по указателям почти нет, постоянно делать свапы не нужно, иногда приходится делать сплит или объединение блоков но это иногда - редко, и затрагиваются этой операцией обычно только 1-2 узла. И можно без проблем хранить структуры в самом btree без лишних указателей. Куча точно лучше?