ParaMonte Fortran 2.0.0
Parallel Monte Carlo and Machine Learning Library
See the latest version documentation.
pm_arraySearch Module Reference

This module contains procedures and generic interfaces for finding the specific array index whose element has the largest value smaller than the input value in arrays of various types.
More...

Data Types

interface  getBin
 Generate and return bin, the index of the element of the input ascending-ordered array, such that array(bin) <= value < array(bin+1) holds for the input value.
More...
 

Variables

character(*, SK), parameter MODULE_NAME = "@pm_arraySearch"
 

Detailed Description

This module contains procedures and generic interfaces for finding the specific array index whose element has the largest value smaller than the input value in arrays of various types.

The input search array must be in ascending order.

Benchmarks:


Benchmark :: The runtime performance of getBin with and without isLess external optional input argument.

1! Test the performance of getBin() with and without the optional external function `isLess` input argument.
2program benchmark
3
4 use iso_fortran_env, only: error_unit
5 use pm_kind, only: IK, LK, SK, RK, RKG => RKS
6 use pm_distUnif, only: setUnifRand
8 use pm_mathMinMax, only: getMinMax
9 use pm_bench, only: bench_type
10
11 implicit none
12
13 integer(IK) :: i
14 integer(IK) :: isize
15 integer(IK) :: fileUnit
16 integer(IK) , parameter :: NSIZE = 20_IK
17 integer(IK) , parameter :: NBENCH = 2_IK
18 integer(IK) :: arraySize(NSIZE)
19 logical(LK) :: dummy = .true._LK
20 real(RKG) , allocatable :: Array(:)
21 real(RKG) :: value
22 real(RKG) :: Limit(2)
23 type(bench_type) :: bench(NBENCH)
24 integer(IK) :: index, bin
25 real(RK) :: MeanTime(2) = 0._RK
26
27 bench(1) = bench_type(name = SK_"default" , exec = default , overhead = setOverhead)
28 bench(2) = bench_type(name = SK_"isLessArg", exec = isLessArg , overhead = setOverhead)
29
30 arraySize = [( 2_IK**(isize+1), isize = 1_IK, NSIZE )]
31
32 write(*,"(*(g0,:,' '))")
33 write(*,"(*(g0,:,' '))") "isLessArg vs. default"
34 write(*,"(*(g0,:,' '))")
35
36 open(newunit = fileUnit, file = "main.out", status = "replace")
37
38 write(fileUnit, "(*(g0,:,', '))") "arraySize", (bench(i)%name, i = 1, NBENCH)
39
40 loopOverArraySize: do isize = 1, NSIZE
41
42 write(*,"(*(g0,:,' '))") "Benchmarking with size", arraySize(isize)
43
44 call random_number(Limit)
45 Limit = getMinMax(Limit(1), Limit(2))
46 Array = getLinSpace(Limit(1), Limit(2), count = arraySize(isize))
47
48 do i = 1, NBENCH
49 bench(i)%timing = bench(i)%getTiming(minsec = 0.03_RK)
50 MeanTime(i) = MeanTime(i) + bench(i)%timing%mean
51 end do
52
53 do i = NBENCH, 1, -1
54 bench(i)%timing = bench(i)%getTiming(minsec = 0.03_RK)
55 MeanTime(i) = MeanTime(i) + bench(i)%timing%mean
56 end do
57
58 write(fileUnit,"(*(g0,:,', '))") arraySize(isize), MeanTime / 2
59
60 end do loopOverArraySize
61 write(*,"(*(g0,:,' '))") dummy
62 write(*,"(*(g0,:,' '))")
63
64 close(fileUnit)
65
66contains
67
68 !%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
69 ! procedure wrappers.
70 !%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
71
72 subroutine setOverhead()
73 call initialize()
74 call finalize()
75 end subroutine
76
77 subroutine initialize()
78 call setUnifRand(index, 1_IK, arraySize(isize))
79 value = Array(index)
80 end subroutine
81
82 subroutine finalize()
83 dummy = dummy .and. bin == index
84 end subroutine
85
86 subroutine isLessArg()
87 use pm_arraySearch, only: getBin
88 call initialize()
89 bin = getBin(Array, value, isLess = isLess)
90 call finalize()
91 end subroutine
92
93 subroutine default()
94 use pm_arraySearch, only: getBin
95 call initialize()
96 bin = getBin(Array, value)
97 call finalize()
98 end subroutine
99
100 pure function isLess(value, segment) result(less)
101 use pm_kind, only: IK, LK
102 integer(IK) , intent(in) :: value, segment
103 logical(LK) :: less
104 less = value < segment
105 end function
106
107end program benchmark
Generate and return bin, the index of the element of the input ascending-ordered array,...
Generate count evenly spaced points over the interval [x1, x2] if x1 < x2, or [x2,...
Generate and return an object of type timing_type containing the benchmark timing information and sta...
Definition: pm_bench.F90:574
Return a uniform random scalar or contiguous array of arbitrary rank of randomly uniformly distribute...
Generate and return an array of size two containing the minimum and maximum of the two input values i...
This module contains procedures and generic interfaces for finding the specific array index whose ele...
This module contains procedures and generic interfaces for generating arrays with linear or logarithm...
This module contains abstract interfaces and types that facilitate benchmarking of different procedur...
Definition: pm_bench.F90:41
This module contains classes and procedures for computing various statistical quantities related to t...
This module defines the relevant Fortran kind type-parameters frequently used in the ParaMonte librar...
Definition: pm_kind.F90:268
integer, parameter RK
The default real kind in the ParaMonte library: real64 in Fortran, c_double in C-Fortran Interoperati...
Definition: pm_kind.F90:543
integer, parameter LK
The default logical kind in the ParaMonte library: kind(.true.) in Fortran, kind(....
Definition: pm_kind.F90:541
integer, parameter IK
The default integer kind in the ParaMonte library: int32 in Fortran, c_int32_t in C-Fortran Interoper...
Definition: pm_kind.F90:540
integer, parameter SK
The default character kind in the ParaMonte library: kind("a") in Fortran, c_char in C-Fortran Intero...
Definition: pm_kind.F90:539
integer, parameter RKS
The single-precision real kind in Fortran mode. On most platforms, this is an 32-bit real kind.
Definition: pm_kind.F90:567
This module contains procedures and generic interfaces for finding the minimum and maximum of two inp...
This is the class for creating benchmark and performance-profiling objects.
Definition: pm_bench.F90:386

Example Unix compile command via Intel ifort compiler
1#!/usr/bin/env sh
2rm main.exe
3ifort -fpp -standard-semantics -O3 -Wl,-rpath,../../../lib -I../../../inc main.F90 ../../../lib/libparamonte* -o main.exe
4./main.exe

Example Windows Batch compile command via Intel ifort compiler
1del main.exe
2set PATH=..\..\..\lib;%PATH%
3ifort /fpp /standard-semantics /O3 /I:..\..\..\include main.F90 ..\..\..\lib\libparamonte*.lib /exe:main.exe
4main.exe

Example Unix / MinGW compile command via GNU gfortran compiler
1#!/usr/bin/env sh
2rm main.exe
3gfortran -cpp -ffree-line-length-none -O3 -Wl,-rpath,../../../lib -I../../../inc main.F90 ../../../lib/libparamonte* -o main.exe
4./main.exe

Postprocessing of the benchmark output
1#!/usr/bin/env python
2
3import matplotlib.pyplot as plt
4import pandas as pd
5import numpy as np
6
7import os
8dirname = os.path.basename(os.getcwd())
9
10fontsize = 14
11
12df = pd.read_csv("main.out", delimiter = ", ")
13colnames = list(df.columns.values)
14
15
18
19ax = plt.figure(figsize = 1.25 * np.array([6.4,4.6]), dpi = 200)
20ax = plt.subplot()
21
22for colname in colnames[1:]:
23 plt.plot( df[colnames[0]].values
24 , df[colname].values
25 , linewidth = 2
26 )
27
28plt.xticks(fontsize = fontsize)
29plt.yticks(fontsize = fontsize)
30ax.set_xlabel(colnames[0], fontsize = fontsize)
31ax.set_ylabel("Runtime [ seconds ]", fontsize = fontsize)
32ax.set_title(" vs. ".join(colnames[1:])+"\nLower is better.", fontsize = fontsize)
33ax.set_xscale("log")
34ax.set_yscale("log")
35plt.minorticks_on()
36plt.grid(visible = True, which = "both", axis = "both", color = "0.85", linestyle = "-")
37ax.tick_params(axis = "y", which = "minor")
38ax.tick_params(axis = "x", which = "minor")
39ax.legend ( colnames[1:]
40 #, loc='center left'
41 #, bbox_to_anchor=(1, 0.5)
42 , fontsize = fontsize
43 )
44
45plt.tight_layout()
46plt.savefig("benchmark." + dirname + ".runtime.png")
47
48
51
52ax = plt.figure(figsize = 1.25 * np.array([6.4,4.6]), dpi = 200)
53ax = plt.subplot()
54
55plt.plot( df[colnames[0]].values
56 , np.ones(len(df[colnames[0]].values))
57 , linestyle = "--"
58 #, color = "black"
59 , linewidth = 2
60 )
61for colname in colnames[2:]:
62 plt.plot( df[colnames[0]].values
63 , df[colname].values / df[colnames[1]].values
64 , linewidth = 2
65 )
66
67plt.xticks(fontsize = fontsize)
68plt.yticks(fontsize = fontsize)
69ax.set_xlabel(colnames[0], fontsize = fontsize)
70ax.set_ylabel("Runtime compared to {}".format(colnames[1]), fontsize = fontsize)
71ax.set_title("Runtime Ratio Comparison. Lower means faster.\nLower than 1 means faster than {}().".format(colnames[1]), fontsize = fontsize)
72ax.set_xscale("log")
73#ax.set_yscale("log")
74plt.minorticks_on()
75plt.grid(visible = True, which = "both", axis = "both", color = "0.85", linestyle = "-")
76ax.tick_params(axis = "y", which = "minor")
77ax.tick_params(axis = "x", which = "minor")
78ax.legend ( colnames[1:]
79 #, bbox_to_anchor = (1, 0.5)
80 #, loc = "center left"
81 , fontsize = fontsize
82 )
83
84plt.tight_layout()
85plt.savefig("benchmark." + dirname + ".runtime.ratio.png")

Visualization of the benchmark output

Benchmark moral
  1. The procedures under the generic interface getBin take an optional isLess() external-function input argument which can perform custom user-defined comparisons between the input value and array elements.
    By default, the comparison is the < operator.
  2. The presence of an external isLess argument without inlining does appear to deteriorate the runtime performance of getBin.
    However, the exact amount of this penalty appears to significantly depend on the computing platform and the ability of the compiler to inline the external function.
Test:
test_pm_arraySearch


Final Remarks


If you believe this algorithm or its documentation can be improved, we appreciate your contribution and help to edit this page's documentation and source file on GitHub.
For details on the naming abbreviations, see this page.
For details on the naming conventions, see this page.
This software is distributed under the MIT license with additional terms outlined below.

  1. If you use any parts or concepts from this library to any extent, please acknowledge the usage by citing the relevant publications of the ParaMonte library.
  2. If you regenerate any parts/ideas from this library in a programming environment other than those currently supported by this ParaMonte library (i.e., other than C, C++, Fortran, MATLAB, Python, R), please also ask the end users to cite this original ParaMonte library.

This software is available to the public under a highly permissive license.
Help us justify its continued development and maintenance by acknowledging its benefit to society, distributing it, and contributing to it.

Author:
Fatemeh Bagheri, Wednesday 12:20 AM, October 13, 2021, Dallas, TX

Variable Documentation

◆ MODULE_NAME

character(*,SK), parameter pm_arraySearch::MODULE_NAME = "@pm_arraySearch"

Definition at line 54 of file pm_arraySearch.F90.