This module contains procedures and generic interfaces for inserting an insertion into the specified locations of an input arrays of various types. More...

Data Types
interface	getInserted
	Generate and return a new array containing the original array within which the input `insertion` has been inserted at the specified indices `index` of the original array. More...

interface	setInserted
	Return a new array `arrayNew` containing the original `array` within which the input `insertion` has been inserted at the specified indices `index` of the original array. More...

Variables
character(*, SK), parameter	MODULE_NAME = "@pm_arrayInsert"

Detailed Description

This module contains procedures and generic interfaces for inserting an insertion into the specified locations of an input arrays of various types.

Benchmarks:

Benchmark :: The runtime performance of setInserted for scalar vs. vector input insertion argument. ⛓

! Test the performance of setInserted() with a vector `insertion` vs. scalar `insertion`.
program benchmark
 
    use iso_fortran_env, only: error_unit
    use pm_kind, only: IK, LK, RK, SK
    use pm_bench, only: bench_type
    use pm_arrayRange, only: getRange
 
    implicit none
 
    integer(IK)                         :: i
    integer(IK)                         :: isize
    integer(IK)                         :: fileUnit
    integer(IK) , parameter             :: NSIZE = 18_IK
    integer(IK) , parameter             :: NBENCH = 2_IK
    integer(IK)                         :: arraySize(NSIZE)
    logical(LK)                         :: dummy = .true._LK
    integer(IK) , allocatable           :: index(:)
    real(RK)    , allocatable           :: array(:)
    real(RK)    , allocatable           :: arrayNew(:)
    real(RK)                            :: insertion(1)
    type(bench_type)                    :: bench(NBENCH)
 
    bench(1) = bench_type(name = SK_"scalarInsertion", exec = scalarInsertion , overhead = setOverhead)
    bench(2) = bench_type(name = SK_"vectorInsertion", exec = vectorInsertion , overhead = setOverhead)
 
    arraySize = [( 2_IK**isize, isize = 1_IK, NSIZE )]
 
    write(*,"(*(g0,:,' '))")
    write(*,"(*(g0,:,' '))") "scalarInsertion() vs. vectorInsertion()"
    write(*,"(*(g0,:,' '))")
 
    open(newunit = fileUnit, file = "main.out", status = "replace")
 
        write(fileUnit, "(*(g0,:,','))") "arraySize", (bench(i)%name, i = 1, NBENCH)
 
        loopOverArraySize: do isize = 1, NSIZE
 
            write(*,"(*(g0,:,' '))") "Benchmarking with size", arraySize(isize)
            allocate(array(arraySize(isize)), arrayNew(arraySize(isize)*2))
            index = getRange(1_IK, arraySize(isize))
 
            do i = 1, NBENCH
                bench(i)%timing = bench(i)%getTiming(minsec = 0.05_RK)
            end do
 
            deallocate(array, arrayNew)
            write(fileUnit,"(*(g0,:,','))") arraySize(isize), (bench(i)%timing%mean, i = 1, NBENCH)
 
        end do loopOverArraySize
        write(*,"(*(g0,:,' '))") dummy
        write(*,"(*(g0,:,' '))")
 
    close(fileUnit)
 
contains
 
    !%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    ! procedure wrappers.
    !%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
    subroutine setOverhead()
        call initialize()
        call finalize()
    end subroutine
 
    subroutine initialize()
        call random_number(insertion)
    end subroutine
 
    subroutine finalize()
        dummy = dummy .and. insertion(1) < 0.5_RK
    end subroutine
 
    subroutine scalarInsertion()
        use pm_arrayInsert, only: setInserted
        call initialize()
        call setInserted(arrayNew, array, insertion(1), index)
        call finalize()
    end subroutine
 
    subroutine vectorInsertion()
        block
            use pm_arrayInsert, only: setInserted
            call initialize()
            call setInserted(arrayNew, array, insertion, index)
            call finalize()
        end block
    end subroutine
 
end program benchmark

Example Unix compile command via Intel ifort compiler ⛓

#!/usr/bin/env sh
rm main.exe
ifort -fpp -standard-semantics -O3 -Wl,-rpath,../../../lib -I../../../inc main.F90 ../../../lib/libparamonte* -o main.exe
./main.exe

Example Windows Batch compile command via Intel ifort compiler ⛓

del main.exe
set PATH=..\..\..\lib;%PATH%
ifort /fpp /standard-semantics /O3 /I:..\..\..\include main.F90 ..\..\..\lib\libparamonte*.lib /exe:main.exe
main.exe

Example Unix / MinGW compile command via GNU gfortran compiler ⛓

#!/usr/bin/env sh
rm main.exe
gfortran -cpp -ffree-line-length-none -O3 -Wl,-rpath,../../../lib -I../../../inc main.F90 ../../../lib/libparamonte* -o main.exe
./main.exe

Postprocessing of the benchmark output ⛓

#!/usr/bin/env python
 
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
 
fontsize = 14
 
methods = ["scalarInsertion", "vectorInsertion"]
 
df = pd.read_csv("main.out")
 
 
 
ax = plt.figure(figsize = 1.25 * np.array([6.4,4.6]), dpi = 200)
ax = plt.subplot()
 
for method in methods:
    plt.plot( df["arraySize"].values
            , df[method].values
            , linewidth = 2
            )
 
plt.xticks(fontsize = fontsize)
plt.yticks(fontsize = fontsize)
ax.set_xlabel("Array Size", fontsize = fontsize)
ax.set_ylabel("Runtime [ seconds ]", fontsize = fontsize)
ax.set_title("Removing array segments with insertion(1) (scalar) vs. insertion(1:1) (vector).\nLower is better.", fontsize = fontsize)
ax.set_xscale("log")
ax.set_yscale("log")
plt.minorticks_on()
plt.grid(visible = True, which = "both", axis = "both", color = "0.85", linestyle = "-")
ax.tick_params(axis = "y", which = "minor")
ax.tick_params(axis = "x", which = "minor")
ax.legend   ( methods
           #, loc='center left'
           #, bbox_to_anchor=(1, 0.5)
            , fontsize = fontsize
            )
 
plt.tight_layout()
plt.savefig("benchmark.scalarInsertion_vs_vectorInsertion.runtime.png")
 
 
 
ax = plt.figure(figsize = 1.25 * np.array([6.4,4.6]), dpi = 200)
ax = plt.subplot()
 
plt.plot( df["arraySize"].values
        , np.ones(len(df["arraySize"].values))
       #, linestyle = "--"
       #, color = "black"
        , linewidth = 2
        )
plt.plot( df["arraySize"].values
        , df["vectorInsertion"].values / df["scalarInsertion"].values
        , linewidth = 2
        )
 
plt.xticks(fontsize = fontsize)
plt.yticks(fontsize = fontsize)
ax.set_xlabel("Array Size", fontsize = fontsize)
ax.set_ylabel("Runtime compared to scalarInsertion()", fontsize = fontsize)
ax.set_title("Runtime Ratio: Insert with insertion(1:1) / Insert with insertion(1).\nLower means faster. Lower than 1 means faster than scalarInsertion.", fontsize = fontsize)
ax.set_xscale("log")
#ax.set_yscale("log")
plt.minorticks_on()
plt.grid(visible = True, which = "both", axis = "both", color = "0.85", linestyle = "-")
ax.tick_params(axis = "y", which = "minor")
ax.tick_params(axis = "x", which = "minor")
ax.legend   ( ["scalarInsertion", "vectorInsertion"]
           #, bbox_to_anchor = (1, 0.5)
           #, loc = "center left"
            , fontsize = fontsize
            )
 
plt.tight_layout()
plt.savefig("benchmark.scalarInsertion_vs_vectorInsertion.runtime.ratio.png")

Visualization of the benchmark output ⛓

Benchmark moral ⛓

The procedures under the generic interface setInserted take both scalar and vector insertion arguments.
As evidenced by the above benchmark, when the input insertion is vector of length 1, it is much faster, by 4X or more, to pass insertion as a scalar instead of a whole array of length 1.
This benchmark represents the worst-case scenario.
Note that this benchmark is likely irrelevant to inserting substrings to Fortran strings.

Benchmark :: The runtime performance of getInserted vs. setInserted ⛓

! Test the performance of `getInserted()` vs. `setInserted()`.
program benchmark
 
    use iso_fortran_env, only: error_unit
    use pm_arrayRange, only: getRange
    use pm_kind, only: IK, LK, RK, SK
    use pm_bench, only: bench_type
 
    implicit none
 
    integer(IK)                         :: i
    integer(IK)                         :: isize
    integer(IK)                         :: fileUnit
    integer(IK) , parameter             :: NSIZE = 15_IK
    integer(IK) , parameter             :: NBENCH = 2_IK
    integer(IK)                         :: arraySize(NSIZE)
    logical(LK)                         :: dummy = .true._LK
    real(RK)                            :: insertion = 1._RK
    real(RK)    , allocatable           :: array(:), arrayNew(:)
    integer(IK) , allocatable           :: index(:)
    type(bench_type)                    :: bench(NBENCH)
 
    bench(1) = bench_type(name = SK_"setInserted", exec = setInserted , overhead = setOverhead)
    bench(2) = bench_type(name = SK_"getInserted", exec = getInserted , overhead = setOverhead)
 
    arraySize = [( 2_IK**isize, isize = 1_IK, NSIZE )]
 
    write(*,"(*(g0,:,' '))")
    write(*,"(*(g0,:,' '))") "setInserted() vs. getInserted()"
    write(*,"(*(g0,:,' '))")
 
    open(newunit = fileUnit, file = "main.out")
 
        write(fileUnit, "(*(g0,:,','))") "arraySize", (bench(i)%name, i = 1, NBENCH)
 
        loopOverArraySize: do isize = 1, NSIZE
 
            write(*,"(*(g0,:,' '))") "Benchmarking with size", arraySize(isize)
 
            index = getRange(1_IK, arraySize(isize))
            allocate(arrayNew(arraySize(isize)+size(index)))
            allocate(array(arraySize(isize)), source = 1._RK)
            do i = 1, NBENCH
                bench(i)%timing = bench(i)%getTiming(minsec = 0.05_RK)
            end do
            deallocate(array, arrayNew)
 
            write(fileUnit,"(*(g0,:,','))") arraySize(isize), (bench(i)%timing%mean, i = 1, NBENCH)
 
        end do loopOverArraySize
        write(*,"(*(g0,:,' '))") dummy
        write(*,"(*(g0,:,' '))")
 
    close(fileUnit)
 
contains
 
    !%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    ! procedure wrappers.
    !%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
    subroutine setOverhead()
        call initialize()
        call finalize()
    end subroutine
 
    subroutine initialize()
        call random_number(insertion)
    end subroutine
 
    subroutine finalize()
        dummy = dummy .and. arrayNew(1) == 0.5_RK
    end subroutine
 
    subroutine setInserted()
        block
            use pm_arrayInsert, only: setInserted
            call initialize()
            call setInserted(arrayNew, array, insertion, index, positive = .true._LK, sorted = .true._LK)
            call finalize()
        end block
    end subroutine
 
    subroutine getInserted()
        block
            use pm_arrayInsert, only: getInserted
            call initialize()
            arrayNew(:) = getInserted(array, insertion, index, positive = .true._LK, sorted = .true._LK)
            call finalize()
        end block
    end subroutine
 
end program benchmark

Example Unix compile command via Intel ifort compiler ⛓

#!/usr/bin/env sh
rm main.exe
ifort -fpp -standard-semantics -O3 -Wl,-rpath,../../../lib -I../../../inc main.F90 ../../../lib/libparamonte* -o main.exe
./main.exe

Example Windows Batch compile command via Intel ifort compiler ⛓

del main.exe
set PATH=..\..\..\lib;%PATH%
ifort /fpp /standard-semantics /O3 /I:..\..\..\include main.F90 ..\..\..\lib\libparamonte*.lib /exe:main.exe
main.exe

Example Unix / MinGW compile command via GNU gfortran compiler ⛓

#!/usr/bin/env sh
rm main.exe
gfortran -cpp -ffree-line-length-none -O3 -Wl,-rpath,../../../lib -I../../../inc main.F90 ../../../lib/libparamonte* -o main.exe
./main.exe

Postprocessing of the benchmark output ⛓

#!/usr/bin/env python
 
import matplotlib.pyplot as plt
import pandas as pd
import numpy as np
 
fontsize = 14
 
methods = ["setInserted", "getInserted"]
 
df = pd.read_csv("main.out")
 
 
 
ax = plt.figure(figsize = 1.25 * np.array([6.4,4.6]), dpi = 200)
ax = plt.subplot()
 
for method in methods:
    plt.plot( df["arraySize"].values
            , df[method].values
            , linewidth = 2
            )
 
plt.xticks(fontsize = fontsize)
plt.yticks(fontsize = fontsize)
ax.set_xlabel("Array Size", fontsize = fontsize)
ax.set_ylabel("Runtime [ seconds ]", fontsize = fontsize)
ax.set_title("setInserted() vs. getInserted()\nLower is better.", fontsize = fontsize)
ax.set_xscale("log")
ax.set_yscale("log")
plt.minorticks_on()
plt.grid(visible = True, which = "both", axis = "both", color = "0.85", linestyle = "-")
ax.tick_params(axis = "y", which = "minor")
ax.tick_params(axis = "x", which = "minor")
ax.legend   ( methods
           #, loc='center left'
           #, bbox_to_anchor=(1, 0.5)
            , fontsize = fontsize
            )
 
plt.tight_layout()
plt.savefig("benchmark.getInserted_vs_setInserted.runtime.png")
 
 
 
ax = plt.figure(figsize = 1.25 * np.array([6.4,4.6]), dpi = 200)
ax = plt.subplot()
 
plt.plot( df["arraySize"].values
        , np.ones(len(df["arraySize"].values))
       #, linestyle = "-"
       #, color = "black"
        , linewidth = 2
        )
plt.plot( df["arraySize"].values
        , df["getInserted"].values / df["setInserted"].values
        , linewidth = 2
        )
 
plt.xticks(fontsize = fontsize)
plt.yticks(fontsize = fontsize)
ax.set_xlabel("Array Size", fontsize = fontsize)
ax.set_ylabel("Runtime compared to setInserted()", fontsize = fontsize)
ax.set_title("getInserted() / setInserted()\nLower means faster. Lower than 1 means faster than setInserted().", fontsize = fontsize)
ax.set_xscale("log")
#ax.set_yscale("log")
plt.minorticks_on()
plt.grid(visible = True, which = "both", axis = "both", color = "0.85", linestyle = "-")
ax.tick_params(axis = "y", which = "minor")
ax.tick_params(axis = "x", which = "minor")
ax.legend   ( ["setInserted", "getInserted"]
           #, bbox_to_anchor = (1, 0.5)
           #, loc = "center left"
            , fontsize = fontsize
            )
 
plt.tight_layout()
plt.savefig("benchmark.getInserted_vs_setInserted.runtime.ratio.png")

Visualization of the benchmark output ⛓

Benchmark moral ⛓

The procedures under the generic interface getInserted are functions while the procedures under the generic interface setInserted are subroutines.
From the benchmark results, it appears that the functional interface performs slightly less efficiently than the subroutine interface.
The sole apparent reason for this performance loss seems to be the extra copy of the result to the allocatable arrayNew on return from the function.
Note that this benchmark does not even include the cost of repeated reallcations, that is, the allocation of arrayNew happen only once in all tests.
Note that this benchmark considers the worst-case scenario where insertion must be inserted at all positions of the input array.

Test:: test_pm_arrayInsert

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.

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.
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.

Copyright: Computational Data Science Lab

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

Variable Documentation

◆ MODULE_NAME

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

Definition at line 67 of file pm_arrayInsert.F90.

Data Types

Variables

Detailed Description

Variable Documentation

◆ MODULE_NAME