class_docstr: The lazy/accelerated greedy algorithm for optimization.
  
  The lazy (or accelerated) greedy algorithm is a fast alternate to the 
  naive greedy algorithm that results in the same items being selected. 
  This algorithm exploits the diminishing returns property of submodular 
  functions in order to avoid re-evaluating examples that are known to 
  provide little gain. If an example has a small gain relative to other 
  examples, it is unlikely to be the next selected example because that 
  gain can only go down as more items are selected. Thus, the example 
  should only be re-evaluated once the gains of other examples have gotten 
  smaller.
  
  The key idea of the lazy greedy algorithm is to maintain a priority queue 
  where the examples are the elements in the queue and the priorities are 
  the gains the last time they were evaluated. The algorithm has two steps. 
  The first step is to calculate the gain that each example would have if 
  selected first (the modular upper bound) and populate the priority queue 
  using these values. The second step is to recalculate the gain of the 
  first example in the priority queue and then add the example back into 
  the queue. If the example remains at the front of the queue it is selected 
  because no other example could have a larger gain once re-evaluated (due 
  to the diminishing returns property).
  
  While the worst case time complexity of this algorithm is the same as the 
  naive greedy algorithm, in practice it can be orders of magnitude faster. 
  Empirically, it appears to accelerate graph-based functions much more 
  than it does feature-based ones. Functions also seem to be more 
  accelerated the more curved they are.
  
  .. code::python
  
          from apricot import FeatureBasedSelection
  
          X = numpy.random.randint(10, size=(10000, 100))
  
          selector = FeatureBasedSelection(100, 'sqrt', optimizer='lazy')
          selector.fit(X)
  
  Parameters
  ----------
  self.function : base.BaseSelection
          A submodular function that implements the `_calculate_gains` and
          `_select_next` methods. This is the function that will be
          optimized.
  
  self.verbose : bool
          Whether to display a progress bar during the optimization process.
  
  
  Attributes
  ----------
  self.function : base.BaseSelection
          A submodular function that implements the `_calculate_gains` and
          `_select_next` methods. This is the function that will be
          optimized.
  
  self.verbose : bool
          Whether to display a progress bar during the optimization process.
  
  self.pq : utils.PriorityQueue
          The priority queue used to order examples for evaluation.
  
  self.gains_ : numpy.ndarray or None
          The gain that each example would give the last time that it was
          evaluated.
class_docstr_tok: ["The","lazy\/accelerated","greedy","algorithm","for","optimization",".","The","lazy","(","or","accelerated",")","greedy","algorithm","is","a","fast","alternate","to","the","naive","greedy","algorithm","that","results","in","the","same","items","being","selected",".","This","algorithm","exploits","the","diminishing","returns","property","of","submodular","functions","in","order","to","avoid","re-evaluating","examples","that","are","known","to","provide","little","gain",".","If","an","example","has","a","small","gain","relative","to","other","examples",",","it","is","unlikely","to","be","the","next","selected","example","because","that","gain","can","only","go","down","as","more","items","are","selected",".","Thus",",","the","example","should","only","be","re-evaluated","once","the","gains","of","other","examples","have","gotten","smaller",".","The","key","idea","of","the","lazy","greedy","algorithm","is","to","maintain","a","priority","queue","where","the","examples","are","the","elements","in","the","queue","and","the","priorities","are","the","gains","the","last","time","they","were","evaluated",".","The","algorithm","has","two","steps",".","The","first","step","is","to","calculate","the","gain","that","each","example","would","have","if","selected","first","(","the","modular","upper","bound",")","and","populate","the","priority","queue","using","these","values",".","The","second","step","is","to","recalculate","the","gain","of","the","first","example","in","the","priority","queue","and","then","add","the","example","back","into","the","queue",".","If","the","example","remains","at","the","front","of","the","queue","it","is","selected","because","no","other","example","could","have","a","larger","gain","once","re-evaluated","(","due","to","the","diminishing","returns","property",")",".","While","the","worst","case","time","complexity","of","this","algorithm","is","the","same","as","the","naive","greedy","algorithm",",","in","practice","it","can","be","orders","of","magnitude","faster",".","Empirically",",","it","appears","to","accelerate","graph-based","functions","much","more","than","it","does","feature-based","ones",".","Functions","also","seem","to","be","more","accelerated","the","more","curved","they","are",".","..","code",":",":python","from","apricot","import","FeatureBasedSelection","X","=","numpy.random.randint","(","10",",","size=","(","10000",",","100",")",")","selector","=","FeatureBasedSelection","(","100",",","'sqrt","'",",","optimizer='lazy","'",")","selector.fit","(","X",")","Parameters","--","--","--","--","--","self.function",":","base.BaseSelection","A","submodular","function","that","implements","the","`","_calculate_gains","`","and","`","_select_next","`","methods",".","This","is","the","function","that","will","be","optimized",".","self.verbose",":","bool","Whether","to","display","a","progress","bar","during","the","optimization","process",".","Attributes","--","--","--","--","--","self.function",":","base.BaseSelection","A","submodular","function","that","implements","the","`","_calculate_gains","`","and","`","_select_next","`","methods",".","This","is","the","function","that","will","be","optimized",".","self.verbose",":","bool","Whether","to","display","a","progress","bar","during","the","optimization","process",".","self.pq",":","utils.PriorityQueue","The","priority","queue","used","to","order","examples","for","evaluation",".","self.gains_",":","numpy.ndarray","or","None","The","gain","that","each","example","would","give","the","last","time","that","it","was","evaluated","."]
code: def select(self, X, k, sample_cost=None):
      cost = 0.0
      if sample_cost is None:
          sample_cost = numpy.ones(X.shape[0], dtype="float64")
  
      gains = (
          self.function._calculate_gains(X)
          / sample_cost[self.function.idxs]
      )
      self.pq = PriorityQueue(self.function.idxs, -gains)
  
      while cost < k:
          best_gain = float("-inf")
          best_idx = None
  
          while True:
              if len(self.pq.pq) == 0:
                  return
  
              prev_gain, idx = self.pq.pop()
              # prev_gain, idx = self.pq.peek()
              prev_gain = -prev_gain
  
              if cost + sample_cost[idx] > k:
                  continue
  
              if best_idx == idx:
                  break
  
              idxs = numpy.array([idx])
              gain = (
                  self.function._calculate_gains(X, idxs)[0]
                  / sample_cost[idx]
              )
  
              # self.pq.swap(idx, -gain)
              self.pq.add(idx, -gain)
  
              if gain > best_gain:
                  best_gain = gain
                  best_idx = idx
              elif gain == best_gain and best_gain == 0.0:
                  best_gain = gain
                  best_idx = idx
                  break
  
          cost += sample_cost[best_idx]
          best_gain *= sample_cost[best_idx]
          self.function._select_next(X[best_idx], best_gain, best_idx)
  
          if self.verbose == True:
              self.function.pbar.update(1)
  
imports: import os
  import copy
  import numpy
  import scipy
  from tqdm import tqdm
  from .utils import PriorityQueue
  from .utils import check_random_state
  from .utils import _calculate_pairwise_distances
label_desc: Use image node_id 2 for calling the LazyGreedy obj's underlying member method code with example usage: obj.select(X, k, sample_cost) without return types