Zip and Skip Tries
Loading...
Searching...
No Matches
Classes | Functions | Variables
plot_genetic Namespace Reference

Classes

class  DataType
 
class  FitLine
 

Functions

 get_dpi (bool savefig)
 
int binary_search (list[int] x, int key)
 
FitLine|None fit_log_line (list[int] x, list[float] y, int skip_until=0, bool all_points=False, list[int] add_next=[])
 
Path get_file (str method_name, DataType data_type)
 
 plot (str figure_name, bool save, str ylabel, str xlabel, str|None legend_loc='best')
 
tuple[list[int], list[int], list[int], list[float]] load_data (str method_name, DataType data_type, int cutoff=0)
 
tuple[tuple[int], tuple[float]] get_data_point (str method_name, DataType data_type, int index, int cutoff=0)
 
tuple[list[int], list[float]] moving_average (list[int] x, list[float] y, float window=1.9)
 
 add_data_point_to_plot (str method_name, DataType data_type, int index, int cutoff=0, int skip_until=0, str fitlabel='', int max_value=-1, float markersize=POINT_SIZE, bool draw_best_fit=True, str label='')
 
 compare_construction_data (bool savefig)
 
 compare_search_data (bool savefig)
 

Variables

 HOSTNAME = socket.gethostname()
 
 DATA_DIRECTORY = Path('data-genetic')
 
str CONSTRUCTION_FILENAME = 'construction-data'
 
str REMOVAL_FILENAME = 'removal-data'
 
str SEARCH_FILENAME = 'search-data'
 
 FIGURE_DIRECTORY = Path('figures')
 
 exist_ok
 
list OKABE_COLORS = ['#000000', '#E69F00', '#56B4E9', '#009E73', '#F0E442', '#0072B2', '#D55E00', '#CC79A7']
 
 color
 
float POINT_SIZE = 0.1
 
bool savefig = False
 

Detailed Description

Plotting script for genetic benchmark data.

This script generates plots from benchmark data collected using genetic_benchmark.cu.
It creates various plots comparing the performance of different trie implementations
on genetic data from the ABC-HuMi dataset, focusing on construction and search times.

The script reads CSV files from the data-genetic directory and generates plots in the
figures directory. It supports plotting construction time and search time against
different parameters (number of keys, total key length, LCP length).

The plots include trend lines with log-log regression to analyze asymptotic behavior.

Function Documentation

◆ add_data_point_to_plot()

plot_genetic.add_data_point_to_plot ( str  method_name,
DataType  data_type,
int  index,
int   cutoff = 0,
int  skip_until = 0,
str  fitlabel = '',
int  max_value = -1,
float   markersize = POINT_SIZE,
bool   draw_best_fit = True,
str   label = '' 
) 
Add a data series to the current plot with optional trend line.

    Loads data for a specific method and parameter, applies smoothing, and adds it to the plot.
    Optionally fits and adds a trend line with equation and R² value in the legend.

    Args:
        method_name: Name of the method/implementation being benchmarked
        data_type: Type of benchmark data (construction, removal, or search)
        index: Which parameter to plot against (0 for n, 1 for m, 2 for l)
        cutoff: Filter value for the parallel cutoff parameter
        skip_until: Skip data points with x values less than this threshold for trend line fitting
        fitlabel: Label to use in the trend line equation (e.g., 'n', 'm', 'L')
        max_value: Maximum x value to include (-1 for no limit)
        markersize: Size of the markers for data points
        draw_best_fit: If True, fit and draw a trend line; if False, only plot data points
        label: Custom label for the data series (defaults to method_name if empty)

Definition at line 302 of file plot_genetic.py.

302def add_data_point_to_plot(method_name: str, data_type: DataType, index: int, cutoff: int = 0, skip_until: int=0, fitlabel: str='', max_value: int=-1, markersize: float = POINT_SIZE, draw_best_fit: bool = True, label: str = ''):
303 """Add a data series to the current plot with optional trend line.
304
305 Loads data for a specific method and parameter, applies smoothing, and adds it to the plot.
306 Optionally fits and adds a trend line with equation and R² value in the legend.
307
308 Args:
309 method_name: Name of the method/implementation being benchmarked
310 data_type: Type of benchmark data (construction, removal, or search)
311 index: Which parameter to plot against (0 for n, 1 for m, 2 for l)
312 cutoff: Filter value for the parallel cutoff parameter
313 skip_until: Skip data points with x values less than this threshold for trend line fitting
314 fitlabel: Label to use in the trend line equation (e.g., 'n', 'm', 'L')
315 max_value: Maximum x value to include (-1 for no limit)
316 markersize: Size of the markers for data points
317 draw_best_fit: If True, fit and draw a trend line; if False, only plot data points
318 label: Custom label for the data series (defaults to method_name if empty)
319 """
320 x, y = get_data_point(method_name, data_type, index, cutoff)
321
322 if max_value > 0:
323 x, y = zip(*[(x[i], y[i]) for i in range(len(x)) if x[i] <= max_value])
324
325 x, y = moving_average(list(x), list(y))
326
327 label = label if label else method_name
328
329 fit = fit_log_line(x, y, skip_until=skip_until)
330
331 if draw_best_fit and fit:
332 p = plt.loglog(x, y, base=2, marker = 'o', markersize = markersize, linestyle = 'None') # type: ignore
333 pcolor = p[0].get_color() # type: ignore
334
335 sign = '+' if fit.b >= 0 else '-'
336
337 plt.loglog(fit.x, fit.y, base=2, color=pcolor, linestyle='--', alpha=0.7, linewidth=0.8, # type: ignore
338 label=f'{label}: $T({fitlabel}) = {fit.m:.1f} {fitlabel} {sign} {abs(fit.b):.1f}, R^2 = {fit.r2:.2f}$')
339 else:
340 plt.loglog(x, y, base=2, marker = 'o', markersize = markersize, linestyle = 'None', label=label) # type: ignore
341
342
343
alloc_to_device
T * alloc_to_device(size_t size)
Allocates memory on the CUDA device.
Definition cuda_utils.cuh:190

◆ binary_search()

int plot_genetic.binary_search ( list[int]  x,
int  key 
) 
Perform binary search to find the insertion point for key in a sorted list.

    Used to find the index where data points should be skipped when fitting trend lines.

    Args:
        x: Sorted list of integers to search in
        key: Value to find the insertion point for

    Returns:
        Index where key should be inserted to maintain sorted order

Definition at line 82 of file plot_genetic.py.

82def binary_search(x: list[int], key: int) -> int:
83 """Perform binary search to find the insertion point for key in a sorted list.
84
85 Used to find the index where data points should be skipped when fitting trend lines.
86
87 Args:
88 x: Sorted list of integers to search in
89 key: Value to find the insertion point for
90
91 Returns:
92 Index where key should be inserted to maintain sorted order
93 """
94 low = 0
95 high = len(x)
96
97 while low < high:
98 mid = (high + low) // 2
99
100 if x[mid] < key:
101 low = mid + 1
102 else:
103 high = mid
104
105 return low
106

◆ compare_construction_data()

plot_genetic.compare_construction_data ( bool  savefig) 
Create plots comparing construction time for different implementations.

    Generates three plots:
    1. Construction time vs. number of keys (n)
    2. Construction time vs. total key length (N)
    3. Construction time vs. total LCP length (L)

    Args:
        savefig: If True, save the figures to files; if False, display them

Definition at line 344 of file plot_genetic.py.

344def compare_construction_data(savefig: bool):
345 """Create plots comparing construction time for different implementations.
346
347 Generates three plots:
348 1. Construction time vs. number of keys (n)
349 2. Construction time vs. total key length (N)
350 3. Construction time vs. total LCP length (L)
351
352 Args:
353 savefig: If True, save the figures to files; if False, display them
354 """
355 plt.figure(num = 0, figsize = (8, 5), dpi = get_dpi(savefig), facecolor = 'w', edgecolor = 'k') # type: ignore
356
357 skip_until = 2 ** 8
358 cutoff = 1
359
360 add_data_point_to_plot('c-trie++', DataType.CONSTRUCTION, 0, fitlabel='n', skip_until=skip_until,markersize=1, label='\\texttt{c-trie++}')
361 add_data_point_to_plot('ZT', DataType.CONSTRUCTION, 0, fitlabel='n', skip_until=skip_until,markersize=1)
362 add_data_point_to_plot('MI-ZT', DataType.CONSTRUCTION, 0, fitlabel='n', skip_until=skip_until,markersize=1)
363 add_data_point_to_plot('PZT', DataType.CONSTRUCTION, 0, cutoff=cutoff, fitlabel='n', skip_until=skip_until,markersize=1)
364 add_data_point_to_plot('MI-PZT', DataType.CONSTRUCTION, 0, cutoff=cutoff, fitlabel='n', skip_until=skip_until,markersize=1)
365
366 plot(figure_name='construction-time-num-keys-comparison', save=savefig, ylabel='Time (ns)', xlabel='Number of Keys ($n$)')
367
368
369 plt.figure(num = 1, figsize = (8, 5), dpi = get_dpi(savefig), facecolor = 'w', edgecolor = 'k') # type: ignore
370
371 skip_until = 2**21
372
373 add_data_point_to_plot('c-trie++', DataType.CONSTRUCTION, 1, fitlabel='N', skip_until=skip_until, label='\\texttt{c-trie++}')
374 add_data_point_to_plot('ZT', DataType.CONSTRUCTION, 1, fitlabel='N', skip_until=skip_until)
375 add_data_point_to_plot('MI-ZT', DataType.CONSTRUCTION, 1, fitlabel='N', skip_until=skip_until)
376 add_data_point_to_plot('PZT', DataType.CONSTRUCTION, 1, cutoff=cutoff, fitlabel='N', skip_until=skip_until)
377 add_data_point_to_plot('MI-PZT', DataType.CONSTRUCTION, 1, cutoff=cutoff, fitlabel='N', skip_until=skip_until)
378
379 plot(figure_name='construction-time-total-key-length-comparison', save=savefig, ylabel='Time (ns)', xlabel='Total Key Length ($N$)')
380
381
382 plt.figure(num = 2, figsize = (8, 5), dpi = get_dpi(savefig), facecolor = 'w', edgecolor = 'k') # type: ignore
383
384 skip_until = 2**17
385
386 add_data_point_to_plot('c-trie++', DataType.CONSTRUCTION, 2, fitlabel='L', skip_until=skip_until, label='\\texttt{c-trie++}')
387 add_data_point_to_plot('ZT', DataType.CONSTRUCTION, 2, fitlabel='L', skip_until=skip_until)
388 add_data_point_to_plot('MI-ZT', DataType.CONSTRUCTION, 2, fitlabel='L', skip_until=skip_until)
389 add_data_point_to_plot('PZT', DataType.CONSTRUCTION, 2, cutoff=cutoff, fitlabel='L', skip_until=skip_until)
390 add_data_point_to_plot('MI-PZT', DataType.CONSTRUCTION, 2, cutoff=cutoff, fitlabel='L', skip_until=skip_until)
391
392 plot(figure_name='construction-time-total-LCP-length-comparison', save=savefig, ylabel='Time (ns)', xlabel='Total LCP Length ($L$)')
393
394# def compare_removal_data(savefig: bool):
395# plt.figure(num=200, figsize=(8, 5), dpi = get_dpi(savefig), facecolor='w', edgecolor='k') # type: ignore
396
397# skip_until = 2**4
398# cutoff = 2**13
399
400# add_data_point_to_plot('c-trie++', DataType.REMOVAL, 0, fitlabel='n', skip_until=skip_until, markersize=1, label='\\texttt{c-trie++}')
401# add_data_point_to_plot('ST', DataType.REMOVAL, 0, fitlabel='n', skip_until=skip_until, markersize=1)
402# add_data_point_to_plot('PST', DataType.REMOVAL, 0, cutoff=cutoff, fitlabel='n', skip_until=skip_until, markersize=1)
403
404# plot(figure_name='removal-time-n-comparison', save=savefig, ylabel='Time (ns)', xlabel='Number of Keys ($n$)')
405
406# plt.figure(num=201, figsize=(8, 5), dpi = get_dpi(savefig), facecolor='w', edgecolor='k') # type: ignore
407
408# skip_until = 2**18
409
410# add_data_point_to_plot('c-trie++', DataType.REMOVAL, 1, fitlabel='N', skip_until=skip_until, label='\\texttt{c-trie++}')
411# add_data_point_to_plot('ST', DataType.REMOVAL, 1, fitlabel='N', skip_until=skip_until)
412# add_data_point_to_plot('PST', DataType.REMOVAL, 1, cutoff=cutoff, fitlabel='N', skip_until=skip_until)
413
414# plot(figure_name='removal-time-N-comparison', save=savefig, ylabel='Time (ns)', xlabel='Total Key Length ($N$)')
415

◆ compare_search_data()

plot_genetic.compare_search_data ( bool  savefig) 
Create plots comparing search time for different implementations.

    Generates two plots:
    1. Search time vs. number of keys (n)
    2. Search time vs. LCP length (ℓ)

    Args:
        savefig: If True, save the figures to files; if False, display them

Definition at line 416 of file plot_genetic.py.

416def compare_search_data(savefig: bool):
417 """Create plots comparing search time for different implementations.
418
419 Generates two plots:
420 1. Search time vs. number of keys (n)
421 2. Search time vs. LCP length (ℓ)
422
423 Args:
424 savefig: If True, save the figures to files; if False, display them
425 """
426 plt.figure(num=300, figsize=(8, 5), dpi = get_dpi(savefig), facecolor='w', edgecolor='k') # type: ignore
427
428 cutoff = 1
429
430 add_data_point_to_plot('c-trie++', DataType.SEARCH, 0, draw_best_fit=False, markersize=4, label='\\texttt{c-trie++}')
431 add_data_point_to_plot('ZT', DataType.SEARCH, 0, draw_best_fit=False, markersize=4)
432 add_data_point_to_plot('MI-ZT', DataType.SEARCH, 0, draw_best_fit=False, markersize=4)
433 add_data_point_to_plot('PZT', DataType.SEARCH, 0, cutoff=cutoff, draw_best_fit=False, markersize=4)
434 add_data_point_to_plot('MI-PZT', DataType.SEARCH, 0, cutoff=cutoff, draw_best_fit=False, markersize=4)
435
436 plot(figure_name='search-time-num-keys-comparison', save=savefig, ylabel='Time (ns)', xlabel='Number of Keys ($n$)')
437
438 # plt.figure(num=301, figsize=(8, 5), dpi = get_dpi(savefig), facecolor='w', edgecolor='k') # type: ignore
439
440 skip_until = 2**12
441
442 # add_data_point_to_plot('c-trie++', DataType.SEARCH, 1, fitlabel='m', skip_until=skip_until)
443 # add_data_point_to_plot('ZT', DataType.SEARCH, 1, fitlabel='m', skip_until=skip_until)
444 # add_data_point_to_plot('MI-ZT', DataType.SEARCH, 1, fitlabel='m', skip_until=skip_until)
445 # add_data_point_to_plot('PZT', DataType.SEARCH, 1, cutoff=cutoff, fitlabel='m', skip_until=skip_until)
446 # add_data_point_to_plot('MI-PZT', DataType.SEARCH, 1, cutoff=cutoff, fitlabel='m', skip_until=skip_until)
447
448 # plot(figure_name='search-time-m-comparison', save=savefig, ylabel='Time (ns)', xlabel='Key Length ($m$)')
449
450 plt.figure(num=302, figsize=(8, 5), dpi = get_dpi(savefig), facecolor='w', edgecolor='k') # type: ignore
451
452 add_data_point_to_plot('c-trie++', DataType.SEARCH, 2, fitlabel='\\ell', skip_until=skip_until, label='\\texttt{c-trie++}')
453 add_data_point_to_plot('ZT', DataType.SEARCH, 2, fitlabel='\\ell', skip_until=skip_until)
454 add_data_point_to_plot('MI-ZT', DataType.SEARCH, 2, fitlabel='\\ell', skip_until=skip_until)
455 add_data_point_to_plot('PZT', DataType.SEARCH, 2, cutoff=cutoff, fitlabel='\\ell', skip_until=skip_until)
456 add_data_point_to_plot('MI-PZT', DataType.SEARCH, 2, cutoff=cutoff, fitlabel='\\ell', skip_until=skip_until)
457
458 plot(figure_name='search-time-lcp-length-comparison', save=savefig, ylabel='Time (ns)', xlabel='LCP Length ($\\ell$)')
459
460# def compare_cutoffs(savefig: bool):
461# plt.figure(num=400, figsize=(8, 5), dpi = get_dpi(savefig), facecolor='w', edgecolor='k') # type: ignore
462
463# # add_data_point_to_plot('PST', DataType.SEARCH, 2, cutoff=1024, fitlabel='n', skip_until=2**4, markersize=1)
464# # add_data_point_to_plot('PST', DataType.SEARCH, 2, cutoff=2048, fitlabel='n', skip_until=2**4, markersize=1)
465# add_data_point_to_plot('ST', DataType.SEARCH, 2, fitlabel='\\ell', skip_until=2**15, markersize=1, label='$c=2^0$')
466# add_data_point_to_plot('PST', DataType.SEARCH, 2, cutoff=2**13, fitlabel='\\ell', skip_until=2**12, markersize=1, label='$c=2^{13}$')
467# add_data_point_to_plot('PST', DataType.SEARCH, 2, cutoff=2**14, fitlabel='\\ell', skip_until=2**12, markersize=1, label='$c=2^{14}$')
468# add_data_point_to_plot('PST', DataType.SEARCH, 2, cutoff=2**15, fitlabel='\\ell', skip_until=2**12, markersize=1, label='$c=2^{15}$')
469# add_data_point_to_plot('PST', DataType.SEARCH, 2, cutoff=2**16, fitlabel='\\ell', skip_until=2**12, markersize=1, label='$c=2^{16}$')
470
471# plot(figure_name='construction-time-l-comparison-cutoff', save=savefig, ylabel='Time (ns)', xlabel='LCP Length ($\\ell$)')
472
473

◆ fit_log_line()

FitLine | None plot_genetic.fit_log_line ( list[int]  x,
list[float]  y,
int   skip_until = 0,
bool   all_points = False,
list[int]   add_next = [] 
) 
Fit a line to log-transformed data points for trend line analysis.

    Performs linear regression on log2-transformed data to analyze asymptotic behavior.
    Can skip initial data points to focus on asymptotic behavior at scale.

    Args:
        x: List of x-coordinates (typically problem sizes)
        y: List of y-coordinates (typically running times)
        skip_until: Skip data points with x values less than this threshold
        all_points: If True, include all points in the result; if False, only include endpoints
        add_next: Additional x values to extrapolate to

    Returns:
        A FitLine object containing the fitted line parameters, or None if fitting failed

Definition at line 107 of file plot_genetic.py.

107def fit_log_line(x: list[int], y: list[float], skip_until: int = 0, all_points: bool = False, add_next: list[int] = []) -> FitLine | None:
108 """Fit a line to log-transformed data points for trend line analysis.
109
110 Performs linear regression on log2-transformed data to analyze asymptotic behavior.
111 Can skip initial data points to focus on asymptotic behavior at scale.
112
113 Args:
114 x: List of x-coordinates (typically problem sizes)
115 y: List of y-coordinates (typically running times)
116 skip_until: Skip data points with x values less than this threshold
117 all_points: If True, include all points in the result; if False, only include endpoints
118 add_next: Additional x values to extrapolate to
119
120 Returns:
121 A FitLine object containing the fitted line parameters, or None if fitting failed
122 """
123 if skip_until > 0:
124 skip = binary_search(x, skip_until)
125 else:
126 skip = 0
127
128 if skip == len(x):
129 warnings.warn(f'The trend line starts after the max data, so it is not shown')
130 return None
131
132 logx, logy = np.log2(x[skip:]), np.log2(y[skip:])
133 m, b = np.polyfit(logx, logy, 1)
134
135 fit = np.poly1d((m, b))
136
137 for next_x in add_next:
138 next_logx = np.log2(next_x)
139 x.append(next_x)
140 logx = np.append(logx, next_logx)
141
142
143 expected_y = fit(logx)
144 average_y = np.sum(logy) / len(logy)
145 r2 = np.sum((expected_y[:len(expected_y) - len(add_next)] - average_y) ** 2) / np.sum((logy - average_y) ** 2)
146
147 return FitLine(m = m, b = b,
148 x = tuple(x[skip::] if all_points else x[skip::len(x) - skip - 1]),
149 y = tuple(2 ** (expected_y if all_points else expected_y[::len(expected_y) - 1])),
150 r2 = r2)
151

◆ get_data_point()

tuple[tuple[int], tuple[float]] plot_genetic.get_data_point ( str  method_name,
DataType  data_type,
int  index,
int   cutoff = 0 
) 
Extract a specific data series from the benchmark data.

    Loads data and extracts a specific parameter (based on index) and the corresponding times.

    Args:
        method_name: Name of the method/implementation being benchmarked
        data_type: Type of benchmark data (construction, removal, or search)
        index: Which parameter to extract (0 for n, 1 for m, 2 for l)
        cutoff: Filter value for the parallel cutoff parameter

    Returns:
        Tuple of (x values, y values) sorted by x, where x is the selected parameter and y is elapsed time

Definition at line 229 of file plot_genetic.py.

229def get_data_point(method_name: str, data_type: DataType, index: int, cutoff: int = 0) -> tuple[tuple[int], tuple[float]]:
230 """Extract a specific data series from the benchmark data.
231
232 Loads data and extracts a specific parameter (based on index) and the corresponding times.
233
234 Args:
235 method_name: Name of the method/implementation being benchmarked
236 data_type: Type of benchmark data (construction, removal, or search)
237 index: Which parameter to extract (0 for n, 1 for m, 2 for l)
238 cutoff: Filter value for the parallel cutoff parameter
239
240 Returns:
241 Tuple of (x values, y values) sorted by x, where x is the selected parameter and y is elapsed time
242 """
243 data = load_data(method_name, data_type, cutoff)
244
245 x, y = zip(*sorted(zip(data[index], data[3])))
246 return x, y
247

◆ get_dpi()

plot_genetic.get_dpi ( bool  savefig) 
Set the DPI (dots per inch) for figures based on whether they will be saved or displayed.

    Args:
        savefig: If True, use higher DPI (600) for saved figures, otherwise use lower DPI (300) for display

Definition at line 52 of file plot_genetic.py.

52def get_dpi(savefig: bool):
53 """Set the DPI (dots per inch) for figures based on whether they will be saved or displayed.
54
55 Args:
56 savefig: If True, use higher DPI (600) for saved figures, otherwise use lower DPI (300) for display
57 """
58 plt.rcParams['figure.dpi'] = 600 if savefig else 300
59
60@unique

◆ get_file()

Path plot_genetic.get_file ( str  method_name,
DataType  data_type 
) 
Get the file path for benchmark data based on method name and data type.

    Args:
        method_name: Name of the method/implementation being benchmarked
        data_type: Type of benchmark data (construction, removal, or search)

    Returns:
        Path object pointing to the CSV file containing the benchmark data

Definition at line 152 of file plot_genetic.py.

152def get_file(method_name: str, data_type: DataType) -> Path:
153 """Get the file path for benchmark data based on method name and data type.
154
155 Args:
156 method_name: Name of the method/implementation being benchmarked
157 data_type: Type of benchmark data (construction, removal, or search)
158
159 Returns:
160 Path object pointing to the CSV file containing the benchmark data
161 """
162 match data_type:
163 case DataType.CONSTRUCTION:
164 return DATA_DIRECTORY / f'{HOSTNAME}-{CONSTRUCTION_FILENAME}-{method_name}.csv'
165 case DataType.REMOVAL:
166 return DATA_DIRECTORY / f'{HOSTNAME}-{REMOVAL_FILENAME}-{method_name}.csv'
167 case DataType.SEARCH:
168 return DATA_DIRECTORY / f'{HOSTNAME}-{SEARCH_FILENAME}-{method_name}.csv'
169

◆ load_data()

tuple[list[int], list[int], list[int], list[float]] plot_genetic.load_data ( str  method_name,
DataType  data_type,
int   cutoff = 0 
) 
Load benchmark data from a CSV file.

    Reads benchmark data for a specific method and data type, filtering by cutoff value.

    Args:
        method_name: Name of the method/implementation being benchmarked
        data_type: Type of benchmark data (construction, removal, or search)
        cutoff: Filter value for the parallel cutoff parameter

    Returns:
        Tuple containing lists of (n values, m values, l values, elapsed times)
        where n is number of keys, m is key length, l is LCP length, and elapsed times are in nanoseconds

Definition at line 195 of file plot_genetic.py.

195def load_data(method_name: str, data_type: DataType, cutoff: int = 0) -> tuple[list[int], list[int], list[int], list[float]]:
196 """Load benchmark data from a CSV file.
197
198 Reads benchmark data for a specific method and data type, filtering by cutoff value.
199
200 Args:
201 method_name: Name of the method/implementation being benchmarked
202 data_type: Type of benchmark data (construction, removal, or search)
203 cutoff: Filter value for the parallel cutoff parameter
204
205 Returns:
206 Tuple containing lists of (n values, m values, l values, elapsed times)
207 where n is number of keys, m is key length, l is LCP length, and elapsed times are in nanoseconds
208 """
209 ns: list[int] = []
210 ms: list[int] = []
211 ls: list[int] = []
212 es: list[float] = []
213
214 with open(get_file(method_name, data_type), 'r') as f:
215 reader = csv.reader(f)
216
217 for row in reader:
218 if int(row[5]) != cutoff:
219 continue
220
221 ns.append(int(row[0]))
222 ms.append(int(row[1]))
223 ls.append(int(row[2]))
224 es.append(int(row[3]) / int(row[4]))
225
226 return ns, ms, ls, es
227
228@cache

◆ moving_average()

tuple[list[int], list[float]] plot_genetic.moving_average ( list[int]  x,
list[float]  y,
float   window = 1.9 
) 
Apply a moving average smoothing to data points.

    First consolidates duplicate x values, then applies a geometric window smoothing
    to reduce noise in the data while preserving trends.

    Args:
        x: List of x-coordinates
        y: List of y-coordinates
        window: Window size factor (points within x/window to x*window are averaged)

    Returns:
        Tuple of (smoothed x values, smoothed y values)

Definition at line 248 of file plot_genetic.py.

248def moving_average(x: list[int], y: list[float], window: float = 1.9) -> tuple[list[int], list[float]]:
249 """Apply a moving average smoothing to data points.
250
251 First consolidates duplicate x values, then applies a geometric window smoothing
252 to reduce noise in the data while preserving trends.
253
254 Args:
255 x: List of x-coordinates
256 y: List of y-coordinates
257 window: Window size factor (points within x/window to x*window are averaged)
258
259 Returns:
260 Tuple of (smoothed x values, smoothed y values)
261 """
262 new_x: list[int] = []
263 new_y: list[float] = []
264
265 i = 0
266 while i < len(x):
267 total_sum = y[i]
268 total_count = 1
269 while i < len(x) - 1 and x[i] == x[i + 1]:
270 total_sum += y[i + 1]
271 total_count += 1
272 i += 1
273
274 new_x.append(x[i])
275 new_y.append(total_sum / total_count)
276 i += 1
277
278 x, y = new_x, new_y
279
280 # Convert x and y to numpy arrays for efficient computation
281 x_array = np.array(x)
282 y_array = np.array(y)
283
284 # Prepare an array to store the moving averages
285 moving_averages = np.zeros_like(y_array)
286
287 # Calculate the moving average for each element in x
288 for i, x_val in enumerate(x_array):
289 # Define the range for the moving average
290 lower_bound = x_val / window
291 upper_bound = x_val * window
292
293 # Get indices of x values that fall within the defined window
294 window_indices = np.where((x_array >= lower_bound) & (x_array <= upper_bound))[0]
295
296 # Calculate the average of y values within this window
297 moving_averages[i] = np.mean(y_array[window_indices])
298
299 # Return the original x values and the calculated moving averages
300 return x, moving_averages.tolist()
301

◆ plot()

plot_genetic.plot ( str  figure_name,
bool  save,
str  ylabel,
str  xlabel,
str | None   legend_loc = 'best' 
) 
Finalize and display or save a plot.

    Adds labels, legend, and either displays the plot or saves it to a file.

    Args:
        figure_name: Base name for the saved figure file (without extension)
        save: If True, save the figure to a file; if False, display it
        ylabel: Label for the y-axis
        xlabel: Label for the x-axis
        legend_loc: Position for the legend (e.g., 'best', 'upper left', etc.)

Definition at line 170 of file plot_genetic.py.

170def plot(figure_name: str, save: bool, ylabel: str, xlabel: str, legend_loc: str | None = 'best'):
171 """Finalize and display or save a plot.
172
173 Adds labels, legend, and either displays the plot or saves it to a file.
174
175 Args:
176 figure_name: Base name for the saved figure file (without extension)
177 save: If True, save the figure to a file; if False, display it
178 ylabel: Label for the y-axis
179 xlabel: Label for the x-axis
180 legend_loc: Position for the legend (e.g., 'best', 'upper left', etc.)
181 """
182 plt.xlabel(xlabel) # type: ignore
183 plt.ylabel(ylabel) # type: ignore
184
185 if legend_loc:
186 plt.legend(loc = legend_loc) # type: ignore
187
188 if save:
189 path = (FIGURE_DIRECTORY / figure_name).with_suffix('.png')
190 plt.savefig(path) # type: ignore
191 else:
192 plt.show() # type: ignore
193
194@cache

Variable Documentation

◆ color

plot_genetic.color

Definition at line 47 of file plot_genetic.py.

◆ CONSTRUCTION_FILENAME

str plot_genetic.CONSTRUCTION_FILENAME = 'construction-data'

Definition at line 37 of file plot_genetic.py.

◆ DATA_DIRECTORY

plot_genetic.DATA_DIRECTORY = Path('data-genetic')

Definition at line 36 of file plot_genetic.py.

◆ exist_ok

plot_genetic.exist_ok

Definition at line 43 of file plot_genetic.py.

◆ FIGURE_DIRECTORY

plot_genetic.FIGURE_DIRECTORY = Path('figures')

Definition at line 42 of file plot_genetic.py.

◆ HOSTNAME

plot_genetic.HOSTNAME = socket.gethostname()

Definition at line 33 of file plot_genetic.py.

◆ OKABE_COLORS

list plot_genetic.OKABE_COLORS = ['#000000', '#E69F00', '#56B4E9', '#009E73', '#F0E442', '#0072B2', '#D55E00', '#CC79A7']

Definition at line 46 of file plot_genetic.py.

◆ POINT_SIZE

float plot_genetic.POINT_SIZE = 0.1

Definition at line 50 of file plot_genetic.py.

◆ REMOVAL_FILENAME

str plot_genetic.REMOVAL_FILENAME = 'removal-data'

Definition at line 38 of file plot_genetic.py.

◆ savefig

bool plot_genetic.savefig = False

Definition at line 475 of file plot_genetic.py.

◆ SEARCH_FILENAME

str plot_genetic.SEARCH_FILENAME = 'search-data'

Definition at line 39 of file plot_genetic.py.

Generated by doxygen 1.9.8