Main commands#

kleinberg_grid_simulator.kleingrid.compute_edt(n=1000, r=2, p=1, q=1, n_runs=10000, julia=True, numba=True, parallel=False)[source]#

Computation of the expected delivery time (edt).

Parameters:

  • n (int, default=1000) – Grid siDe

  • r (float, default=2.0) – Shortcut exponent

  • p (int, default=1) – Local range

  • q (int, default=1) – Number of shortcuts

  • n_runs (int, default=10000) – Number of routes to compute

  • julia (bool, default=True) – Use Julia backend.

  • numba (bool, default=True) – Use JiT compilation (Python backend)

  • parallel (bool, default=False) – Parallelize runs (Python backend with Numba). Use for single, lengthy computation. Coarse-grained (high-level) parallelisation is preferred.

Returns:

The expected number of steps to go from one point of the grid to another point of the grid.

Return type:

Result

Examples

>>> from juliacall import Main as jl
>>> jl.set_seed(42)
Julia: TaskLocalRNG()
>>> from kleinberg_grid_simulator.python_implementation.seed import set_seeds
>>> set_seeds(42, 51)
>>> compute_edt(n=1000, r=.5, n_runs=100)  
Result(edt=79.93, process_time=..., n=1000, r=0.5, p=1, q=1, n_runs=100, julia=True)
>>> compute_edt(n=1000, r=.5, n_runs=100, julia=False, numba=False)  
Result(edt=85.93, process_time=..., n=1000, r=0.5, p=1, q=1, n_runs=100, numba=False, parallel=False)
>>> compute_edt(n=1000, r=1, n_runs=100)  
Result(edt=66.39, process_time=..., n=1000, r=1, p=1, q=1, n_runs=100, julia=True)
>>> compute_edt(n=1000, r=1, n_runs=100, julia=False, numba=False)  
Result(edt=69.44, process_time=..., n=1000, r=1, p=1, q=1, n_runs=100, numba=False, parallel=False)
>>> compute_edt(n=1000, r=1.5, n_runs=100)  
Result(edt=57.91, process_time=..., n=1000, r=1.5, p=1, q=1, n_runs=100, julia=True)
>>> compute_edt(n=1000, r=1.5, n_runs=100, julia=False, numba=False)  
Result(edt=55.8, process_time=..., n=1000, r=1.5, p=1, q=1, n_runs=100, numba=False, parallel=False)
>>> compute_edt(n=1000, r=2, n_runs=100)  
Result(edt=69.53, process_time=..., n=1000, r=2, p=1, q=1, n_runs=100, julia=True)
>>> compute_edt(n=1000, r=2, n_runs=100, julia=False, numba=False)  
Result(edt=67.28, process_time=..., n=1000, r=2, p=1, q=1, n_runs=100, numba=False, parallel=False)
>>> compute_edt(n=1000, r=2.5, n_runs=100)  
Result(edt=187.74, process_time=..., n=1000, r=2.5, p=1, q=1, n_runs=100, julia=True)
>>> compute_edt(n=1000, r=2.5, n_runs=100, julia=False, numba=False)  
Result(edt=167.85, process_time=..., n=1000, r=2.5, p=1, q=1, n_runs=100, numba=False, parallel=False)
>>> compute_edt(n=10000000000, r=1.5, n_runs=10000, p=2, q=2)  
Result(edt=6846.631, process_time=13.0, n=10000000000, r=1.5, p=2, q=2, n_runs=10000, julia=True)
>>> compute_edt(n=10000000000, r=1.5, n_runs=10000, p=2, q=2, julia=False, parallel=True)  
Result(edt=6823.2369, process_time=27.796875, n=10000000000, r=1.5, p=2, q=2, n_runs=10000, numba=True, parallel=True)
kleinberg_grid_simulator.kleingrid.estimate_alpha(r, p=10, budget=20)[source]#
Parameters:

  • r (float) – Shortcut exponent to investigate.

  • p (int) – Initial investigation starts at 2**p.

  • budget (int) – How many seconds we want to spend on the estimation.

Returns:

  • alpha (float) – Complexity exponent, e.g. the edt seems to behave in n**alpha.

  • n (int) – Greatest value of n considered.

Examples

>>> alpha, n = estimate_alpha(1.5, budget=4)
>>> alpha  
0.33442226161905353
>>> n  
10071350
kleinberg_grid_simulator.kleingrid.get_bounds(n, offset_start=0.1, n_runs=10000, golden_boost=100)[source]#
Parameters:

  • n (int, default=1000) – Grid siDe,

  • offset_start (float, default=.1) – Increments to use to discover upper/lower bounds.

  • n_runs (int, default=10000) – Number of runs for regular computation.

  • golden_boost (class:int) – Number of runs multiplier for the Golden-search, which is more noise-sensitive.

Returns:

Estimated bounds + relevant input parameters.

Return type:

dict

Examples

>>> from juliacall import Main as jl
>>> jl.set_seed(42)
Julia: TaskLocalRNG()
>>> get_bounds(2**20, n_runs=100, golden_boost=10)  
{'n': 1048576, 'n_runs': 100, 'golden_boost': 10, 'ref_edt': 350.54, 'r2+': 2.1828125000000003,
 'r_opt': 1.8667184270002521, 'min_edt': 323.95000000000005, 'r-': 1.825038820250189, 'r2-': 1.4624999999999995}
kleinberg_grid_simulator.kleingrid.parallelize(values, function=None, n_jobs=-1)[source]#

Straight-forward parallel computing for different values.

Parameters:

  • values (list of dict) – Values to test. Each element is a dict of arguments to pass.

  • function (callable, default=:meth:~kleingrid.kleingrid.compute_edt) – Function to apply.

  • n_jobs (int, default=-1) – Number of workers to spawn using joblib convention.

Returns:

The outputs of the function.

Return type:

list

Examples

>>> values = [{'n': 2**i, 'n_runs': 100} for i in range(7, 11)]
>>> res = parallelize(values)
>>> [r.edt for r in res]  
[30.95, 40.82, 54.06, 69.9]