Выделяем некую область памяти. Зависящую от границ чисел. Заполняем 0. Далее генерируем число. И пишем в эту память со смещением равным этому числу 1. При записи проверяем если там уже 1 - задача решена.
Да. Я предложил (но не успел опубликовать) похожий вариант. ;)
ЗЫ: Любой генератор случайных чисел оперирует в фиксированных границах. В LibC это 0..RAND_MAX (2147483647).
что-то в условиях задачи я не вижу про границы диапозона чисел
long
В LibC
это привязка к ядру получается? "правильное" решение как выяснилось, это абстрактный рандом в сферическом вакууме.
как же это по майкрасовтски, а? никто не думает что есть другие программы, возможно второй рандом генератор, которому нужно сверятся с первым.. никто не думает что вам не отдадут память и.тд.
правильным лично я считаю B-tree.
это привязка к ядру получается? "правильное" решение как выяснилось, это абстрактный рандом в сферическом вакууме.
как же это по майкрасовтски, а? никто не думает что есть другие программы, возможно второй рандом генератор, которому нужно сверятся с первым.. никто не думает что вам не отдадут память и.тд.
"Абстрактных" генераторов случайных чисел не бывает. Бывают аппаратные и программные. Но. Оба оне "привязаны к ядру". Ибо широко используются ядром.
А в случае аппаратного генератора - так тем более. Ибо нужен драйвер. :/
правильным лично я считаю B-tree.
Если я правильно понял/перевел. То она получится более универсально, но работать (при одном и том же количестве генераций) будет значительно дольше.. И чем больше количество генераций тем больше будет разница.
Но если честно я не слишком хорошо знаю английский и в идею не очень проник.
свот на русском :)
ну так что, ядро NT отдаст память для подсчетов? а ядро *nix?
Блин! При чем тут привязка к ядру и весь остальное? Разговор шел об алгоритме
Про Microsoft просто была неудачная (как я теперь понимаю) шутка
Hvzh, но ведь правильнее в файл! в файл и сверять.
плюсы:
с файлом могут работать другие программы
файл будет больше возможного кол-ва ОЗУ
файл можно использовать повторно
данные не двоичные, а значит ими можно управлять без дополнительных затрат.
применение возможностей о которых вы пока не знаете.
минусы?
ну да, это не так элегантно как сферический рандом орудующий памятью как хочет.
это разве не решение и алгоритм?
это разве не решение и алгоритм?
А еще лучше - писать не в "файл" а в SQL базу данных! Там будет и структура, и запросы, и упомянутый B-tree реализован. :P
system-root,
Да, но не оптимальное по скорости. Предположим, функция генерит 100 000 чисел в секунду. Насколько замедлится скорость проверки при записи/чтении в файл?
[quote=system-root]это разве не решение и алгоритм?
А еще лучше - писать не в "файл" а в SQL базу данных! Там будет и структура, и запросы, и упомянутый B-tree реализован. :P[/quote]
Ага, а можно еще в SortedList хранить. Вото только памяти очень быстро перестанет хватать
Да, но не оптимальное по скорости.
здрасте приехали, вы задали задачку: (сейчас внимание) найти повторения в рандоме
это мягко говоря не самая тривиальная задача чтоб думать о скорости
здрасте приехали, вы задали задачку: (сейчас внимание) найти повторения в рандоме
это мягко говоря не самая тривиальная задача чтоб думать о скорости
Вы совершенно правы... Моя ошибочка :( Забыл упомянуть в задаче слово оптимальный
Кстати, при собеседовании никто не задает вопрос про оптимальность по первой, но потом в итоге говорят, что вы ошиблись, ваше решение не оптимально
ну дык, это.. кластер организуем как у АНБ или НАСА и посмотрим еще про оптимальность и масштабируемость..
хм, странное решение. как правило, sizeof(intptr_t) == sizeof(long)
Поэтому, сложновато выделить массив равный по размерам адресуемой памяти. А уж если речь идет о 64 битах... тут мы и адресовать столько не сможем.
Но для 32 бит можно конечно создать отдельный сегмент для хранения этого массива.
Файловые операции не масштабируются.ну дык, это.. кластер организуем как у АНБ или НАСА и посмотрим еще про оптимальность и масштабируемость..
Кстати, при собеседовании никто не задает вопрос про оптимальность по первой, но потом в итоге говорят, что вы ошиблись, ваше решение не оптимально
- Или говорят вы ошиблись, слишком замудрили. Гораздо проще будет сделать так и так...
- Но ведь это не оптимально
- А что этот участкок кода для нас критичен по производительности?
..
Файловые операции не масштабируются.
Тем более - в кластере. В лучшем случае - они КЕШИРУЮТСЯ. hmm Программно или аппаратно.
Ага, вычислительный кластер вообще имеет смысл только для распараллеливаемых задач - а тут все строго последовательно.
Файловые операции не масштабируются.
как это? если в RAID10 писать тоже прибавки не будет? представите рандом который делает 1 повтор на 600 ТБ выводимых данных? а вам его очень надо найти, т.к. это шифр на самом деле, там.. не знаю, плохих парней.
чтож вы 600ТБ на кластере не разместите? значит масштабируются? или я мало выпил?
Ребят, вы что? Для храниения в памяти битовй маски размером в long нужно полгига памяти. В любом случае при наличии отсутствия других задач, оптимальный алгоритм - это работа с битовой маской, а никак не с файлом или с базой данных
И давайте не будем обсуждать критичность/некритичность данной секции кода. Речь шла про алгоритм. Прошу еще раз извинение за то, что упустил слово "оптимальный".
нужно полгига памяти
пыщ, оптимальный, а осуществимый в не сферических ОС? как можно придумывать сферические алгоритмы?
system-root,
В конце концов, вопрос не ко мне, а к тем, кто эту задачу придумывал. Она, кстати, сугубо теоретическая. Я на собеседованиях с ней сталкивался несколько раз и решением оптимальным все время признавали работу с битовыми полями. Так или иначе, я закрываю тему во избежание дальнейшего флейма
