<div dir="ltr"><div>Yep, right now I try to do something similar with bitmap and sliding window, that will shift. Could you explain about maps?<br></div><div><br></div><div>Thanks!</div></div><div class="gmail_extra"><br><div class="gmail_quote">2016-02-18 16:37 GMT+03:00 Jesper Louis Andersen <span dir="ltr"><<a href="mailto:jesper.louis.andersen@gmail.com" target="_blank">jesper.louis.andersen@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div><div><div>A simple solution that may work in the end is to keep track of a window of bits:<br><br></div>* shift the window as the ID increases<br></div>* check older packets against the window<br><br></div>This gives you "SACK" support, is fast to check against and fast to expire old data due to the shifting.<br><br></div>Simply using an ordered list or a map could also work if you clean it up eventually. It depends on how fast your CPU core is.<br><br></div><div class="gmail_extra"><div><div class="h5"><br><div class="gmail_quote">On Thu, Feb 18, 2016 at 2:24 PM, Alexander Petrovsky <span dir="ltr"><<a href="mailto:askjuise@gmail.com" target="_blank">askjuise@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Ouch, I forgot to say, the IDs can be sparse, so they not really monotonically, they just grow, and can be reordered.</div><div><div><div class="gmail_extra"><br><div class="gmail_quote">2016-02-18 16:20 GMT+03:00 Danil Zagoskin <span dir="ltr"><<a href="mailto:z@gosk.in" target="_blank">z@gosk.in</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi!<div><br></div><div>If ID grows monotinically and you have no plans of recovering after packet reordering, then you can just keep the previous ID.</div><div>  - If CurID > PrevID, CurID is unique;</div><div>  - If CurID == PrevID, it is not unique;</div><div>  - If CurID < PrevID, it is a bug or reordering, let it crash.</div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote"><div><div>On Thu, Feb 18, 2016 at 3:01 PM, Alexander Petrovsky <span dir="ltr"><<a href="mailto:askjuise@gmail.com" target="_blank">askjuise@gmail.com</a>></span> wrote:<br></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div><div dir="ltr">Hi!<div><br></div><div>I have the stream of packets with ID (int), and I need to check is the packet is uniq (by ID) or not?<div><br></div><div>Incoming rate is about 20k pps and ID is monotonically grows. What's the best way and data structure fit for this problem?</div><span><font color="#888888"><div><br></div>-- <br><div><div dir="ltr">Петровский Александр / Alexander Petrovsky,<br><br>Skype: askjuise<br><div>Phone: +7 914 8 820 815<div><br></div></div></div></div>
</font></span></div></div>
<br></div></div>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><span><font color="#888888"><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr"><div><font face="'courier new', monospace">Danil Zagoskin | <a href="mailto:z@gosk.in" target="_blank">z@gosk.in</a></font></div></div></div>
</font></span></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div><div dir="ltr">Петровский Александр / Alexander Petrovsky,<br><br>Skype: askjuise<br><div>Phone: +7 914 8 820 815<div><br></div></div></div></div>
</div>
</div></div><br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/listinfo/erlang-questions</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br></div></div><span class="HOEnZb"><font color="#888888"><div>J.</div>
</font></span></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr">Петровский Александр / Alexander Petrovsky,<br><br>Skype: askjuise<br><div>Phone: +7 914 8 820 815<div><br></div></div></div></div>
</div>