nprofile1qy2hwumn8ghj7un9d3shjtnddaehgu3wwp6kyqpqdhnn6acp8d933rcmkrw8vceqfhyfr26jw4a9katmwqhqelwkc50swqrcc0 (nprofile…rcc0) I took a look at your index_slow_and_bad, and I think that the reason it’s slow is that you’re iterating over the whole reindeers set in each iteration of the loop. this means that choosing the best reindeer takes O(n) time, and the whole algorithm takes O(n²) time.
to make A* actually be fast, you need a better data structure for this – a priority queue
these are usually implemented as a heap. let me know if you’d like me to explain further!
mei /
npub1mx…mgnxv
2024-12-26 09:51:34
in reply to nevent1q…uawy
Author Public Key
npub1mx50e9vuyx0eytmncz2mvv68kgc6402qypkm22uk9uk9x7u6vl3symgnxvPublished at
2024-12-26 09:51:34Event JSON
{
"id": "10c9b0491b512fb737676bebde9353e2e76f1443e27203714d8c9dd557f84bcd",
"pubkey": "d9a8fc959c219f922f73c095b63347b231aabd40206db52b962f2c537b9a67e3",
"created_at": 1735206694,
"kind": 1,
"tags": [
[
"p",
"6de73d77013b4b188f1bb0dc7663204dc891ab52757a5b757b702e0cfdd6c51f",
"wss://relay.mostr.pub"
],
[
"p",
"a165e2c61e5bc7612f4fe5f5f08470b16d325f295e0b8030676818209fdd9b84",
"wss://relay.mostr.pub"
],
[
"e",
"4a773e06ba94faaf2e99273140b934891ddfac7a116892d198e73b5ac6c65af8",
"wss://relay.mostr.pub",
"reply"
],
[
"content-warning",
"advent of code day 16"
],
[
"proxy",
"https://donotsta.re/objects/06f2fdf1-4b51-4dfa-af74-cdf155f9ffca",
"activitypub"
]
],
"content": "nostr:nprofile1qy2hwumn8ghj7un9d3shjtnddaehgu3wwp6kyqpqdhnn6acp8d933rcmkrw8vceqfhyfr26jw4a9katmwqhqelwkc50swqrcc0 I took a look at your index_slow_and_bad, and I think that the reason it’s slow is that you’re iterating over the whole reindeers set in each iteration of the loop. this means that choosing the best reindeer takes O(n) time, and the whole algorithm takes O(n²) time.\n\nto make A* actually be fast, you need a better data structure for this – a priority queue\n\nthese are usually implemented as a heap. let me know if you’d like me to explain further!",
"sig": "e6fc88e928a8a6db017f75972172952c13644bb22c532757cdb774ecf37281e907adadd4a7d510e5031bbf90845808bbedaa523c20a3e0e6d7f6938c6e21692b"
}