有快速从数组中提取全部偶数项的算法吗?

C语言 码拜 9年前 (2016-02-01) 1293次浏览
源数据数组, 如 char a[640 * 480],
要将全部偶数项,即a[0],a[2],a[4]…a[640*480-2]复制到 char b[640*240]数组。
直接的方法是

int i;
int j = 0;
for(i=0; i<640*480; i++)
{
    if(i % 0 == 0) 
    {
        b[j] = a[i];
        j++;
    }
}

由于是在嵌入式系统下运行,且一秒钟要做20~30次。负担太重了。
问一下各位有没有可以快速实现的方法?
谢谢

解决方案:5分
int  i;
int  j = 0;
for(i=0; i<640*480; i+=2,j++)
{  
        b[j] = a[i];
}

那个 求余算法是不必要的

解决方案:2分
int i;
for(i = 0; i < 640 * 480; i +=2)
{
    b[i / 2] = a[i];
}

其实j也是不必要的

解决方案:2分
for(i=0; i<640*480/2; i++)
		b[i] = a[i * 2];

乘以2的倍数的常数优化后会变成移位运算

解决方案:5分
int  i;
int  j = 0;
char * b[640*240]
for(i=0; i<640*480; i+=2,j++)
{  
        b[j] = &a[i];
}

以后再也不用复制了

解决方案:10分
一般情况下,用最简洁易懂的方式写出的c代码,靠编译器优化往往比手工优化更有效。
以下面的代码为例:

// test1.c
#include <stdio.h>
#include <stdint.h>
#include <time.h>
#define GET_EVEN_BYTES(x1, x2)  (x1 & 0xff) | (((x1 >> 16) & 0xff) << 8) | \
								(((x2 & 0xff)) << 16) | (((x2 >> 16) & 0xff) << 24) 
static void func1(const char * a, size_t size, char * b)
{
	uint32_t * p_a = (uint32_t *)a;
	uint32_t * p_end = (uint32_t *)(a + size);
	uint32_t * p_b = (uint32_t *)b;
	
	while(p_a < p_end)
	{
		*p_b++ = (uint32_t)GET_EVEN_BYTES(p_a[0], p_a[1]);
		p_a += 2;		
	}
}
static void func2(const char * a, size_t size, char * b)
{
	size_t i;
	size /= 2;
	for(i = 0; i < size; ++i)
		b[i] = a[i * 2];
	
}
int main(int argc, char **argv)
{
	size_t size;								
	char a[640 * 480] = {0x11,0x22,0x33,0x44, 0x55, 0x66, 0x77, 0x88};
	char b[640 * 240] = {0};
	
	size = sizeof(a);
	
	clock_t t;
	int i;
	const int ROUNDS = 10000;
	
	t = clock();
	for(i = 0; i < ROUNDS; ++i)
	{
		func1(a, size, b);
	}
	t = clock() - t;
	
	printf("func1 time: %f\n", (double)t / (double)CLOCKS_PER_SEC);
	
	t = clock();
	for(i = 0; i < ROUNDS; ++i)
	{
		func2(a, size, b);
	}
	t = clock() - t;
	
	printf("func2 time: %f\n", (double)t / (double)CLOCKS_PER_SEC);
	
	
	
	for(i = 0; i < 16; ++i)
	{
		printf("%.2x ", b[i]);
	}
	printf("\n");
	
	return 0;
}

func1是用手工优化的方式来实现,将位运算的结果赋值给uint类型,这通常比直接逐字节赋值要快很多。
func2是用最简单易懂的方式来实现。
假如不通过编译器优化:
$ gcc -o test1 test1.c
$ ./test1
func1 time: 1.317621
func2 time: 4.110902
-O2 优化下:
$ gcc -O2 -o test1 test1.c
$ ./test1
func1 time: 0.688920
func2 time: 1.076817
此时,手工优化的代码(func1)均比简洁方式的代码(func2)快很多;但是,
-O6优化下,简洁方式的代码效率胜出了:
$ gcc -O6 -o test1 test1.c
$ ./test1
func1 time: 0.255404
func2 time: 0.207539

解决方案:2分
假如不需要存储的话,可以用#8的方法:
char a[640 * 480];
short *b = (short *)a;
之后直接用(char)b[xxx]来访问。
要存储的话可以考虑SSE指令,pshufb、packuswb之类的,假如你的架构支持的话。
解决方案:2分
嵌入式的话可以看看芯片提供的接口,这种取值使用dma是最快的,现在很多图像处理的dsp都提供了这样的dma操作。
解决方案:2分
LZ说的是“源数据数组, 如 char a[640 * 480]”,大嘴你非要整成int/short…
解决方案:10分
最近本人好象眼睛里面揉进沙子了。

#include <stdio.h>
char a[640*480];
char b[640*480/2];
void func1() {
    int i;
    int j = 0;
    for (i=0; i<640*480; i++) {
        if (i % 2 == 0) {
            b[j] = a[i];
            j++;
        }
    }
}
void func2() {
    __asm {
        push esi
        push edi
        push ecx
        lea esi,a
        lea edi,b
        mov ecx,640*480/2
        cld
    step1:
        lodsb
        stosb
        inc esi
        loop step1
        pop ecx
        pop edi
        pop esi
    }
}
int main() {
    for (int i=0; i<640*480; i++) a[i]=(char)(i%100);
    func1();
    printf("%d\n",b[640*480/2-1]);
    b[640*480/2-1]=0;
    func2();
    printf("%d\n",b[640*480/2-1]);
    return 0;
}
//98
//98
//

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明有快速从数组中提取全部偶数项的算法吗?
喜欢 (0)
[1034331897@qq.com]
分享 (0)