修改后的代码如下:
此外如果内存还是太小,宏STABLE还可以改小一半左右.但是需要注意STABLE和WALK必须互素.// chp.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#define N 8
#define BITS (N*N)
typedef unsigned long long SET;
SET nghb;
#define EMPTY_SET 0LL
#define INDEX(x,y) ((x)*N+(y))
#define GET_X(ind) ((ind)/N)
#define GET_Y(ind) ((ind)%N)
#define ADD_INDEX(s, ind)((s)|=1LL<<(ind))
#define TEST_INDEX(s, ind)(((s)&(1LL<<(ind)))!=0)
#define CORNMASK (3|(3<<N))
#define TEST_BIT(x, b) (((x)&(1LL<<(b)))!=0)
#define SET_BIT(x, b) ((x)|=(1LL<<(b)))
#define GET_CORN(x)(((x)&3)| (((x)>>N)&3)<<2)
#define DISP_CORN(x) (((x)&3)| ((((x)>>2)&3)<<N))
#define ECVALUE(x) (((x)&~CORNMASK)|DISP_CORN(cr))
#define STABLE 50000033
#define WALK 1000
int hc;
int ec;
int nec;
int lec;
long long htable;
//long long htable2;
char cr={1,-1,-1,-1,-1,-1,-1,-1,4,-1,5,-1,3,-1,11,7};
char rc={-1,0,-1,12,8,10,-1,15,-1,-1,-1,14,-1,-1,-1,-1};
FILE *fout;
void dump(long long v)
{
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(TEST_BIT(v,i*N+j)){
fprintf(fout,"1 ");
}else{
fprintf(fout,"0 ");
}
}
fprintf(fout,"\n");
}
fprintf(fout,"\n");
}
void copy_ec(long long *p)
{
int i,t;
for(i=0,t=0;i<STABLE;i++){
if(htable!=-1LL){
if(cr)]!=-1){
p=htable;
}
}
}
}
void dump_ec(long long htable[])
{
int i;
fout = fopen("dump.txt","w");
for(i=0;i<STABLE;i++){
if(htable!=-1LL){
if(cr)]!=-1){
dump(htable);
}
}
}
fclose(fout);
}
void init()
{
memset(htable,-1,sizeof(htable));
// memset(htable2,-1,sizeof(htable2));
}
int hash(SET s)
{
return (int)(s%STABLE);
}
int add_hash(long long htable[],long long key, bool eq)
{
int v=hash(key);
long long ev;
ev=ECVALUE(key);
if(hc>=STABLE){
fprintf(stderr,"out of hash table range\n");
exit(-1);
}
do{
if(htable==-1LL){
if(eq){
htable=ev;nec++;
}else{
htable=key;
ec++;
}
hc++;
return v;
}else if(htable!=key&&htable!=ev){
v=(v+WALK)%STABLE;
}else{
if(eq){
assert(htable==ev);
}else{
assert(htable==key);
}
return v;
}
}while(1);
}
int query_hash_entry(long long htable[],long long key)///return index to hash table
{
long long ev=ECVALUE(key);
int v=hash(key);
do{
if(htable==-1LL)return v;
if(htable==key||htable==ev)
return v;
v=(v+WALK)%STABLE;
}while(1);
}
void init_neighbour()
{
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
SET s=EMPTY_SET;
ADD_INDEX(s,INDEX(i,j));
if(i>0&&j>0){
ADD_INDEX(s,INDEX(i-1,j-1));
}
if(i>0){
ADD_INDEX(s,INDEX(i-1,j));
}
if(j>0){
ADD_INDEX(s,INDEX(i,j-1));
}
if(i>0&&j<N-1){
ADD_INDEX(s,INDEX(i-1,j+1));
}
if(j<N-1){
ADD_INDEX(s,INDEX(i,j+1));
}
if(i<N-1&&j>0){
ADD_INDEX(s,INDEX(i+1,j-1));
}
if(i<N-1){
ADD_INDEX(s,INDEX(i+1,j));
}
if(i<N-1&&j<N-1){
ADD_INDEX(s,INDEX(i+1,j+1));
}
nghb=s;
}
}
}
#if 0
void visit(long long neighb)
{
int i;
int e=query_hash_entry(htable,neighb);
if(htable==neighb){
int ee=query_hash_entry(htable2,neighb);
if(htable2==-1){
htable2=neighb;
lec++;
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
long long newneighb=neighb;
newneighb|=nghb;
visit(newneighb);
}
}
}
}else{
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
long long newneighb=neighb;
newneighb|=nghb;
int e2=query_hash_entry(htable,newneighb);
if(htable==newneighb){
visit(newneighb);
break;
}
}
}
}
}
#endif
int query(long long neighb)
{
int e=query_hash_entry(htable,neighb);
if(htable!=-1)
return e;
int i;
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
long long newneighb=neighb;
newneighb|=nghb;
int r=query(newneighb);
if(htable==newneighb)
break;
}
}
if(i<BITS){///find any status is newneighb
return add_hash(htable,neighb,true);
}else{
return add_hash(htable,neighb,false);
}
}
int cmpll(const void *p,const void *q)
{
const long long *lp=(const long long *)p;
const long long *lq=(const long long *)q;
if(*lp==*lq)return 0;
if(*lp<*lq)return -1;
return 1;
}
int _tmain(int argc, _TCHAR* argv[])
{
int i,j;
init();
init_neighbour();
int s=query(0LL);
if(htable==0LL){
printf("First fail\n");
}else{
printf("First successful\n");
}
printf("Total table size %d\n",hc);
printf("Total eq stat found %d\n",ec);
printf("Total neq stat found %d\n",nec);
#if 0
for(i=0;i<BITS;i++){
long long r=nghb;
printf("%d set={ ",i);
for(j=0;j<BITS;j++){
if(!TEST_BIT(r,j)){
long long newneighb=r;
newneighb|=nghb;
int u=query_hash_entry(htable,newneighb);
if(htable==newneighb){
printf("%d ",j);
}
}
}
printf("}\n");
}
#endif
return 0;
}
发现宏STABLE已经不能再小了(除非修改代码再考虑对称性),实际上最后使用的数目为31816105.
如果在vc6下,将所有long long 改为__int64.
mathe 发表于 2009-10-16 09:17 http://bbs.emath.ac.cn/images/common/back.gif
我照做了,但是LL还报错，于是1LL->(__int64)1,0LL->(__int64)0
C:\vc6>cl ch.cpp
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 12.00.8168 for 80x86
Copyright (C) Microsoft Corp 1984-1998. All rights reserved.
ch.cpp
Microsoft (R) Incremental Linker Version 6.00.8168
Copyright (C) Microsoft Corp 1992-1998. All rights reserved.
/out:ch.exe
ch.obj
ch.exe : warning LNK4084: total image size 800043008 exceeds max (268435456); image may not run
你可以试着将htable的内存初始化改成动态分配(用malloc)
堆栈溢出？
不是说运行很长时间？
我把21楼改成下面，马上运行结束。
First fail
Total table size 0
Total eq stat found 0
Total neq stat found 0
// chp.cpp : Defines the entry point for the console application.
//
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdlib.h>
#define N 8
#define BITS (N*N)
typedef unsigned __int64 SET;
SET nghb;
#define EMPTY_SET (__int64)0
#define INDEX(x,y) ((x)*N+(y))
#define GET_X(ind) ((ind)/N)
#define GET_Y(ind) ((ind)%N)
#define ADD_INDEX(s, ind)((s)|=(__int64)1<<(ind))
#define TEST_INDEX(s, ind)(((s)&((__int64)1<<(ind)))!=0)
#define CORNMASK (3|(3<<N))
#define TEST_BIT(x, b) (((x)&((__int64)1<<(b)))!=0)
#define SET_BIT(x, b) ((x)|=((__int64)1<<(b)))
#define GET_CORN(x)(((x)&3)| (((x)>>N)&3)<<2)
#define DISP_CORN(x) (((x)&3)| ((((x)>>2)&3)<<N))
#define ECVALUE(x) (((x)&~CORNMASK)|DISP_CORN(cr))
#define STABLE 50000033
#define WALK 1000
int hc;
int ec;
int nec;
int lec;
__int64 *htable=(__int64 *)malloc(sizeof(__int64)*STABLE);
//__int64 htable2;
char cr={1,-1,-1,-1,-1,-1,-1,-1,4,-1,5,-1,3,-1,11,7};
char rc={-1,0,-1,12,8,10,-1,15,-1,-1,-1,14,-1,-1,-1,-1};
FILE *fout;
void dump(__int64 v)
{
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
if(TEST_BIT(v,i*N+j)){
fprintf(fout,"1 ");
}else{
fprintf(fout,"0 ");
}
}
fprintf(fout,"\n");
}
fprintf(fout,"\n");
}
void copy_ec(__int64 *p)
{
int i,t;
for(i=0,t=0;i<STABLE;i++){
if(htable!=-(__int64)1){
if(cr)]!=-1){
p=htable;
}
}
}
}
void dump_ec(__int64 htable[])
{
int i;
fout = fopen("dump.txt","w");
for(i=0;i<STABLE;i++){
if(htable!=-(__int64)1){
if(cr)]!=-1){
dump(htable);
}
}
}
fclose(fout);
}
void init()
{
memset(htable,-1,sizeof(htable));
// memset(htable2,-1,sizeof(htable2));
}
int hash(SET s)
{
return (int)(s%STABLE);
}
int add_hash(__int64 htable[],__int64 key, bool eq)
{
int v=hash(key);
__int64 ev;
ev=ECVALUE(key);
if(hc>=STABLE){
fprintf(stderr,"out of hash table range\n");
exit(-1);
}
do{
if(htable==-(__int64)1){
if(eq){
htable=ev;nec++;
}else{
htable=key;
ec++;
}
hc++;
return v;
}else if(htable!=key&&htable!=ev){
v=(v+WALK)%STABLE;
}else{
if(eq){
assert(htable==ev);
}else{
assert(htable==key);
}
return v;
}
}while(1);
}
int query_hash_entry(__int64 htable[],__int64 key)///return index to hash table
{
__int64 ev=ECVALUE(key);
int v=hash(key);
do{
if(htable==-(__int64)1)return v;
if(htable==key||htable==ev)
return v;
v=(v+WALK)%STABLE;
}while(1);
}
void init_neighbour()
{
int i,j;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
SET s=EMPTY_SET;
ADD_INDEX(s,INDEX(i,j));
if(i>0&&j>0){
ADD_INDEX(s,INDEX(i-1,j-1));
}
if(i>0){
ADD_INDEX(s,INDEX(i-1,j));
}
if(j>0){
ADD_INDEX(s,INDEX(i,j-1));
}
if(i>0&&j<N-1){
ADD_INDEX(s,INDEX(i-1,j+1));
}
if(j<N-1){
ADD_INDEX(s,INDEX(i,j+1));
}
if(i<N-1&&j>0){
ADD_INDEX(s,INDEX(i+1,j-1));
}
if(i<N-1){
ADD_INDEX(s,INDEX(i+1,j));
}
if(i<N-1&&j<N-1){
ADD_INDEX(s,INDEX(i+1,j+1));
}
nghb=s;
}
}
}
#if 0
void visit(__int64 neighb)
{
int i;
int e=query_hash_entry(htable,neighb);
if(htable==neighb){
int ee=query_hash_entry(htable2,neighb);
if(htable2==-1){
htable2=neighb;
lec++;
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
__int64 newneighb=neighb;
newneighb|=nghb;
visit(newneighb);
}
}
}
}else{
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
__int64 newneighb=neighb;
newneighb|=nghb;
int e2=query_hash_entry(htable,newneighb);
if(htable==newneighb){
visit(newneighb);
break;
}
}
}
}
}
#endif
int query(__int64 neighb)
{
int e=query_hash_entry(htable,neighb);
if(htable!=-1)
return e;
int i;
for(i=0;i<BITS;i++){
if(TEST_BIT(neighb,i)==0){
__int64 newneighb=neighb;
newneighb|=nghb;
int r=query(newneighb);
if(htable==newneighb)
break;
}
}
if(i<BITS){///find any status is newneighb
return add_hash(htable,neighb,true);
}else{
return add_hash(htable,neighb,false);
}
}
int cmpll(const void *p,const void *q)
{
const __int64 *lp=(const __int64 *)p;
const __int64 *lq=(const __int64 *)q;
if(*lp==*lq)return 0;
if(*lp<*lq)return -1;
return 1;
}
int main(int argc, char* argv[])
{
int i,j;
init();
init_neighbour();
int s=query((__int64)0);
if(htable==(__int64)0){
printf("First fail\n");
}else{
printf("First successful\n");
}
printf("Total table size %d\n",hc);
printf("Total eq stat found %d\n",ec);
printf("Total neq stat found %d\n",nec);
#if 0
for(i=0;i<BITS;i++){
__int64 r=nghb;
printf("%d set={ ",i);
for(j=0;j<BITS;j++){
if(!TEST_BIT(r,j)){
__int64 newneighb=r;
newneighb|=nghb;
int u=query_hash_entry(htable,newneighb);
if(htable==newneighb){
printf("%d ",j);
}
}
}
printf("}\n");
}
#endif
return 0;
}
void init()
{
memset(htable,-1,sizeof(htable));
// memset(htable2,-1,sizeof(htable2));
}
需要修改
下载了一个Microsoft Visual C++ Toolkit 2003，可以编译long long了，运行时间确实很长
First fail
Total table size 31816105
Total eq stat found 5732950
Total neq stat found 26083155
Total lec stat found 1869201
21楼
Timer 3.01Copyright (c) 2002-2003 Igor Pavlov2003-07-10
First fail
Total table size 31816105
Total eq stat found 5732950
Total neq stat found 26083155
Kernel Time= 0.639 = 00:00:00.639 = 1%
User Time = 45.240 = 00:00:45.240 =98%
Process Time = 45.879 = 00:00:45.879 =99%
Global Time= 45.911 = 00:00:45.911 = 100%