# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# This notebook compares the performance of SignHunter and Harmonica on the two examples provided by Harmonica's authors.
#
# To run this notebook, please copy the contents of this notebook's directory (`samplings.py`, `main.py`, and `SignHunter - Harmonica Comparison.ipynb`)  into the directory of the Harmonica's [source code](https://github.com/callowbird/Harmonica)
#
# One should note that the two algorithms make different assumptions on the objective function to be optimized.
# SignHunter assumes the function is separable in its variables, while Harmonica assumes that the function _can be approximated by a sparse and low degree polynomial in the Fourier basis. This
# means intuitively that it can be approximated well by a decision tree_. See [this](https://arxiv.org/pdf/1706.00764.pdf)

# From below, we can see that SignHunter minimizes the first objective function using 20 queries achieving a value of -50.0 whereas Harmonica does the same using 4223 queries!
#
# For the second objective function, Signhunter achieves a better objective value of -916.2654 with 500 queries. On the other hand, Harmonica employs 4223 queries to obtain an objective value of -916.247764.
#
# In terms of computational complexity per query, SignHunter is far more efficient. Please see the time per query from each cell below. E.g., SignHunter takes $36\mu s$ per query and Harmonica takes $67ms$!
#
# Please note that we are using Harmonica's examples and its default parameters. There are no hyperparameter for SignHunter. 

import samplings
import numpy as np
import time


def sign_hunter(f, dim, max_num_queries):
    """
    A simple implementation of SignHunter
    """
    best_guess = np.ones(dim)
    best_f = f(best_guess)
    guess = best_guess.copy()
    num_queries = 1
    while num_queries < max_num_queries:
        for h in range(np.ceil(np.log2(dim)).astype(int) + 1):
            chunk_len = np.ceil(dim / 2**h).astype(int)
            for i in range(2**h):
                istart = i * chunk_len
                iend = min(istart + chunk_len, dim)
                guess[istart:iend] *= -1
                val = f(guess)
                num_queries += 1
                if val <= best_f:
                    #print("guess is better", istart, iend, best_guess, guess)
                    best_guess = guess.copy()
                    best_f = val
                else:
                    #print("guess is worse", istart, iend, best_guess, guess)
                    guess = best_guess.copy()
                #print(istart, iend)
                if istart == dim - 1:
                    break
                if num_queries >= max_num_queries:
                    break
            if num_queries >= max_num_queries:
                break
        if num_queries >= max_num_queries:
            break
        # signhunter assumes the objective function is separable so it returns a solution in O(n)
        # if the assumption is not satisfied we can start with a new guess after O(n) queries.
        guess = np.sign(np.random.randn(dim))
        num_queries += 1
        val = f(guess)
        if val <= best_f:
            best_guess = guess.copy()
            best_f = val
    return best_f, guess, num_queries


# ### Objective Function 1 from Harmonica source code
#
# https://github.com/callowbird/Harmonica

# ###### SignHunter

samplings.num_queries = 0
query = samplings.f1
start_time = time.time()
best_f, sol, num_queries= sign_hunter(query, 60, 20)
end_time = time.time()
time_per_query = (end_time - start_time) / num_queries * 1e6
print("\n SignHunter: Number of queries {}| Solution cost {}| Time per query {:.2f}us".format(
    samplings.num_queries, best_f,time_per_query))

# ###### Harmonica

# !python main.py -query f1

# ### Objective Function 2 from Harmonica source code
#
# https://github.com/callowbird/Harmonica

# ###### SignHunter

samplings.num_queries = 0
query = samplings.f2
start_time = time.time()
best_f, sol, num_queries= sign_hunter(query, 60, 500)
end_time = time.time()
time_per_query = (end_time - start_time) / num_queries * 1e6
print("\n SignHunter: Number of queries {}| Solution cost {}| Time per query {:.2f}us".format(
    samplings.num_queries, best_f,time_per_query))

# ###### Harmonica

# !python main.py -query f2



StarcoderdataJupyterScriptsDedupFiltered