Mercurial > hg > CbC > old > device

changeset 295:2437a94a1538

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
merge chunks in case value
author kono
date Sun, 06 Jun 2004 01:46:58 +0900 (2004-06-05)
parents ab715ae6b468
children 284aa4eaab0d
files Changes mc-codegen.c
diffstat 2 files changed, 196 insertions(+), 15 deletions(-) [+]
line wrap: on
line diff
--- a/Changes	Sat Jun 05 14:54:13 2004 +0900
+++ b/Changes	Sun Jun 06 01:46:58 2004 +0900
@@ -4633,3 +4633,69 @@
 switch ��ޤȤ��ΤϤ�ä����ɡ������Υ����ɤ���table
 �ϡ��ۤȤ�ɤǤʤ��͡�2ʬ�ڤϽФ뤱�ɡ�ID��Ϣ³����褦��
 ���פ������������Τ��ʡ�
+
+chunk �� merge ��algorithm ������.... O(N^2) ����͡�
+
+     c0,  c1,  c2, ... cn
+
+�ǡ�(�ʤ󤫸������Ȥ���...)
+
+     c0,  c1,  c2, ... cn
+     +------------------+ rate
+     +---------------+    rate
+     +----------+         rate
+     +----+               rate
+          +-------------+ rate
+          +----------+    rate
+          +-----+         rate
+                   ...
+
+�Ȥ����Τ��롣((n-1)*(n-2)/2) �����ǡ����֡�rate �ι⤤��Τ�
+���Τ����������Ȥϸ¤�ʤ�.... rate ����ʤ��ơ�cover Ψ��
+�⤤��Τ������ɤ����õ�ˡ���ɤ��ơ��ޤ���
+
+     RATE �ʲ��Τ�Τ�õ�� (�������ʤ�)
+     �����ơ�cover Ψ�ι⤤��Τ�Ȥäơ����٤Ƥ���Ԥ���
+
+           +------------+ rate 75%
+     +-------++------+    rate 80%
+
+�ߤ����ʤΤ�ɤ����뤫������... �ơ��֥뤬���ʤ�����ͥ��?
+�ơ��֥뤬��Ĥ��ɤ��Ȥϸ¤�ʤ���
+
+count ��¿���Τ� delta ���ۤʤ�Ȱ���Ū�ˤϤ��ᡣ
+
+     +-------++---------+ rate 80%
+          <------>   �ߤ����ʷ��Ǽ��礦���⤢�롣
+
+���ξ��� cover rate ���Ѥ��ʤ��Τǡ�table rate �Ƿ׻�����?
+
+�����ȡ������������Ƥζ�֤��ȹ礻���������櫓�ǤϤʤ���
+
+     c0,  c1,  c2, ... cn
+     +----+               rate   ���줬 fix ����ȡ�
+              +---------+ rate
+          +-------------+ rate
+          +-----+         rate
+                   ...           �ʤɤ���������ʤ���
+
+�������׻����Ƥ�������׻����Ƥ⤪��ʤ��Ϥ���
+�����������ͤ�¿�����η׻��̤��ʤ���
+
+�ޤ�����äѤꡢ
+
+  for i (0..n) {
+    c_i ���ǽ�ʸ¤���礹��
+    �Ǥ��ʤ��ä��顢���������
+  }
+
+�Ǥ���?
+
+�ޤ������������Ǥ���������ɡ��٤����Х����ĤäƤ��������͡�
+
+    < # chunks 1 = sum  1/123 sum = 1
+    ---
+    > # chunks 1 = sum  1/2 sum = 1
+
+�ʤ�ƤΤ⤢�뤷��
+
--- a/mc-codegen.c	Sat Jun 05 14:54:13 2004 +0900
+++ b/mc-codegen.c	Sun Jun 06 01:46:58 2004 +0900
@@ -1774,7 +1774,11 @@
 
 /*
       cslist = list3(value,next,label)  label==0 means skip
-      chunk  = list3(cslist,next,delta,count)
+      chunk  = list4(cslist,next,delta,list3(count,min,max))
+ */
+
+/*
+   group continous case value
  */
 
 static int
@@ -1782,7 +1786,8 @@
 {
     int delta,delta1,list,p,count;
     // cslist is already sorted
-    list = list4(cslist,0,delta=0,0); 
+    delta = 0;
+    list = list4(cslist,0,1,list3(0,car(cslist) /* min */,0)); 
     count=1;
     for(p=0;cadr(cslist);cslist = cadr(cslist),count++) {
 	delta1 = car(cadr(cslist))-car(cslist);
@@ -1791,44 +1796,154 @@
 	    caddr(list) = delta = delta1;
 	    if (p) cadr(p)=0;  // terminate previous chunk
 	} else if (delta1!=delta) {
-	    // start new list
-	    cadddr(list) = count; count=0;
-	    list = list4(cadr(cslist),list,delta=0,0);
+	    // not contiguous, start new list
+	    caddr(cadddr(list)) = car(cslist);      // max
+	    car(cadddr(list)) = count; count=0;
+            delta = 0;
+	    list = list4(cadr(cslist),list,1,list3(0,0,0));
+	    cadr(cadddr(list)) = car(cadr(cslist)); // min
 	    p=cslist;
 	}
     }
     if (p) cadr(p)=0;  // terminate previous chunk
-    cadddr(list) = count;
+    car(cadddr(list)) = count;
+    caddr(cadddr(list)) = car(cslist);   // max
     return list;
 }
 
+#define CASE_MERGE_RATE 80
+/*
+    rate = (sum count(c_i))/(max-min)
+      list3(count,min,max)
+ */
+
+static int gcd(int i,int j)
+{
+    int k;
+    if (i<j) { k=i; i=j; j=k;}
+    for(;;) {
+	if ((k=i%j)==0) return j;
+	i = j; j = k;
+    }
+}
+
+/*
+    check two chunks are mergeable or not.
+ */
+
+int
+merge_chunk_p(int *delta,int max,int min,int *count,int delta1,int count1) 
+{
+    int range = max-min;
+    int g;
+    g = gcd(*delta,delta1);
+    g = gcd(g,range);
+    range /= g;
+    *count = count1 = count1+*count;
+    *delta = g;
+#if 1
+    printf("# min %d, max %d, count %d, delta %d, rate %g t=%d\n",
+	min,max,count1,g,
+	     ((double)count1)*100.0/range,
+           count1*128>(range*128*CASE_MERGE_RATE/100)
+    );
+#endif
+    return count1*128>(range*128*CASE_MERGE_RATE/100);
+}
+
+/*
+     merge possible chunk
+      input:  list4(cslist,next,delta,list3(count,min,max))
+      output: list3(continuous number of chunk,next,delta);
+ */
+
+static int
+merge_chunk(int cslist)
+{
+    int list = cslist;
+    int tail,last,max,min,i;
+    int count,p,widest,delta=1;
+    int chunks = 0;
+    while(cadr(list)) {
+	p = cadddr(list);
+	count = car(p); max=caddr(p);
+	widest = 1; last = list;
+	delta = caddr(list);
+	for(i=1,tail=cadr(list);cadr(tail); tail=cadr(tail),i++) {
+	    p = cadddr(tail);
+	    min = cadr(p);
+	    if (merge_chunk_p(&delta,max,min,&count,caddr(tail),car(p))) {
+		widest = i+1; last = tail;
+	    }
+	}
+	chunks = list3(widest,chunks,delta);
+	list = cadr(last);
+    }
+    if (list) chunks = list3(1,chunks,delta);
+    return reverse0(chunks);
+}
+
 static void
-cascade_compare(int cslist,int cslabel,int dlabel)
+table_jump(int cslist)
 {
-    if (cslabel)
-	fwddef(cslabel);
     for(;cslist; cslist=cadr(cslist)) {
 	if (caddr(cslist))
 	    cmpdimm(car(cslist),csvalue1,caddr(cslist),0);
     }
-    if (dlabel) jmp(dlabel);
 }
 
+static void
+cascade_compare(int cslist)
+{
+    for(;cslist; cslist=cadr(cslist)) {
+	if (caddr(cslist))
+	    cmpdimm(car(cslist),csvalue1,caddr(cslist),0);
+    }
+}
+
+#define CASE_TABLE_COUNT 10
+
 void
 switch_table(int cslist,int cslabel,int dlabel)
 {
-#if 1
-    int i;
+    int chunks;
+    int i,j;
+#if 0
     for(i=cslist;i;i=cadr(i)) {
 	printf("# case %d L_%d\n",car(i),caddr(i));
     }
 #endif
-    cslist = make_chunk(cslist);
+    cslist=make_chunk(cslist);
+#if 1
+    chunks = 0;
+    for(i=cslist;i;i=cadr(i)) {
+        chunks++;
+    }
+    j = chunks;
+#endif
+    chunks = merge_chunk(cslist);
+#if 1
+    //  chunks: list3(widest,next,delta);
+    printf("# chunks %d = sum ",j);
+    j = 0;
+    for(i=chunks;i;i=cadr(i)) {
+	printf(" %d/%d",car(i),caddr(i));
+	j+=car(i);
+    }
+    printf(" sum = %d\n",j);
+#endif
     fwddef(cslabel);
     for(;cslist;cslist=cadr(cslist)) {
-	printf("# case chunk delta=%d count=%d\n",caddr(cslist),cadddr(cslist));
-	cascade_compare(car(cslist),0,cadr(cslist)?0:dlabel);
+	printf("# case chunk delta=%d count=%d min=%d max=%d\n",
+		caddr(cslist),car(cadddr(cslist)),
+				cadr(cadddr(cslist)),caddr(cadddr(cslist))
+		);
+	if (cadddr(cslist)>CASE_TABLE_COUNT)
+	    table_jump(car(cslist));
+	else
+	    cascade_compare(car(cslist));
     }
+    if (dlabel) jmp(dlabel);
 }
 
 #endif