Здравствуйте, Xobotik, Вы писали:
X>Я заполняю значениями для того, чтобы снизить вероятность коллизии. Значения получаются все разные, тем самым хэши значений тоже разные и из-за этого снижается вероятность коллизии.
Словарь хранит пары (ключ -> значение). Его основная цель — быстро находить "значение" по его "ключу". В данном контейнере поиск пары (ключ -> значение) осуществляется по хэшу "ключа", а хэш "значения" в поиске не участвует. Поэтому на коллизии влияет только хэш ключа.
Нужна другая структура данных, от которой требуется:
— быстро проверять наличие элемента (на основе хэша)
— быстро добавлять новый элемент
Б>>1. Запутывает код. X>Отнюдь.
Запутывает, потому что словарь используется не по назначению.
Б>>2. Увеличивает требования к памяти. X>Увеличивает на парочку бит
Не, так неинтересно: я про большие числа потому и спросил, что бы узнать, можно ли выделять память, пропорциональную N или M.
Есть известная задачка на поиск цикла в однонаправленном списке. Многие задают ей, не говоря об имеющихся ограничениях. А самое простейшее решение в таких случаях — тот же HashSet — запоминание того, что прошли в нём. Всяко быстрее догонялок будет :о))
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Xobotik, Вы писали:
X>>Я заполняю значениями для того, чтобы снизить вероятность коллизии. Значения получаются все разные, тем самым хэши значений тоже разные и из-за этого снижается вероятность коллизии.
Б>Словарь хранит пары (ключ -> значение). Его основная цель — быстро находить "значение" по его "ключу". В данном контейнере поиск пары (ключ -> значение) осуществляется по хэшу "ключа", а хэш "значения" в поиске не участвует. Поэтому на коллизии влияет только хэш ключа.
Точно, перепутал.
Б>Нужна другая структура данных, от которой требуется: Б>- быстро проверять наличие элемента (на основе хэша) Б>- быстро добавлять новый элемент
здесь было предложение использовать фильтр Блума.
Б>>>1. Запутывает код. X>>Отнюдь. Б>Запутывает, потому что словарь используется не по назначению.
Ну извините мы же не решаем задачу о нахождения оптимального стиля программирования, а решаем конкретную постановку. Да и 10 строк мало кого запутают.
Б>>>2. Увеличивает требования к памяти. X>>Увеличивает на парочку бит Б>Можно обойтись и без этого.
ну а вообще объясняю еще раз причину добавления в ключи значений из массива построчно исходя из кода.
public int GetDuplicateNumber(int[] array)
{
Dictionary<TKey, TValue> dictionary = new Dictionary<TKey, TValue>(array.Length);
for (int i = 0; i < array.Length; i++)
{
if (dictionary.ContainsKey(array[i])) // операция ContainsKey равна O(1)
{
return array[i];
}
else
{
// операция Add() - O(1) при фиксированном значении размера словаря
dictionary.Add(array[i], 0); // добавляем в ключи значения из массива не найденные методом ContainsKey(). Так как мы ищем методом ContainsKey() не в значения же словаря
//добавлять значения массива
}
}
return 0;
}
На счет ContainsKey(): здесь см. заметки
На счет Add(): здесь см. заметки
Здравствуйте, _FRED_, Вы писали:
_FR>Здравствуйте, Xobotik, Вы писали:
X>>Да задачу (стартовую) решили уже без применения каких-то сложных структур:
X>>здесь
_FR>Не, так неинтересно: я про большие числа потому и спросил, что бы узнать, можно ли выделять память, пропорциональную N или M.
Ну тут просто постановка задачи всячески искажалась, что я сам запутался Вы правы в любом случае.
_FR>Есть известная задачка на поиск цикла в однонаправленном списке. Многие задают ей, не говоря об имеющихся ограничениях. А самое простейшее решение в таких случаях — тот же HashSet — запоминание того, что прошли в нём. Всяко быстрее догонялок будет :о))
Здравствуйте, Буравчик, Вы писали:
Б>Нужна другая структура данных, от которой требуется: Б>- быстро проверять наличие элемента (на основе хэша) Б>- быстро добавлять новый элемент
Б>>>1. Запутывает код. X>>Отнюдь.
Б>Запутывает, потому что словарь используется не по назначению.
Да, конечно, в терминах C# надо вместо Dictionary использовать свежепоявившийся HashSet, совсем про него забыл
Здравствуйте, _FRED_, Вы писали:
_FR> неизвестно, что больше — N или M
Судя по условию задачи, N ограничено сверху значением M+1, т.к. иначе будет более одного дубликата.
Кстати, если бы было соблюдено равенство N = M + 1 (т.е. присутствовали бы все без исключения числа от 1 до M с одним дубликатом), то задача бы решалась обычным XOR-ом за O(N) без доп. памяти.
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Я сомневаюсь, что существует решение лутче чем через хеш (в дотнете — HashSet). Если такое решение существует, то оно должно использовать либо меньше памяти, либо меньшую временную сложность. Само существование такое алгоритма означает, что его можно использовать для стандартного хеша, у которого отсутсвует операция удаления — некий AddOnlyHashSet. А это, согласитесь, довольно таки полезный класс. То есть, если б существовал такой алгоритм — в бибилиотеках был бы специальный класс AddOnlyHashSet.
Здравствуйте, andy1618, Вы писали:
_FR>> неизвестно, что больше — N или M
A>Судя по условию задачи, N ограничено сверху значением M+1, т.к. иначе будет более одного дубликата.
Вовсе не обязательно: в первоначальной формулировке не сказано, что какое-либо числе не может повторяться в массиве три и большее количество раз.
A>Кстати, если бы было соблюдено равенство N = M + 1 (т.е. присутствовали бы все без исключения числа от 1 до M с одним дубликатом), то задача бы решалась обычным XOR-ом за O(N) без доп. памяти.
Тогда xor был бы не нужен: достаточно получить сумму всех чисел в массиве и вычесть из неё сумму всех чисел диапазона 1..M — получим аккурат значение числа, которое встречается дважды.
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, Pro100Oleh, Вы писали:
PO>некий AddOnlyHashSet. А это, согласитесь, довольно таки полезный класс. То есть, если б существовал такой алгоритм — в бибилиотеках был бы специальный класс AddOnlyHashSet.
Ну, вышеупомянутые фильтры Блума это и есть что типа AddOnlyHashSet
Здравствуйте, _FRED_, Вы писали:
_FR>Тогда xor был бы не нужен: достаточно получить сумму всех чисел в массиве и вычесть из неё сумму всех чисел диапазона 1..M — получим аккурат значение числа, которое встречается дважды.
Здравствуйте, Xobotik, Вы писали:
_FR>>Тогда xor был бы не нужен: достаточно получить сумму всех чисел в массиве и вычесть из неё сумму всех чисел диапазона 1..M — получим аккурат значение числа, которое встречается дважды.
X>Только больно медленный этот метод.
Да ладно, это как раз практически идеальный метод — требуется только один проход с суммированием плюс несколько арифметических действий. Быстрее на стандартных компьютерных архитектурах вряд ли получится!
Но, как написано выше, этот алгоритм относится к частному случаю N=M+1 (т.е. в исходном массиве есть ВСЕ числа от 1 до M плюс какое-то число встречается дважды).
Здравствуйте, Xobotik, Вы писали:
_FR>>Тогда xor был бы не нужен: достаточно получить сумму всех чисел в массиве и вычесть из неё сумму всех чисел диапазона 1..M — получим аккурат значение числа, которое встречается дважды.
X>Только больно медленный этот метод.
Какой именно? Это так же один проход по массиву.
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, -VladK-, Вы писали:
VK>Народ, да вы че? VK>сколько уже прочитал вариантов и некто не догадался просто просуммировать массив и сравнить с суммой арифметической прогрессии ?!
Разве в условии сказано что N = M + 1?
N = 10, M = 1000. Куда приложить прогрессию?
Здравствуйте, samius, Вы писали:
S>Здравствуйте, -VladK-, Вы писали:
VK>>Народ, да вы че? VK>>сколько уже прочитал вариантов и некто не догадался просто просуммировать массив и сравнить с суммой арифметической прогрессии ?!
S>Разве в условии сказано что N = M + 1? S>N = 10, M = 1000. Куда приложить прогрессию?
"Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно
число в этом массиве повторяется два раза." Раз повторяется одно число, значит N = M + 1.
Да, круто!
Но для обсуждаемой задачки при больших M (например, 2^64) этот подход будет неприменим из-за необходимости аллоцировать O(M) памяти (пусть и грязной) под массив sparse.
