假设您有一个未签名int的列表。假设有些元素等于0，您希望将它们推回。当前我使用此代码（list是指向大小为n的无符号整数列表的指针
for (i = 0; i < n; ++i)
{
if (list[i])
continue;
int j;
for (j = i + 1; j < n && !list[j]; ++j);
int z;
for (z = j + 1; z < n && list[z]; ++z);
if (j == n)
break;
memmove(&(list[i]), &(list[j]), sizeof(unsigned int) * (z - j)));
int s = z - j + i;
for(j = s; j < z; ++j)
list[j] = 0;
i = s - 1;
}
你能想出一种更有效的方法来完成这项任务吗？
这个片段纯粹是理论上的，在生产代码中，list的每个元素都是一个64字节的结构
编辑：
我会发布我的解决方案。多谢乔纳森·莱夫勒。
void RemoveDeadParticles(int * list, int * n)
{
int i, j = *n - 1;
for (; j >= 0 && list[j] == 0; --j);
for (i = 0; i <= j; ++i)
{
if (list[i])
continue;
memcpy(&(list[i]), &(list[j]), sizeof(int));
list[j] = 0;
for (; j >= 0 && list[j] == 0; --j);
if (i == j)
break;
}
*n = i;
}
最佳答案
下面的代码实现了我在注释中概述的线性算法：
如果你小心的话，有一个直线O（N）算法；你的是O（N2）。考虑到这个顺序是不相关的，每次在数组中遇到一个0时，就用最后一个可能不是0的元素交换它这是一次通过数组。需要注意边界条件。
需要小心；测试代码中list3[]的酸性测试导致了悲伤，直到我得到正确的边界条件请注意，大小为0或1的列表已按正确顺序排列。
#include <stdio.h>
#define DIM(x) (sizeof(x)/sizeof(*(x)))
extern void shunt_zeroes(int *list, size_t n);
void shunt_zeroes(int *list, size_t n)
{
if (n > 1)
{
size_t tail = n;
for (size_t i = 0; i < tail - 1; i++)
{
if (list[i] == 0)
{
while (--tail > i + 1 && list[tail] == 0)
;
if (tail > i)
{
int t = list[i];
list[i] = list[tail];
list[tail] = t;
}
}
}
}
}
static void dump_list(const char *tag, int *list, size_t n)
{
printf("%-8s", tag);
for (size_t i = 0; i < n; i++)
{
printf("%d ", list[i]);
}
putchar('\n');
fflush(0);
}
static void test_list(int *list, size_t n)
{
dump_list("Before:", list, n);
shunt_zeroes(list, n);
dump_list("After:", list, n);
}
int main(void)
{
int list1[] = { 1, 0, 2, 0, 3, 0, 4, 0, 5 };
int list2[] = { 1, 2, 2, 0, 3, 0, 4, 0, 0 };
int list3[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
int list4[] = { 0, 1 };
int list5[] = { 0, 0 };
int list6[] = { 0 };
test_list(list1, DIM(list1));
test_list(list2, DIM(list2));
test_list(list3, DIM(list3));
test_list(list4, DIM(list4));
test_list(list5, DIM(list5));
test_list(list6, DIM(list6));
}
示例运行：
$ shuntzeroes
Before: 1 0 2 0 3 0 4 0 5
After: 1 5 2 4 3 0 0 0 0
Before: 1 2 2 0 3 0 4 0 0
After: 1 2 2 4 3 0 0 0 0
Before: 0 0 0 0 0 0 0 0 0
After: 0 0 0 0 0 0 0 0 0
Before: 0 1
After: 1 0
Before: 0 0
After: 0 0
Before: 0
After: 0
$
代码复杂性
我断言这个问题和UmNyobe的answer中的原始代码是O（N2），但这是O（N）。然而，在这三种情况下，一个循环中都有一个循环；为什么当其他的是O（N2）时，这个答案是线性的？
好问题！
不同的是，我的代码中的内部循环向后扫描数组，找到一个非零值与刚刚找到的零值进行交换。这样做，就减少了外环要做的工作。因此，
i索引向前扫描一次，并且tail索引向后扫描一次，直到两个在中间相遇。相比之下，在原始代码中，内部循环从当前索引开始，每次都向前工作到结尾，这导致了二次行为。复杂性论证
UmNyobe和Argeman都断言code的答案中的UmNyobe是线性的O（N），而不是二次的O（N2），正如我在对答案的评论中断言的那样。给出两个相反的观点，我编写了一个程序来检查我的断言。
这是一个测试的结果，充分证明了这一点。
"timer.h"描述的代码是我的平台中立计时接口；它的代码可以根据请求提供（参见myprofile）测试是在一台MacBook Pro上进行的，它的英特尔酷睿i7、Mac OS X 10.7.5、GCC 4.7.1均为2.3 GHz。我对UmNyobe代码所做的唯一更改是将数组索引从
int更改为size_t，以便外部函数接口与我的相同，并保持内部一致性。测试代码包括一个热身练习，以显示这些函数产生了等价的答案；UmNyobe的答案保留了数组中的顺序，而mine则没有。我从计时数据中漏掉了那个信息。
$ make on2
gcc -O3 -g -I/Users/jleffler/inc -std=c99 -Wall -Wextra -L/Users/jleffler/lib/64 on2.c -ljl -o on2
$
时机
设置1：在没有UmNyobe修正算法的旧版本测试工具上。
shunt_zeroes: 100 0.000001
shunt_zeroes: 1000 0.000005
shunt_zeroes: 10000 0.000020
shunt_zeroes: 100000 0.000181
shunt_zeroes: 1000000 0.001468
pushbackzeros: 100 0.000001
pushbackzeros: 1000 0.000086
pushbackzeros: 10000 0.007003
pushbackzeros: 100000 0.624870
pushbackzeros: 1000000 46.928721
shunt_zeroes: 100 0.000000
shunt_zeroes: 1000 0.000002
shunt_zeroes: 10000 0.000011
shunt_zeroes: 100000 0.000113
shunt_zeroes: 1000000 0.000923
pushbackzeros: 100 0.000001
pushbackzeros: 1000 0.000097
pushbackzeros: 10000 0.007077
pushbackzeros: 100000 0.628327
pushbackzeros: 1000000 41.512151
这台机器最多只能承受很轻的背景负荷；例如，我暂停了通常在后台运行的Boinc计算。具体的时间安排并不像我希望的那样稳定，但结论是明确的。
我的算法是O（N）
UmNyobe（原始）算法是O（N2）
集合2：使用UmNyobe的修正算法
还包括Patrik的前后算法和Wildplasser的算法（见下面的源代码）；测试程序从
on2重命名为timezeromoves。$ ./timezeromoves -c -m 100000 -n 1
shunt_zeroes: (Jonathan)
shunt_zeroes: 100 0.000001
shunt_zeroes: 1000 0.000003
shunt_zeroes: 10000 0.000018
shunt_zeroes: 100000 0.000155
RemoveDead: (Patrik)
RemoveDead: 100 0.000001
RemoveDead: 1000 0.000004
RemoveDead: 10000 0.000018
RemoveDead: 100000 0.000159
pushbackzeros2: (UmNyobe)
pushbackzeros2: 100 0.000001
pushbackzeros2: 1000 0.000005
pushbackzeros2: 10000 0.000031
pushbackzeros2: 100000 0.000449
list_compact: (Wildplasser)
list_compact: 100 0.000004
list_compact: 1000 0.000005
list_compact: 10000 0.000036
list_compact: 100000 0.000385
shufflezeroes: (Patrik)
shufflezeroes: 100 0.000003
shufflezeroes: 1000 0.000069
shufflezeroes: 10000 0.006685
shufflezeroes: 100000 0.504551
pushbackzeros: (UmNyobe)
pushbackzeros: 100 0.000003
pushbackzeros: 1000 0.000126
pushbackzeros: 10000 0.011719
pushbackzeros: 100000 0.480458
$
这表明UmNyobe的修正算法是O（N），其他解也是O（N）。原始代码显示为O（N2），正如UmNyobe的原始算法一样。
来源
这是修改后的测试程序（重命名为
testzeromoves.c）。算法实现在顶部。测试线束在注释“测试线束”之后。该命令可以执行检查或计时，或者两者都执行（默认）；默认情况下，它执行两次迭代；默认情况下，它的大小可达一百万个条目。可以使用-c标志省略检查，-t标志省略定时，-n标志指定迭代次数，以及-m标志指定最大大小。小心不要超过一百万；你可能会遇到VLA（可变长度数组）吹堆栈的问题。修改代码以使用malloc()和free()是很容易的；但是似乎没有必要。#include <string.h>
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
extern void shunt_zeroes(int *list, size_t n);
extern void pushbackzeros(int *list, size_t n);
extern void pushbackzeros2(int *list, size_t n);
extern void shufflezeroes(int *list, size_t n);
extern void RemoveDead(int *list, size_t n);
extern void list_compact(int *arr, size_t cnt);
void list_compact(int *arr, size_t cnt)
{
size_t dst,src,pos;
/* Skip leading filled area; find start of blanks */
for (pos=0; pos < cnt; pos++) {
if ( !arr[pos] ) break;
}
if (pos == cnt) return;
for(dst= pos; ++pos < cnt; ) {
/* Skip blanks; find start of filled area */
if ( !arr[pos] ) continue;
/* Find end of filled area */
for(src = pos; ++pos < cnt; ) {
if ( !arr[pos] ) break;
}
if (pos > src) {
memmove(arr+dst, arr+src, (pos-src) * sizeof arr[0] );
dst += pos-src;
}
}
}
/* Cannot change j to size_t safely; algorithm relies on it going negative */
void RemoveDead(int *list, size_t n)
{
int i, j = n - 1;
for (; j >= 0 && list[j] == 0; --j)
;
for (i = 0; i <= j; ++i)
{
if (list[i])
continue;
memcpy(&(list[i]), &(list[j]), sizeof(int));
list[j] = 0;
for (; j >= 0 && list[j] == 0; --j);
if (i == j)
break;
}
}
void shufflezeroes(int *list, size_t n)
{
for (size_t i = 0; i < n; ++i)
{
if (list[i])
continue;
size_t j;
for (j = i + 1; j < n && !list[j]; ++j)
;
size_t z;
for (z = j + 1; z < n && list[z]; ++z)
;
if (j == n)
break;
memmove(&(list[i]), &(list[j]), sizeof(int) * (z - j));
size_t s = z - j + i;
for(j = s; j < z; ++j)
list[j] = 0;
i = s - 1;
}
}
static int nextZero(int* list, size_t start, size_t n){
size_t i = start;
while(i < n && list[i])
i++;
return i;
}
static int nextNonZero(int* list, size_t start, size_t n){
size_t i = start;
while(i < n && !list[i])
i++;
return i;
}
void pushbackzeros(int* list, size_t n){
size_t i = 0;
size_t j = 0;
while(i < n && j < n){
i = nextZero(list,i, n);
j = nextNonZero(list,i, n);
if(i >= n || j >=n)
return;
list[i] = list[j];
list[j] = 0;
}
}
/* Amended algorithm */
void pushbackzeros2(int* list, size_t n){
size_t i = 0;
size_t j = 0;
while(i < n && j < n){
i = nextZero(list, i, n);
j = nextNonZero(list, MAX(i,j), n);
if(i >= n || j >=n)
return;
list[i] = list[j];
list[j] = 0;
}
}
void shunt_zeroes(int *list, size_t n)
{
if (n > 1)
{
size_t tail = n;
for (size_t i = 0; i < tail - 1; i++)
{
if (list[i] == 0)
{
while (--tail > i + 1 && list[tail] == 0)
;
if (tail > i)
{
int t = list[i];
list[i] = list[tail];
list[tail] = t;
}
}
}
}
}
/* Test Harness */
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include "timer.h"
#define DIM(x) (sizeof(x)/sizeof(*(x)))
typedef void (*Shunter)(int *list, size_t n);
typedef struct FUT /* FUT = Function Under Test */
{
Shunter function;
const char *name;
const char *author;
} FUT;
static int tflag = 1; /* timing */
static int cflag = 1; /* checking */
static size_t maxsize = 1000000;
static void dump_list(const char *tag, int *list, size_t n)
{
printf("%-8s", tag);
for (size_t i = 0; i < n; i++)
{
printf("%d ", list[i]);
}
putchar('\n');
fflush(0);
}
static void test_list(int *list, size_t n, Shunter s)
{
dump_list("Before:", list, n);
(*s)(list, n);
dump_list("After:", list, n);
}
static void list_of_tests(const FUT *f)
{
int list1[] = { 1, 0, 2, 0, 3, 0, 4, 0, 5 };
int list2[] = { 1, 2, 2, 0, 3, 0, 4, 0, 0 };
int list3[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0 };
int list4[] = { 0, 1 };
int list5[] = { 0, 0 };
int list6[] = { 0 };
test_list(list1, DIM(list1), f->function);
test_list(list2, DIM(list2), f->function);
test_list(list3, DIM(list3), f->function);
test_list(list4, DIM(list4), f->function);
test_list(list5, DIM(list5), f->function);
test_list(list6, DIM(list6), f->function);
}
static void test_timer(int *list, size_t n, const FUT *f)
{
Clock t;
clk_init(&t);
clk_start(&t);
f->function(list, n);
clk_stop(&t);
char buffer[32];
printf("%-15s %7zu %10s\n", f->name, n, clk_elapsed_us(&t, buffer, sizeof(buffer)));
fflush(0);
}
static void gen_test(size_t n, const FUT *f)
{
int list[n];
for (size_t i = 0; i < n/2; i += 2)
{
list[2*i+0] = i;
list[2*i+1] = 0;
}
test_timer(list, n, f);
}
static void timed_run(const FUT *f)
{
printf("%s (%s)\n", f->name, f->author);
if (cflag)
list_of_tests(f);
if (tflag)
{
for (size_t n = 100; n <= maxsize; n *= 10)
gen_test(n, f);
}
}
static const char optstr[] = "cm:n:t";
static const char usestr[] = "[-ct][-m maxsize][-n iterations]";
int main(int argc, char **argv)
{
FUT functions[] =
{
{ shunt_zeroes, "shunt_zeroes:", "Jonathan" }, /* O(N) */
{ RemoveDead, "RemoveDead:", "Patrik" }, /* O(N) */
{ pushbackzeros2, "pushbackzeros2:", "UmNyobe" }, /* O(N) */
{ list_compact, "list_compact:", "Wildplasser" }, /* O(N) */
{ shufflezeroes, "shufflezeroes:", "Patrik" }, /* O(N^2) */
{ pushbackzeros, "pushbackzeros:", "UmNyobe" }, /* O(N^2) */
};
enum { NUM_FUNCTIONS = sizeof(functions)/sizeof(functions[0]) };
int opt;
int itercount = 2;
while ((opt = getopt(argc, argv, optstr)) != -1)
{
switch (opt)
{
case 'c':
cflag = 0;
break;
case 't':
tflag = 0;
break;
case 'n':
itercount = atoi(optarg);
break;
case 'm':
maxsize = strtoull(optarg, 0, 0);
break;
default:
fprintf(stderr, "Usage: %s %s\n", argv[0], usestr);
return(EXIT_FAILURE);
}
}
for (int i = 0; i < itercount; i++)
{
for (int j = 0; j < NUM_FUNCTIONS; j++)
timed_run(&functions[j]);
if (tflag == 0)
break;
cflag = 0; /* Don't check on subsequent iterations */
}
return 0;
}
关于c - 高效列表压缩，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12515755/