параллельная быстрая сортировка в c

Question

После долгих поисков реализации параллельной быстрой сортировки в c я собираюсь погрузиться в нее и написать ее сам. (Мне нужно отсортировать массив из примерно 1 миллиона текстовых строк.) Кажется, что все реализации, которые я нашел, разделяют работу внутри самой функции qsort, что создает огромные накладные расходы при разбиении относительно небольшого объема работы на поток .

Не будет ли намного быстрее разделить миллион строк на количество потоков (в моем случае 24 потока), и каждый из них будет работать над разделом, а затем выполнять сортировку слиянием? Конечно, это имеет теоретический недостаток, заключающийся в том, что он не является сортировкой на месте, но с доступными объемами памяти это не проблема. Машина, на которой она работает, имеет 12 (очень быстрых) физических / 24 логических ядра и 192 ГБ (да, гигабайт) памяти. В настоящее время даже на этой машине сортировка занимает почти 8 минут!

Answer 1

Не будет ли намного быстрее разделить миллион строк на количество потоков (в моем случае 24 потока), и каждый из них будет работать с разделом, а затем выполнять сортировку слиянием?

Это хорошая идея.

Но вы можете сделать некоторые наблюдения, написав игрушечные программы для quick-sort и merge-sort и использовать преимущества их алгоритмического поведения во время выполнения.

Например.quick-sort сортирует, в то время как процесс dividing (элемент pivot будет помещен в его окончательное место в конце этой итерации) и merge-sort сортирует, пока merging (сортировка выполняется после разбивки всего рабочего набора(разделенный) на очень гранулированные единицы, где его можно напрямую сравнить с другими гранулярными единицами (== или strcmp()).

Хорошей идеей является смешивание алгоритмов, основанных на природе рабочего набора..

Что касается параллельной сортировки, вот мое parallel merge-sort для вас, чтобы начать.

#include <stdio.h>
#include <pthread.h>
#include <stdlib.h>

#define NOTHREADS 2

/*

gcc -ggdb -lpthread parallel-mergesort.c 


NOTE: 
The mergesort boils downs to this.. 
Given two sorted array's how do we merge this?

We need a new array to hold the result of merging
otherwise it is not possible to do it using array, 
so we may need a linked list

*/

int a[] = {10, 8, 5, 2, 3, 6, 7, 1, 4, 9};

typedef struct node {
int i;
int j;
} NODE;

void merge(int i, int j)
{
        int mid = (i+j)/2;
        int ai = i;
        int bi = mid+1;

        int newa[j-i+1], newai = 0;

        while(ai <= mid && bi <= j) {
                if (a[ai] > a[bi])
                        newa[newai++] = a[bi++];
                else                    
                        newa[newai++] = a[ai++];
        }

        while(ai <= mid) {
                newa[newai++] = a[ai++];
        }

        while(bi <= j) {
                newa[newai++] = a[bi++];
        }

        for (ai = 0; ai < (j-i+1) ; ai++)
                a[i+ai] = newa[ai];

}

void * mergesort(void *a)
{
                NODE *p = (NODE *)a;
                NODE n1, n2;
                int mid = (p->i+p->j)/2;
                pthread_t tid1, tid2;
                int ret;

                n1.i = p->i;
                n1.j = mid;

                n2.i = mid+1;
                n2.j = p->j;

                if (p->i >= p->j) return;

                ret = pthread_create(&tid1, NULL, mergesort, &n1);
                if (ret) {
                        printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);    
                        exit(1);
                }


                ret = pthread_create(&tid2, NULL, mergesort, &n2);
                if (ret) {
                        printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);    
                        exit(1);
                }

                pthread_join(tid1, NULL);
                pthread_join(tid2, NULL);

                merge(p->i, p->j);
                pthread_exit(NULL);
}


int main()
{
                int i;
                NODE m;
                m.i = 0;
                m.j = 9;
                pthread_t tid;

                int ret; 

                ret=pthread_create(&tid, NULL, mergesort, &m);
                if (ret) {
                        printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);    
                        exit(1);
                }

                pthread_join(tid, NULL);

                for (i = 0; i < 10; i++)
                                printf ("%d ", a[i]);

                printf ("\n");

                // pthread_exit(NULL);
                return 0;
}

Удачи!

Answer 2

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

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

Answer 3

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

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

Другое возможное решение - обернуть алгоритм параллельной сортировки из C ++. Реализация GNU STL имеет параллельный режим , который содержит реализацию параллельной быстрой сортировки. Это, наверное, самое простое решение.

Answer 4

Для обеспечения возможности многопоточной быстрой сортировки доступ к памяти должен быть оптимизирован таким образом, чтобы большая часть работы по сортировке выполнялась внутри кешей без общего доступа (L1 и L2). Я держу пари, что однопоточная быстрая сортировка будет быстрее, чем многопоточная, если вы не готовы выполнить много работы.

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

Что касается специальной подпрограммы сортировки, адаптированной для строк, то концепция звучит для меня странно. Я имею в виду, что не так много случаев, когда сортировка вектора только строк (или целых чисел) особенно полезна. Обычно данные организуются в таблицу со столбцами и строками, и вам нужно отсортировать строки по одному столбцу, содержащему буквы, и, если они равны, вы будете сортировать, используя дополнительный столбец, содержащий метку времени или ранжирование. или что-то другое. Таким образом, процедура сортировки должна иметь возможность обрабатывать многоуровневый набор правил сортировки, который может указывать любой тип данных (логические, целые, даты, строки, с плавающей запятой и т. Д.) В любом направлении (по возрастанию или по убыванию), присутствующему в столбцах таблицы.