beam.h

Go to the documentation of this file.

/*
Copyright (c) by respective owners including Yahoo!, Microsoft, and
individual contributors. All rights reserved.  Released under a BSD
license as described in the file LICENSE.
*/
#pragma once

#include <cstdio>
#include <cfloat>
#include <cstdlib>
#include "v_array.h"

// TODO: special case the version where beam_size == 1
// TODO: *maybe* special case the version where beam_size <= 10

#define BEAM_CONSTANT_SIZE 0

namespace Beam
{
template <class T>
struct beam_element
{
  uint32_t hash;  // a cached hash value -- if a ~= b then h(a) must== h(b)
  float cost;     // cost of this element
  T *data;        // pointer to element data -- rarely accessed!
  bool active;    // is this currently active
  //  bool     recombined;                 // if we're not the BEST then we've been recombined
  //  v_array<T*> * recomb_friends;   // if we're the BEST (among ~= elements), then recomb_friends is everything that's
  //  equivalent to us but worse... NOT USED if we're not doing k-best predictions
};

inline int compare_on_cost(const void *void_a, const void *void_b)
{
  if (void_a == void_b)
    return 0;
  const beam_element<void> *a = (const beam_element<void> *)void_a;
  const beam_element<void> *b = (const beam_element<void> *)void_b;
  if (a->active && !b->active)
    return -1;  // active things come before inactive things
  else if (!a->active && b->active)
    return 1;
  else if (!a->active && !b->active)
    return 0;
  else if (a->cost < b->cost)
    return -1;  // otherwise sort by cost
  else if (a->cost > b->cost)
    return 1;
  else
    return 0;
}

inline int compare_on_hash_then_cost(const void *void_a, const void *void_b)
{
  if (void_a == void_b)
    return 0;
  const beam_element<void> *a = (const beam_element<void> *)void_a;
  const beam_element<void> *b = (const beam_element<void> *)void_b;
  if (a->active && !b->active)
    return -1;  // active things come before inactive things
  else if (!a->active && b->active)
    return 1;
  else if (!a->active && !b->active)
    return 0;
  else if (a->hash < b->hash)
    return -1;  // if the hashes are different, sort by hash
  else if (a->hash > b->hash)
    return 1;
  else if (a->cost < b->cost)
    return -1;  // otherwise sort by cost
  else if (a->cost > b->cost)
    return 1;
  else
    return 0;
}

template <class T>
class beam
{
 private:
  size_t beam_size;           // the beam size -- how many active elements can we have
  size_t count;               // how many elements do we have currently -- should be == to A.size()
  float pruning_coefficient;  // prune anything with cost >= pruning_coefficient * best, set to FLT_MAX to not do
                              // coefficient-based pruning
  float worst_cost;           // what is the cost of the worst (highest cost) item in the beam
  float best_cost;            // what is the cost of the best (lowest cost) item in the beam
  float prune_if_gt;          // prune any element with cost greater than this
  T *best_cost_data;          // easy access to best-cost item
  bool do_kbest;
  v_array<beam_element<T>> A;  // the actual data
  //  v_array<v_array<beam_element<T>*>> recomb_buckets;

  //  static size_t NUM_RECOMB_BUCKETS = 10231;

  bool (*is_equivalent)(T *, T *);  // test if two items are equivalent; nullptr means don't do hypothesis recombination

 public:
  beam(size_t beam_size, float prune_coeff = FLT_MAX, bool (*test_equiv)(T *, T *) = nullptr, bool kbest = false)
      : 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
  }

  inline bool might_insert(float cost) { return (cost <= prune_if_gt) && ((count < beam_size) || (cost < worst_cost)); }

  bool insert(T *data, float cost, uint32_t hash)  // returns TRUE iff element was actually added
  {
    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;
  }

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

  beam_element<T> *pop_best_item()
  {
    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;
  }

  void do_recombination()
  {
    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;
    }
  }

  void compact(void (*free_data)(T *) = nullptr)
  {
    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;
  }

  void maybe_compact(void (*free_data)(T *) = nullptr)
  {
    if (count >= beam_size * 10)
      compact(free_data);
  }

  void erase(void (*free_data)(T *) = nullptr)
  {
    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;
  }

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

  beam_element<T> *begin() { return A.begin; }
  beam_element<T> *end() { return A.end; }
  size_t size() { return count; }
  bool empty() { return A.empty(); }
  size_t get_beam_size() { return beam_size; }

 private:
  // void add_recomb_friend(beam_element<T> *better, beam_element<T> *worse) {
  //   assert( better->cost <= worse->cost );
  //   if (better->recomb_friends == nullptr) {
  //     if (worse->recomb_friends != nullptr) {
  //       better->recomb_friends = worse->recomb_friends;
  //       worse->recomb_friends = nullptr;
  //     } else
  //       better->recomb_friends = new std::vector<beam_element<T>*>;
  //   } else {
  //     assert(worse->recomb_friends == nullptr);
  //   }
  // }
};

}  // namespace Beam