Есть ли способ получить индекс элемента, хранящегося в C # s 'OrderedDictionary DS в O (1) ~ сложность - PullRequest
Новая
       33

Есть ли способ получить индекс элемента, хранящегося в C # s 'OrderedDictionary DS в O (1) ~ сложность

0 голосов
/ 06 августа 2020

Другими словами - как мне получить его, не повторяя значение GetEnumerator () (O (n))? Например,

, допустим, я создал следующий упорядоченный словарь (с именем aOrdDict), который содержит следующие пары: 

   INDEX      KEY                       VALUE
   0          testKey1                  testValue1
   1          testKey2                  testValue2
   2          keyToDelete               valueToDelete
   3          testKey3                  testValue3

как мне показать, что индекс testKey3 в aOrdDict.GetEnumerator () равен 3, без выполнения какой-либо процедуры следующего вида: 

int i = 0;
var ListedPairs = aOrdDict.GetEnumerator();
string wantedKey = "testKey3";

for(; i < aOrdDict.Keys.Count; i++)
{
    if (ListedPairs.key == wantedKey)
        break;
    listedPairs.MoveNext();
}

РЕДАКТИРОВАТЬ - Временное решение и некоторый контекст

небольшая проработка декораций, которая привела к моему вопросу, сопровождаемая временным решением, которое я реализовал (которое похоже на то, что Мартин Ливерсейдж предложил в комментариях):

Я в основном работаю над какой-то двунаправленный посредник клиент <-> сервер. после того, как сообщение сервер -> клиент входит в посредник и обрабатывается, после передачи его клиенту, как его тело, так и значение DateTime.Now () (до мс), взятые в этот момент, должны быть сохранены в посреднике в ассоциации с друг друга, упаковываются, а затем отправляются клиенту.

позже клиент отправляет запросы на сервер, каждый из которых отмечен специальной c отметкой времени.

он ожидает для получения некоторого диапазона сохраненных значений, которые находятся рядом и в хронологическом порядке перед меткой времени ввода. на этом этапе упорядоченный словарь должен был пригодиться, позволяя мне адресовать значение, которое было сохранено в timeStamp, по ключу (отсюда - необходимость в dict), а затем итерацию назад, значение за значением, в противоположном направлении. порядок того, в котором они были вставлены. (отсюда - необходимость в списке)

в конечном итоге - я использовал: 

ConcurrentDictionary<string, int> aIndicesDict

для пары {timeStamp, index} и 

List<Tuple<string, someObject>> aSomeObjectsList

для пары (timestamp, messageBody),

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

затем, по входящему запросу от клиент на сервер, мы получаем индекс, связанный с вводом timeStamp (из aIndicesDict - O (1)), что позволяет нам начать итерацию назад от соответствующего индекса списка кортежей (внутри aSomeObjectsList - O (1), чтобы получить прямую к соответствующей записи в списке).

как я писал в комментариях - я все же хотел бы найти немного более эффективное решение (с точки зрения памяти).

1 Ответ

2 голосов
/ 06 августа 2020

OrderedDictionary не обеспечивает нужную вам функциональность. Внутри нет сопоставления ключа с индексом. Вместо этого вы можете сопоставить либо ключ, либо индекс с фактическим значением.

Вы можете создать собственный упорядоченный словарь, в котором вы будете хранить внутри список и массив: список сопоставляется от индекса к ключу, а словарь сопоставляется с ключом ценить, оценивать. Это предоставит способ получить индекс из ключа в O (1), но чтение значения по индексу (и последовательное выполнение итераций) будет более затратным из-за дополнительной косвенности. Если вы создаете свою собственную коллекцию, вы также можете использовать дженерики, которых не поддерживает древний OrderedDictionary.

Однако зачем вам получать индекс из ключа? Если вы используете ключи для поиска значений и индекс действительно является упорядочивающим, тогда вы, возможно, можете включить «индекс» (на самом деле, порядок) в значение?

...