一个快速得到bit位索引的算法 - 第5页 - 算法交流 - 数学研发论坛

无心人 发表于 2008-3-11 11:39:18

//////////////////
E:\yaojialin\FindBits\Debug>findbits
yaos: 345.155
yaos_1: 343.801
yaos_2: 165.216
GXQ: 169.795
GXQ used BT: 249.897

E:\yaojialin\FindBits\Debug>findbits
yaos: 344.554
yaos_1: 343.643
yaos_2: 165.530
GXQ: 170.582
GXQ used BT: 249.942

E:\yaojialin\FindBits\Debug>findbits
yaos: 344.908
yaos_1: 346.577
yaos_2: 166.864
GXQ: 171.155
GXQ used BT: 252.270

E:\yaojialin\FindBits\Debug>findbits
yaos: 344.171
yaos_1: 346.151
yaos_2: 166.900
GXQ: 171.366
GXQ used BT: 252.932

E:\yaojialin\FindBits\Debug>findbits
yaos: 344.697
yaos_1: 343.413
yaos_2: 165.558
GXQ: 171.240
GXQ used BT: 249.706

E:\yaojialin\FindBits\Debug>findbits
yaos: 345.192
yaos_1: 343.298
yaos_2: 165.210
GXQ: 170.112
GXQ used BT: 250.019
//////////////////

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

__int64 GetCPUCounter(void)
{
__asm rdtsc;
}

DWORD find_empty(DWORD a, DWORD index)
{
return 0;
}

DWORD find_by_yaos(DWORD a, DWORD index)
{
__asm
{
   mov edx, a;
   mov edi, dword ptr index;
   xor eax, eax;
loop1:
   bsr ecx, edx;
   je exit1;
   btr edx, ecx;
   mov dwordptr , ecx;
   inc eax;
   jmp loop1;
exit1:
   mov dword ptr , -1;
}
}

void find_by_yaos_1(DWORD a, DWORD index)
{
__asm
{
mov eax, a
mov edi, dword ptr
loop1:
bsr ebx, eax
je exit1
btr eax, ebx
mov dword ptr , ebx
add edi, 4
jmp loop1
exit1:
mov dword ptr , -1
}
}

void find_by_yaos_2(DWORD a, DWORD index)
{
__asm
{
mov eax, a
mov edi, dword ptr
mov ecx, 0
loop1:
shr eax, 1
jnc loop2
mov dword ptr , ecx
add edi, 4
loop2:
inc ecx
cmp ecx, 32
jne loop1
mov dword ptr , -1

}
}

DWORD find_by_GxQ(DWORD code, DWORD index)
{
__asm
{
   mov ecx, code;

   xor eax, eax;

   shr ecx, 1;
   mov dword ptr, 0;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 1;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 2;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 3;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 4;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 5;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 6;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 7;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 8;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 9;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 10;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 11;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 12;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 13;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 14;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 15;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 16;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 17;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 18;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 19;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 20;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 21;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 22;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 23;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 24;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 25;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 26;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 27;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 28;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 29;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 30;
   adc eax, 0;

   shr ecx, 1;
   mov dword ptr, 31;
   adc eax, 0;

   // 休止符
   mov dword ptr, -1;
}
}

DWORD find_by_GxQ_bt(DWORD code, DWORD index)
{
__asm
{
   mov ecx, code;

   xor eax, eax;

   bt    ecx, 0;
   mov dword ptr, 0;
   adc eax, 0;

   bt    ecx, 1;
   mov dword ptr, 1;
   adc eax, 0;

   bt ecx, 2;
   mov dword ptr, 2;
   adc eax, 0;

   bt ecx, 3;
   mov dword ptr, 3;
   adc eax, 0;

   bt ecx, 4;
   mov dword ptr, 4;
   adc eax, 0;

   bt ecx, 5;
   mov dword ptr, 5;
   adc eax, 0;

   bt ecx, 6;
   mov dword ptr, 6;
   adc eax, 0;

   bt ecx, 7;
   mov dword ptr, 7;
   adc eax, 0;

   bt ecx, 8;
   mov dword ptr, 8;
   adc eax, 0;

   bt ecx, 9;
   mov dword ptr, 9;
   adc eax, 0;

   bt ecx, 10;
   mov dword ptr, 10;
   adc eax, 0;

   bt ecx, 11;
   mov dword ptr, 11;
   adc eax, 0;

   bt ecx, 12;
   mov dword ptr, 12;
   adc eax, 0;

   bt ecx, 13;
   mov dword ptr, 13;
   adc eax, 0;

   bt ecx, 14;
   mov dword ptr, 14;
   adc eax, 0;

   bt ecx, 15;
   mov dword ptr, 15;
   adc eax, 0;

   bt ecx, 16;
   mov dword ptr, 16;
   adc eax, 0;

   bt ecx, 17;
   mov dword ptr, 17;
   adc eax, 0;

   bt ecx, 18;
   mov dword ptr, 18;
   adc eax, 0;

   bt ecx, 19;
   mov dword ptr, 19;
   adc eax, 0;

   bt ecx, 20;
   mov dword ptr, 20;
   adc eax, 0;

   bt ecx, 21;
   mov dword ptr, 21;
   adc eax, 0;

   bt ecx, 22;
   mov dword ptr, 22;
   adc eax, 0;

   bt ecx, 23;
   mov dword ptr, 23;
   adc eax, 0;

   bt ecx, 24;
   mov dword ptr, 24;
   adc eax, 0;

   bt ecx, 25;
   mov dword ptr, 25;
   adc eax, 0;

   bt ecx, 26;
   mov dword ptr, 26;
   adc eax, 0;

   bt ecx, 27;
   mov dword ptr, 27;
   adc eax, 0;

   bt ecx, 28;
   mov dword ptr, 28;
   adc eax, 0;

   bt ecx, 29;
   mov dword ptr, 29;
   adc eax, 0;

   bt ecx, 30;
   mov dword ptr, 30;
   adc eax, 0;

   bt ecx, 31;
   mov dword ptr, 31;
   adc eax, 0;

   // 休止符
   mov dword ptr, -1;
}
}

int main(int argc, char * argv[])
{
::SetThreadPriority(::GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL);
LARGE_INTEGER lTimestart, lTimeEnd, liFreq;
__int64 CounterStart, CounterStop;
double dbMs;

DWORD index;

QueryPerformanceCounter(&lTimestart);
for(DWORD i = 0; i < 1000000; i++){
find_by_yaos(0xFFFFFFFF,index);// 调用bit扫描函数
}
QueryPerformanceCounter(&lTimeEnd);
QueryPerformanceFrequency(&liFreq);
dbMs = ((double) (lTimeEnd.QuadPart - lTimestart.QuadPart)) * 1000.0/ (double)liFreq.QuadPart;
printf("yaos: %.3f\n", dbMs);

QueryPerformanceCounter(&lTimestart);
for(DWORD i = 0; i < 1000000; i++){
find_by_yaos_1(0xFFFFFFFF,index);// 调用bit扫描函数
}
QueryPerformanceCounter(&lTimeEnd);
QueryPerformanceFrequency(&liFreq);
dbMs = ((double) (lTimeEnd.QuadPart - lTimestart.QuadPart)) * 1000.0 / (double)liFreq.QuadPart;
printf("yaos_1: %.3f\n", dbMs);

QueryPerformanceCounter(&lTimestart);
for(DWORD i = 0; i < 1000000; i++){
find_by_yaos_2(0xFFFFFFFF,index);// 调用bit扫描函数
}
QueryPerformanceCounter(&lTimeEnd);
QueryPerformanceFrequency(&liFreq);
dbMs = ((double) (lTimeEnd.QuadPart - lTimestart.QuadPart)) * 1000.0 / (double)liFreq.QuadPart;
printf("yaos_2: %.3f\n", dbMs);

QueryPerformanceCounter(&lTimestart);
for(DWORD i = 0; i <1000000; i++){
find_by_GxQ(0xFFFFFFFF,index);// 调用bit扫描函数
}
QueryPerformanceCounter(&lTimeEnd);
QueryPerformanceFrequency(&liFreq);
dbMs = ((double) (lTimeEnd.QuadPart - lTimestart.QuadPart)) * 1000.0 / (double)liFreq.QuadPart;
printf("GXQ: %.3f\n", dbMs);

QueryPerformanceCounter(&lTimestart);
for(DWORD i = 0; i <1000000; i++){
find_by_GxQ_bt(0xFFFFFFFF,index);// 调用bit扫描函数
}
QueryPerformanceCounter(&lTimeEnd);
QueryPerformanceFrequency(&liFreq);
dbMs = ((double) (lTimeEnd.QuadPart - lTimestart.QuadPart)) * 1000.0 / (double)liFreq.QuadPart;
printf("GXQ used BT: %.3f\n", dbMs);

return 0;
}

gxqcn 发表于 2008-3-11 12:04:14

验证了我在 35# 的几个提醒。:)

其实，find_by_yaos_2() 还可进一步优化，如下：
void find_by_yaos_3(DWORD a, DWORD index)
{
__asm
{
mov eax, a
mov edi, dword ptr index
mov ecx, 32
loop1:
shr eax, 1
jnc loop2
mov dword ptr , ecx
add edi, 4
loop2:
sub ecx, 1
jne loop1

mov dword ptr , -1
}
}
从而在循环中省掉了一条比较指令。

无心人 发表于 2008-3-11 13:49:01

呵呵
不用我说吧
自己看有什么问题

不是不能用loop或者loopne

关键是索引是从0-31的啊

void find_by_yaos_3(DWORD a, DWORD index)
{
   __asm
   {
            mov eax, a
            mov edi, dword ptr index
            mov ecx, 32
loop1:
            shr eax, 1
            jnc loop2
            mov dword ptr , ecx
            add edi, 4
loop2:
            sub ecx, 1
            jne loop1

            mov dword ptr , -1
   }
}

无心人 发表于 2008-3-11 13:57:50

我这么改的

void find_by_yaos_3(DWORD a, DWORD index)
{
__asm
{
mov eax, a
mov edi, dword ptr
mov ecx, 32
loop1:
shl eax, 1
jnc loop2
mov dword ptr , ecx
dec dword ptr
add edi, 4
loop2:
sub ecx, 1
jmpne loop1
mov dword ptr , -1

}
}

void find_by_yaos_4(DWORD a, DWORD index)
{
__asm
{
mov eax, a
mov edi, dword ptr
mov ecx, 32
loop1:
shl eax, 1
jnc loop2
mov dword ptr , ecx
dec dword ptr
add edi, 4
loop2:
loopne loop1
mov dword ptr , -1

}
}

结论时间2>4>3

无心人 发表于 2008-3-11 14:22:08

分析结果

bit中1越少find_by_yaos越快
在小数字超过GxQ很多
普遍情况find_by_yaos_3, find_by_yaos_4获胜
小数字find_by_yaos_4优于find_by_yaos

gxqcn 发表于 2008-3-12 07:35:31

我在 42# 对你的汇编优化时，没有注意到 ecx 同时还作为将要存的index，对不起。

但你后来的改动也改变了数据的存放格式，由先前默认的升序变成了降序。

无心人 发表于 2008-3-12 07:49:46

已经到这个方法的极限了
或者有方法判断小于0时跳出
========================
除非不用移位做
还有其他测试bit的方法否?

gxqcn 发表于 2008-3-12 08:01:25

你还可试着利用 shr/shl 产生的 ZF 标记位来提前跳出循环（若同时 CF=1，要记得存储index）。

无心人 发表于 2008-3-12 08:35:26

两个改进, 无论什么情况
均比find_by_yaos_3, find_by_yaos_2快
但比较不出两种写法的差异

void find_by_yaos_5(DWORD a, DWORD index)
{
__asm
{
mov eax, a
mov edi, dword ptr
mov ecx, 31
loop1:
shl eax, 1
jnc loop2
mov dword ptr , ecx
// dec dword ptr
add edi, 4
loop2:
sub ecx, 1
jns loop1
mov dword ptr , -1

}
}

void find_by_yaos_6(DWORD a, DWORD index)
{
__asm
{
mov eax, a
mov edi, dword ptr
mov ecx, 31
loop1:
shl eax, 1
jnc loop2
mov dword ptr , ecx
// dec dword ptr
add edi, 4
loop2:
sub ecx, 1
jnc loop1
mov dword ptr , -1

}
}

无心人 发表于 2008-3-12 08:41:09

对着void find_by_yaos_6(DWORD a, DWORD index)
发了一会儿呆
无论如何添加jz或者je均要增加至少三条指令
还是不用了
====================================
顺便说下, 最近的改进
增加检测bit=1的数量的语句是很容易的
也应该增加不了多少时间

页: 1 2 3 4 [5] 6 7

数学研发论坛's Archiver