Есть ли эффективный способ поиска ключа в очереди и переопределить его значение? - PullRequest
Новая
       10

Есть ли эффективный способ поиска ключа в очереди и переопределить его значение?

0 голосов
/ 05 ноября 2019

Я пишу приложение на C ++, в котором мне нужно реализовать очередь сообщений, которая будет непрерывно получать данные (т.е. объект) из сети, каждый объект имеет ключ (например, название компании, скажем, Oracle, Google и т. Д.). Если потребитель очереди медленнее, у меня может быть огромное количество элементов в очереди (максимальный предел может быть сохранен в миллионах).

Требование: если объект с ключом XYZ прибыл из сети и очередь уже имеетобъект с ключом XYZ, то мне нужно перезаписать этот объект, и положение этого объекта в очереди должно остаться прежним. Например, если объект с ключом «Oracle» со значением 25 поступил из сети, а объект с ключом «Oracle» и значением 10 уже присутствует в позиции 120 в очереди, то мне нужно перезаписать значение 10 значением 25и позиция должна оставаться 120.

Я пытаюсь реализовать это, используя потокобезопасную очередь и установить, по прибытии объекта из сети сначала я проверяю, присутствует ли ключ в наборе, если нет ключа, я добавляю ключ вустановить и добавить объект в очередь. Если ключ присутствует, тогда я выполняю линейный поиск ключа в очереди и перезаписываю объект.

Производительность будет очень низкой, если я получу очень частые обновления для ключей, которые уже находятся в очереди.

Есть ли эффективный способ реализовать это? Заранее спасибо.

1 Ответ

1 голос
/ 05 ноября 2019

Поскольку очередь не отсортирована, реального способа получить данные быстрее, чем линейный поиск, не существует. Вы можете использовать очередь с приоритетом. Std :: priority_queue не позволяет быстро менять приоритет, вам придется использовать повышение.

Вы также можете попробовать этот алгоритм:

  • Ключ хранилища, например Google, Microsoft, Apple. и т. д. в unordered_map. Сохраняйте также количество обработанных элементов.
  • При удалении элемента из очереди увеличьте его и удалите ключ с карты.
  • Когда элемент прибудет вочереди,
    • посмотрите на карте, если ключ существует (линейное время)
    • , если он существует, измените значение на queue[index -count] (линейное время)
    • , если это не такпока нет, сохраните map[key] = count + index where the new item is placed in the queue (линейное амортизированное время)

Я не даю никаких гарантий, я не проверял этот алгоритм.

...