Задача для желающих пошевелить мозгами

Есть функция, генерящая числа типа long в произвольном порядке (random). Предложите алгоритм работы программы, при котором ее выполнение прерывается как только вышеупомянутая функция сгенерит уже ранее сгенеренное ею число.

P.S. Просьба уже знающих решение в тему не писать. Пусть попробуют решить те, кто с этой задачей не сталкивался (задача очень часто встречается на собеседованиях, поэтому многим, наверное, это будет полезно)

Теоретически я представляю как это можно сделать :lol:

Leviafan написал:

Теоретически я представляю как это можно сделать :lol:

Ну так расскажите. Я нигде не говорил, что обязательно писать код. Я говорил про АЛГОРИТМ

Я знаю только вариант на быдлокоде: сгенеренные числа складируются в список (текстовый файл), каждое новое число сравнивается со списком по какому-то одному параметру (например первой цифре, или числу знаков). Если есть совпадение, то сравниваем уже всё число с выборкой от предыдущего условия. Совпадает - goto end.

С удовольствием узнаю более изящное решение.

Надо генерируемые числа куда то сохранять, а потом при новой генерации сверять с сохраненными значениями

Leviafan написал:

Надо генерируемые числа куда то сохранять, а потом при новой генерации сверять с сохраненными значениями

Ключевое слово "куда-то" :) Вопрос в том, куда и как?

Writer написал:

Я знаю только вариант на быдлокоде: сгенеренные числа складируются в список (текстовый файл)

http://en.wikipedia.org/wiki/B-tree ?

nesk,
представьте себе, что в течение довольно продолжительного времени рандом-функция генерит вам лонги. За какой промежуток времени у вас память забьется? А потом, поиск (в массиве значений) занимает какое-никакое время, которое увеличивается с ростом объема просматриваемых данных

Leviafan написал:

если я не ошибаюсь то можно сразу в массив добавлять минуя текстовые файлы или БД

Мой опыт половой жизни с BAT-файламив досе подсказывает, что нужно складироватьчисла в обычный текстовый файл, а потом читать из него строки для сравнения. Если кого волнует размер файла, то весь процесс можно организовать на ФС со сжатием.

Writer написал:

Я знаю только вариант на быдлокоде: сгенеренные числа складируются в список (текстовый файл), каждое новое число сравнивается со списком по какому-то одному параметру (например первой цифре, или числу знаков). Если есть совпадение, то сравниваем уже всё число с выборкой от предыдущего условия. Совпадает - goto end.

С удовольствием узнаю более изящное решение.

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

Hvzh написал:

представьте себе, что в течение довольно продолжительного времени рандом-функция генерит вам лонги. За какой промежуток времени у вас память забьется? А потом, поиск (в массиве значений) занимает какое-никакое время, которое увеличивается с ростом объема просматриваемых данных

Числа хранить в любом случае не надо. Надо хранить бит по адресу сосуществующему сгенерированному лонгу.

Немножко упрощу (или усложню - как для кого) задачу. На компе нет внешнего носителя информации. Программа грузится в оперативную память размером, ну пусть будет 16 Гб или 32, или 64. Кроме этой программы никаких других процессов нет. Учтите господа, что я этим сильно облегчаю вам задачу

Выделяем некую область памяти. Зависящую от границ чисел. Заполняем 0. Далее генерируем число. И пишем в эту память со смещением равным этому числу 1. При записи проверяем если там уже 1 - задача решена.

Ой не до конца тему дочитал nesk уже практически это написал

voral,
5 баллов! Вы прошли тестирование на должность программиста в компании Microsoft!
Кстати, ответ знали или как?

это не юникс дао, мы не смещаем и не заполняем память, мы обращаемся к pipe как к вершине совершенства.

Hvzh написал:

voral,
5 баллов! Вы прошли тестирование на должность программиста в компании Microsoft!
Кстати, ответ знали или как?

Нет. Я с такой задачей не сталкивался.

Но работал с неким протоколом в котором очень много работал по байтно с памятью, а потом отправлял. Видимо это и помогло

что-то в условиях задачи я не вижу про границы диапозона чисел

system-root написал:

это не юникс дао, мы не смещаем и не заполняем память, мы обращаемся к pipe как к вершине совершенства.

Вероятно. На линуксе я 1 год. И, пока, ни одного значительного проекта под Линукс не делал. (Точнее даже мелких завершенных нет)
Интересно, а как с пайпами в этой задаче работать? Если это коротко можно . Подробнее пойду в гугль курить когда время будет.

komcumir написал:

что-то в условиях задачи я не вижу про границы диапозона чисел

Да же если использовать лонг. На это потребуется 4,294,967,295 байт (на 32 разрядной системе)
Но как, правило, ведь генерят в задачах в неком диапазоне (более узком)