1
$\begingroup$

Let's assume that I am continuously receiving big amount of data. For example, this millisecond I get 100 numbers, next millisecond I get another 500 numbers, after that I might get nothing for a several milliseconds and then again get some numbers in the next millisecond. Also assume that this process lasts for weeks. However, I don't really need to save old data in memory. What I really need is to remember data received in the last 5 minutes. That is, all I want is to be able to present data for last 5 minutes whenever I am asked to.

Do you have any ideas on how to realize this? What kind of data structure would help in such a situation and how should I use it? All I could imagine was saving with every piece of data the moment of time when it was received, storing everything in a queue and constantly deleting element from queue's head if its time shows that it was received more than 5 minutes ago. I hope there is a more elegant/efficient solution.

Thank you.

$\endgroup$
2
  • 2
    $\begingroup$ Why do you think that your solution is inelegant/inefficient? $\endgroup$
    – Steven
    Jul 15, 2022 at 21:40
  • $\begingroup$ idk, I just quickly improvised that. It seems that this kind of problem must be very popular in the industry (HFT etc.), thus I concluded that for years there must have been introduced some super clever ways to work with this. $\endgroup$
    – Haldot
    Jul 15, 2022 at 21:57

1 Answer 1

2
$\begingroup$

The data structure you are looking for is double-ended queue (deque). It is basically what you have imagined, with the extra ease of operations on the front.

Deque has been implemented in many languages in their standard libraries or packages, with some extra operations available for practical convenience usually. For example, you can access any element by an index in a deque in C++ or Python implementation (that index is the number of elements before the element accessed).

$\endgroup$
1
  • $\begingroup$ But in which way is it better than queue in my problem? It seems to me that I would still use one end for inserting elements and another for deleting them, therefore not using this double-endedness. $\endgroup$
    – Haldot
    Jul 28, 2022 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.