|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
19.02.2013, 19:07 | #1 |
Новичок
Джуниор
Регистрация: 19.02.2013
Сообщений: 2
|
C Идентификатор пользователя
Здравствуйте.
На собеседовании была выдана следующая задача для реализации на С: Дан текстовый файл с 4 миллиардами натуральных чисел, представляющих собой идентификаторы пользователей некой соц. сети. В сети регистрируется новый пользователь, и для него нужно выделить уникальный идентификатор. Т.е. нужно найти число, которого еще нет в файле. При этом даны условия - программа может использовать лишь ограниченное кол-во памяти(1 Гб) и файл может быть прочитан не более 4 раз. Собственно, вопрос - каким образом все это можно реализовать? Я пробовал решить через нахождение максимума среди всех чисел, но было сказано, что максимум int может входить в список чисел. |
19.02.2013, 21:10 | #2 |
Пользователь
Регистрация: 16.02.2013
Сообщений: 53
|
Если файл упорядоченный, то ищем первое свободное место в порядке номеров. Если не упорядоченный, то надо сделать его упорядоченным, и в дальнейшем использовать его. По ограничению на память используем проецируемые в память файлы. Подходит?
|
19.02.2013, 21:33 | #3 |
Новичок
Джуниор
Регистрация: 19.02.2013
Сообщений: 2
|
Во-первых, спасибо за ответ.
Во-вторых, файл, конечно, не упорядоченный. Спасибо за подсказку про проецируемые в память файлы, но у меня возникает ( вероятно в силу неопытности ) пара вопросов о них. Насколько я понимаю, размер файла все равно не позволит целиком его спроецировать в адресное пространство, или это не так? Как дополнительное условие к задаче стоит цель реализовать все тоже, используя только 1 Кб памяти. И еще при маппинге вроде бы достаточно только 1 раз прочитать файл( или я заблуждаюсь? ), тогда зачем стоит ограничение в 4 считывания файла? |
19.02.2013, 21:37 | #4 | |
Старожил
Регистрация: 23.10.2010
Сообщений: 2,309
|
Цитата:
Может туда надо посмотреть?
Как-то так, ...
|
|
19.02.2013, 22:17 | #5 |
Пользователь
Регистрация: 16.02.2013
Сообщений: 53
|
При проецировании файлов создаётся окно, в которое файл можно грузить по частям, двигая его по файлу. Насчёт дополнительного условия в 1 кб, можно просто посимвольно читать файл, используя стандартные функции в/в Си, тут же преобразовывать его в число, пока не встретился используемый разделитель. Про чтение, может речь идёт о том, чтобы файл был просканирован не более 4 раз? Что бы не возникало соблазна генерировать случайные числа и искать из в файле?
Можно решить при помощи использования битовой каррты. Каждое число из 4 млрд. соответствует определённому номеру бита. То есть для 4 млрд. чисел нам потребуется 4 млрд. бит или 0.5 млрд байт. А уже в битовом массиве вести поиск первого свободного идентификатора. Даже упорядочивать файл не надо. Опять же битовая карта может быть использована для превращения файла в упорядоченный. Аналогично можно решить вопрос и при использовании 1 кб памяти. Только вместо битовой карты в памяти, можно создать битовую карту в файле. Последний раз редактировалось Alchemic; 19.02.2013 в 22:46. Причина: Добавил |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
идентификатор в паскале | drcoxer | Паскаль, Turbo Pascal, PascalABC.NET | 28 | 13.11.2011 14:22 |
Неизвестный идентификатор | dubailand | Общие вопросы Delphi | 6 | 24.08.2011 12:15 |
Идентификатор строки | eda | Microsoft Office Excel | 9 | 25.08.2009 21:56 |
Идентификатор в DBF | mixer94 | БД в Delphi | 10 | 14.07.2009 13:56 |
Уникальный идентификатор | romets | Win Api | 9 | 03.02.2008 02:30 |