Coverage for moptipy / evaluation / selector.py: 93%

1""" 

2A tool for selecting a consistent subset of data from partial experiments. 

3 

4When we have partial experimental data, maybe collected from experiments that 

5are still ongoing, we want to still evaluate them in some consistent way. The 

6right method for doing this could be to select a subset of that data that is 

7consistent, i.e., a subset where the algorithms have the same number of runs 

8on the instances using the same seeds. The function :func:`select_consistent` 

9offered by this module provides the functionality to make such a selection. 

10It may be a bit slow, but hopefully it will pick the largest possible 

11consistent sub-selection or, at least, get close to it. 

12 

13Our :func:`select_consistent` tries to find such a consistent dataset using 

14different :class:`Selector` methods that are passed to it as second parameter. 

15 

16In the most basic and defaul setting, :const:`SELECTOR_SAME_RUNS_FOR_ALL`, it 

17simply retains the exactly same number of runs for all 

18instance/algorithm/objective/encoding combinations, making sure that the same 

19seeds are used for a given instance. 

20This can be done rather quickly, but it may not yield the largest possible 

21set of consistent runs. 

22It will also fail if there are some combinations that have runs with mutually 

23distinct seeds. 

24 

25In this case, using :const:`SELECTOR_MAX_RUNS_SIMPLE` might be successful, as 

26it is a more heuristic approach. 

27The heuristic methods implemented here always begin with the full set of data 

28and aim to delete the element that will cause the least other deletions down 

29the road, until we arrive in a consistent state. 

30I strongly suspect that doing this perfectly would be NP-hard, so we cannot 

31implement this in a perfect way. Instead, we use different heuristics and then 

32pick the best result. 

33:const:`SELECTOR_MAX_RUNS` uses more heuristics, which means that it will be 

34slower, but may have a bigger chance to yield a consistent experiment. 

35""" 

36 

37from typing import Any, Final, Iterable, TypeVar 

38 

39from pycommons.io.console import logger 

40from pycommons.types import type_error 

41 

42from moptipy.evaluation.base import PerRunData 

43 

44#: the type variable for the selector routine 

45T = TypeVar("T", bound=PerRunData) 

46 

47#: the algorithm key 

48KEY_ALGORITHM: Final[int] = 0 

49#: the instance key 

50KEY_INSTANCE: Final[int] = KEY_ALGORITHM + 1 

51#: the encoding key 

52KEY_ENCODING: Final[int] = KEY_INSTANCE + 1 

53#: the objective key 

54KEY_OBJECTIVE: Final[int] = KEY_ENCODING + 1 

55#: the seed key 

56KEY_SEED: Final[int] = KEY_OBJECTIVE + 1 

57#: the number of keys 

58TOTAL_KEYS: Final[int] = KEY_SEED + 1 

59 

60 

61class Selector: 

62 """ 

63 The base class for selectors. 

64 

65 Each selector offers a routine that can select a subset of runs from a 

66 given description. For the selection process, all instances, objective 

67 functions, encodings, and algorithms as well as (instance-seed) 

68 combinations are replaced with integer numbers identifying them. 

69 

70 The data that is passed to the method :meth:`select` is already purified. 

71 Algorithm, instance, objective function, and encoding names are replaced 

72 with consecutive integers. Instance/seed combinations are also replaced 

73 with such integer values. 

74 Each run of the original experiment is thus identified by a five-tuple of 

75 integer values. 

76 """ 

77 

78 def select(self, 

79 dims: tuple[int, int, int, int, int], 

80 keys: tuple[tuple[int, int, int, int, int], ...], 

81 best_length: int) -> list[tuple[ 

82 int, int, int, int, int]] | None: 

83 """ 

84 Perform the dataset selection. 

85 

86 The `keys` array is an immutable list of keys. Each key uniquely 

87 identifies one run in the experiment. It is a tuple of five integer 

88 values: 

89 

90 0. The value at index :const:`KEY_ALGORITHM` identifies the 

91 algorithm used in the run, 

92 1. the value at index :const:`KEY_INSTANCE` identifies the instance, 

93 2. the value at index :const:`KEY_OBJECTIVE` identifies the objective 

94 function, 

95 3. the value at index :const:`KEY_ENCODING` identifies the encoding, 

96 and 

97 4. the value at index :const:`KEY_SEED` identifies the instance-seed 

98 combination, meaning that each seed on each instance maps to a 

99 unique value here. 

100 

101 The number of values in each key dimension is given in the array 

102 `dims`. The instance identifiers, for example, are all in the interval 

103 `0..dims[KEY_INSTANCE]-1`. Because of this, you can use the key values 

104 as indexes into consecutive lists to keep track of counts, if you want 

105 to. 

106 

107 The parameter `best_length` provides the largest number of consistent 

108 runs discovered by any selection method so far. It is `-1` for the 

109 first selector that is attempted. 

110 The selection routines returns a list of selected run keys, or `None` 

111 if this selector could not surpass `best_length`. 

112 

113 :param dims: the number of different values per key dimension 

114 :param keys: the data keys to select from 

115 :param best_length: the largest number of consistent runs discovered 

116 by any previously applied selector. 

117 :return: the selected data 

118 """ 

119 raise NotImplementedError 

120 

121 

122def _count_inc(scores: list[list[int]], key: tuple[int, ...]) -> None: 

123 """ 

124 Increment the score of a given tuple. 

125 

126 :param scores: the scores 

127 :param key: the key 

128 """ 

129 for i, k in enumerate(key): 

130 scores[i][k] += 1 

131 

132 

133def _count_dec(scores: list[list[int]], key: tuple[int, ...]) -> None: 

134 """ 

135 Decrement the score of a given tuple. 

136 

137 :param scores: the scores 

138 :param key: the key 

139 """ 

140 for i, k in enumerate(key): 

141 scores[i][k] -= 1 

142 

143 

144class HeuristicSelector(Selector): 

145 """A heuristic selector.""" 

146 

147 def weight(self, counts: list[list[int]]) -> Any: # pylint: disable=W0613 

148 """ 

149 Compute a weight for the scores. 

150 

151 This function can be overwritten to compute the total score. 

152 

153 :param counts: the number of currently selected runs for each 

154 dimension and each dimension value 

155 :return: a weight factor, that may be ignored by some methods 

156 """ 

157 return 1 

158 

159 def score(self, element: tuple[int, ...], # pylint: disable=W0613 

160 counts: list[list[int]], # pylint: disable=W0613 

161 weights: Any) -> Any: # pylint: disable=W0613 

162 """ 

163 Score a given element. 

164 

165 :param element: the tuple to score 

166 :param counts: the number of currently selected runs for each 

167 dimension and each dimension value 

168 :param weights: the weights, which may sometimes be ignored 

169 :returns: the score 

170 """ 

171 return None 

172 

173 def select(self, 

174 dims: tuple[int, int, int, int, int], 

175 keys: tuple[tuple[int, int, int, int, int], ...], 

176 best_length: int) -> list[tuple[ 

177 int, int, int, int, int]] | None: 

178 """ 

179 Perform the heuristic dataset selection. 

180 

181 Heuristic selectors attempt to step-by-step delete keys that lead to 

182 the fewest dropped instances, algorithms, objectives, and encodings. 

183 

184 :param dims: the number of different values per key dimension 

185 :param keys: the data keys to select from 

186 :param best_length: the length of the best-so-far set of runs, 

187 will be `-1` if no such best exists 

188 :return: the selected data 

189 """ 

190 # the counters for the score calculations 

191 source: Final[list[list]] = [[k, 0] for k in keys] 

192 dataset_size: Final[int] = list.__len__(source) 

193 scorer_name: Final[str] = str(self) 

194 

195 # compute the original item scores 

196 counts: list[list[int]] = [[0] * i for i in dims] 

197 count: int = dataset_size 

198 for er in source: 

199 _count_inc(counts, er[0]) 

200 

201 changed: bool = True 

202 while changed: 

203 changed = False 

204 

205 # Find the setups with maximum and minimum scores. 

206 min_score: Any = None 

207 max_score: Any = None 

208 weights: Any = self.weight(counts) 

209 

210 if weights is None: # cannot proceed 

211 logger(f"Method {scorer_name!r} is not applicable.") 

212 return None 

213 

214 for er in source: 

215 er[1] = score = self.score( # pylint: disable=E1128 

216 er[0], counts, weights) 

217 if score is not None: 

218 if (min_score is None) or (min_score > score): 

219 min_score = score 

220 if (max_score is None) or (max_score < score): 

221 max_score = score 

222 del weights 

223 if min_score is None: 

224 logger(f"{scorer_name!r} failed.") 

225 return None 

226 if min_score < max_score: # Some setups have lower scores. 

227 del_count: int = 0 # We will delete them. 

228 for i in range(count - 1, -1, -1): 

229 er = source[i] 

230 score = er[1] 

231 if (score is None) or (score <= min_score): 

232 del source[i] 

233 _count_dec(counts, er[0]) 

234 del_count += 1 

235 if del_count <= 0: 

236 raise ValueError( 

237 f"Did not delete anything under {scorer_name!r}?") 

238 

239 new_count: int = list.__len__(source) 

240 if new_count != (count - del_count): 

241 raise ValueError("List inconsistent after deletion " 

242 f"under {scorer_name!r}?") 

243 logger(f"Deleted {del_count} of the {count} records because " 

244 f"their score was {min_score}. Retained {new_count} " 

245 f"records under {scorer_name!r}.") 

246 count = new_count 

247 changed = True 

248 continue 

249 

250 logger(f"All setups now have the same score {max_score} under" 

251 f" {scorer_name!r}.") 

252 if count <= best_length: 

253 logger(f"We now only have {count} setups, which means we " 

254 "cannot get better than the current best set with " 

255 f"{best_length} setups, so we quit.") 

256 return None 

257 

258 # If we get here, all elements have the same score. 

259 # This means that we are basically done. 

260 # 

261 # However, this may also happen if a very odd division exists in 

262 # the data. Maybe we have one algorithm that was applied to one 

263 # instance ten times and another algorithm applied to another 

264 # instance ten times. This data would still be inconsistent, as it 

265 # does not allow for any comparison. 

266 

267 # Compute the different values for everything except the seeds. 

268 usekeys: tuple[int, ...] = tuple( 

269 v for v, s in enumerate(counts) 

270 if (v != KEY_SEED) and (len(s) > 1)) 

271 

272 if tuple.__len__(usekeys) > 1: 

273 logger("Now checking for inconsistencies in " 

274 "algorithm/instance/objective/encoding under" 

275 f" {scorer_name!r}.") 

276 # Only if there are different values in at least one tuple 

277 # dimension, we need to check for strange situations. 

278 

279 # For each of (instance, algorithm, encoding, objective), we 

280 # must have the same number of other records. 

281 # If not, then we have some strange symmetric situation that 

282 # needs to be solved. 

283 per_value: dict[int, set[Any]] = {} 

284 last: set[Any] | None = None 

285 for key in usekeys: 

286 other_keys: tuple[int, ...] = tuple( 

287 kk for kk in usekeys if kk != key) 

288 for er in source: 

289 kv = er[0][key] 

290 other = tuple(er[0][ok] for ok in other_keys) 

291 if kv in per_value: 

292 per_value[kv].add(other) 

293 else: 

294 per_value[kv] = last = {other} 

295 for v in per_value.values(): 

296 if v != last: 

297 changed = True 

298 break 

299 per_value.clear() 

300 

301 # We just need to delete one random element. This will 

302 # break the symmetry 

303 if changed: 

304 logger( 

305 f"Deleting one of the {count} elements to " 

306 "break the erroneous symmetry under " 

307 f"{scorer_name}.") 

308 er = source[-1] 

309 del source[-1] 

310 _count_dec(counts, er[0]) 

311 count -= 1 

312 break 

313 del per_value 

314 del usekeys 

315 if changed: 

316 continue 

317 

318 if count <= best_length: 

319 logger(f"We now only have {count} setups, which means we " 

320 "cannot get better than the current best set with " 

321 f"{best_length} setups, so we quit.") 

322 return None 

323 

324 # If we get here, the only problem left could be if algorithms 

325 # have different seeds for the same instances. We thus need to 

326 # check that for each instance, all the seeds are the same. 

327 # Notice that such inconsistencies can only occur if different 

328 # seeds occurred exactly as same as often. 

329 logger("Now checking for inconsistencies in instance " 

330 f"seeds under {scorer_name!r}.") 

331 seeds: dict[int, dict[tuple[int, int, int], set[int]]] = {} 

332 for er in source: 

333 inst: int = er[0][KEY_INSTANCE] 

334 cur: dict[tuple[int, int, int], set[int]] 

335 if inst in seeds: 

336 cur = seeds[inst] 

337 else: 

338 seeds[inst] = cur = {} 

339 kx: tuple[int, int, int] = ( 

340 er[0][KEY_ALGORITHM], er[0][KEY_OBJECTIVE], 

341 er[0][KEY_ENCODING]) 

342 if kx in cur: 

343 cur[kx].add(er[0][KEY_SEED]) 

344 else: 

345 cur[kx] = {er[0][KEY_SEED]} 

346 

347 max_seed_insts: set[int] = set() 

348 max_seeds: int = -1 

349 min_seed_inst: int | None = None 

350 min_seeds: int = -1 

351 must_delete_from_insts: set[int] = set() 

352 for instance, inst_setups in seeds.items(): 

353 kvx: set[int] | None = None 

354 for setup_seeds in inst_setups.values(): 

355 if kvx is None: 

356 kvx = setup_seeds 

357 seed_cnt: int = set.__len__(setup_seeds) 

358 if seed_cnt >= max_seeds: 

359 if seed_cnt > max_seeds: 

360 max_seed_insts.clear() 

361 max_seeds = seed_cnt 

362 max_seed_insts.add(instance) 

363 if (seed_cnt < min_seeds) or (min_seed_inst is None): 

364 min_seeds = seed_cnt 

365 min_seed_inst = instance 

366 elif kvx != setup_seeds: 

367 # We got a symmetric inconsistency 

368 must_delete_from_insts.add(instance) 

369 break 

370 if min_seeds < max_seeds: 

371 must_delete_from_insts.update(max_seed_insts) 

372 del max_seed_insts 

373 

374 del_count = set.__len__(must_delete_from_insts) 

375 if del_count > 0: 

376 logger("Must delete one record from all of " 

377 f"{must_delete_from_insts!r}.") 

378 for i in range(count - 1, -1, -1): 

379 er = source[i] 

380 instance = er[0][KEY_INSTANCE] 

381 if instance in must_delete_from_insts: 

382 must_delete_from_insts.remove(instance) 

383 del source[i] 

384 _count_dec(counts, er[0]) 

385 changed = True 

386 if set.__len__(must_delete_from_insts) <= 0: 

387 break 

388 new_count = list.__len__(source) 

389 if new_count != (count - del_count): 

390 raise ValueError("Error when deleting instances " 

391 f"under {scorer_name!r}.") 

392 count = new_count 

393 if not changed: 

394 raise ValueError( 

395 f"Seeds inconsistent under {scorer_name!r}.") 

396 del must_delete_from_insts 

397 

398 del seeds 

399 if count <= best_length: 

400 logger(f"We now only have {count} setups, which " 

401 "means we cannot get better than the current " 

402 f"best set with {best_length} setups, so we " 

403 "quit.") 

404 return None 

405 # There should not be any problems left, but we need to check 

406 # again if something has changed. 

407 

408 if count <= best_length: 

409 logger(f"We now only have {count} setups, which means we " 

410 "cannot get better than the current best set with " 

411 f"{best_length} setups, so we quit..") 

412 return None # We can do nothing here 

413 # We are finally finished. The scores are no longer needed. 

414 del counts 

415 if count <= 0: 

416 raise ValueError("No data found at all?") 

417 return [b[0] for b in source] 

418 

419 

420class __HeuristicSelectorTiered(HeuristicSelector): 

421 """A tiered heuristic selector.""" 

422 

423 def score(self, element: tuple[int, ...], counts: list[list[int]], 

424 _: Any) -> list[int]: 

425 """ 

426 Score a given element. 

427 

428 :param element: the tuple to score 

429 :param counts: the element counts per dimension 

430 :param _: the weights, which may sometimes be ignored 

431 :returns: the score 

432 """ 

433 return sorted(counts[i][t] for i, t in enumerate(element)) 

434 

435 def __str__(self) -> str: 

436 """ 

437 Get the selector name. 

438 

439 :returns "tiered": always 

440 """ 

441 return "tiered" 

442 

443 

444class __HeuristicSelectorTieredReverse(HeuristicSelector): 

445 """A reverse tiered heuristic selector.""" 

446 

447 def score(self, element: tuple[int, ...], counts: list[list[int]], 

448 _: Any) -> list[int]: 

449 """ 

450 Score a given element. 

451 

452 :param element: the tuple to score 

453 :param counts: the element counts per dimension 

454 :param _: the weights, which may sometimes be ignored 

455 :returns: the score 

456 """ 

457 return sorted((counts[i][t] for i, t in enumerate(element)), 

458 reverse=True) 

459 

460 def __str__(self) -> str: 

461 """ 

462 Get the selector name. 

463 

464 :returns "tieredReverse": always 

465 """ 

466 return "tieredReverse" 

467 

468 

469class __HeuristicSelectorSum(HeuristicSelector): 

470 """A sum heuristic selector.""" 

471 

472 def score(self, element: tuple[int, ...], counts: list[list[int]], 

473 _: Any) -> int: 

474 """ 

475 Score a given element. 

476 

477 :param element: the tuple to score 

478 :param counts: the element counts per dimension 

479 :param _: the weights, which may sometimes be ignored 

480 :returns: the score 

481 """ 

482 return sum(counts[i][t] for i, t in enumerate(element)) 

483 

484 def __str__(self) -> str: 

485 """ 

486 Get the selector name. 

487 

488 :returns "sum": always 

489 """ 

490 return "sum" 

491 

492 

493class __HeuristicSelectorProduct(HeuristicSelector): 

494 """A product heuristic selector.""" 

495 

496 def score(self, element: tuple[int, ...], counts: list[list[int]], 

497 _: Any) -> int: 

498 """ 

499 Score a given element. 

500 

501 :param element: the tuple to score 

502 :param counts: the element counts per dimension 

503 :param _: the weights, which may sometimes be ignored 

504 :returns: the score 

505 """ 

506 result: int = 1 

507 for i, t in enumerate(element): 

508 result *= counts[i][t] 

509 return result 

510 

511 def __str__(self) -> str: 

512 """ 

513 Get the selector name. 

514 

515 :returns "product": always 

516 """ 

517 return "product" 

518 

519 

520class __HeuristicSelectorMinimum(HeuristicSelector): 

521 """A minimum heuristic selector.""" 

522 

523 def score(self, element: tuple[int, ...], counts: list[list[int]], 

524 _: Any) -> int: 

525 """ 

526 Score a given element. 

527 

528 :param element: the tuple to score 

529 :param counts: the element counts per dimension 

530 :param _: the weights, which may sometimes be ignored 

531 :returns: the score 

532 """ 

533 return min(element) 

534 

535 def __str__(self) -> str: 

536 """ 

537 Get the selector name. 

538 

539 :returns "min": always 

540 """ 

541 return "min" 

542 

543 

544class __NormalizedHeuristicSelector(HeuristicSelector): 

545 """A heuristic selector.""" 

546 

547 def weight(self, counts: list[list[int]]) -> list[int] | None: 

548 """ 

549 Compute the total score. 

550 

551 This function can be overwritten to compute the total score. 

552 

553 :param counts: the counts 

554 :return: a weight factor, that may be ignored by some methods 

555 """ 

556 result: list[int] = [sum(t) for t in counts] 

557 return None if (list.__len__(result) < 1) or ( 

558 max(result) <= 0) else result 

559 

560 

561class __HeuristicSelectorNormTiered(__NormalizedHeuristicSelector): 

562 """A normalized tiered heuristic selector.""" 

563 

564 def score(self, element: tuple[int, ...], counts: list[list[int]], 

565 weights: Any) -> list[float]: 

566 """ 

567 Score a given element. 

568 

569 :param element: the tuple to score 

570 :param counts: the element counts per dimension 

571 :param weights: the weights 

572 :returns: the score 

573 """ 

574 return sorted(counts[i][t] / weights[i] for i, t in enumerate( 

575 element) if weights[i] > 0) 

576 

577 def __str__(self) -> str: 

578 """ 

579 Get the selector name. 

580 

581 :returns "normalizedTiered": always 

582 """ 

583 return "normalizedTiered" 

584 

585 

586class __HeuristicSelectorNormTieredRev(__NormalizedHeuristicSelector): 

587 """A normalized tiered reverse heuristic selector.""" 

588 

589 def score(self, element: tuple[int, ...], counts: list[list[int]], 

590 weights: Any) -> list[float]: 

591 """ 

592 Score a given element. 

593 

594 :param element: the tuple to score 

595 :param counts: the element counts per dimension 

596 :param weights: the weights 

597 :returns: the score 

598 """ 

599 return sorted((counts[i][t] / weights[i] for i, t in enumerate( 

600 element) if weights[i] > 0), reverse=True) 

601 

602 def __str__(self) -> str: 

603 """ 

604 Get the selector name. 

605 

606 :returns "normalizedTieredReverse": always 

607 """ 

608 return "normalizedTieredReverse" 

609 

610 

611class __HeuristicSelectorNormSum(__NormalizedHeuristicSelector): 

612 """A normalized sum heuristic selector.""" 

613 

614 def score(self, element: tuple[int, ...], counts: list[list[int]], 

615 weights: Any) -> float: 

616 """ 

617 Score a given element. 

618 

619 :param element: the tuple to score 

620 :param counts: the element counts per dimension 

621 :param weights: the weights 

622 :returns: the score 

623 """ 

624 return sum(counts[i][t] / weights[i] for i, t in enumerate( 

625 element) if weights[i] > 0) 

626 

627 def __str__(self) -> str: 

628 """ 

629 Get the selector name. 

630 

631 :returns "normalizedSum": always 

632 """ 

633 return "normalizedSum" 

634 

635 

636class __SameNumberOfRuns(Selector): 

637 """A selector choosing the same runs for all instance/algorithm combos.""" 

638 

639 def select(self, 

640 dims: tuple[int, int, int, int, int], 

641 keys: tuple[tuple[int, int, int, int, int], ...], 

642 best_length: int) -> list[tuple[ 

643 int, int, int, int, int]] | None: 

644 """ 

645 Perform the dataset selection. 

646 

647 :param dims: the number of different values per key dimension 

648 :param keys: the data keys to select from 

649 :param best_length: the length of the best-so-far set of runs, 

650 will be `-1` if no such best exists 

651 :return: the selected data 

652 """ 

653 runs: list[dict[tuple[int, int, int], set[int]]] = [ 

654 {} for _ in range(dims[KEY_INSTANCE])] 

655 n_combos: int = 0 

656 for key in keys: 

657 dct = runs[key[KEY_INSTANCE]] 

658 subkey = (key[KEY_ALGORITHM], key[KEY_ENCODING], 

659 key[KEY_OBJECTIVE]) 

660 if subkey in dct: 

661 dct[subkey].add(key[KEY_SEED]) 

662 else: 

663 dct[subkey] = {key[KEY_SEED]} 

664 n_combos += 1 

665 

666 if n_combos <= 0: 

667 raise ValueError("No runs??") 

668 

669 inst_seeds: list[set[int]] = [ 

670 next(iter(dct.values())) for dct in runs] 

671 min_set_len: int = tuple.__len__(keys) 

672 for i, dct in enumerate(runs): 

673 base = inst_seeds[i] 

674 for st in dct.values(): 

675 base.intersection_update(st) 

676 sl: int = set.__len__(base) 

677 if sl < min_set_len: 

678 if sl <= 0: 

679 logger("Cannot find non-empty instance/run intersection.") 

680 return None 

681 if (sl * n_combos) <= best_length: 

682 logger(f"Cannot surpass best length {best_length}.") 

683 return None 

684 min_set_len = sl 

685 

686 logger(f"Get {min_set_len} seeds per instance/algorithm/objective/" 

687 f"encoding combination.") 

688 use_seeds: list[list[int]] = [ 

689 sorted(st)[:min_set_len] for st in inst_seeds] 

690 logger(f"Found {len(use_seeds)} seeds to use.") 

691 return [key for key in keys if key[KEY_SEED] in use_seeds[ 

692 key[KEY_INSTANCE]]] 

693 

694 def __str__(self) -> str: 

695 """ 

696 Get the text representation of this selector. 

697 

698 :returns "sameNumberOfRuns": always 

699 """ 

700 return "sameNumberOfRuns" 

701 

702 

703def __seed_hash(x: tuple[str, int]) -> tuple[str, int]: 

704 """ 

705 Compute a hash for instance-random seeds. 

706 

707 The selection algorithm will deterministically choose which runs to 

708 keep. To make it truly deterministic, we always sort the settings 

709 according to the algorithm, instance, objective function, encoding, and 

710 random seed. 

711 

712 When we create this order of configurations, we can normally rely on the 

713 natural or alphabetic order for algorithms, objectives, instances, and 

714 encodings. 

715 However, if we also use the natural order for random seeds, this might 

716 potentially lead to the problem that runs with larger random seeds are 

717 deleted more likely. 

718 Deleting some algorithms or instances is not really a problem, but using 

719 the seed value to select runs via a natural order of seeds could be 

720 problematic. 

721 The hash is based on a tuple containing the seed, which is different from 

722 the seed but still reliably the same in every run. 

723 This should lead to a uniform probability of seed deletion over the random 

724 seed spectrum in the absence of other criteria. 

725 

726 :param x: the instance-random seeds 

727 :return: the hash 

728 """ 

729 return x[0], hash((x[1], )) # force hash to be different from x[1] 

730 

731 

732#: All combinations of instances/algorithms/encodings/objectives get the same 

733#: number of runs, and on all instances the same seeds are used. 

734#: This selector is quite fast and simple. 

735#: It will only delete runs, but attempt to retain all instance, algorithms, 

736#: objective, and encoding combinations. 

737#: It will thus fail if there are some combinations with mutually distinct 

738#: run sets. 

739SELECTOR_SAME_RUNS_FOR_ALL: Final[tuple[Selector, ...]] = ( 

740 __SameNumberOfRuns(), ) 

741 

742#: A simple selector set for maximum runs. 

743#: This selector first attempts to do the selection given in 

744#: :const:`SELECTOR_SAME_RUNS_FOR_ALL` and then attempts to find 

745#: a larger set of consistent runs that might result from dropping off 

746#: instances, encodings, algorithms, or objectives. 

747SELECTOR_MAX_RUNS_SIMPLE: Final[tuple[Selector, ...]] = ( 

748 *SELECTOR_SAME_RUNS_FOR_ALL, __HeuristicSelectorTiered()) 

749 

750#: Select the maximum number of runs in the most thoroughly possible way. 

751#: This selector performs many more different attempts compared to 

752#: :const:`SELECTOR_MAX_RUNS_SIMPLE`. It is very thorough in attempting to 

753#: find the largest possible set of consistent runs. It will therefore also 

754#: be much slower. 

755SELECTOR_MAX_RUNS: Final[tuple[Selector, ...]] = ( 

756 *SELECTOR_MAX_RUNS_SIMPLE, 

757 __HeuristicSelectorNormTieredRev(), 

758 __HeuristicSelectorSum(), __HeuristicSelectorProduct(), 

759 __HeuristicSelectorMinimum(), __HeuristicSelectorNormTiered(), 

760 __HeuristicSelectorNormTieredRev(), __HeuristicSelectorNormSum()) 

761 

762 

763def select_consistent( 

764 data: Iterable[T], 

765 selectors: Iterable[Selector] = SELECTOR_MAX_RUNS) -> list[T]: 

766 """ 

767 Select data such that the numbers of runs are consistent. 

768 

769 The input is a set of data items which represent some records over the 

770 runs of algorithms on instances. It may be that not all algorithms have 

771 been applied to all instances. Maybe the number of runs is inconsistent 

772 over the algorithm-instance combinations, too. Maybe some algorithms 

773 have more runs on some instances. Maybe the runs are even different, 

774 it could be that some algorithms have runs for seed `A`, `B`, and `C` on 

775 instance `I`, while others have runs for seed `C` and `D`. This function 

776 is designed to retain only the runs with seed `C` in such a case. It may 

777 discard algorithms or instances or algorithm-instance-seed combinations 

778 in order to obtain a selection of data where all algorithms have been 

779 applied to all instances as same as often and using the same seeds. 

780 

781 Now there are different ways to select such consistent subsets of a 

782 dataset. Of course, we want to select the data such that as much as 

783 possible of the data is retained and as little as possible is discarded. 

784 This may be a hard optimization problem in itself. Here, we offer a 

785 heuristic solution. Basically, we step-by-step try to cut away the 

786 setups that are covered by the least amount of runs. We keep repeating 

787 this until we arrive in a situation where all setups have the same 

788 amount of runs. We then check if there were some strange symmetries that 

789 still make the data inconsistent and, if we found some, try to delete 

790 one run to break the symmetries and then repeat the cleaning-up process. 

791 In the end, we should get a list of overall consistent data elements that 

792 can be used during a normal experiment evaluation procedure. 

793 

794 This iterative process may be rather slow on larger datasets, but it is 

795 maybe the best approximation we can offer to retain as much data as 

796 possible. 

797 

798 :param data: the source data 

799 :param selectors: the selectors to use 

800 :return: a list with the selected data 

801 

802 >>> def __p(x) -> str: 

803 ... return (f"{x.algorithm}/{x.instance}/{x.objective}/{x.encoding}/" 

804 ... f"{x.rand_seed}") 

805 

806 >>> a1i1o1e1s1 = PerRunData("a1", "i1", "o1", "e1", 1) 

807 >>> a1i1o1e1s2 = PerRunData("a1", "i1", "o1", "e1", 2) 

808 >>> a1i1o1e1s3 = PerRunData("a1", "i1", "o1", "e1", 3) 

809 >>> a1i2o1e1s1 = PerRunData("a1", "i2", "o1", "e1", 1) 

810 >>> a1i2o1e1s2 = PerRunData("a1", "i2", "o1", "e1", 2) 

811 >>> a1i2o1e1s3 = PerRunData("a1", "i2", "o1", "e1", 3) 

812 >>> a2i1o1e1s1 = PerRunData("a2", "i1", "o1", "e1", 1) 

813 >>> a2i1o1e1s2 = PerRunData("a2", "i1", "o1", "e1", 2) 

814 >>> a2i1o1e1s3 = PerRunData("a2", "i1", "o1", "e1", 3) 

815 >>> a2i2o1e1s1 = PerRunData("a1", "i2", "o1", "e1", 1) 

816 >>> a2i2o1e1s2 = PerRunData("a2", "i2", "o1", "e1", 2) 

817 >>> a2i2o1e1s3 = PerRunData("a2", "i2", "o1", "e1", 3) 

818 

819 >>> list(map(__p, select_consistent(( 

820 ... a1i1o1e1s1, a1i1o1e1s2, a1i1o1e1s3, 

821 ... a1i2o1e1s1, a1i2o1e1s2, a1i2o1e1s3, 

822 ... a2i1o1e1s1, a2i1o1e1s2, 

823 ... a2i2o1e1s2, a2i2o1e1s3)))) 

824 ['a1/i1/o1/e1/1', 'a1/i1/o1/e1/2', 'a1/i2/o1/e1/2', 'a1/i2/o1/e1/3',\ 

825 'a2/i1/o1/e1/1', 'a2/i1/o1/e1/2', 'a2/i2/o1/e1/2', 'a2/i2/o1/e1/3'] 

826 

827 >>> list(map(__p, select_consistent(( 

828 ... a1i1o1e1s2, a1i1o1e1s3, 

829 ... a1i2o1e1s1, a1i2o1e1s2, a1i2o1e1s3, 

830 ... a2i1o1e1s1, a2i1o1e1s2, 

831 ... a2i2o1e1s2, a2i2o1e1s3)))) 

832 ['a1/i1/o1/e1/2', 'a1/i2/o1/e1/3', 'a2/i1/o1/e1/2', 'a2/i2/o1/e1/3'] 

833 

834 >>> list(map(__p, select_consistent(( 

835 ... a1i1o1e1s2, a1i1o1e1s3, 

836 ... a1i2o1e1s1, a1i2o1e1s2, a1i2o1e1s3, 

837 ... a2i1o1e1s1, a2i1o1e1s2, 

838 ... a2i2o1e1s2)))) 

839 ['a1/i1/o1/e1/2', 'a1/i2/o1/e1/2', 'a2/i1/o1/e1/2', 'a2/i2/o1/e1/2'] 

840 

841 >>> list(map(__p, select_consistent(( 

842 ... a1i1o1e1s1, a1i1o1e1s2, a1i1o1e1s3, 

843 ... a2i2o1e1s1, a2i2o1e1s2, a2i2o1e1s3)))) 

844 ['a1/i1/o1/e1/1', 'a1/i1/o1/e1/2', 'a1/i1/o1/e1/3'] 

845 

846 >>> list(map(__p, select_consistent(( 

847 ... a1i1o1e1s1, a1i1o1e1s2, a1i1o1e1s3, 

848 ... a2i1o1e1s1, a2i1o1e1s2, a2i1o1e1s3)))) 

849 ['a1/i1/o1/e1/1', 'a1/i1/o1/e1/2', 'a1/i1/o1/e1/3', \ 

850'a2/i1/o1/e1/1', 'a2/i1/o1/e1/2', 'a2/i1/o1/e1/3'] 

851 

852 >>> list(map(__p, select_consistent(( 

853 ... a1i1o1e1s1, a1i1o1e1s2, a1i2o1e1s2, a1i2o1e1s3)))) 

854 ['a1/i1/o1/e1/1', 'a1/i1/o1/e1/2', 'a1/i2/o1/e1/2', 'a1/i2/o1/e1/3'] 

855 

856 >>> list(map(__p, select_consistent(( 

857 ... a1i1o1e1s1, a1i1o1e1s2, a1i2o1e1s2)))) 

858 ['a1/i1/o1/e1/1', 'a1/i2/o1/e1/2'] 

859 

860 >>> list(map(__p, select_consistent(( 

861 ... a1i1o1e1s1, a2i1o1e1s2)))) 

862 ['a1/i1/o1/e1/1'] 

863 

864 >>> list(map(__p, select_consistent(( 

865 ... a1i1o1e1s1, a2i1o1e1s2, a2i1o1e1s3)))) 

866 ['a2/i1/o1/e1/2', 'a2/i1/o1/e1/3'] 

867 

868 >>> try: 

869 ... select_consistent((a1i1o1e1s1, a1i1o1e1s2, a1i2o1e1s2, a1i2o1e1s2)) 

870 ... except ValueError as ve: 

871 ... print(str(ve)[:30]) 

872 Found two records of type PerR 

873 

874 >>> try: 

875 ... select_consistent(1) 

876 ... except TypeError as te: 

877 ... print(te) 

878 data should be an instance of typing.Iterable but is int, namely 1. 

879 

880 >>> try: 

881 ... select_consistent({234}) 

882 ... except TypeError as te: 

883 ... print(str(te)[:20]) 

884 data[0] should be an 

885 

886 >>> try: 

887 ... select_consistent((a1i1o1e1s1, a1i1o1e1s2, a1i2o1e1s2), 1) 

888 ... except TypeError as te: 

889 ... print(str(te)[:19]) 

890 selectors should be 

891 

892 >>> try: 

893 ... select_consistent((a1i1o1e1s1, a1i1o1e1s2, a1i2o1e1s2), (1, )) 

894 ... except TypeError as te: 

895 ... print(str(te)[:21]) 

896 selectors[0] should b 

897 """ 

898 if not isinstance(data, Iterable): 

899 raise type_error(data, "data", Iterable) 

900 if not isinstance(selectors, Iterable): 

901 raise type_error(selectors, "selectors", Iterable) 

902 

903 # make data re-iterable 

904 use_data = data if isinstance(data, list | tuple) else list(data) 

905 total_len: Final[int] = len(use_data) 

906 if total_len <= 0: 

907 raise ValueError("The data is empty!") 

908 algorithm_set: set[str] = set() 

909 instance_set: set[str] = set() 

910 objective_set: set[str] = set() 

911 encoding_set: set[str] = set() 

912 seed_set: set[tuple[str, int]] = set() 

913 for i, item in enumerate(use_data): 

914 if not isinstance(item, PerRunData): 

915 raise type_error(item, f"data[{i}]", PerRunData) 

916 algorithm_set.add(item.algorithm) 

917 instance_set.add(item.instance) 

918 objective_set.add(item.objective) 

919 encoding_set.add(item.encoding)