vector.c

用C语言实现的最新且最快的SVM源码,可用于解决多类分类问题

/***********************************************************************
 * 
 *  LUSH Lisp Universal Shell
 *    Copyright (C) 2002 Leon Bottou, Yann Le Cun, AT&T Corp, NECI.
 *  Includes parts of TL3:
 *    Copyright (C) 1987-1999 Leon Bottou and Neuristique.
 *  Includes selected parts of SN3.2:
 *    Copyright (C) 1991-2001 AT&T Corp.
 * 
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 * 
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 * 
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA
 * 
 ***********************************************************************/

/***********************************************************************
 * $Id: vector.c,v 1.4 2005/11/16 00:10:01 agbs Exp $
 **********************************************************************/

#include <stdlib.h>
#include <stdarg.h>
#include <stdio.h>
#include <string.h>

#include "messages.h"
#include "vector.h"


#ifdef __cplusplus__
#define this  mythis
#define or    myor
#define and   myand
#endif

#ifndef min
# define min(a,b) (((a)<(b))?(a):(b))
#endif

#ifndef max
# define max(a,b) (((a)>(b))?(a):(b))
#endif

static void* 
xmalloc(int n)
{
  void *p = malloc(n);
  if (! p) 
    lasvm_error("Function malloc() has returned zero\n");
  return p;
}


/* ------------------------------------- */
/* SIMPLE VECTORS */


lasvm_vector_t *
lasvm_vector_create(int size)
{
  lasvm_vector_t *v;
  ASSERT(size>1);
  v = (lasvm_vector_t*)xmalloc(sizeof(lasvm_vector_t) + (size-1)*sizeof(double));
  v->size = size;
  return v;
}

void 
lasvm_vector_destroy(lasvm_vector_t *v)
{
  v->size = 0;
  free(v);
}

double 
lasvm_vector_dot_product(lasvm_vector_t *v1, lasvm_vector_t *v2)
{
  int i;
  int n = min(v1->size, v2->size);
  double sum = 0;
  for (i=0; i<n; i++)
    sum += v1->data[i] * v2->data[i];
  return sum;
}



/* ------------------------------------- */
/* SPARSE VECTORS */


lasvm_sparsevector_t *
lasvm_sparsevector_create(void)
{
  lasvm_sparsevector_t *v;
  v = (lasvm_sparsevector_t*)xmalloc(sizeof(lasvm_sparsevector_t));
  v->size = 0;
  v->npairs = 0;
  v->pairs = 0;
  v->last = &v->pairs;
  return v;
}

void 
lasvm_sparsevector_clear(lasvm_sparsevector_t *v)
{
  lasvm_sparsevector_pair_t *p = v->pairs;
  while (p)
    {
      lasvm_sparsevector_pair_t *q = p->next;
      free(p);
      p = q;
    }
  v->size = 0;
  v->npairs = 0;
  v->pairs = NULL;
  v->last = &v->pairs;
}

void 
lasvm_sparsevector_destroy(lasvm_sparsevector_t *v)
{
  lasvm_sparsevector_clear(v);
  free(v);
}

double 
lasvm_sparsevector_get(lasvm_sparsevector_t *v, int index)
{
  lasvm_sparsevector_pair_t *p = v->pairs;
  ASSERT(index>=0);
  while (p && p->index < index)
    p = p->next;
  if (p && p->index == index)
    return p->data;
  return 0;
}

static void 
quickappend(lasvm_sparsevector_t *v, int index, double data)
{
  lasvm_sparsevector_pair_t *d;
  d = (lasvm_sparsevector_pair_t*)xmalloc(sizeof(lasvm_sparsevector_pair_t));
  ASSERT(index >= v->size);
  d->next = 0;
  d->index = index;
  d->data = data;
  *(v->last) = d;
  v->last = &(d->next);
  v->size = index + 1;
  v->npairs += 1;
}

void 
lasvm_sparsevector_set(lasvm_sparsevector_t *v, int index, double data)
{
  if (index >= v->size)
    {
      /* Quick append */
      quickappend(v, index, data);
    }
  else
    {
      /* Slow insert */
      lasvm_sparsevector_pair_t **pp = &v->pairs;
      lasvm_sparsevector_pair_t *p, *d;
      while ( (p=*pp) && (p->index<index) )
	pp = &(p->next);
      ASSERT(p);
      if (p && p->index == index)
	{
	  p->data = data;
	  return;
	}
      d = (lasvm_sparsevector_pair_t*)xmalloc(sizeof(lasvm_sparsevector_pair_t));
      d->next = p;
      d->index = index;
      d->data = data;
      *pp = d;
      v->npairs += 1;
    }
}

lasvm_sparsevector_t *
lasvm_sparsevector_combine(lasvm_sparsevector_t *v1, double c1,
			   lasvm_sparsevector_t *v2, double c2)
{
  
  lasvm_sparsevector_t *r;
  lasvm_sparsevector_pair_t *p1 = v1->pairs;
  lasvm_sparsevector_pair_t *p2 = v2->pairs;
  r = lasvm_sparsevector_create();
  
  while (p1 && p2)
    {
      if (p1->index < p2->index)
	{
	  quickappend(r, p1->index, c1*p1->data);
	  p1 = p1->next;
	}
      else if (p1->index > p2->index)
	{
	  quickappend(r, p2->index, c2*p2->data);
	  p2 = p2->next;
	}
      else
	{
	  quickappend(r, p1->index, c1*p1->data + c2*p2->data);
	  p1 = p1->next;
	  p2 = p2->next;
	}
    }
  while (p1)
    {
      quickappend(r, p1->index, c1*p1->data);
      p1 = p1->next;
    }
  while (p2)
    {
      quickappend(r, p2->index, c2*p2->data);
      p2 = p2->next;
    }
  return r;
}

double 
lasvm_sparsevector_dot_product(lasvm_sparsevector_t *v1, 
			       lasvm_sparsevector_t *v2)
{
  double sum = 0;
  lasvm_sparsevector_pair_t *p1 = v1->pairs;
  lasvm_sparsevector_pair_t *p2 = v2->pairs;
  while (p1 && p2)
    {
      if (p1->index < p2->index)
	p1 = p1->next;
      else if (p1->index > p2->index)
	p2 = p2->next;
      else
	{
	  sum += p1->data * p2->data;
	  p1 = p1->next;
	  p2 = p2->next;
	}
    }
  return sum;
}