| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Общие вопросы по .NET и C# > Поиск уникальных значений |
| Автор: Mormishka 23.5.2012, 13:07 |
| Имеются массив размера n, каждый элемент, которого состоят из m чисел типа double. n может быть очень большим, около 10^7. m от 2 до 5. Нужно создать уникальный массив, не содержащий повторяющие элементы. Пробовал сделать прямым способом добавлять в лист проверяя есть ли там этот элемент. Но даже при распараллеривании на 12 потоков выходит очень долго времени ждать. Есть ли какие-какие нибудь способы ускорить расчет ? |
| Автор: Voyager 24.5.2012, 13:04 |
| Можно попробовать использовать Dictionary, где значения будут ключами dict[a[i]] = 0; на выходе получите уникальную коллекцию элементов в ключах. |
| Автор: agitprop 24.5.2012, 14:33 |
| Dictionaty так же захлебнется. задача непростая. скажу сразу - тут лучше выйти за рамки C#, потому что C# не поддерживает то, что я предложу. насчет самого алгоритма: можно попробовать использовать индекс для этого дела. double - 8 байт. разбить их на четыре группы-ключа, 2+2+2+2. Тут возможны варианты, но мне так кажется самым правильным. делаете массив массивов массивов массивов. размер первого - 2^16 массива, каждый элемент - это тоже массив размером 2^16, который в свою очередь содержит массивы 2^16, чего бы вы думали? правильно, массив 2^16 boolean-ов. (можно оптимизировать, и уменшить в 8 раз за счет использовтания не boolean как boolean, а байта полностью, но это надо думать получше. ) как проверить наличие числа? берете первые 2 байта, смотрите по ключу, если есть такой массив, в нем смотрите по ключу из 3-4 байтов вашего числа, потом в нем по 5-6 байтам, и в нем уже по 7-8. памяти отожрет, конечно, немеряно, зато будет быстро. |
| Автор: Ch0bits 24.5.2012, 21:58 | ||
А что с повторяющимися элементами? Выкинуть их? Думаю решение тривиально. Немного модифицировать merge sort. Делим массив на куски помещающиеся в оперативку, сортируем tim sort и пишем в файлы. Затем сливаем файлы не допуская дубликаты. Потянет любой компьютер даже при космическом размере n, лишь бы места на диске хватило.  |
| Автор: Mormishka 25.5.2012, 18:50 |
| Ch0bits С повторяющимися элементами ничего делать не надо. |
