如何“排序和修改”一个列表？

huangapple
go评论83阅读模式
英文:

How to "sort and modify" a list?

问题

我不确定这个主题是否已经被讨论过，但如果是这样，我没有正确的关键词来找到它。在我的代码中，我提取一个映射，就像这样：{5,0,23,2,2,0}。如你所见，这些值不是连续的。我想要做的是将这个映射转换为返回的列表是{3,0,4,1,2,0}。这里的0表示元素应该被忽略。所以基本上我想做的是根据它们的顺序重新编号这些元素，而不是移动它们在列表中的位置。

我通过首先创建我的初始数组的副本，然后使用stdlib C库中的qsort对这个副本进行排序来实现这个目标。我还创建了一个return_list，其中将存储我的最终映射。

(初始数组是vec)

  1. elt_count = 1;
  2. for (size_t i = 0; i < n; i++) {
  3.     if (copy[i] != 0) {
  4.         for (size_t j = 0; j < n; j++) {
  5.             if (copy[i] == vec[j]) {
  6.                 return_list[j] = elt_count;
  7.                 vec[j] = 0;
  8.                 elt_count++;
  9.                 break;
  10.             }
  11.         }
  12.     }
  13. }

在这里，我使用一个计数器为最终映射赋予它的值。

问题是，我的方法中的这部分需要很多时间，而且减慢了我的整个程序，而我本应该使用映射来节省时间。

我认为我可以像这样存储每个元素的位置来尝试提高性能：

  1. vec = (5,0,23,2,2,0)
  2. 5: (0)
  3. 23: (2)
  4. 2: (3,4)

然而，我不确定如何实施这个并且如何使用它来提高性能。

当然，欢迎任何其他改进性能的想法！

英文:

I am not sure if this subject was already treated but if it's the case I did not have the right keyword to find it.
In my code I extract a mapping so let's say: {5,0,23,2,2,0}. As you can see the values are not contiguous. What I would like to do is transform this mapping so that the returned list is {3,0,4,1,2,0}. Here 0 means that the element should be ignored. So basically what I want to do is renumber the elements based on their order without moving them in the list.

I did that by first creating a copy of my initial array and then sorting this copy using qsort from the stdlib C library. I also created a return_list in which my final mapping will be stored.

(the initial array is vec)

  1.     elt_count = 1;
  2.     for (size_t i = 0; i &lt; n; i++) {
  3.         if (copy[i] != 0) {
  4.             for (size_t j = 0; j &lt; n; j++) {
  5.                 if (copy[i] == vec[j]) {
  6.                     return_list[j] = elt_count;
  7.                     vec[j] = 0;
  8.                     elt_count++;
  9.                     break;
  10.                 }
  11.             }
  12.         }
  13.     }

Here I use a counter to give the final mapping its values.

The problem is that this part of my method takes a lot of time and slows down my whole program while I was supposed to use the mapping to gain time.

I think I could store the position of each elements like this to try and improve the performances:

  1. vec = (5,0,23,2,2,0)
  2. 5: (0)
  3. 23: (2)
  4. 2: (3,4)

However I am not sure how to implement this and then use it to gain performance.

Of course any other ideas to improve the performances are welcome !

答案1

得分: 2

以下是您要翻译的内容：

  1. 一种简单的方法是创建一个包含值的索引的数组副本：
  3.     int a2[n][2];
  4.     int zeros = 0;
  5.     for (int i = 0; i < n; i++) {
  6.         a2[i - zeros][0] = vec[i];
  7.         a2[i - zeros][1] = i;
  8.         zeros += (vec[i] == 0);
  9.     }
  11. 现在 `a2` 是一个长度为 `n-zeros` 的数组，其条目是 `vec` 的非零元素与它们的索引配对。
  13. 现在对 `a2` 进行排序：
  15.     qsort(a2, n - zeros, sizeof(a2[0]), cmp_a2);
  17. 使用这个比较函数：
  19.     int cmp_a2(const void *v, const void *w) {
  20.         const int *a = v;
  21.         const int *b = w;
  22.         if (a[0] < b[0]) return -1;
  23.         if (a[0] > b[0]) return 1;
  24.         if (a[1] < b[1]) return -1;
  25.         if (a[1] > b[1]) return 1;
  26.         return 0;
  27.     }
  29. 现在，您可以使用排序后的 `a2` 中存储的原始索引替换数组中的原始元素：
  31.     for (int i = 0; i < n - zeros; i++) {
  32.         vec[a2[i][1]] = i + 1;
  33.     }
  35. 这里是所有部分完整的工作示例：
  37.     #include <stdlib.h>
  38.     #include <stdio.h>
  39.     
  40.     void print_array(int *a, size_t n) {
  41.     	for (int i = 0; i < n; i++)
  42.     		printf("%s%d", i > 0 ? ", " : "", a[i]);
  43.     	printf("\n");
  44.     }
  45.     
  46.     int cmp_a2(const void *v, const void *w) {
  47.         const int *a = v;
  48.         const int *b = w;
  49.         if (a[0] < b[0]) return -1;
  50.         if (a[0] > b[0]) return 1;
  51.         if (a[1] < b[1]) return -1;
  52.         if (a[1] > b[1]) return 1;
  53.         return 0;
  54.     }
  55.     
  56.     void order_array(int *vec, size_t n) {
  57.     	int (*a2)[2] = malloc(n * 2 * sizeof(int));
  58.         size_t zeros = 0;
  59.         for (int i = 0; i < n; i++) {
  60.             a2[i - zeros][0] = vec[i];
  61.             a2[i - zeros][1] = i;
  62.             zeros += (vec[i] == 0);
  63.         }
  64.         qsort(a2, n - zeros, sizeof(a2[0]), cmp_a2);
  65.     
  66.         for (int i = 0; i < n - zeros; i++) {
  67.             vec[a2[i][1]] = i + 1;
  68.         }
  69.         free(a2);
  70.     }
  71.     
  72.     int main(int argc, char *argv[]) {
  73.     	int a[] = {5,0,23,2,2,0};
  74.     	size_t n = sizeof(a) / sizeof(*a);
  75.     	print_array(a, n);
  76.     	order_array(a, n);
  77.     	print_array(a, n);
  78.     }

请注意，这段代码将数组 a 中的元素重新排序，将非零元素替换为它们在重新排序后的数组中的索引。

英文:

One easy approach is to make a copy of your array including the indexes of the values:

  1. int a2[n][2];
  2. int zeros = 0;
  3. for (int i = 0; i &lt; n; i++) {
  4. a2[i - zeros][0] = vec[i];
  5. a2[i - zeros][1] = i;
  6. zeros += (vec[i] == 0);
  7. }

Now a2 is an array of length n-zeros, and its entries are the non-zero elements of vec paired with their indexes.

Now sort a2:

  1. qsort(a2, n - zeros, sizeof(a2[0]), cmp_a2);

Using this comparison function:

  1. int cmp_a2(const void *v, const void*w) {
  2. const int *a = v;
  3. const int *b = w;
  4. if (a[0] &lt; b[0]) return -1;
  5. if (a[0] &gt; b[0]) return 1;
  6. if (a[1] &lt; b[1]) return -1;
  7. if (a[1] &gt; b[1]) return 1;
  8. return 0;
  9. }

Now you can replace the original elements in the array, using the original indices stored in the sorted a2:

  1. for (int i = 0; i &lt; n - zeros; i++) {
  2. vec[a2[i][1]] = i + 1;
  3. }

Here's all the pieces together as complete working example:

  1. #include &lt;stdlib.h&gt;
  2. #include &lt;stdio.h&gt;
  3. void print_array(int *a, size_t n) {
  4. for (int i = 0; i &lt; n; i++)
  5. printf(&quot;%s%d&quot;, i&gt;0 ? &quot;, &quot; : &quot;&quot;, a[i]);
  6. printf(&quot;\n&quot;);
  7. }
  8. int cmp_a2(const void *v, const void*w) {
  9. const int *a = v;
  10. const int *b = w;
  11. if (a[0] &lt; b[0]) return -1;
  12. if (a[0] &gt; b[0]) return 1;
  13. if (a[1] &lt; b[1]) return -1;
  14. if (a[1] &gt; b[1]) return 1;
  15. return 0;
  16. }
  17. void order_array(int *vec, size_t n) {
  18. int (*a2)[2] = malloc(n * 2 * sizeof(int));
  19. size_t zeros = 0;
  20. for (int i = 0; i &lt; n; i++) {
  21. a2[i - zeros][0] = vec[i];
  22. a2[i - zeros][1] = i;
  23. zeros += (vec[i] == 0);
  24. }
  25. qsort(a2, n - zeros, sizeof(a2[0]), cmp_a2);
  26. for (int i = 0; i &lt; n - zeros; i++) {
  27. vec[a2[i][1]] = i + 1;
  28. }
  29. free(a2);
  30. }
  31. int main(int argc, char *argv[]) {
  32. int a[] = {5,0,23,2,2,0};
  33. size_t n = sizeof(a) / sizeof(*a);
  34. print_array(a, n);
  35. order_array(a, n);
  36. print_array(a, n);
  37. }

答案2

得分: -1

你可以使用标准库函数 qsort 和 bsearch 来解决这个问题。以下是一个开始：

  1. #include <assert.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  5. #define LEN(arr) (sizeof (arr) / sizeof (arr)[0])
  7. int ElemDiff(const void *leftElemPtr, const void *rightElemPtr) {
  8.     return *(int *) leftElemPtr - *(int *) rightElemPtr;
  9. }
  11. int main(void)
  12. {
  13.     int vec[] = {5, 0, 23, 2, 2, 0};
  14.     int sortedVec[LEN(vec)];
  15.     int i, *tail;
  17.     memcpy(sortedVec, vec, sizeof (vec));
  18.     qsort(sortedVec, LEN(sortedVec), sizeof sortedVec[0], ElemDiff);
  19.     for (i = 0; i < LEN(vec); i++) {
  20.         tail = bsearch(vec + i, sortedVec, LEN(sortedVec), sizeof sortedVec[0], ElemDiff);
  21.         assert(tail != NULL);
  22.         printf("%lld ", tail - sortedVec);
  23.     }
  24.     putchar('\n');
  26.     return 0;
  27. }

这会打印：

  1. 4 0 5 2 2 0
英文:

You can use the the standard library functions qsort and bsearch to solve the problem. Here is a start:

  1. #include &lt;assert.h&gt;
  2. #include &lt;stdio.h&gt;
  3. #include &lt;stdlib.h&gt;
  4. #define LEN(arr) (sizeof (arr) / sizeof (arr)[0])
  5. int ElemDiff(const void *leftElemPtr, const void *rightElemPtr) {
  6. return *(int *) leftElemPtr - *(int *) rightElemPtr;
  7. }
  8. int main(void)
  9. {
  10. int vec[] = {5, 0, 23, 2, 2, 0};
  11. int sortedVec[LEN(vec)];
  12. int i, *tail;
  13. memcpy(sortedVec, vec, sizeof (vec));
  14. qsort(sortedVec, LEN(sortedVec), sizeof sortedVec[0], ElemDiff);
  15. for (i = 0; i &lt; LEN(vec); i++) {
  16. tail = bsearch(vec + i, sortedVec, LEN(sortedVec), sizeof sortedVec[0], ElemDiff);
  17. assert(tail != NULL);
  18. printf(&quot;%lld &quot;, tail - sortedVec);
  19. }
  20. putchar(&#39;\n&#39;);
  21. return 0;
  22. }

This will print

  1. 4 0 5 2 2 0

huangapple
  • 本文由 发表于 2023年4月4日 16:00:00
  • 转载请务必保留本文链接：https://go.coder-hub.com/75926871.html
  • arrays
  • c
  • list
  • sorting
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定