Как лучше всего отсортировать часть кругового буфера?

Question

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

Я подумал о нескольких подходах:

1. Используйте отдельный линейный буфер - сначала скопируйте элементы из кольцевого буфера, затем примените qsort, затем скопируйте их обратно. Использование дополнительного буфера означает дополнительное O (N) пространство, которое приводит меня к
   • Сортируйте половину "top" и "bottom" с помощью qsort, а затем объедините их, используя дополнительный буфер
   • То же, что и 2., но выполняем окончательное слияние на месте (я не нашел много информации о слиянии на месте, но реализации, которые я видел, не стоят уменьшенной сложности пространства)

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

Исправление: Допущена глупая ошибка переключения DFS и BFS (я предпочитаю писать DFS, но в данном конкретном случае я должен использовать BFS), извините за путаницу.

Дальнейшее описание исходной задачи:

Я реализую ширину первого поиска (для чего-то похожего на головоломку пятнадцать , просто более сложную, с примерно O (n ^ 2) возможными расширениями в каждом состоянии, вместо 4). Алгоритм "грубой силы" готов, но он "глупый" - в каждой точке он расширяет все допустимые состояния в жестко заданном порядке. Очередь реализована в виде циклического буфера (беззнаковая очередь [MAXLENGTH]) и хранит целочисленные индексы в таблице состояний. Помимо двух простых функций, которые ставят в очередь и удаляют из индекса индекс, он не имеет инкапсуляции - это просто простой статически размещенный массив беззнаковых.

Теперь я хочу добавить эвристику. Первое, что я хочу попробовать, это отсортировать расширенные дочерние состояния после расширения («разверните их в лучшем порядке») - точно так же, как если бы я программировал простую лучшую первую DFS. Для этого я хочу взять часть очереди (представляющую самые последние расширенные состояния) и отсортировать их, используя какую-то эвристику. Я мог бы также расширить состояния в другом порядке (поэтому в этом случае это не очень важно, если я нарушу свойства FIFO очереди).

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

Answer 1

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

---

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

Круговой буфер уже решил эту проблему, используя арифметику% (mod). QSort и т. Д. Не заботятся о местах в памяти - им просто нужна схема для линейного обращения с данными.

Они работают также для связанных списков (которые не являются линейными в памяти), как для «реальных» линейных некруговых массивов.

Так что, если у вас есть круговой массив с 100 записями, и вы обнаружите, что вам нужно отсортировать первые 10, а первые десять попали в верхнюю часть, то вы передадите сортировке следующие два бита информации:

• Функция поиска элемента массива: (x% 100)
• Предметы для сортировки находятся в местах от 95 до 105

Функция преобразует адреса, используемые сортировкой, в индекс, используемый в реальном массиве, и тот факт, что массив оборачивается, скрыт, хотя сортировка массива за его пределы может показаться странным, определение, не имеет границ. Оператор% справится с этим за вас, и вы можете также сослаться на часть массива с 1295 по 1305 для всех своих забот.

Бонусные баллы за массив с 2 ^ n элементами.

---

Дополнительные вопросы для рассмотрения:

Мне кажется, что вы используете библиотеку сортировки, которая не способна сортировать что-либо, кроме линейного массива - поэтому она не может сортировать связанные списки или массивы с чем-либо, кроме простого упорядочения. У вас действительно есть только три варианта:

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

Теперь, со своей стороны, я бы переписал код сортировки, чтобы он был более гибким (или продублировал его и отредактировал новую копию, чтобы у вас были сортировки, которые быстры для линейных массивов, и сортировки, которые гибки для не линейные массивы)

Но реальность такова, что сейчас ваша библиотека сортировки настолько проста, что вы даже не можете сказать ей, как получить доступ к данным, которые хранятся нелинейно.

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

Попытка создания уродливого клуджа, например, как-то превратить ваш буфер в линейный массив, отсортировать его, а затем снова поместить в него - это всего лишь уродливый клудж, который вы должны будете понять и поддержать позже. Вы собираетесь «вломиться» в свой FIFO и возиться с внутренностями.

-Adam

Answer 2

Я не вижу именно того решения, о котором вы просили в c. Вы могли бы рассмотреть одну из этих идей:

• Если у вас есть доступ к источнику для libc qsort(), вы можете скопировать его и просто заменить весь код доступа к массиву и индексирования соответствующими обобщенными эквивалентами. Это дает вам некоторую скромную уверенность в том, что нижележащая сортировка эффективна и имеет мало ошибок. Конечно, не поможет с риском появления собственных ошибок. Большой О, как система qsort, но, возможно, с худшим множителем.

• Если сортируемая область мала по сравнению с размером буфера, вы можете использовать прямую линейную сортировку, защищая вызов с помощью теста для переноса и выполняя копирование в линейную Буферная сортировка и копирование только при необходимости. Вводит дополнительную операцию O(n) в случаях, когда срабатывает защита (для n размера региона, подлежащего сортировке), что составляет среднее значение O(n^2/N) < O(n).

---

Я вижу, что C ++ не подходит для вас. :: sigh :: Я оставлю это здесь на случай, если кто-то другой может использовать его.

• Если C ++ является опцией, вы можете (подклассировать буфер при необходимости и) перегрузить оператор [], чтобы заставить работать стандартные алгоритмы сортировки. Опять же, должен работать как стандартная сортировка с штрафом множителя.

Answer 3

Вы можете вращать циклическую очередь до тех пор, пока рассматриваемое подмножество больше не будет вращаться вокруг. Затем просто передайте это подмножество в qsort как обычно. Это может быть дорого, если вам нужно часто сортировать или размер элемента массива очень велик. Но если ваши элементы массива являются просто указателями на другие объекты, то вращение очереди может быть достаточно быстрым. И на самом деле, если они просто указатели, то ваш первый подход также может быть достаточно быстрым: сделать отдельную линейную копию подмножества, отсортировать ее и записать результаты обратно.

Answer 4

Возможно, очередь с приоритетом может быть адаптирована для решения вашей проблемы.

Answer 5

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

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

Правила оптимизации:

1. Не оптимизировать.

2. Если вы знаете, что делаете, см. Правило № 1

Вы можете перейти к более сложным правилам:

Правила оптимизации (продолжение):

3. Если у вас есть спецификация, которая требует определенного уровня производительности, напишите код без оптимизации и напишите тест, чтобы проверить, соответствует ли он этой спецификации. Если это встречается, то все готово. НИКОГДА не пишите код с учетом производительности, пока не достигнете этой точки.

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

5. Если ваши улучшения сделали тесты успешными, убедитесь, что тесты остаются в кодовой базе и перезапускаются, а исходный код остается там в виде комментариев.

Примечание: должно быть 3. 4. 5. Что-то напортачило - я даже не использую теги разметки.

Хорошо, наконец, я не говорю это, потому что где-то читал. Я провел ДНИ, пытаясь распутать некоторые ужасные беспорядки, которые закодировали другие люди, потому что это было «Оптимизировано» - и действительно забавно то, что 9 раз из 10 компилятор мог бы оптимизировать его лучше, чем они.

Я понимаю, что бывают случаи, когда вам НУЖНО оптимизировать, все, что я говорю, это напишите его без оптимизации, протестируйте и перекодируйте. Это действительно не займет у вас много времени - может даже упростить написание оптимизированного кода.

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

Answer 6

Как насчет этого примера здесь. Этот пример легко сортирует часть или все, что вы хотите, без необходимости переопределять много дополнительной памяти. Он занимает всего два указателя бит состояния и счетчик для цикла for.

#define _PRINT_PROGRESS
#define N 10
BYTE buff[N]={4,5,2,1,3,5,8,6,4,3};
BYTE *a = buff;
BYTE *b = buff;
BYTE changed = 0;
int main(void)
{
    BYTE n=0;
    do
    {
        b++;
        changed = 0;
        for(n=0;n<(N-1);n++)
        {
            if(*a > *b)
            {
                *a ^= *b;
                *b ^= *a;
                *a ^= *b;
                changed = 1;
            }
            a++;
            b++;
        }
        a = buff;
        b = buff;
#ifdef _PRINT_PROGRESS
        for(n=0;n<N;n++)
            printf("%d",buff[n]);
        printf("\n");
    }
#endif
    while(changed);
    system( "pause" );
}