<turbo-stream action="append" target="posts_list"><template>    <div class="postbit" id="371028" data-post-id="371028">
  <section>
    <div class="post-wrap">


					<div class="post-header">
		        <div class="user-avatar">
		          <img alt="jaybe78" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/jaybe78/120/36069_2.png" width="120" height="120" />
		        </div>
					
						<div class="user-details">
		          <div class="user-name">
		            <h3>
                  jaybe78
                    <span class="op-star" title="Thread Starter">
                      <img alt="OP" class="op-star-icon" src="/assets/thread-icons/thread-icon-thread-starter-df91e872.png" />
                    </span>
                  </h3>
		          </div>
						
						</div>
					
					</div>

	        <div class="thread-main">
	            <div class="post-body" data-turbo="false">
								<blockquote>
<p>For matchmaking wouldn’t you want to prefer people having waited longer over people just having joined the queue</p>
</blockquote>
<p>Not sure the word “queue” is the right word in that context.<br>
Users are not really waiting in line, they are not really waiting anything.</p>
<p>It’s more like at some point we have an X amount of users online, ready to play a certain game, and as a user whether there’s 100_000 or less of those, I want to see a random 100 of those displayed in a list that I can scroll through .</p>
<p>Therefore, I keep track of all those guys at all time and remove them either when they disconnect or they have already found a partner to play with.</p>
<p>It’s more a status tracking across different games and levels(beginner, good, high).</p>
<blockquote>
<p>Also would there really be a million people waiting in the queue or rather be a million people playing?</p>
</blockquote>
<p>It could be a million users, some of them might look at the search result and scroll through it for some time (minutes) before they find someone they want to play with.</p>
<p>It’s difficult to predict how fast the number of users would decrease.</p>
<p>It depends on user’s preference and how “good” the result of the search is.<br>
Once again, that’s why I want the result to be as different as possible for everyone.</p>
<p>So I guess sometimes it could be really fast to decrease and sometimes it could stagnate for some time</p>
<blockquote>
<p>If you form couples quickly enought the queue might stay at a reasonable size</p>
</blockquote>
<p>Well if I manage to return users list fast enough and shuffle enough so that users don’t see the same users on their screen, I definitely have a higher change to create couple faster, but as I said, then the ball is on the side of the user looking scrolling through the results returned.</p>
<p>If he’s not please with it, he could still click “search” again and see another set of random users.</p>
<p>that’s basically the goal</p> 
	            </div>

	            <div class="base-line">
	                <div class="thread-counters">
	                    <span class="thread-count count-likes js-likers-trigger" title="Likes" data-post-id="371028" data-batch-url="/posts/batch_likers">
                        0
                      </span>
                      <!-- <span class="thread-count js-solved-indicator" title="Marked as solution"></span> -->
	                </div>
	                <div class="go-to-post">
	                  <a title="Go to post" alt="Go to post" href="https://forum.elixirforum.com/t/search-random-elements-in-a-big-ets-table-1m/71997/12">Post #11</a>
	                </div>
	            </div>
              <div id="likers-container-371028" 
                   class="likers-container"
                   data-first-post="false"
                   data-batch-url="/posts/batch_likers">
                   <div class="likers-placeholder" 
                     data-likers-post-id="371028"
                     data-batch-url="/posts/batch_likers">
                  <div class="post-likers"></div>
                </div>
              </div>
	        </div>
			

    </div>

    <div class="triangle-top-right type-standard-post cat-standard-post" title="Post #11"></div>
  </section>
</div>
    <div class="postbit" id="371029" data-post-id="371029">
  <section>
    <div class="post-wrap">


					<div class="post-header">
		        <div class="user-avatar">
		          <img alt="derek-zhou" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/derek-zhou/120/19943_2.png" width="120" height="120" />
		        </div>
					
						<div class="user-details">
		          <div class="user-name">
		            <h3>
                  derek-zhou
                  </h3>
		          </div>
						
						</div>
					
					</div>

	        <div class="thread-main">
	            <div class="post-body" data-turbo="false">
								<aside class="quote no-group" data-username="jaybe78" data-post="8" data-topic="71997" data-full="true">
<div class="title">
<div class="quote-controls"></div>
<img alt="" width="24" height="24" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/jaybe78/48/36069_2.png" class="avatar"> jaybe78:</div>
<blockquote>
<p>That would not solve the current_max increasing constantly while the table is mostly unoccupied as pointed out by <a class="mention" href="/u/al2o3cr" rel="nofollow">@al2o3cr</a></p>
</blockquote>
</aside>
<p>If there are constant churns,  then current_max will be ever increasing. However, <code>:ets.next/2</code> should still be log(n) time, because ordered_set is a binary tree under the hood, <code>next</code> works the same way regardless if the element exist or not.</p>
<p>If you want to keep your id space from getting too sparse,  you can take a random jab into <code>1..current_max</code> at allocation time and reuse that id if not occupied.</p> 
	            </div>

	            <div class="base-line">
	                <div class="thread-counters">
	                    <span class="thread-count count-likes js-likers-trigger" title="Likes" data-post-id="371029" data-batch-url="/posts/batch_likers">
                        0
                      </span>
                      <!-- <span class="thread-count js-solved-indicator" title="Marked as solution"></span> -->
	                </div>
	                <div class="go-to-post">
	                  <a title="Go to post" alt="Go to post" href="https://forum.elixirforum.com/t/search-random-elements-in-a-big-ets-table-1m/71997/13">Post #12</a>
	                </div>
	            </div>
              <div id="likers-container-371029" 
                   class="likers-container"
                   data-first-post="false"
                   data-batch-url="/posts/batch_likers">
                   <div class="likers-placeholder" 
                     data-likers-post-id="371029"
                     data-batch-url="/posts/batch_likers">
                  <div class="post-likers"></div>
                </div>
              </div>
	        </div>
			

    </div>

    <div class="triangle-top-right type-standard-post cat-standard-post" title="Post #12"></div>
  </section>
</div>
    <div class="postbit" id="371030" data-post-id="371030">
  <section>
    <div class="post-wrap">


					<div class="post-header">
		        <div class="user-avatar">
		          <img alt="jaybe78" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/jaybe78/120/36069_2.png" width="120" height="120" />
		        </div>
					
						<div class="user-details">
		          <div class="user-name">
		            <h3>
                  jaybe78
                    <span class="op-star" title="Thread Starter">
                      <img alt="OP" class="op-star-icon" src="/assets/thread-icons/thread-icon-thread-starter-df91e872.png" />
                    </span>
                  </h3>
		          </div>
						
						</div>
					
					</div>

	        <div class="thread-main">
	            <div class="post-body" data-turbo="false">
								<blockquote>
<p>If there are constant churns, then current_max will be ever increasing. However, <code>:ets.next/2</code> should still be log(n) time,</p>
</blockquote>
<p>Ok, I read somewhere that it would not scale well, but I guess I should prototype and benchmark this <img src="https://forum.elixirforum.com/images/emoji/apple/slight_smile.png?v=15" title=":slight_smile:" class="emoji" alt=":slight_smile:" loading="lazy" width="20" height="20"></p>
<blockquote>
<p>f you want to keep your id space from getting too sparse, you can take a random jab into <code>1..current_max</code> at allocation time and reuse that id if not occupied.</p>
</blockquote>
<p>Yes I was thinking about storing the removed indexes and reusing them when a new user join.<br>
that could work</p>
<p>Thanks</p> 
	            </div>

	            <div class="base-line">
	                <div class="thread-counters">
	                    <span class="thread-count count-likes js-likers-trigger" title="Likes" data-post-id="371030" data-batch-url="/posts/batch_likers">
                        0
                      </span>
                      <!-- <span class="thread-count js-solved-indicator" title="Marked as solution"></span> -->
	                </div>
	                <div class="go-to-post">
	                  <a title="Go to post" alt="Go to post" href="https://forum.elixirforum.com/t/search-random-elements-in-a-big-ets-table-1m/71997/14">Post #13</a>
	                </div>
	            </div>
              <div id="likers-container-371030" 
                   class="likers-container"
                   data-first-post="false"
                   data-batch-url="/posts/batch_likers">
                   <div class="likers-placeholder" 
                     data-likers-post-id="371030"
                     data-batch-url="/posts/batch_likers">
                  <div class="post-likers"></div>
                </div>
              </div>
	        </div>
			

    </div>

    <div class="triangle-top-right type-standard-post cat-standard-post" title="Post #13"></div>
  </section>
</div>
    <div class="postbit" id="371031" data-post-id="371031">
  <section>
    <div class="post-wrap">


					<div class="post-header">
		        <div class="user-avatar">
		          <img alt="jstimps" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/jstimps/120/37213_2.png" width="120" height="120" />
		        </div>
					
						<div class="user-details">
		          <div class="user-name">
		            <h3>
                  jstimps
                  </h3>
		          </div>
						
						</div>
					
					</div>

	        <div class="thread-main">
	            <div class="post-body" data-turbo="false">
								<p>What if you were to insert into an <code>:ordered_set</code> table with a uniformly random key? Then the first N items in the table would be properly shuffled ahead of time. When you want to sample N items, you just choose the first N you encounter with <code>:ets.first</code>/<code>:ets.next</code> and then reshuffle them (by deleting and re-inserting).</p>
<p>Some disadvantages</p>
<ul>
<li>deleting and re-inserting should be atomic, hence the GenServer</li>
<li>collisions theoretically possible</li>
</ul>
<aside class="onebox githubgist" data-onebox-src="https://gist.github.com/jessestimpson/3ac340166cc5f6acce40ad1239412d94">
  <header class="source">

      <a href="https://gist.github.com/jessestimpson/3ac340166cc5f6acce40ad1239412d94" target="_blank" rel="noopener nofollow ugc">gist.github.com</a>
  </header>

  <article class="onebox-body">
    <h4><a href="https://gist.github.com/jessestimpson/3ac340166cc5f6acce40ad1239412d94" target="_blank" rel="noopener nofollow ugc">https://gist.github.com/jessestimpson/3ac340166cc5f6acce40ad1239412d94</a></h4>



  </article>

  <div class="onebox-metadata">
    
    
  </div>

  <div style="clear: both"></div>
</aside>
 
	            </div>

	            <div class="base-line">
	                <div class="thread-counters">
	                    <span class="thread-count count-likes js-likers-trigger" title="Likes" data-post-id="371031" data-batch-url="/posts/batch_likers">
                        0
                      </span>
                      <!-- <span class="thread-count js-solved-indicator" title="Marked as solution"></span> -->
	                </div>
	                <div class="go-to-post">
	                  <a title="Go to post" alt="Go to post" href="https://forum.elixirforum.com/t/search-random-elements-in-a-big-ets-table-1m/71997/15">Post #14</a>
	                </div>
	            </div>
              <div id="likers-container-371031" 
                   class="likers-container"
                   data-first-post="false"
                   data-batch-url="/posts/batch_likers">
                   <div class="likers-placeholder" 
                     data-likers-post-id="371031"
                     data-batch-url="/posts/batch_likers">
                  <div class="post-likers"></div>
                </div>
              </div>
	        </div>
			

    </div>

    <div class="triangle-top-right type-solved cat-solved" title="Marked as solution"></div>
  </section>
</div>
    <div class="postbit" id="371032" data-post-id="371032">
  <section>
    <div class="post-wrap">


					<div class="post-header">
		        <div class="user-avatar">
		          <img alt="LostKobrakai" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/LostKobrakai/120/3072_2.png" width="120" height="120" />
		        </div>
					
						<div class="user-details">
		          <div class="user-name">
		            <h3>
                  LostKobrakai
                  </h3>
		          </div>
						
						</div>
					
					</div>

	        <div class="thread-main">
	            <div class="post-body" data-turbo="false">
								<p>I guess you’d incur the same perf problems with that, just not on lookup, but on reshuffling.</p> 
	            </div>

	            <div class="base-line">
	                <div class="thread-counters">
	                    <span class="thread-count count-likes js-likers-trigger" title="Likes" data-post-id="371032" data-batch-url="/posts/batch_likers">
                        0
                      </span>
                      <!-- <span class="thread-count js-solved-indicator" title="Marked as solution"></span> -->
	                </div>
	                <div class="go-to-post">
	                  <a title="Go to post" alt="Go to post" href="https://forum.elixirforum.com/t/search-random-elements-in-a-big-ets-table-1m/71997/16">Post #15</a>
	                </div>
	            </div>
              <div id="likers-container-371032" 
                   class="likers-container"
                   data-first-post="false"
                   data-batch-url="/posts/batch_likers">
                   <div class="likers-placeholder" 
                     data-likers-post-id="371032"
                     data-batch-url="/posts/batch_likers">
                  <div class="post-likers"></div>
                </div>
              </div>
	        </div>
			

    </div>

    <div class="triangle-top-right type-standard-post cat-standard-post" title="Post #15"></div>
  </section>
</div>
    <div class="postbit" id="371033" data-post-id="371033">
  <section>
    <div class="post-wrap">


					<div class="post-header">
		        <div class="user-avatar">
		          <img alt="jstimps" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/jstimps/120/37213_2.png" width="120" height="120" />
		        </div>
					
						<div class="user-details">
		          <div class="user-name">
		            <h3>
                  jstimps
                  </h3>
		          </div>
						
						</div>
					
					</div>

	        <div class="thread-main">
	            <div class="post-body" data-turbo="false">
								<p>With 1M items, sampling 10 takes ~100 usec, sampling 1000 takes ~3 msec.</p> 
	            </div>

	            <div class="base-line">
	                <div class="thread-counters">
	                    <span class="thread-count count-likes js-likers-trigger" title="Likes" data-post-id="371033" data-batch-url="/posts/batch_likers">
                        0
                      </span>
                      <!-- <span class="thread-count js-solved-indicator" title="Marked as solution"></span> -->
	                </div>
	                <div class="go-to-post">
	                  <a title="Go to post" alt="Go to post" href="https://forum.elixirforum.com/t/search-random-elements-in-a-big-ets-table-1m/71997/17">Post #16</a>
	                </div>
	            </div>
              <div id="likers-container-371033" 
                   class="likers-container"
                   data-first-post="false"
                   data-batch-url="/posts/batch_likers">
                   <div class="likers-placeholder" 
                     data-likers-post-id="371033"
                     data-batch-url="/posts/batch_likers">
                  <div class="post-likers"></div>
                </div>
              </div>
	        </div>
			

    </div>

    <div class="triangle-top-right type-standard-post cat-standard-post" title="Post #16"></div>
  </section>
</div>
    <div class="postbit" id="371034" data-post-id="371034">
  <section>
    <div class="post-wrap">


					<div class="post-header">
		        <div class="user-avatar">
		          <img alt="LostKobrakai" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/LostKobrakai/120/3072_2.png" width="120" height="120" />
		        </div>
					
						<div class="user-details">
		          <div class="user-name">
		            <h3>
                  LostKobrakai
                  </h3>
		          </div>
						
						</div>
					
					</div>

	        <div class="thread-main">
	            <div class="post-body" data-turbo="false">
								<p>Oh, I was reading this as the whole table would be reshuffled.</p> 
	            </div>

	            <div class="base-line">
	                <div class="thread-counters">
	                    <span class="thread-count count-likes js-likers-trigger" title="Likes" data-post-id="371034" data-batch-url="/posts/batch_likers">
                        0
                      </span>
                      <!-- <span class="thread-count js-solved-indicator" title="Marked as solution"></span> -->
	                </div>
	                <div class="go-to-post">
	                  <a title="Go to post" alt="Go to post" href="https://forum.elixirforum.com/t/search-random-elements-in-a-big-ets-table-1m/71997/18">Post #17</a>
	                </div>
	            </div>
              <div id="likers-container-371034" 
                   class="likers-container"
                   data-first-post="false"
                   data-batch-url="/posts/batch_likers">
                   <div class="likers-placeholder" 
                     data-likers-post-id="371034"
                     data-batch-url="/posts/batch_likers">
                  <div class="post-likers"></div>
                </div>
              </div>
	        </div>
			

    </div>

    <div class="triangle-top-right type-standard-post cat-standard-post" title="Post #17"></div>
  </section>
</div>
    <div class="postbit" id="371035" data-post-id="371035">
  <section>
    <div class="post-wrap">


					<div class="post-header">
		        <div class="user-avatar">
		          <img alt="jstimps" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/jstimps/120/37213_2.png" width="120" height="120" />
		        </div>
					
						<div class="user-details">
		          <div class="user-name">
		            <h3>
                  jstimps
                  </h3>
		          </div>
						
						</div>
					
					</div>

	        <div class="thread-main">
	            <div class="post-body" data-turbo="false">
								<p>Yeah good point. My method would make it very unlikely to ever sample an item that was inserted at the end. You’re right, reshuffling the whole table would be necessary.</p> 
	            </div>

	            <div class="base-line">
	                <div class="thread-counters">
	                    <span class="thread-count count-likes js-likers-trigger" title="Likes" data-post-id="371035" data-batch-url="/posts/batch_likers">
                        0
                      </span>
                      <!-- <span class="thread-count js-solved-indicator" title="Marked as solution"></span> -->
	                </div>
	                <div class="go-to-post">
	                  <a title="Go to post" alt="Go to post" href="https://forum.elixirforum.com/t/search-random-elements-in-a-big-ets-table-1m/71997/19">Post #18</a>
	                </div>
	            </div>
              <div id="likers-container-371035" 
                   class="likers-container"
                   data-first-post="false"
                   data-batch-url="/posts/batch_likers">
                   <div class="likers-placeholder" 
                     data-likers-post-id="371035"
                     data-batch-url="/posts/batch_likers">
                  <div class="post-likers"></div>
                </div>
              </div>
	        </div>
			

    </div>

    <div class="triangle-top-right type-standard-post cat-standard-post" title="Post #18"></div>
  </section>
</div>
    <div class="postbit" id="371039" data-post-id="371039">
  <section>
    <div class="post-wrap">


					<div class="post-header">
		        <div class="user-avatar">
		          <img alt="garrison" src="/assets/icons/user-9f439610.png" width="120" height="120" />
		        </div>
					
						<div class="user-details">
		          <div class="user-name">
		            <h3>
                  garrison
                  </h3>
		          </div>
						
						</div>
					
					</div>

	        <div class="thread-main">
	            <div class="post-body" data-turbo="false">
								<p>Lol I read the OP and knew there had to be matchmaking involved. I don’t think I fully understand the use-case here but putting that aside for a moment…</p>
<aside class="quote no-group" data-username="jstimps" data-post="15" data-topic="71997">
<div class="title">
<div class="quote-controls"></div>
<img alt="" width="24" height="24" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/jstimps/48/37213_2.png" class="avatar"> jstimps:</div>
<blockquote>
<p>What if you were to insert into an <code>:ordered_set</code> table with a uniformly random key?</p>
</blockquote>
</aside>
<p>This is what I was going to suggest, but I see you figured it out first <img src="https://forum.elixirforum.com/images/emoji/apple/slight_smile.png?v=15" title=":slight_smile:" class="emoji" alt=":slight_smile:" loading="lazy" width="20" height="20"> I was feeling so clever, too!</p>
<aside class="quote no-group" data-username="jstimps" data-post="19" data-topic="71997" data-full="true">
<div class="title">
<div class="quote-controls"></div>
<img alt="" width="24" height="24" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/jstimps/48/37213_2.png" class="avatar"> jstimps:</div>
<blockquote>
<p>Yeah good point. My method would make it very unlikely to ever sample an item that was inserted at the end. You’re right, reshuffling the whole table would be necessary.</p>
</blockquote>
</aside>
<p>But why do you have to sample from the start? Sample from a random index in the uniform space and just scan until you hit the quota. Wrap around if you hit the end.</p>
<p>I don’t think this is equivalent to a true random sample but for this use-case I don’t think anyone will be able to tell.</p>
<p>Edit: Actually if you choose 100 random indices and call <code>:ets.next_lookup()</code> with them (instead of scanning from the first) I think this would be a truly random sample. Right?</p>
<pre data-code-wrap="elixir"><code class="lang-elixir">1..100
|&gt; Enum.map(fn _ -&gt; Enum.random(1..1_000_000) end)
|&gt; Enum.map(fn i -&gt;
  {_, [{_, value}]} = :ets.next_lookup(table, i)
  value
end)
</code></pre>
<p>Of course you could get duplicates but there are ways to deal with that.</p>
<p>Since the keys are already truly random there should be no bias from adding/removing users, no matter which users they are.</p> 
	            </div>

	            <div class="base-line">
	                <div class="thread-counters">
	                    <span class="thread-count count-likes js-likers-trigger" title="Likes" data-post-id="371039" data-batch-url="/posts/batch_likers">
                        4
                      </span>
                      <!-- <span class="thread-count js-solved-indicator" title="Marked as solution"></span> -->
	                </div>
	                <div class="go-to-post">
	                  <a title="Go to post" alt="Go to post" href="https://forum.elixirforum.com/t/search-random-elements-in-a-big-ets-table-1m/71997/20">Post #19</a>
	                </div>
	            </div>
              <div id="likers-container-371039" 
                   class="likers-container"
                   data-first-post="false"
                   data-batch-url="/posts/batch_likers">
                   <div class="likers-placeholder" 
                     data-likers-post-id="371039"
                     data-batch-url="/posts/batch_likers">
                  <div class="post-likers"></div>
                </div>
              </div>
	        </div>
			

    </div>

    <div class="triangle-top-right type-standard-post cat-standard-post" title="Post #19"></div>
  </section>
</div>
    <div class="postbit" id="371043" data-post-id="371043">
  <section>
    <div class="post-wrap">


					<div class="post-header">
		        <div class="user-avatar">
		          <img alt="jstimps" src="https://forum.elixirforum.com/user_avatar/forum.elixirforum.com/jstimps/120/37213_2.png" width="120" height="120" />
		        </div>
					
						<div class="user-details">
		          <div class="user-name">
		            <h3>
                  jstimps
                  </h3>
		          </div>
						
						</div>
					
					</div>

	        <div class="thread-main">
	            <div class="post-body" data-turbo="false">
								<p>Ah yes, you can start at a random location by generating a fake key and then wrap around. That seems to fix the problem. I updated the GitHub gist above with this idea… code was done in haste, so don’t judge me too hard <img src="https://forum.elixirforum.com/images/emoji/apple/slight_smile.png?v=15" title=":slight_smile:" class="emoji" alt=":slight_smile:" loading="lazy" width="20" height="20"></p> 
	            </div>

	            <div class="base-line">
	                <div class="thread-counters">
	                    <span class="thread-count count-likes js-likers-trigger" title="Likes" data-post-id="371043" data-batch-url="/posts/batch_likers">
                        1
                      </span>
                      <!-- <span class="thread-count js-solved-indicator" title="Marked as solution"></span> -->
	                </div>
	                <div class="go-to-post">
	                  <a title="Go to post" alt="Go to post" href="https://forum.elixirforum.com/t/search-random-elements-in-a-big-ets-table-1m/71997/21">Post #20</a>
	                </div>
	            </div>
              <div id="likers-container-371043" 
                   class="likers-container"
                   data-first-post="false"
                   data-batch-url="/posts/batch_likers">
                   <div class="likers-placeholder" 
                     data-likers-post-id="371043"
                     data-batch-url="/posts/batch_likers">
                  <div class="post-likers"></div>
                </div>
              </div>
	        </div>
			

    </div>

    <div class="triangle-top-right type-standard-post cat-standard-post" title="Post #20"></div>
  </section>
</div>
</template></turbo-stream><turbo-stream action="replace" target="load-more-container"><template><div id="load-more-container" class="load-more-container">
    <a class="load-more-button" data-turbo-stream="true" href="/topics/71997/load_more?page=3">Load more posts (9 remaining)</a>
</div></template></turbo-stream>