OS
регион блюда наследник переопределяет
Size: a a a
2020 September 08
MC
@ad1Dima мы недавно разговаривали про сравнение строк.
Есть большой массив пар (несколько тысяч значений) строка-значение, строки могут повторяться. Есть идеи максимально быстро найти все пары строка-значение с нужной строкой?
Сейчас я разбиваю этот большой массив на словари согласно длине строк, и записываю эти словари в другой массив так чтобы индекс равнялся длине строки. Словари эти Dictionary<string, List<value>>
Есть большой массив пар (несколько тысяч значений) строка-значение, строки могут повторяться. Есть идеи максимально быстро найти все пары строка-значение с нужной строкой?
Сейчас я разбиваю этот большой массив на словари согласно длине строк, и записываю эти словари в другой массив так чтобы индекс равнялся длине строки. Словари эти Dictionary<string, List<value>>
MC
т.е мы максимально быстро находим строки со схожей длиной. А вот идентичную строку мы находим как влюч словаря возможно с немаксимальной скоростью
B
Dictionary? Ты хотел сказать Hashset или как его?
MC
Dictionary? Ты хотел сказать Hashset или как его?
точно не хешсет
YS
для сравнения длинных строк точно нужен хэш, превращающий здоровенные N символов в фикс с размером, например, 4 байта
YS
проблема - неуникальность хэша, возможны коллизии, зависящие от нашей хэш-функции, поэтому хэш как ключ мапится на список значений, где уже проверяем посимвольно равенство
YS
насколько знаю, быстрее такой идеи в общем случае ничего нет
MC
Yury Schkatula
проблема - неуникальность хэша, возможны коллизии, зависящие от нашей хэш-функции, поэтому хэш как ключ мапится на список значений, где уже проверяем посимвольно равенство
Так словарь так внутри ж и делает? Разве нет?
MC
Если б он так не делал, то это было б общеизвестной проблемой
MC
Ещё интересует как сравнивать строки прям очбыстро. == даёт оверхед, потому что ещё раз сравнивает строки по ссылке, длину и на нулл
MC
И наверное внутри словаря используется ==
YS
насколько помню, обычные словари строят дерево, а вот хэш-словари - да, хэш-таблица
YS
дерево опирается на операцию сравнения, определённую для типа-ключа
YS
равно - попали, меньше - в одно поддерево, больше - в другое
YS
но опять же, там хватает нюансов какое именно дерево будет использоваться