adventofcode

commit

c2ce18451bcacb6ccde51a26aeabe387ca9ecc9f

parent

756fbba13da3082a2a58bde4d13a55a5710bd821

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2021-12-23 14:01

sort on insert

in theory, both should behave the same. They do not though:

-	with sort, a possible path is found quickly, but the search continues
	for a while until the best path is found. The stack size hovers around
	100.
-	with insert, the stack increases linearily. Once a path is found the
	search quickly ends.

This behavior is the same no matter whether the sorting is based on
positive or negative estimations. However, the sort order again has
suprising effects:

-	with sort, negative is much faster than positive order
-	with insert, positive is much faster than negative order

theory: with sort, duplicates were re-ordered according to their updated
(lower) estimate. With insert, duplicates remain far back in the queue
until they are (probably) disgarded once a path is found. This is not an
issue for time, only for memory. Checking for duplicates would require
additional time. Since time is more an issue than memory here I will
leave it this way.

Diffstat

1 files changed, 4 insertions, 2 deletions

diff --git a/2021/23/part1.rs b/2021/23/part1.rs

@@ -228,11 +228,13 @@ fn main() {
  228   228                 if m == target {
  229   229                     queue = queue.into_iter().filter(|map| *estimates.get(map).unwrap() < e).collect();
  230   230                 } else {
  231    -1                     queue.push(m);
   -1   231                     match queue.binary_search_by_key(&ee, |map| *estimates.get(map).unwrap()) {
   -1   232                         Ok(i) => queue.insert(i, m),
   -1   233                         Err(i) => queue.insert(i, m),
   -1   234                     }
  232   235                 }
  233   236             }
  234   237         }
  235    -1         queue.sort_by_key(|map| -estimates.get(map).unwrap());
  236   238     }
  237   239 
  238   240     println!("{}", energies.get(&target).unwrap());