Beam::beam< T > Class Template Reference

#include <beam.h>

Public Member Functions
	beam (size_t beam_size, float prune_coeff=FLT_MAX, bool(*test_equiv)(T *, T *)=nullptr, bool kbest=false)
bool	might_insert (float cost)
bool	insert (T *data, float cost, uint32_t hash)
beam_element< T > *	get_best_item ()
beam_element< T > *	pop_best_item ()
void	do_recombination ()
void	compact (void(*free_data)(T *)=nullptr)
void	maybe_compact (void(*free_data)(T *)=nullptr)
void	erase (void(*free_data)(T *)=nullptr)
	~beam ()
beam_element< T > *	begin ()
beam_element< T > *	end ()
size_t	size ()
bool	empty ()
size_t	get_beam_size ()

Private Attributes
size_t	beam_size
size_t	count
float	pruning_coefficient
float	worst_cost
float	best_cost
float	prune_if_gt
T *	best_cost_data
bool	do_kbest
v_array< beam_element< T > >	A
bool(*	is_equivalent )(T *, T *)

Detailed Description

template<class T>
class Beam::beam< T >

Definition at line 77 of file beam.h.

Constructor & Destructor Documentation

beam()

template<class T >

Beam::beam< T >::beam ( size_t  beam_size, float  prune_coeff = FLT_MAX, bool(*)(T *, T *)  test_equiv = nullptr, bool  kbest = false  )

inline

Definition at line 97 of file beam.h.

References BEAM_CONSTANT_SIZE, and v_array< T >::resize().

      : beam_size(beam_size), pruning_coefficient(prune_coeff), do_kbest(kbest), is_equivalent(test_equiv)
  {
    count = 0;
    worst_cost = -FLT_MAX;
    best_cost = FLT_MAX;
    prune_if_gt = FLT_MAX;
    best_cost_data = nullptr;
    A = v_init<beam_element<T>>();
    if (beam_size <= BEAM_CONSTANT_SIZE)
      A.resize(beam_size, true);
    else
      A.resize((beam_size + 1) * 4, true);
    if (beam_size == 1)
      do_kbest = false;  // automatically turn of kbest
  }

~beam()

template<class T >

Beam::beam< T >::~beam ( )

inline

Definition at line 307 of file beam.h.

References v_array< T >::delete_v(), and v_array< T >::size().

  {
    assert(A.size() == 0);
    A.delete_v();
  }

Member Function Documentation

begin()

template<class T >

beam_element<T>* Beam::beam< T >::begin ( )

inline

Definition at line 313 of file beam.h.

References v_array< T >::begin().

{ return A.begin; }

compact()

template<class T >

void Beam::beam< T >::compact ( void(*)(T *)  free_data = nullptr )

inline

Definition at line 265 of file beam.h.

References v_array< T >::begin(), Beam::compare_on_cost(), v_array< T >::end(), f, and v_array< T >::size().

  {
    if (is_equivalent)
      do_recombination();
    qsort(A.begin, A.size(), sizeof(beam_element<T>), compare_on_cost);  // TODO: quick select

    if (count <= beam_size)
      return;

    count = beam_size;
    if (is_equivalent)  // we might be able to get rid of even more
      while ((count > 1) && !A[count - 1].active) count--;

    if (free_data)
      for (beam_element<T> *be = A.begin + count; be != A.end; ++be) free_data(be->data);

    A.end = A.begin + count;

    best_cost = A[0].cost;
    worst_cost = A[count - 1].cost;
    prune_if_gt = std::max(1.f, best_cost) * pruning_coefficient;
    best_cost_data = A[0].data;
  }

do_recombination()

template<class T >

void Beam::beam< T >::do_recombination ( )

inline

Definition at line 228 of file beam.h.

References v_array< T >::begin(), Beam::compare_on_hash_then_cost(), Beam::beam_element< T >::data, Beam::beam_element< T >::hash, and v_array< T >::size().

  {
    qsort(A.begin, A.size(), sizeof(beam_element<T>), compare_on_hash_then_cost);
    size_t start = 0;
    while (start < A.size() - 1)
    {
      size_t end = start + 1;
      for (; (end < A.size()) && (A[start].hash == A[end].hash); end++)
        ;
      assert(start < A.size());
      assert(end <= A.size());
      // std::cerr << "start=" << start << " end=" << end << std::endl;
      // go over all pairs
      for (size_t i = start; i < end; i++)
      {
        if (!A[i].active)
          continue;
        assert(i < A.size());
        for (size_t j = i + 1; j < end; j++)
        {
          if (!A[j].active)
            continue;
          assert(j < A.size());
          // std::cerr << "te " << i << "," << j << std::endl;
          if (is_equivalent(A[i].data, A[j].data))
          {
            A[j].active = false;  // TODO: if kbest is on, do recomb_friends
            // std::cerr << "equivalent " << i << "," << j << ": " << ((size_t)A[i].data) << " and " <<
            // ((size_t)A[j].data)
            // << std::endl;
          }
        }
      }
      start = end;
    }
  }

empty()

template<class T >

bool Beam::beam< T >::empty ( )

inline

Definition at line 316 of file beam.h.

References v_array< T >::empty().

{ return A.empty(); }

end()

template<class T >

beam_element<T>* Beam::beam< T >::end ( )

inline

Definition at line 314 of file beam.h.

References v_array< T >::end().

{ return A.end; }

erase()

template<class T >

void Beam::beam< T >::erase ( void(*)(T *)  free_data = nullptr )

inline

Definition at line 295 of file beam.h.

References v_array< T >::begin(), and v_array< T >::end().

  {
    if (free_data)
      for (beam_element<T> *be = A.begin; be != A.end; ++be) free_data(be->data);
    A.erase();
    count = 0;
    worst_cost = -FLT_MAX;
    best_cost = FLT_MAX;
    prune_if_gt = FLT_MAX;
    best_cost_data = nullptr;
  }

get_beam_size()

template<class T >

size_t Beam::beam< T >::get_beam_size ( )

inline

Definition at line 317 of file beam.h.

{ return beam_size; }

get_best_item()

template<class T >

beam_element<T>* Beam::beam< T >::get_best_item ( )

inline

Definition at line 186 of file beam.h.

References Beam::beam_element< T >::active, v_array< T >::begin(), and v_array< T >::end().

  {
    if (count == 0)
      return nullptr;
    beam_element<T> *ret = A.begin;
    while ((ret != A.end) && (!ret->active)) ++ret;
    return (ret == A.end) ? nullptr : ret;
  }

insert()

template<class T >

bool Beam::beam< T >::insert ( T *  data, float  cost, uint32_t  hash  )

inline

Definition at line 116 of file beam.h.

References Beam::beam_element< T >::active, BEAM_CONSTANT_SIZE, Beam::beam_element< T >::cost, Beam::beam_element< T >::data, f, Beam::beam_element< T >::hash, and v_array< T >::push_back().

  {
    if (!might_insert(cost))
      return false;

    // bool we_were_worse = false;
    // if (is_equivalent) {
    //   size_t mod = recomb_buckets.size();
    //   size_t id  = hash % mod;
    //   size_t equiv_pos = bucket_contains_equiv(recomb_buckets[i], data, hash);
    //   if (equiv_pos != (size_t) -1) { // we can recombing at equiv_pos
    //     if (cost >= recomb_buckets[i][equiv_pos].cost) {
    //       // we are more expensive, so ignore
    //       we_were_worse = true;
    //       beam_element<T> * be = new beam_element<T>;
    //       be->hash = hash; be->cost = cost; be->data = data; be->active = true; be->recombined = false;
    //       be->recomb_friends = nullptr; add_recomb_friend(recomb_buckets[i][equiv_pos], be);
    //   }
    // }

    if (beam_size < BEAM_CONSTANT_SIZE)
    {  // find the worst item and directly replace it
      size_t worst_idx = 0;
      float worst_idx_cost = A[0].cost;
      for (size_t i = 1; i < beam_size; i++)
        if (A[i].cost > worst_idx_cost)
        {
          worst_idx = i;
          worst_idx_cost = A[i].cost;
          if (worst_idx_cost <= worst_cost)
            break;
        }
      if (cost >= worst_idx_cost)
        return false;

      A[worst_idx].hash = hash;
      A[worst_idx].cost = cost;
      A[worst_idx].data = data;
      A[worst_idx].active = true;
      // A[worst_idx].recombined = false;
      // A[worst_idx].recomb_friends = nullptr;  // TODO: free it if it isn't nullptr
      worst_cost = cost;
    }
    else
    {
      beam_element<T> be;
      be.hash = hash;
      be.cost = cost;
      be.data = data;
      be.active = true;
      // be.recombined = false;
      // be.recomb_friends = nullptr;

      A.push_back(be);
      count++;
    }

    if (cost < best_cost)
    {
      best_cost = cost;
      best_cost_data = data;
    }
    if (cost > worst_cost)
    {
      worst_cost = cost;
      prune_if_gt = std::max(1.f, best_cost) * pruning_coefficient;
    }
    return true;
  }

maybe_compact()

template<class T >

void Beam::beam< T >::maybe_compact ( void(*)(T *)  free_data = nullptr )

inline

Definition at line 289 of file beam.h.

  {
    if (count >= beam_size * 10)
      compact(free_data);
  }

might_insert()

template<class T >

bool Beam::beam< T >::might_insert ( float  cost )

inline

Definition at line 114 of file beam.h.

{ return (cost <= prune_if_gt) && ((count < beam_size) || (cost < worst_cost)); }

pop_best_item()

template<class T >

beam_element<T>* Beam::beam< T >::pop_best_item ( )

inline

Definition at line 195 of file beam.h.

References Beam::beam_element< T >::active, v_array< T >::begin(), Beam::beam_element< T >::cost, v_array< T >::end(), and f.

  {
    if (count == 0)
      return nullptr;

    beam_element<T> *ret = nullptr;
    float next_best_cost = FLT_MAX;
    for (beam_element<T> *el = A.begin; el != A.end; el++)
      if ((ret == nullptr) && el->active && (el->cost <= best_cost))
        ret = el;
      else if (el->active && (el->cost < next_best_cost))
      {
        next_best_cost = el->cost;
        best_cost_data = el->data;
      }

    if (ret != nullptr)
    {
      best_cost = next_best_cost;
      prune_if_gt = std::max(1.f, best_cost) * pruning_coefficient;
      ret->active = false;
      count--;
    }
    else
    {
      best_cost = FLT_MAX;
      prune_if_gt = FLT_MAX;
      best_cost_data = nullptr;
    }

    return ret;
  }

size()

template<class T >

size_t Beam::beam< T >::size ( )

inline

Definition at line 315 of file beam.h.

{ return count; }

Member Data Documentation

A

template<class T >

v_array<beam_element<T> > Beam::beam< T >::A

private

Definition at line 89 of file beam.h.

beam_size

template<class T >

size_t Beam::beam< T >::beam_size

private

Definition at line 80 of file beam.h.

best_cost

template<class T >

float Beam::beam< T >::best_cost

private

Definition at line 85 of file beam.h.

best_cost_data

template<class T >

T* Beam::beam< T >::best_cost_data

private

Definition at line 87 of file beam.h.

count

template<class T >

size_t Beam::beam< T >::count

private

Definition at line 81 of file beam.h.

do_kbest

template<class T >

bool Beam::beam< T >::do_kbest

private

Definition at line 88 of file beam.h.

is_equivalent

template<class T >

bool(* Beam::beam< T >::is_equivalent) (T *, T *)

private

Definition at line 94 of file beam.h.

prune_if_gt

template<class T >

float Beam::beam< T >::prune_if_gt

private

Definition at line 86 of file beam.h.

pruning_coefficient

template<class T >

float Beam::beam< T >::pruning_coefficient

private

Definition at line 82 of file beam.h.

worst_cost

template<class T >

float Beam::beam< T >::worst_cost

private

Definition at line 84 of file beam.h.

---

The documentation for this class was generated from the following file:

• /mnt/c/w/linux/vowpal_wabbit/vowpalwabbit/beam.h