сортировка 5d массива в c - PullRequest
Новая
       28

сортировка 5d массива в c

12 голосов
/ 30 марта 2012

Я пытаюсь выяснить, как сортировать многомерные данные (5 измерений) в C. Я знаю, что использование массива 5d - это решение, которое, читая другие посты в SO по этой теме, найдут многие, если не совсемнеэтично, настолько эстетически отвратительно, что вызывает непрерывную рвоту снаряда ... поэтому я заранее извиняюсь.

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

Вот как выглядят данные: 

dataValue[ algo ][ lengthVar ][ durationVar ][ plasticityVar ] [ fungibilityVar]

Имеется:

  • 35 алгоритмов
  • 10 переменных длины
  • 230 длительностей vars
  • 27 переменных пластичности
  • 400 переменных гибкости

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

Это будет выполняться на машине с 12 физическими / 24 логическими ядрами и 192 гигабайтами (не мегабайтами) ОЗУ с использованием VS 2010 C (не C ++).

Я предполагаю, что qsort будетнаиболее эффективный вариант сортировки.Я много раз искал в Google и SO, как это сделать, но безрезультатно.Есть ответы для одномерных массивов, многомерных массивов в PHP или C # и т. Д., Но не для C ... или, по крайней мере, я не могу их найти.

Ответы [ 2 ]

4 голосов
/ 30 марта 2012

qsort в cstdlib будет работать. Массив имеет тип данных *** data.

Итак, во-первых, допустим, вы хотите отсортировать первый индекс массива. Вам нужно написать функцию сравнения для сравнения двух типов данных ****. Компаратор должен возвращать значение меньше нуля, если ab. 

int myComparator(void *a, void *b){
    Datatype ****c=(Datatype****)a; Datatype ****d=(Datatype****)b
    return algorithmRatingFunction(b)-algorithmRatingFunction(a);
}

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

qsort(data,35,sizeOf(Datatype),myComparator);

Вот и все!

Тогда возникает проблема неэффективности ... Если для алгоритма алгоритма RatingFunction требуется много времени (что, я полагаю, так и есть), то вам нужно вычислить все 35 алгоритмов один раз и только один раз. Что вы можете сделать, это рассчитать баллы заранее: 

int scores[35];
for(int n=0;n<35;n++)
    scores[n]=algorithmRatingFunction(data[n]);

Затем создайте еще один упорядоченный массив целых чисел: 

int ordering[35];
for(int n=0;n<35;n++)
    ordering[n]=n;

Таким образом, состояние «порядок» соответствует порядку вашего набора данных. Затем вы можете создать новый компаратор: 

int myFasterComparator(void *a, void *b){
    int c=*(int*)a; int d=*(int*)b
    return scores[c]-scores[d];
}

И позвоните при заказе: 

qsort(ordering,35,sizeOf(int),myFasterComparator);

Затем восстановите массив, используя порядок. вот так: 

Datatype ****ordereddata[35];
for(int n=0;n<35;n++)
    ordereddata[n]=data[ordering[n]];

То же самое относится ко всем остальным уровням. Как и в опубликованном dasblinkenlight, qsort уменьшает проблему сортировки 5d-массивов по сравнению со сравнением двух 4d-массивов. Поэтому вместо сортировки каждого 4-мерного массива вам просто нужно сравнить два 3D-массива и т. Д.

2 голосов
/ 30 марта 2012

Я думаю, вам действительно нужно отказаться от рвоты из-за 5D эффекта. Вместо этого создайте структуру: 

typedef struct {
    int algorithm;
    int length;
    int duration;
    int plasticity;
    int fungibility;
    int dataValue;
} AlgorithmTestData;

А затем определите массив 1D тестовых данных: 

AlgorithmTestData algoTestCases[NUMBER_OF_TEST_CASES];

или вы можете выделить его динамически, если вы не знаете размер тестовых случаев с помощью malloc.

Тогда вы получите qsort массив algoTestCases 1D в соответствии с вашими требованиями сравнения.

...