Гость
Войти | Профиль | Очистить
Действия ...
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Порядок ключей в Dictionary<TKey, TValue> / 8 сообщений из 8, страница 1 из 1
22.01.2021, 14:30
    #40038026
Сон Веры Павловны
Сон Веры Павловны
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Порядок ключей в Dictionary<TKey, TValue>
Казалось бы тема старая, давно разобранная, и ответ здесь только один - в общем случае порядок ключей недетерминирован. Однако на днях выяснилось, что некоторые разработчики считают иначе.
Предыстория. На днях понадобилось порыться в исходниках EPPlus для уяснения некоторых нюансов формирования разметки в потрохах xslx. В процессе наткнулся на следующее.
В составе пакета xslx есть т.н. shared strings table - просто словарик со строками, на которые даются ссылки. Сделано это для предотвращения распухания размера xlsx.
Сам словарик живет в файле sharedStrings.xml в составе пакета, имеет вид
Код: xml
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
<sst xmlns="http://schemas.openxmlformats.org/spreadsheetml/2006/main" count="5853" uniqueCount="5853">
  <si>
    <t>Мама</t>
  </si>
  <si>
    <t>мыла</t>
  </si>
  <si>
    <t>раму</t>
  </si>
  ................
</sst>


Ссылки на строки делаются в файлах содержимого worksheets (sheet1.xml .. sheetN.xml), имеющих вид (в части описания ячеек)
Код: xml
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
<sheetData>
  <row r="1">
    <c r="A1" s="3" t="s">
      <v>0</v>
    </c>
    <c r="B1" s="3" t="s">
      <v>1</v>
    </c>
    <c r="C1" s="3" t="s">
      <v>2</v>
    </c>
  </row>
</sheetData>


Ссылка на строку из словаря - значение тэга v, zero-based индекс узла si в файле sharedStrings.xml. Т.е. порядок следования строк в sharedStrings.xml имеет значение.
Далее. В EPPLus словарь со строками заполняется при сохранении пакета в тот момент, когда формируются файлы листов (sheet1.xml .. sheetN.xml). Делается это вот здесь . Строки сохраняется в обычный Dictionary<>, у которого ключ - сама строка, а значение - internal-класс со служебной информацией (в т.ч. порядковым номером строки в словаре).
После того, как все файлы листов сформированы, словарик считается заполненным, и сериализуется в xml вот здесь . И сериализуется он простым проходом по итератору коллекции ключей словаря, без каких-либо упорядочиваний и сортировок. Т.е. автор библиотеки уверен, что ключи в итераторе следуют в той последовательности, в которой они были добавлены (а эта последовательность важна - см. выше).
Поскольку EPPlus - достаточно серьёзная разработка, за которую сейчас люди платят деньги, то, я думаю, если бы препдположение о следовании ключей в порядке добавления было бы неверным, это где-нибудь уже вылезло, и было пофиксено. Сижу вот, роюсь в документации-форумах, и нигде пока ничего не нахожу в подтверждение, кроме всё того же постулата о недетерминированности порядка.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.01.2021, 14:36
    #40038035
Shocker.Pro
Shocker.Pro
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Порядок ключей в Dictionary<TKey, TValue>
Ну по факту хэш int-ключа будет сам int, поэтому сортировка случайно совпадает, видимо, поэтому глюк нигде не всплыл.
Но это глюк, да, никто не обещал детерминированность. Я и сам иной раз забывал по ключу отсортировать, но вовремя спохватывался.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.01.2021, 15:41
    #40038064
Roman Mejtes
Roman Mejtes
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Порядок ключей в Dictionary<TKey, TValue>
из этого словаря могут строки удаляться? если нет, то строка попав хоть раз в эту коллекцию получает индекс и её порядок не меняется
вообще не сталкивался с такой проблемой, если честно, хоть и с табличкой строк приходилось работать.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.01.2021, 15:49
    #40038067
Сон Веры Павловны
Сон Веры Павловны
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Порядок ключей в Dictionary<TKey, TValue>
Shocker.Pro,

Тем более что там ключ string, а не int. И, тем не менее:
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
const string loremIpsum = "Lorem ipsum dolor sit amet consectetur adipiscing elit sed do eiusmod tempor incididunt ut labore et dolore magna aliqua";
var dic = new Dictionary<string, int>();
var n = 0;
foreach(var s in loremIpsum.Split(' '))
  dic.Add(s, n++);
var sb = new StringBuilder();
foreach (var s in dic.Keys)
  sb.Append(s).Append(" ");
Console.WriteLine(sb.ToString());
Console.WriteLine(loremIpsum.Equals(sb.ToString().Trim(), StringComparison.Ordinal));


Код: plaintext
1.
Lorem ipsum dolor sit amet consectetur adipiscing elit sed do eiusmod tempor incididunt ut labore et dolore magna aliqua
True
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.01.2021, 15:53
    #40038069
Сон Веры Павловны
Сон Веры Павловны
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Порядок ключей в Dictionary<TKey, TValue>
Roman Mejtes
из этого словаря могут строки удаляться? если нет, то строка попав хоть раз в эту коллекцию получает индекс и её порядок не меняется

Понятно, что порядок не меняется, вопрос - какой порядок не меняется. Что это за порядок. Как бы все считают, что непонятно какой ввиду использования хэшфункции. На практике получается, что это порядок добавления ключей. Только это нигде не документировано.
Roman Mejtes
вообще не сталкивался с такой проблемой, если честно, хоть и с табличкой строк приходилось работать.

Это не проблема, это просто вопрос, почему так.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.01.2021, 16:04
    #40038072
Shocker.Pro
Shocker.Pro
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Порядок ключей в Dictionary<TKey, TValue>
Сон Веры Павловны
Код: plaintext
Lorem ipsum dolor sit amet consectetur adipiscing elit sed do eiusmod tempor incididunt ut labore et dolore magna aliqua
Насколько я помню, в каком-то из словарей до определенного количества ключей не используется хэш... только не помню, есть ли так в обычном словаре
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.01.2021, 16:05
    #40038073
Shocker.Pro
Shocker.Pro
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Порядок ключей в Dictionary<TKey, TValue>
Сон Веры Павловны
Только это нигде не документировано.
если это будет документировано, но это не позволит менять реализацию, так что всё правильно
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
22.01.2021, 17:06
    #40038085
Сон Веры Павловны
Сон Веры Павловны
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Порядок ключей в Dictionary<TKey, TValue>
Shocker.Pro
Насколько я помню, в каком-то из словарей до определенного количества ключей не используется хэш...

Не тот случай - здесь ключей может быть очень много. Сейчас вот под рукой не особенно большой документ, sharedStrings.xml из него в распакованном виде весит 13 Мб. А если в документе несколько листов (sharedStrings.xml всегда один на весь документ), много колонок, значения строк редко повторяются, то легко может быть и в 5 раз больше.

Shocker.Pro
если это будет документировано, но это не позволит менять реализацию, так что всё правильно

Ну, т.е. автор не особенно правильно делает, используя вот такое недокументированное поведение словаря.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / Порядок ключей в Dictionary<TKey, TValue> / 8 сообщений из 8, страница 1 из 1
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 349ms
Закрыть
start [/forum/topic.php?fid=20&tablet=1&tid=1398381]:
 0ms
get settings:
 11ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 25ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 44ms
get tp. blocked users:
 2ms
others: 233ms
total:  349ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]