0

I have a list of strings which are Guids. I want to return them in sorted order in a api and I want to return 1000 Guids at a time. So, I may have a list of 20000 guids and I want to return them in sorted manner 1000 Guids at a time. I thought of using PriorityQueue and get first 1000 elements. How shall I get next page size from PriorityQueue (from 1000 to 2000, from 2000 to 3000).

The reason I want to use priority queue is because I want it to be performant. I don't want to sort using simple list and take n elements based on page number.

Also, I want to get any suggestion, if someone has any other data structure in getting list of subscriptionIds in sorted manner by pages.

Utkarsh Srivastav
  • 3,105
  • 7
  • 34
  • 53
  • 1
    What about your use case makes a PriorityQueue more performant than a sorted list? How do you populate the list of GUIDs? Can multiple clients request the same GUIDs? Your question doesn't make it seem like a queue is necessarily the right choice here. – HasaniH Sep 20 '22 at 18:11
  • If the list of strings is dynamic (getting updated over time), then you might want a priority queue. If it’s static, sorting the list once and then iterating through it will be more “performant”. – pjs Sep 20 '22 at 18:20

2 Answers2

1

I am not sure that a PriorityQueue<TElement,TPriority> is the best collection for your scenario. If you put 20,000 values in the priority queue, you have already paid a significant computational cost for maintaining the heap property while adding the values. This cost is O(n*log n), so it is comparable with sorting a List<T>. And then you'll have to pay a similar cost for retrieving the values in a sorted order, because the priority queue has to move log(N) elements to maintain the heap, each time you retrieve the min value.

The PriorityQueue<TElement,TPriority> is a specialized collection, and it's much less flexible than a List<T>. If you have a sorted list, you can read any element of the list. If you have a priority queue, you can read only the element at the top (the min element). You can't read the next element, without removing (dequeuing) the top element.

If you still think that using a PriorityQueue<TElement,TPriority> is a good idea, here is what you can do. You can write an extension method that consumes (dequeues) the collection, and returns an IEnumerable with the consumed elements, like this one:

/// <summary>
/// Gets an enumerable sequence that consumes the elements of the queue
/// in an ordered manner.
/// </summary>
public static IEnumerable<(TElement Element, TPriority Priority)>
    GetConsumingEnumerable<TElement, TPriority>(
    this PriorityQueue<TElement, TPriority> source)
{
    while (source.TryDequeue(out TElement element, out TPriority priority))
    {
        yield return (element, priority);
    }
}

...and then use the Chunk LINQ operator to batch the consumed elements in chunks of 1000:

IEnumerable<(SomeElementType, SomePriorityType)[]> consumedChunks = queue
    .GetConsumingEnumerable().Chunk(1000);
Theodor Zoulias
  • 34,835
  • 7
  • 69
  • 104
0

There's a lot to unpack here...but I'm going to assume that you don't actually want a priority queue because nothing in your question dictates an actual priority or a FIFO queue.

On the back end, sort your Guids however you see fit. This will sort them:

var sorted = guids.OrderBy(i=>i).ToList();

Then in your API you can accept a 'page' number, and return the results based on the page

return guids.Skip((page-1)*1000).Take(1000).ToList();
Joel
  • 33
  • 4
  • The reason I want to use priority queue is because I want it to be performant. I don't want to sort using simple list and take n elements based on page number. – Utkarsh Srivastav Sep 20 '22 at 18:01