Сортировка связанного списка параллельно с помощью Insertion Sort

Question

У меня есть назначение, где я должен написать программу C, которая сортирует связанный список землетрясений по величине в нескольких процессах. Для этой первой части задания наш учитель разрешит нам использовать несколько процессов вместо потоков.

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

Есть ли лучший способ решить эту проблему? Если нет, как я могу использовать разделяемую память для сортировки списка землетрясений с помощью сортировки вставки?

Answer 1

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

http://msdn.microsoft.com/en-us/library/windows/desktop/aa366763(v=vs.85).aspx

http://man7.org/linux/man-pages/man7/shm_overview.7.html

http://linux.die.net/man/2/mmap

Я DON» t знать, используете ли вы Linux или Windows.

Если базовый адрес для общей памяти не совпадает, то, как указано в статье msdn, указатели обычно заменяются смещениями от базового адреса. Я не уверен, что связанный список с использованием следующего «смещения» по сравнению с следующим «указателем» - это то, что предназначено для этого назначения.

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

Answer 2

Как насчет использования сортировки слияния и многопоточности?
Каждое разделение массива создает новый поток, а в конце - выход синхронизации. Таким образом, для глубины n будут потоки < (2^n + 1).
Следовательно, вы сортируете связанный список параллельно, а также нет случая с неправильным использованием ресурсов.

Извините, недостаточно репо, чтобы написать его в комментарии.

Answer 3

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

Однако быстрая сортировка может деградировать en O (n^2), если шар не выбран. Позаботьтесь об этом

Уважение к числу потоков, я бы рекомендовал фиксированное число, не превышающее количество ядер. И здесь снова quicksort проще. Например, если у вас есть 4 потока, то вы используете первый поток для первого раздела. Затем вы используете два потока для выполнения 4 разделов. С помощью этих 4 разделов вы назначаете каждый раздел каждому потоку. Когда 4 потока присоединяются к вызывающему потоку, массив будет отсортирован.