[xiph-cvs] cvs commit: speex/libspeex vq.c

[Jean-Marc Valin]

jm          02/12/14 23:45:41

  Modified:    libspeex vq.c
  Log:
  Patch by Bernard Blackham <b-speex at blackham.com.au> that speeds up the
  VQ N-best search. Can reach up to 10-15% speed improvement on higher
  complexity settings.

Revision  Changes    Path
1.8       +18 -30    speex/libspeex/vq.c

Index: vq.c
===================================================================
RCS file: /usr/local/cvsroot/speex/libspeex/vq.c,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -r1.7 -r1.8
--- vq.c	23 Oct 2002 05:18:29 -0000	1.7
+++ vq.c	15 Dec 2002 04:45:41 -0000	1.8
@@ -59,7 +59,8 @@
 /*Finds the indices of the n-best entries in a codebook*/
 void vq_nbest(float *in, float *codebook, int len, int entries, float *E, int N, int *nbest, float *best_dist)
 {
-   int i,j,k;
+   int i,j,k,used;
+   used = 0;
    for (i=0;i<entries;i++)
    {
       float dist=.5*E[i];
@@ -67,21 +68,14 @@
          dist -= in[j]**codebook++;
       if (i<N || dist<best_dist[N-1])
       {
-
-         for (j=0;j<N;j++)
+         for (k=N-1; (k >= 1) && (k > used || dist < best_dist[k-1]); k--)
          {
-            if (j >= i || dist < best_dist[j])
-            {
-               for (k=N-1;k>j;k--)
-               {
-                  best_dist[k]=best_dist[k-1];
-                  nbest[k] = nbest[k-1];
-               }
-               best_dist[j]=dist;
-               nbest[j]=i;
-               break;
-            }
+            best_dist[k]=best_dist[k-1];
+            nbest[k] = nbest[k-1];
          }
+         best_dist[k]=dist;
+         nbest[k]=i;
+         used++;
       }
    }
 }
@@ -89,7 +83,8 @@
 /*Finds the indices of the n-best entries in a codebook with sign*/
 void vq_nbest_sign(float *in, float *codebook, int len, int entries, float *E, int N, int *nbest, float *best_dist)
 {
-   int i,j,k, sign;
+   int i,j,k, sign, used;
+   used=0;
    for (i=0;i<entries;i++)
    {
       float dist=0;
@@ -106,23 +101,16 @@
       dist += .5*E[i];
       if (i<N || dist<best_dist[N-1])
       {
-
-         for (j=0;j<N;j++)
+         for (k=N-1; (k >= 1) && (k > used || dist < best_dist[k-1]); k--)
          {
-            if (j >= i || dist < best_dist[j])
-            {
-               for (k=N-1;k>j;k--)
-               {
-                  best_dist[k]=best_dist[k-1];
-                  nbest[k] = nbest[k-1];
-               }
-               best_dist[j]=dist;
-               nbest[j]=i;
-               if (sign)
-                  nbest[j]+=entries;
-               break;
-            }
+            best_dist[k]=best_dist[k-1];
+            nbest[k] = nbest[k-1];
          }
+         best_dist[k]=dist;
+         nbest[k]=i;
+         used++;
+         if (sign)
+            nbest[k]+=entries;
       }
    }
 }

<p><p>--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'cvs-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.