В общем есть двух связный кольцевой список некой структуры(размером до 60 байт). Какой бы лучше выбрать алгоритм сортировки ? интересует в первую очередь скорость. Информация о списке: Список может быть частично на 10 - 30% отсортирован. Количество элементов теоретически безгранично, а практически 500 - 5000 . Пока что думается конвертировать список в массив указателей и использовать быструю сортировку. Но не очень мне это нравиться. Сортировка нужна для более быстрого поиска элемента в списке. Буду хранить 3 элемента (начало, средину, и последний используемый элемент ) и от них уже делать линейный поиск. Есть лучше вариант для сортировки\поиска в списке?
Быстрая сортировка как раз для такого и придумывалась. А мне нравится. Зависит от задачи. Но часто можно свести к O(1) для 50-99%, вычисляя угадывая наиболее вероятный результат для следующего поискового запроса.
Тогда зависит от того, что он описывает. Если для бинарного кода и должен модифицироваться для дальнейшей компиляции, то только трассировка. Иначе можно просто все элементы перебрать подряд.
Malfoy Да бинарного кода. Есть отдельное поле которое все элементы связывает, нужно для освобождения ресурсов. Если в конце изменить связи по этому полю граф не нарушиться, а вот к примеру поиск блока по адресу ускорится. Что ты имеешь ввиду под трассировкой? Вызов CallBack функции для каждого узла/элемента ?
XshStasX Граф может быть массивом, а может им не являться. Массив это последовательность описателей, которые находятся друг за другом в определённой области памяти. Тогда следующий описатель J' = @J + sizeof(J). Если граф будет изменяться, например добавляться часть другого графа, то он уже не может быть массивом. Память между двумя элементами двух графов не принадлежит ни однуму из них. К примеру морфите вы вы блок в определённой процедуре - придётся смещать весь граф, править все ссылки, короче это полный бред. Вот для такого графа описатели перечисляются только раскрытием ссылок(напр J' = J.Flink). При этом не важно где в памяти находится описатель. Такое перечисление называется трассировкой.
Не совсем понял тебя. Описатели ты имеешь ввиду структуры блоков\переходов\тп ? К примеру иметься полный граф кода(все блоки и переходы известны, нету переходов внутрь инструкций). Если я что-то добавлю в процедуры (к примеру свой блок) то мне нужно 1. пересчитать ссылки всех блоков. 2. Указатели на данные, пока это можно и опустить. То нужно 1. Перечислить все линейные блоки внутрь которых нету переходов из других блоков. Переходы могут быть только на первую инстр. блока. И поправить смещения. 2. поправить смещения всех переходов которые ссылаются на смещенные блоки. Смещенные блоки можно получить из п.1 введя флаг поправки блока или отдельный список . вроде ничего не опустил ?
Может лучше поглядеть в сторону хэш-таблиц? Эдакая комбинация хэш-таблиц и списков - вместо одного списка - целый массив списков (скажем несколько тысяч), растущих из слотов, соответствующих хэшам от ключевых значений?
XshStasX Зачем чтото пересчитывать, если можно этого не делать.. Вы в любом случае будите при вставках в граф(при его создании) добавлять новые элементы(описатели) в конец графа. Это сделает граф не линейным - описатели подряд идущих в памяти блоков будут находится в разных местах в графе. Чтобы привести его в годный вид, придётся конвертировать граф в линейный, посредством трассировки. В противном случае например последовательно не получится енумить описатели. Таким образом оказывается что линейный граф очень не удобный. Манипуляции должны выполняться с не линейным графом. Dmitry_Milk Вместо одного списка - целый массив костылей
Можно и один (список), но с массивом "костылей", указывающих, где в списке начинаются/заканчиваются соответствующие слотам участки. Хочешь - пользуйся списком как обычно (только не забывай и костыли подправлять при вставке-удалении), а надо быстро найти - ползуйся указателями слотов по хешу.
