Post Az2clZXXqXHODMWe8m by louis@social.louis-vallat.dev
(DIR) More posts by louis@social.louis-vallat.dev
(DIR) Post #Az2bdio7PI8GgZyEBE by aparrish@friend.camp
2025-10-09T18:14:35Z
0 likes, 0 repeats
so i have an array with several thousand elements, ~50% of which are empty. the empty elements aren't uniformly distributed over the length of the array. (it's a hash table.) i want to select a non-empty array element at random. is there a clever way to do this that (a) is constant time (or close); (b) doesn't require a second data structure; and (c) isn't just sampling at random in a loop until you get a hit? (this is for an embedded application so RAM is at a premium)
(DIR) Post #Az2bdk0CxpOgOMdOfA by louis@social.louis-vallat.dev
2025-10-09T18:32:03.028Z
0 likes, 0 repeats
@aparrish@friend.camp I guess you can't just filter the hash-table and remove the empty elements to make things easier, right?
(DIR) Post #Az2bdnXdnyvHMvIdgu by aparrish@friend.camp
2025-10-09T18:18:49Z
0 likes, 0 repeats
(the question is mostly academic because sampling at random until i get a hit is probably fast enough for my application? same with starting from a random index and then iterating forward through the array until i find a non-empty entry. mostly just curious if there's some "good enough" solution to the problem with these constraints)
(DIR) Post #Az2clYL6JJjOUThC6a by aparrish@friend.camp
2025-10-09T18:33:48Z
0 likes, 0 repeats
@louis that would either be O(n) (iterating through the array to find the non-empty elements) or require a second data structure (an array that has the indices of non-empty elements)
(DIR) Post #Az2clZXXqXHODMWe8m by louis@social.louis-vallat.dev
2025-10-09T18:44:42.884Z
0 likes, 0 repeats
@aparrish@friend.camp ah yeah, preparation is included in the algorithm complexity (which is fair, I just wasn't sure that you were allowed to count it separately)Like for example if you were reading the hash-table from a file, you could just not include the empty elements if you never need them :apensive: