Как «сортировать и изменять» список?
Я не уверен, что эта тема уже обсуждалась, но если это так, у меня не было подходящего ключевого слова, чтобы найти ее.
В моем коде я извлекаю сопоставление, скажем: {5,0,23,2,2,0}. Как видите, значения не являются смежными. Что я хотел бы сделать, так это преобразовать это сопоставление, чтобы возвращаемый список был {3,0,4,1,2,0}. Здесь 0 означает, что элемент следует игнорировать. Итак, в основном, что я хочу сделать, это перенумеровать элементы в зависимости от их порядка, не перемещая их в списке.
Я сделал это, сначала создав копию исходного массива, а затем отсортировав эту копию с помощью qsort из библиотеки C stdlib. Я также создал return_list, в котором будет храниться мое окончательное сопоставление.
(исходный массив vec)
elt_count = 1;
for (size_t i = 0; i < n; i++) {
if (copy[i] != 0) {
for (size_t j = 0; j < n; j++) {
if (copy[i] == vec[j]) {
return_list[j] = elt_count;
vec[j] = 0;
elt_count++;
break;
}
}
}
}
Здесь я использую счетчик, чтобы дать окончательному отображению его значения.
Проблема в том, что эта часть моего метода занимает много времени и замедляет всю мою программу, в то время как я должен был использовать сопоставление, чтобы выиграть время.
Я думаю, что я мог бы сохранить положение каждого элемента, как это, чтобы попытаться улучшить производительность:
vec = (5,0,23,2,2,0)
5: (0)
23: (2)
2: (3,4)
Однако я не уверен, как это реализовать, а затем использовать для повышения производительности.
Конечно, любые другие идеи по улучшению производительности приветствуются!
@ Алекс, да, это то, что я пытаюсь сделать. (это кажется намного проще, как вы это сказали, я, возможно, слишком усложнил :))
Ответы 2
Один простой подход - сделать копию вашего массива, включая индексы значений:
int a2[n][2];
int zeros = 0;
for (int i = 0; i < n; i++) {
a2[i - zeros][0] = vec[i];
a2[i - zeros][1] = i;
zeros += (vec[i] == 0);
}
Теперь a2 — это массив длины n-zeros, а его элементы — ненулевые элементы vec в паре с их индексами.
Теперь сортируйте a2:
qsort(a2, n - zeros, sizeof(a2[0]), cmp_a2);
Используя эту функцию сравнения:
int cmp_a2(const void *v, const void*w) {
const int *a = v;
const int *b = w;
if (a[0] < b[0]) return -1;
if (a[0] > b[0]) return 1;
if (a[1] < b[1]) return -1;
if (a[1] > b[1]) return 1;
return 0;
}
Теперь вы можете заменить исходные элементы в массиве, используя исходные индексы, хранящиеся в отсортированном a2:
for (int i = 0; i < n - zeros; i++) {
vec[a2[i][1]] = i + 1;
}
Вот все части вместе как полный рабочий пример:
#include <stdlib.h>
#include <stdio.h>
void print_array(int *a, size_t n) {
for (int i = 0; i < n; i++)
printf("%s%d", i>0 ? ", " : "", a[i]);
printf("\n");
}
int cmp_a2(const void *v, const void*w) {
const int *a = v;
const int *b = w;
if (a[0] < b[0]) return -1;
if (a[0] > b[0]) return 1;
if (a[1] < b[1]) return -1;
if (a[1] > b[1]) return 1;
return 0;
}
void order_array(int *vec, size_t n) {
int (*a2)[2] = malloc(n * 2 * sizeof(int));
size_t zeros = 0;
for (int i = 0; i < n; i++) {
a2[i - zeros][0] = vec[i];
a2[i - zeros][1] = i;
zeros += (vec[i] == 0);
}
qsort(a2, n - zeros, sizeof(a2[0]), cmp_a2);
for (int i = 0; i < n - zeros; i++) {
vec[a2[i][1]] = i + 1;
}
free(a2);
}
int main(int argc, char *argv[]) {
int a[] = {5,0,23,2,2,0};
size_t n = sizeof(a) / sizeof(*a);
print_array(a, n);
order_array(a, n);
print_array(a, n);
}
Спасибо за ваш быстрый ответ ! У меня есть 3 ошибки компиляции при компиляции вашего кода. Один здесь: const int *a = v; и строка ниже и еще один здесь: int (*a2)[2] = malloc(n * 2 * sizeof(int));. Первую исправил так: const int* a = (int*)v;. Я даже не знаю, не сломает ли это ваш код, а для второго я не знаю, как его исправить. Вот сообщение об ошибке: Преобразование из "void*" в указатель на не-"void" требует явного приведения
Вы уверены, что используете компилятор C (а не компилятор C++) для компиляции кода? Программа компилируется без предупреждения с использованием параметров -ansi -pedantic -Wall -std=c99 как в clang, так и в gcc.
Теперь, когда вы это сказали, я думаю, что работаю с компилятором C++. Код, над которым я работаю, написан на C, но инструменты компиляции, используемые моей командой, — C++. Я собираюсь попытаться найти способ заставить его работать с этим компилятором. Во всяком случае, теперь яснее, что вы дали мне этот метод. Благодарю за ваш ответ !
Примечание. a2 — это указатель на массив, что может затруднить поиск правильного синтаксиса приведения. Вы можете использовать static_cast<decltype(a2)>(malloc(...)) вместо malloc(...), чтобы заставить компилятор C++ принять этот синтаксис C.
Спасибо за это замечание, я нашел способ использовать компилятор C, поэтому у меня больше нет проблем с этим. Ваш метод вааааа быстрее моего, это даже не сравнимо!
Мне просто нужно одно уточнение о вашей функции сравнения. Итак, если a[0] < b[0], он возвращает 1, а если наоборот, возвращает -1. А две строчки внизу сделаны для случаев, когда a[0] = b[0] это правильно?
Да, для одинаковых значений (т. е.: a[0] == b[0]) он сравнивает исходные индексы, чтобы дубликаты в исходном массиве получали последовательные значения, причем крайний левый получает наименьшее значение, а крайний правый — наивысшее значение и так далее.
Вы можете использовать стандартные библиотечные функции qsort и bsearch для решения проблемы. Вот начало:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define LEN(arr) (sizeof (arr) / sizeof (arr)[0])
int ElemDiff(const void *leftElemPtr, const void *rightElemPtr) {
return *(int *) leftElemPtr - *(int *) rightElemPtr;
}
int main(void)
{
int vec[] = {5, 0, 23, 2, 2, 0};
int sortedVec[LEN(vec)];
int i, *tail;
memcpy(sortedVec, vec, sizeof (vec));
qsort(sortedVec, LEN(sortedVec), sizeof sortedVec[0], ElemDiff);
for (i = 0; i < LEN(vec); i++) {
tail = bsearch(vec + i, sortedVec, LEN(sortedVec), sizeof sortedVec[0], ElemDiff);
assert(tail != NULL);
printf("%lld ", tail - sortedVec);
}
putchar('\n');
return 0;
}
Это напечатает
4 0 5 2 2 0
Желаемое решение, данное в вопросе, 3, 0, 4, 1, 2, 0 не 4, 0, 5, 2, 2, 0.
Да, поэтому я сказал "вот начало".
Итак, вы хотите заменить каждый элемент его позицией, если список был отсортирован, а нули проигнорированы?