Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу 4 300 000 000 чисел жемчужины программирования
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 4 300 000 000 чисел жемчужины программирования - 05.08.2007, 20:44

Читаю книжку Жемчужины программирования. там есть задача:
Дан файл с 4 300 000 000 целыми 32 битными числами.
Найти число, которое встречается дважды.

У мя вопросы:
Откуда они столько 32 битных целых чисел взяли? их меньше ведь.
Как решить?

Я пока не придумал.


импортирован с progz.ru
Ответить с цитированием
  (#2 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 05.08.2007, 22:07

Ну, не намного меньше - 4 294 967 296

Это означает, что встречающиеся как минимум дважды числа обязательно встретятся, но их может быть относительно мало.

Кроме того, не совсем понятно, нужно ли найти число, которое встречается точно дважды - вот таких может и не быть.
Ответить с цитированием
  (#3 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 06.08.2007, 05:03

Ну, рас уж нету ограничений по времени и по памяти то у меня много вариантов :)
Ответить с цитированием
  (#4 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 06.08.2007, 10:36

Первое, что пришло в голову - создать битовый массив длиной 2^32 (512 мб), 1 - число уже встречалось, 0 - еще нет. Соответственно, достаточно одного прохода. Разумеется, можно конвертировать пространство и время - 256 мб и два прохода, 128 мб и четыре прохода и т.д.
Ответить с цитированием
  (#5 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 06.08.2007, 14:12

Ну, можно, вероятно, попытаться конвертировать более эффективно.

Собственно, идея конвертации основана на разбиении общего интервала на диапазоны и последовательной их обработке. Если завести на каждый диапазон счетчик, за первый проход получится посчитать, какой из диапазонов содержит достаточно много чисел. И тогда за следующий проход пройти его.

Только лень считать оптимальное количество диапазонов.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 06.08.2007, 17:51

gromozeka
Не совсем ваш первый метод подходит при случае встречания числа 3 раза и более :)
Ответить с цитированием
  (#7 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 06.08.2007, 23:03

Цитата:
gromozeka
Не совсем ваш первый метод подходит при случае встречания числа 3 раза и более
Почему, собственно, не подходит?
Разве что для случая отлова чисел встречающихся точно дважды.
Но мы так и не решили, насколько это важно.

Для случая отлова чисел встречающихся по меньшей мере дважды - отлично работает
Ответить с цитированием
  (#8 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 07.08.2007, 19:37

я тоже так думал:
разбиваем интервал возможных значений на N подинтервалов.
потом проходим по файлу один раз и смотрим, в какой интервал попадает число. И соответственно: если в первый, то записываем в первый файл, если во второй, то во второй файл.
Итого получим N файлов меньшей длинны вместо одного большого. Если какой-то файл слишком длинный, то можно разбить диапазон на поддиапазоны, пока нас всё не устроит.
потом каждый файл обрабатывается отдельно с помощью битового массива.

Но что-то мне кажется, что решение должно быть элегантнее.


импортирован с progz.ru
Ответить с цитированием
  (#9 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 07.08.2007, 21:39

Alexiski
> Разве что для случая отлова чисел встречающихся точно дважды.

Ну я именно об этом и говорил, это же очевидно.
Ответить с цитированием
  (#10 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 07.08.2007, 22:07

если повторов будет не катострофически много, то можно без проблем всё организовать... я так и думал.
Ответить с цитированием
  (#11 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,266
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 08.08.2007, 00:01

Если считать только точные попадания в двойку, то потребуется фиксировать три состояния каждого числа (в 1.5-2 раза больше памяти), и мое жульничество с подсчетом чисел по диапазонам работать не будет.
Ответить с цитированием
  (#12 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 08.08.2007, 12:01

нет, не надо будет.. Зачем тебе каждого числа? Только повторяющихся.
Если нам надо поставить единицу в битовом массиве, а она там уже стоит, то это число записать в список_повторяющихся_чисел. Если повторяющихся чисел будет мало, то этот список будет короткий и не составит никакого труда посчитать, сколько раз каждое число входит в этот список и прибавить к этому 1.

А если делать три состояния, то не понятно, почему нельзя бить на диапазоны.. ничего ведь не поменялось... всё можно.
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 08.08.2007, 14:23

Цитата:
Ну, можно, вероятно, попытаться конвертировать более эффективно.

Собственно, идея конвертации основана на разбиении общего интервала на диапазоны и последовательной их обработке. Если завести на каждый диапазон счетчик, за первый проход получится посчитать, какой из диапазонов содержит достаточно много чисел. И тогда за следующий проход пройти его.

Только лень считать оптимальное количество диапазонов.
Давно меня тут не было.
Разумеется, Вы абсолютно правы.
По поводу диапазонов. Вариантов совсем немного:

Код:
1 байт на счетчик.
длина диапазона 2^8=256 бит=32 байта
счетчиков нужно 2^(32-8)=16777216*1 байт=16 мегабайт

2 байта на счетчик.
длина диапазона 2^16=65536 бит=8 килобайт
счетчиков нужно 2^(32-16)=65536*2 байта=128 килобайт

3 байта на счетчик.
длина диапазона 2^24=16777216 бит=2 мегабайта
счетчиков нужно 2^(32-24)=256*3 байта=768 байт

4 байта на счетчик.
мой тривиальный вариант, требующий 512 мегабайт памяти
Очевидно, второй вариант - оптимальный.
Ответить с цитированием
  (#14 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 08.08.2007, 15:45

Цитата:
нет, не надо будет.. Зачем тебе каждого числа? Только повторяющихся.
Если нам надо поставить единицу в битовом массиве, а она там уже стоит, то это число записать в список_повторяющихся_чисел. Если повторяющихся чисел будет мало, то этот список будет короткий и не составит никакого труда посчитать, сколько раз каждое число входит в этот список и прибавить к этому 1.

А если делать три состояния, то не понятно, почему нельзя бить на диапазоны.. :? ничего ведь не поменялось... всё можно.
Таким образом на тесте, где одно и то же число посторяется максимальное кол-во раз ваша прога наберет максимальное кол-во памяти и худший резалт) Здесь ведь нельзя рассчитывать на "скорее всего" или "обычно повторяющихся чисел мало".
Ответить с цитированием
  (#15 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 08.08.2007, 15:49

По условию оригинальной задачи из "жемчужин" - не ровно два раза, а как минимум два раза. Так что наше совместное решение по всей видимости оптимально.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нужно разобрать программу для перевода списка арабских чисел в список римских чисел. RuslanTM Prolog 2 18.12.2011 17:04
Из множества целых чисел 1..100 выделить множество чисел, являющихся, в свою очере Tormiz61 Pascal 4 18.06.2011 15:07
Методология программирования Arachnelis Мысли вслух 18 01.08.2007 01:11
1C vs С/С++ что выбрать для программирования Gillian Мысли вслух 73 04.07.2007 13:42
языки программирования Матрикс Pascal 15 18.06.2007 11:46
язык программирования Матрикс Форум программистов 1 07.06.2007 19:16
О языках программирования Misha123 Мысли вслух 8 10.05.2006 23:54
О языках программирования Dian Юмор 3 27.04.2006 17:50
Язык программирования Loid Мысли вслух 17 29.05.2005 23:20
Дао программирования Garik Юмор 10 06.08.2004 19:15
Технологии программирования Andrey1 Мысли вслух 1 07.07.2004 06:48
Искусство программирования VitauT Офтопик 0 23.06.2004 18:21



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов