2
$\begingroup$

Suppose I have a time series of values $v_1, \dotsc, v_n, \dots,$ (think of the data as being generated by repeated function calls, like a Python generator, or being captured in real time) and I want to maintain a window of the last $k$ values in sorted order. If $k$ were small, I could just keep re-sorting, but assume that $k$ is large. If I were doing this in C (or some such), this would be easy: I would find where each new value goes by binary search (then delete the "stale" value), but in Mathematica nothing leaps to mind. Any suggestions? One could ask a similar question in higher dimensions (where one is asking for a dynamic voronoi triangulation or kd tree), but one thing at a time...

$\endgroup$
  • $\begingroup$ If you ultimately need all values in sorted order, you should sort the full data set first. $\endgroup$ – David G. Stork Mar 31 '17 at 23:57
  • 1
    $\begingroup$ @DavidG.Stork I do not, and think of the data as being generated on the fly, so I know the past, but not the future. $\endgroup$ – Igor Rivin Mar 31 '17 at 23:58
  • $\begingroup$ I recommend you edit your question to clarify your key point about data being generated "on the fly." $\endgroup$ – David G. Stork Apr 1 '17 at 0:06
  • 1
    $\begingroup$ @DavidG.Stork I say this in the parenthetical comment at the end (we are trying to maintain a dynamic Voronoi triangulation (in one dimension :)) $\endgroup$ – Igor Rivin Apr 1 '17 at 0:37
  • 2
    $\begingroup$ I think this could be implemented with a priority queue see mathematica.stackexchange.com/q/31968/36788 $\endgroup$ – mikado Apr 1 '17 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.