0

I'm looking for a collection that would suit my scenario:

  1. I will be inserting key-value pairs (both integers) of ID and timestamp. The ID must be unique.
  2. At some interval I will be checking that collection for "expired" items (as in the timestamp + X < current_timestamp) and will need to both remove the key-value pair and act on the key.

I stated that I'm looking for sorted collection, because I think with the collection sorted by value (descending order) I could break the loop over the collection at the point I reach first not "expired" timestamp (that would mean rest of them is active too).

I predict that 95% of my entries will not be "expired" at the time I loop over them.

There will be way more inserts/modifications than reads.

I couldn't find anything that would match this scenario, the closest one is SortedMap.

Is there anything that would be more suitable? Perhaps completely other approach?

I think it's also important to point out it will hold up to 10000 keys (pairs).

If there's anyone with JavaScript (node) background then providing some links to implementations would also be great.

  • 2
    Do the timestamps come (at the point of insertion) in increasing order (e.g. increasing time), or in some random order? – Erik Eidt May 25 '17 at 18:01
  • @ErikEidt yes, the timestamp is a current timestamp, there would be a method receiving only ID, getting current timestamp and inserting that pair into the collection :) I would use a simple queue for this, but I don't think queue is capable of ensuring key uniqueness – pzaj May 26 '17 at 8:58
  • @ErikEidt oh, but it's possible to set new timestamp for ID that is already in use and this would require sorting / re-ordering. – pzaj May 26 '17 at 9:12
1

It is not necessary to have a single collection that satisfies your requirements. Instead, you can combine two collections to get the required properties. You then only modify these collections through an interface that ensures that the two collections are kept in sync.

  • for uniqueness, keep a Set of IDs.
  • for ordering, keep a Queue of Timestamps.

Deleting old entries requires that you can remove the IDs from the Set, so you need to find the ID from a Queue-item. We could therefore implement this as a Map from IDs to Timestamps, and a Queue of IDs, sorted by corresponding timestamp.

Pseudocode:

queue: min-priority queue for map[entry]

insert(map, queue, ID):
  map[ID] = now()
  queue.insert(ID)

delete-expired(map, queue):
  while map[queue.first] is expired:
    delete map[queue.first]
    queue.unqueue()

Ah, but what about updating the timestamp? If memory is not the limiting factor, I would leave the old entries in the queue but mark them as invalid. This defers their removal until they are dequeued.

queue: min-priority queue for entry.timestamp

insert(map, queue, ID):
  if ID in map:
    map[ID].valid = false
  entry = { timestamp: now(), id: ID, valid: true }
  map[ID] = entry
  queue.insert(entry)

delete-expired(map, queue):
  while queue is not empty:
    entry = queue.first

    if entry.valid and entry.timestamp is not expired:
      return

    delete map[entry.id]
    queue.unqueue()

Alternatively, you can delete the entry from the middle of the queue. However, queue-removal generally requires you to scan or move all elements in the queue, and is therefore a very time-intensive operation. This might be the correct choice if you are memory-constrained.

The priority queue can in general be implemented as a heap. Since you only insert newer elements, an array-like data structure would also be a good choice. But dynamic arrays (the lists JavaScript gives you by default) are not desirable since the elements have to be regularly moved into the space freed up at the front by dequeuing entries. An alternative that doesn't have to move elements is a ring buffer, which could be made self-resizing like a dynamic array.

  • This looks very promising! I think I'm more CPU constrained than memory, so the second approach seems like a great fit. I only see one issue there, perhaps I missed something, but the if conditions and return will cause some entries to get stuck in the queue? Like having an invalid, not expired entry "after" (queued before) the valid and not expired entry which breaks the loop with return? Having in mind this would run every 15 seconds, I can imagine there may be even 10 queue entries per ID by that time. Would using deque significantly affect performance? – pzaj May 26 '17 at 11:37
  • Just to clarify on deque. I could then have another loop to periodically remove (starting from "behind") invalid entries. But I suppose this may not be necessary as long as the queue performance does not degrade with 10000~ entries. – pzaj May 26 '17 at 11:38
  • @user1970395 The reverse of the if-condition is if entry is not valid or entry.timestamp is expired: dequeue entry. Because timestamps are always increasing, all invalid entries will eventually reach the front of the queue just like the other entries. Yes, this approach leaves a lot of garbage in the queue. But you can only avoid that if you occasionally do a “garbage collection” pass to remove invalid entries through the complete queue. For only 10k elements you can probably do that every 2 secs without noticing the overhead. Just don't do it on every update. – amon May 26 '17 at 12:22
  • I see, that you for clarification. So I could run "garbage collection" in the same method I process my queue then. I will definitely use this approach of yours which is something I've missed being too focused on finding one collection that would handle it for me. I do have just one question though, seems you see to know more about JS than I do. Do you know any good Queue implementation for JS (node.js)? I couldn't find any :) – pzaj May 26 '17 at 13:04
  • @user1970395 Nope, I don't have any library recommendations, mostly because I don't actually use JS that much. But I found a description of an ArrayQueue that seems reasonably straightforward to implement. – amon May 26 '17 at 14:01

Your Answer

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

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