ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Выборка из миллиарда
88 сообщений из 88, показаны все 4 страниц
  все  
Выборка из миллиарда
    #38639090
maxtrav
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
maxtrav
Гость
Попалась задачка. Есть ее решение. Но не могу понять хоть убей, как ее решает автор. Пожалуйста помогите. Растолкуйте решение.
http://www.lotos-khv.narod.ru/dist/lek6.htm
...
Рейтинг: 0 / 0
12.05.2014, 18:34
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639122
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ее автор - хабаровская "школа программистов". Она и должна растолковывать и пояснять
потоки своего сознания. При чём здесь sql.ru - непонятно.

P.S. Просто мнение....
...
Рейтинг: 0 / 0
12.05.2014, 19:11
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639163
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Высосали проблему из пальца.
При известной нижней границе "наименьшее отсутствующее" или "ничего" или "нижняя граница".
Соответственно, требуется проверить, есть ли в выборке число, равное нижней границе. Один проход.
Даже если переформулировать идиотскую формулировку - всё равно один проход. Без всяких сортировок.
...
Рейтинг: 0 / 0
12.05.2014, 20:08
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639167
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Basil A. SidorovПри известной нижней границе "наименьшее отсутствующее" или "ничего" или "нижняя граница".Это почему же?
Вполне может быть, что "нижняя граница" занята, а "наименьшее отсутствующее" где-то больше.
...
Рейтинг: 0 / 0
12.05.2014, 20:15
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639176
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
miksoftВполне может быть, что "нижняя граница" занята, а "наименьшее отсутствующее" где-то больше.Да, в этой формулировке больше похоже на правду, но это всё равно один проход.
...
Рейтинг: 0 / 0
12.05.2014, 20:25
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639177
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Basil A. SidorovДа, в этой формулировке больше похоже на правду, но это всё равно один проход.Два. Первый на поиск наименьшего, второй - на поиск дырки.
...
Рейтинг: 0 / 0
12.05.2014, 20:27
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639178
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Basil A. SidorovmiksoftВполне может быть, что "нижняя граница" занята, а "наименьшее отсутствующее" где-то больше.Да, в этой формулировке больше похоже на правду, но это всё равно один проход.Числа не отсортированы. Как?
...
Рейтинг: 0 / 0
12.05.2014, 20:27
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639181
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
miksoftЧисла не отсортированы. Как?Как искать наименьшее в один проход?
Сравнивать очередного кандидата с уже найденным претендентом.
...
Рейтинг: 0 / 0
12.05.2014, 20:30
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639182
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Задача ниочем
авторИз числового интервала от единицы до миллиарда выбираются случайным образом без повторений миллион чисел и записываются в файл. Необходимо за приемлемое время выяснить, какое наименьшее число отсутствует в файле. Использовать массивы или иные структуры данных, их заменяющие, запрещается.
Там в решении предлагается сначала отсортировать, затем искать дырки между соседними. Алгоритмы сортировки в куче источников описаны.

Только наполнение 0,1% (миллион из миллиарда), т.е. вероятность 1000 к 1 что нет первого, поэтому можно тупо перебирать 1,2,3,4,5, сканировать весь файл и с большой вероятностью получить отсутствующее за несколько проходов. Скорость чтения со среднего диска 70-80 Мб/сек, т.е. 4Мб (миллион int`ов) прочитаются 20 раз в секунду . Можно предположить случай что последовательность 1-999`999 непрерывна, затем 1`000`001, тогда потребуется 13-14 часов, но это из области невероятного, т.к. генератор случайных чисел не дает такие последовательности. Даже если так и изначально прочитать в память (в кэш проца все войдет), то 4000-8000 сканов в секунду или 3-5 минут в худшем случае, задача параллелится и на 4 ядрах можно за минуту уложиться.
...
Рейтинг: 0 / 0
12.05.2014, 20:31
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639183
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Basil A. SidorovmiksoftЧисла не отсортированы. Как?Как искать наименьшее в один проход?
Сравнивать очередного кандидата с уже найденным претендентом.Вы совсем не вчитались в задачу.
Ищется не наименьшее присутствующее, а наименьшее отсутствующее.
В файле вполне могут быть числа 1,2,3, ... 1000, 1002, ... (только в произвольном порядке). А 1001 нужно найти.
...
Рейтинг: 0 / 0
12.05.2014, 20:33
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639187
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Dima TТам в решении предлагается сначала отсортироватьСортировка нужна для поиска медианы.
Для поиска граничных значений сортировка избыточна. После того, как граничное значение известно - поиск дырки становится тривиальным.
...
Рейтинг: 0 / 0
12.05.2014, 20:36
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639190
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Basil A. SidorovПосле того, как граничное значение известно - поиск дырки становится тривиальным.Погорячился.
...
Рейтинг: 0 / 0
12.05.2014, 20:38
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639192
miksoft
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
miksoft
Участник
Dima T,

Решение "в лоб" можно ускорить тем, что переписать из исходного в промежуточный файл числа, которые меньше или равны миллиону. При равномерном распределении чисел это даст сокращение объема файла в тысячу раз.
...
Рейтинг: 0 / 0
12.05.2014, 20:40
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639195
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
miksoftDima T,

Решение "в лоб" можно ускорить тем, что переписать из исходного в промежуточный файл числа, которые меньше или равны миллиону. При равномерном распределении чисел это даст сокращение объема файла в тысячу раз.
можно 1000 если будет 1000, то следующую 1000 и т.д. пока меньше 1000 за раз не считается. Случайное распределение заданное в ТЗ тоже надо использовать. 1000 условно, точнее его можно рассчитать из скорости записи и чтения файла и параметра "приемлемое время"
...
Рейтинг: 0 / 0
12.05.2014, 20:47
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639223
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
Миллион четырёхбайтовых чисел - меньше четырёх мегабайт.
Даже в рамках идиотских ограничений сортировка миллиона чисел не может дать миллиарды файловых операций.
...
Рейтинг: 0 / 0
12.05.2014, 21:59
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639255
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
maxtravПопалась задачка. Есть ее решение. Но не могу понять хоть убей, как ее решает автор. Пожалуйста помогите. Растолкуйте решение.
http://www.lotos-khv.narod.ru/dist/lek6.htm

Больше всего улыбнуло желание автора статьи доказать свою правоту, а потому "неудачные" решения расчитываются исходя их миллиарда элементов, а удачное - из миллиона. Круто конечно ))) откуда взято число миллиард?! Да от балды...

Перефразирую. В файле записаны 1'000'000 чисел из интервала 1 - 1'000'001 в случайном порядке. Найти пропущенное число. Как уже сказали, и в том и в другом случае будет как минимум одно число пропущено, нам осталось его найти.

Вот теперь оцениваем задачу правильно. :)

В итоге представленное решение (точнее идея) неплохое. Хотя я предложу немного лучше :)

Я по подобному принципу (на основании, кстати, метода быстрой сортировки) сортировал все числа у себя в программках (когда учился или участвовал в олимпиадах). Сортировка разумеется была побитная (то есть меняем местами числа, если число с соответствующим битом равным 1 стоит левее числа с тем же битом равным нулю. Таким образом рекурсия уходит максимум на n уровней, где n - число бит в числе)

Отвлёкся :) Итак... поясняю решение автора:

У нас есть миллион чисел, которыми можно заполнить без пробелов только миллион первых позиций. Потому, если есть пробел, то он находится в позиции от 1 до 1000000. Этот интервал мы и проверяем. Берём число 500000, начинаем читать файл и сравнивать каждое число с данным. Если прочитанное из файла меньше - прибавляем 1 к счётчику. Если в итоге счётчик равен 500000 - значит первые пол миллиона позиций заполнены без пробелов и нас интересует вторая половина миллиона. Итак, когда мы узнали в какой половине миллиона интересующий нас пропуск, повторяем то же действие для соответствующей половины миллиона, и делим ещё на 2 интервала... и так пока у нас не останется интервал в 1... именно он и будет нашим искомым пропуском.

Это всё нормальными словами и без лишних действий, которые он описал...

Не буду сильно комментировать его решение... из недостатков отмечу - он говорит о миллиардах операций, зато его программа сама вынуждена провести чтение 20'000'000 чисел по 4 байта (при чтении с диска в 512 байт, то есть по одному сектору, это будет около 16000 операций чтения). Замечу что методу быстрой сортировки потребуется приблизительно столько же... просто у него ещё будут затраты на запись чисел в их новые позиции.


На практике такая задача решилась бы в разы легче (мной по крайней мере). Я бы завёл файл на миллион байт и заполнил бы его нулями. А потом читая число из первого файла, выставлял бы байт во втором файле с соответствующим смещением в единицу (можно и с битами работать конечно, но тут вопрос простоты реализации. С битами не удобно работать). В итоге, задача свелась бы к чтению и записи миллиона чисел. После записи второго файла читаем его побайтово и смещении байта со значением 0 даёт нам искомое число (пропущенную позицию).

Кстати... на практике не бывает ограничения "не использовать массивы". :) А учитывая метод решения, если заюзать массив как напрерывный набор двоичных флагов, то и памяти на такой массив потребуется 8МБ. Большинству даже вэб приложений такое количество памяти спокойно выделяется (им выделяется даже в разы больше). Потому правильно тут сказали, при разумных ограничениях задача решаема в 2 прохода... 1 - пишем массив, второй - ищем пропуск.
...
Рейтинг: 0 / 0
12.05.2014, 22:52
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639270
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
что то мне кажется автор там слишком мудрит
так же непонятно ограничение на массивы, сам он вполне их использует
видимо имеется ввиду что весь файл напрямую в массив загонять нельзя
если так, то достаточно выполнить подсчёт пройдясь по всему файлу

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
M1,M2,M3,M4 : array [0..255]of integer;

while no EOF(T) do begin
readln(v);
inc(M1[v and 255]); v :=v shr 8;
inc(M2[v and 255]); v :=v shr 8;
inc(M3[v and 255]); v :=v shr 8;
inc(M4[v and 255]); 
end;


и уже дальше анализировать
в этом русле решить задачу наверное будет легче
...
Рейтинг: 0 / 0
12.05.2014, 23:18
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639313
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ограничение на "неиспользование" массивов выглядит весьма странно. Особенно на фоне сортировок.
Ну... на малых выборки объёмах можно было задействовать массив с биткартой. Идея
- похожа на поиск неуникального целого числа в потоке целых.

А на больших объёмах - merge-сортировкой и 1 проходом по результату.

Или - гибридный вариант. Биткарта (по оценке) превышает memory двукратно - бъём
диапазон на два поддиапазона. И в два прохода находим дырку в "биткарте".
Всяко лучше чем сортировка.

Кстати совершенно напрасно автор ограничился типом integer... :)
...
Рейтинг: 0 / 0
13.05.2014, 00:46
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639346
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Тьфу ты, спать надо по ночам
простая задача, там действительно не надо массивов, щас время появится накатаю решение
...
Рейтинг: 0 / 0
13.05.2014, 06:03
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639351
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
никакой сортировки там не надо
просто пройтись по файлу с подсчётом Log2(MaxN) раз
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
program o1;
type
  { TFIterator }
  TFIterator=class
  private
    FCurrent: integer;
   public
    function MoveNext:boolean;
    property Current:integer read FCurrent;
  end;
  { TSomeFile }
  TSomeFile=class
    public
     class function GetEnumerator():TFIterator;
  end;
{ TFIterator }
function TFIterator.MoveNext: boolean;
begin
  inc(FCurrent);
  Result:=(Current<=1000001);
  if Current=11111 then inc(FCurrent); //наш пропуск
end;
{ TSomeFile }
class function TSomeFile.GetEnumerator: TFIterator;
begin
  Result:=TFIterator.Create;
end;
var a:integer;
  f:TSomeFile;
  L,R,M:integer;
  C:integer;
begin
  f:=TSomeFile.Create;
  L:=1;
  R:=1000000000;
  repeat
    M:=(L+R)div 2;
    C:=0;
    for a in  f do begin  //цикл пробежки по файлу с подсчётом
      if (a<L)or(a>R) then continue;
      if a<=M then inc(C);
    end;
    if C<(M-L+1) then begin
      R:=M;
    end else begin
      L:=M+1;
    end;
  until L=R;
  Writeln(L); // найденная дырка
  f.Free;
end.
...
Рейтинг: 0 / 0
13.05.2014, 06:49
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639352
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
maytonЕе автор - хабаровская "школа программистов". Она и должна растолковывать и пояснять
потоки своего сознания. При чём здесь sql.ru - непонятно.

именно в кавычках, поддерживаю


miksoftВы совсем не вчитались в задачу.
Ужасная постановка задачи.
...
Рейтинг: 0 / 0
13.05.2014, 06:56
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639354
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
ПрограмёрБольше всего улыбнуло желание автора статьи доказать свою правоту, а потому "неудачные" решения расчитываются исходя их миллиарда элементов, а удачное - из миллиона. Круто конечно ))) откуда взято число миллиард?! Да от балды...

Перефразирую. В файле записаны 1'000'000 чисел из интервала 1 - 1'000'001 в случайном порядке. Найти пропущенное число. Как уже сказали, и в том и в другом случае будет как минимум одно число пропущено, нам осталось его найти.

такая постановка решается очень просто :), код примерно такой:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
	//поиск единственного отсутствующего
	int res = 1 ^ *(a + 0);
	for (int i = 2; i < 1000001; i++)
	{
		res = res^(*(a + i - 1)^i);
	}
	res = res ^ 1000001;



если индексы не напутал, но смысл думаю понятен :)
...
Рейтинг: 0 / 0
13.05.2014, 07:11
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639355
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
гадкое решение ужасно поставленной задачиПоделим миллиардный интервал на два интервала по 500 миллионов. Где может находиться искомое число? Очевидно, в первом, так как 500-миллионный интервал миллионом чисел не заполнить. Теперь поделим первый 500-миллионный интервал на два и т. д. Рано или поздно заключение о том, что интервал, содержащий искомое число, будет первым, окажется несправедливым. Поэтому давайте для любой пары интервалов разработаем более универсальный метод.
а где в постановке задачи написано что все числа должны быть подряд ?????


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


а если они подряд, то можно найти мак и мин, и сделать через код приведённый мной выше.
...
Рейтинг: 0 / 0
13.05.2014, 07:18
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639382
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
SashaMercury, для олимпиады задача вполне нормальная
автора где в постановке задачи написано что все числа должны быть подряд ?????
как раз написано обратное
авторИз числового интервала от единицы до миллиарда выбираются случайным образом без повторений миллион чисел и записываются в файл
авторНеобходимо за приемлемое время выяснить, какое наименьшее число отсутствует в файле.

т.е. нет если в файле 1 - значит единица

задача на бинарный поиск - сложность C(log(N)*N), где N - количество цифр в файле

я правда в начальных условиях погорячился
Код: pascal
1.
2.
  L:=1;
  R:=1000000000;


достаточно
Код: pascal
1.
2.
  L:=1;
  R:=L+1000000;


искомое число может быть в интервале [1..N+1]

никаких сортировок тут делать не нужно
...
Рейтинг: 0 / 0
13.05.2014, 08:54
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639396
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПЕНСИОНЕРКА
Участник
maxtrav,
Код: vbnet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
Sub w140513_0845()
Dim s1, s2, j1, j2
''Выборка из миллиарда
''
''Условие задачи.
''
''Из числового интервала от единицы до миллиарда выбираются случайным образом без
''повторений миллион чисел и записываются в файл.
''Необходимо за приемлемое время выяснить, какое наименьшее число отсутствует в файле.
''Использовать массивы или иные структуры данных, их заменяющие, запрещается.

''=================упрощенный пример================
''есть 10 цифр, выбрано случайно 6
''
''возможны две ситуации
''1-выбраны от 1 до 6 , решение= 7
''2-выбор включает дырку,например=4
''
s1 = "`5`1`6`2`4`3`"           '''выборка1, числа через любой разделитель
's1 = "`5`1`6`2`9`3`"           '''выборка2, числа через любой разделитель
j1 = 0

Do While j1 <= 6
j1 = j1 + 1

s2 = "`" & j1 & "`"            '''
If InStr(s1, s2) = 0 Then

Debug.Print s2
Exit Do
End If

Loop
End Sub



подобные задачи решаю поиском в строке
здесь сложность --в длине строки(1000000 по 6 символов и 2 разделителя=8млн символов), несколько меньше с учетом длины числа
количество чиселзначностьразделители91 цифра2902290032900042900005290000062
...
Рейтинг: 0 / 0
13.05.2014, 09:11
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639406
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ПЕНСИОНЕРКАmaxtrav,
[src VB]
Sub w140513_0845()
Dim s1, s2, j1, j2
''Выборка из миллиарда
''
''Условие задачи.
''
''Из числового интервала от единицы до миллиарда выбираются случайным образом без
''повторений миллион чисел и записываются в файл.
''Необходимо за приемлемое время выяснить, какое наименьшее число отсутствует в файле.
''Использовать массивы или иные структуры данных, их заменяющие, запрещается.


а по вашему строка из кучи символов это не массив?
...
Рейтинг: 0 / 0
13.05.2014, 09:24
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639414
Фотография ПЕНСИОНЕРКА
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ПЕНСИОНЕРКА
Участник
kealon(Ruslan),

нет, это файл на диске, согласно условию задачиавторповторений миллион чисел и записываются в файл.
...
Рейтинг: 0 / 0
13.05.2014, 09:34
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639426
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ПЕНСИОНЕРКАkealon(Ruslan),

нет, это файл на диске, согласно условию задачиавторповторений миллион чисел и записываются в файл.

и вы его полностью в строку решили загрузить?
...
Рейтинг: 0 / 0
13.05.2014, 09:41
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639585
ALOTE
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ALOTE
Участник
Может я чего не понял, но по-моему все тривиально - объявляется интервал с нижней и верхней границей 1..1000000000. Потом идется по файлу. Если встреченное число рано нижней границе к нижней границе прибавляется 1 , если меньше верхней, верхняя равна встреченному числу. Если нижняя граница становится равна верхней, начинаем заново, но нижней границе+1, а верхнюю опять делаем опять 1000000000.
...
Рейтинг: 0 / 0
13.05.2014, 12:04
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639594
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ALOTE, а если-бы в задаче надо было найти две нижних "дырки" ?
...
Рейтинг: 0 / 0
13.05.2014, 12:11
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639602
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Почитал топик, оказывается очень хорошая задачка ... чтобы проверить как разработчики умеют понимать ТЗ :)

...
Рейтинг: 0 / 0
13.05.2014, 12:14
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639623
ALOTE
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ALOTE
Участник
maytonALOTE, а если-бы в задаче надо было найти две нижних "дырки" ?
То же самое, нижняя граница+1
...
Рейтинг: 0 / 0
13.05.2014, 12:22
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639647
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ALOTE, хех. Хвастун. А вот тебе еще мысль. Дана выборка из 2^32 - 1 уникальных элементов int.
Я вот думаю как найти дырку без использования проверок условий "if-then-else".
...
Рейтинг: 0 / 0
13.05.2014, 12:41
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639652
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ALOTEМожет я чего не понял, но по-моему все тривиально - объявляется интервал с нижней и верхней границей 1..1000000000. Потом идется по файлу. Если встреченное число рано нижней границе к нижней границе прибавляется 1 , если меньше верхней, верхняя равна встреченному числу. Если нижняя граница становится равна верхней, начинаем заново, но нижней границе+1, а верхнюю опять делаем опять 1000000000.
и сколько раз придётся читать файл твоему алгоритму в худшем случае ?
...
Рейтинг: 0 / 0
13.05.2014, 12:46
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639666
ALOTE
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ALOTE
Участник
kealon(Ruslan)и сколько раз придётся читать файл твоему алгоритму в худшем случае ?
В худшем случае миллион раз, при условии, что случайная выборка даст отсортированный в обратном порядке массив чисел от 1 до 100000. Но при каждом проходе число читаемых строк будет уменьшаться на 1.
...
Рейтинг: 0 / 0
13.05.2014, 12:51
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639669
ALOTE
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ALOTE
Участник
maytonALOTE, хех. Хвастун. А вот тебе еще мысль. Дана выборка из 2^32 - 1 уникальных элементов int.
Я вот думаю как найти дырку без использования проверок условий "if-then-else".
Может вообще без программирования?
...
Рейтинг: 0 / 0
13.05.2014, 12:53
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639682
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
ALOTEkealon(Ruslan)и сколько раз придётся читать файл твоему алгоритму в худшем случае ?
В худшем случае миллион раз, при условии, что случайная выборка даст отсортированный в обратном порядке массив чисел от 1 до 100000. Но при каждом проходе число читаемых строк будет уменьшаться на 1.
посмотри мой алгоритм, c бинарным поиском, он делает это гарантированно за 20 проходов и ему неважно в каком порядке данные 10^6 < 2^20

PS: задача то олимпиадная, проверка на входе будет подсовывать самые неудобные случаи
...
Рейтинг: 0 / 0
13.05.2014, 12:59
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639693
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
maytonALOTE, хех. Хвастун. А вот тебе еще мысль. Дана выборка из 2^32 - 1 уникальных элементов int.
Я вот думаю как найти дырку без использования проверок условий "if-then-else".
:-)

а сколько чисел в выборке, всего одно выпало?
а While использовать можно?

если всего одно число

сумма всех чисел от 1 до N = (1+N)*N/2
вычитаем из него все числа в файле
итоговым результатом будет невключённое число
...
Рейтинг: 0 / 0
13.05.2014, 13:06
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639862
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Может XOR-ем попробовать?
...
Рейтинг: 0 / 0
13.05.2014, 15:02
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38639894
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Поделим миллиардный интервал на два интервала по 500 миллионов. Где может находиться искомое число? Очевидно, в первом, так как 500-миллионный интервал миллионом чисел не заполнить. Теперь поделим первый 500-миллионный интервал на два и т. д. Рано или поздно заключение о том, что интервал, содержащий искомое число, будет первым, окажется несправедливым. Поэтому давайте для любой пары интервалов разработаем более универсальный метод.

Почему очевидно в первом ?
...
Рейтинг: 0 / 0
13.05.2014, 15:26
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640044
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
SashaMercuryПоделим миллиардный интервал на два интервала по 500 миллионов. Где может находиться искомое число? Очевидно, в первом, так как 500-миллионный интервал миллионом чисел не заполнить. Теперь поделим первый 500-миллионный интервал на два и т. д. Рано или поздно заключение о том, что интервал, содержащий искомое число, будет первым, окажется несправедливым. Поэтому давайте для любой пары интервалов разработаем более универсальный метод.

Почему очевидно в первом ?

как уже говорил... автор предоставил избыточное решение (делается больше чем надо). Очевидно, что пропуск находится в одной из первых 1000001 позиций. А значит и 1000 000 000 проверять не надо... достаточно начинать делить интервалы начиная с миллиона (точнее начиная с 0xFFFFF = 1048576, тогда все операции легко сводятся к битовым, а потому идёт экономия времени и упрощение логики).

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
Program propusk;
var f: text;
    res: longword;
    mask: longword;
    counter: longword;
    num: longword;
begin
    mask := $80000;
    res := $FFFFF;
    assign(f, 'input.txt');
    while mask>0 do
    begin
        reset(f);
        counter := 0;
        while (not eof(f)) do
        begin
            read(f, num);
            dec(num); {это костыль, все числа сдвигаем на единицу вниз, из-за того, что считаем не от нуля, а от единицы}
            if ((num and res and (not mask))=num) then inc(counter); {если при накладывании маски число не изменилось - оно в нашем интервале}
        end;
        if (counter<mask) then {если счётчик меньше возможного количества чисел в интервале, 
значит нас интересует именно он и потому мы сбрасываем соответствующий бит в 0, иначе мы будем рассматривать интервал "над" данным}
        begin
            res := res and (not mask);
        end;
        mask := mask shr 1;
    end;
    close(f);
    writeln(res+1);
end.



Вот так :) Вот моё решение, на основании решения автора.
...
Рейтинг: 0 / 0
13.05.2014, 17:08
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640197
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ох уж эти любители Паскаля...
...
Рейтинг: 0 / 0
13.05.2014, 18:56
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640220
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
[quot Програмёр]SashaMercuryпропущено...
Вот так :) Вот моё решение, на основании решения автора.

Не работает ваше решение, я его немного модифицировал без потери смысла
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
Program propusk;
var
    res: longword;
    mask: longword;
    counter: longword;
    num: longword;
    i:integer;
begin
    mask := $80000;
    res := $FFFFF;

    while mask>0 do
    begin

        counter := 0;
        for i:=1 to 1000001 do
        begin
            if i=11 then continue;
            num:=i;
            dec(num); {это костыль, все числа сдвигаем на единицу вниз, из-за того, что считаем не от нуля, а от единицы}
            if ((num and res and (not mask))=num) then inc(counter); {если при накладывании маски число не изменилось - оно в нашем интервале}
        end;
        if (counter<mask) then {если счётчик меньше возможного количества чисел в интервале,
значит нас интересует именно он и потому мы сбрасываем соответствующий бит в 0, иначе мы будем рассматривать интервал "над" данным}
        begin
            res := res and (not mask);
        end;
        mask := mask shr 1;
    end;

    writeln(res+1);
end.



выводит 16, хотя должно быть 11
кроме того оно выходит считает файл 32 раза
...
Рейтинг: 0 / 0
13.05.2014, 19:23
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640336
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
 
[quot kealon(Ruslan)]Програмёрпропущено...


Не работает ваше решение, я его немного модифицировал без потери смысла
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
Program propusk;
var
    res: longword;
    mask: longword;
    counter: longword;
    num: longword;
    i:integer;
begin
    mask := $80000;
    res := $FFFFF;

    while mask>0 do
    begin

        counter := 0;
        for i:=1 to 1000001 do
        begin
            if i=11 then continue;
            num:=i;
            dec(num); {это костыль, все числа сдвигаем на единицу вниз, из-за того, что считаем не от нуля, а от единицы}
            if ((num and res and (not mask))=num) then inc(counter); {если при накладывании маски число не изменилось - оно в нашем интервале}
        end;
        if (counter<mask) then {если счётчик меньше возможного количества чисел в интервале,
значит нас интересует именно он и потому мы сбрасываем соответствующий бит в 0, иначе мы будем рассматривать интервал "над" данным}
        begin
            res := res and (not mask);
        end;
        mask := mask shr 1;
    end;

    writeln(res+1);
end.



выводит 16, хотя должно быть 11
кроме того оно выходит считает файл 32 раза


Сильно извиняюсь :) реально ошибся... в последний момент перед заливкой поправил и не проверил. В условии увеличения счётчика ошибся... вот код с правильным накладыванием маски:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
Program propusk;
var
    res: longword;
    mask: longword;
    counter: longword;
    num: longword;
    i:longword;
begin
    mask := $80000;
    res := $FFFFF;

    while mask>0 do
    begin

        counter := 0;
        for i:=1 to 1000001 do
        begin
            if i=11 then continue;
            num:=i;
            dec(num); {это костыль, все числа сдвигаем на единицу вниз, из-за того, что считаем не от нуля, а от единицы}
            if ((num xor (res and (not mask)))<mask) then inc(counter); {если при накладывании маски число не изменилось - оно в нашем интервале}
        end;
        if (counter<mask) then {если счётчик меньше возможного количества чисел в интервале,
значит нас интересует именно он и потому мы сбрасываем соответствующий бит в 0, иначе мы будем рассматривать интервал "над" данным}
        begin
            res := res and (not mask);
        end;
        mask := mask shr 1;
    end;

    writeln(res+1);
end.



файл читается 20 раз... Ровно столько раз, сколько бит в самом большом числе искомого интервала (в нашем случае это 1000001 < 2^20).
...
Рейтинг: 0 / 0
13.05.2014, 22:26
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640452
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Ребята, вы издеваетесь ?

Я уже единственное нормальное, и с большой долей вероятности самое быстрое решение привёл вышел.

такая постановка решается очень просто :), код примерно такой:
SS
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
//поиск единственного отсутствующего
	int res = 1 ^ *(a + 0);
	for (int i = 2; i < 1000001; i++)
	{
		res = res^(*(a + i - 1)^i);
	}
	res = res ^ 1000001;


если индексы не напутал, но смысл думаю понятен :)

Програмёркак уже говорил... автор предоставил избыточное решение (делается больше чем надо). Очевидно, что пропуск находится в одной из первых 1000001 позиций. А значит и 1000 000 000 проверять не надо... достаточно начинать делить интервалы начиная с миллиона (точнее начиная с 0xFFFFF = 1048576, тогда все операции легко сводятся к битовым, а потому идёт экономия времени и упрощение логики).

автор предоставил порнографическую постановку задачи, и аналогичное решение задачи.

Удивлён что mayton участвовал в этой вашей дискуссии. Хотя, судя по тому как он тонко намекнул остальным на XOR..
...
Рейтинг: 0 / 0
14.05.2014, 01:50
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640457
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
пИз числового интервала от единицы до миллиарда выбираются случайным образом без повторений миллион чисел и записываются в файл. Необходимо за приемлемое время выяснить, какое наименьшее число отсутствует в файле. Использовать массивы или иные структуры данных, их заменяющие, запрещается.

ну очевидно что в полученном массиве будет 10^6 чисел, и зачем мне смотреть те индексы что даже не существуют ????

И поэтому вашу фразу

ПрограмёрОчевидно, что пропуск находится в одной из первых 1000001 позиций.
я понимаю как -очевидно что искомое число имеет значение в диапазоне 1 - 10^6+1.

Вот как я вижу эту задачу:
1. Дан массив array мощностью 10^6. Каждый элемент массива целое число в диапазоне от 1 до 10^9. Каждый элемент массива уникален. Найти минимальное пропущенное число в array. К этой задаче решение выше не подходит.

Вот, как мне кажется, вы видите эту задачу.
2. Дан массив array мощностью 10^6. Каждый элемент массива целое число в диапазоне от 1 до 10^6. Каждый элемент массива уникален. Найти минимальное пропущенное число в array. К этой задаче решение выше.


Допустим, мы рассматриваем задачу 1.
Програмёркак уже говорил... автор предоставил избыточное решение (делается больше чем надо). Очевидно, что пропуск находится в одной из первых 1000001 позиций

Возможно, вы хотите сказать что значение искомого числа в диапазоне 1 - 10^6+1, но и это неверно.
Допустим все array[i]=0.5^10^9+i. Тогда минимальное пропущенное 0.5^10^9-1

Значит, вы возможно рассматриваете такую постановку:
3. Дан массив array мощностью 10^6. Каждый элемент массива целое число в диапазоне от 1 до 10^9. Каждый элемент массива уникален. Найти минимальное не включенное в array число из диапазона 1 - 10^9.


И тогда, ДЕЙСТВИТЕЛЬНО, наше число находится в диапазоне 1 - 10^6+1.

Вы рассматриваете задачу 3 ?
...
Рейтинг: 0 / 0
14.05.2014, 03:00
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640482
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
SashaMercuryРебята, вы издеваетесь ?

Я уже единственное нормальное, и с большой долей вероятности самое быстрое решение привёл вышел.

такая постановка решается очень просто :), код примерно такой:
SS
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
//поиск единственного отсутствующего
	int res = 1 ^ *(a + 0);
	for (int i = 2; i < 1000001; i++)
	{
		res = res^(*(a + i - 1)^i);
	}
	res = res ^ 1000001;


если индексы не напутал, но смысл думаю понятен :)

Програмёркак уже говорил... автор предоставил избыточное решение (делается больше чем надо). Очевидно, что пропуск находится в одной из первых 1000001 позиций. А значит и 1000 000 000 проверять не надо... достаточно начинать делить интервалы начиная с миллиона (точнее начиная с 0xFFFFF = 1048576, тогда все операции легко сводятся к битовым, а потому идёт экономия времени и упрощение логики).

автор предоставил порнографическую постановку задачи, и аналогичное решение задачи.

Удивлён что mayton участвовал в этой вашей дискуссии. Хотя, судя по тому как он тонко намекнул остальным на XOR..

Да, просто я когба подбирал аналогичную задачу, забыл о более оптимальном поиске одного пропуска. Потому задачу лучше свести к 2 пропускам, и она станет аналогичной изначальной задаче, только без излишеств. То есть, есть 1000000 чисел в диапазоне 1000002. Найти меньшее из пропущеных чисел.
...
Рейтинг: 0 / 0
14.05.2014, 07:28
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640513
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Тогда мы имеем поиск неподвижной точки. Не стал разбираться как сделано у автора по ссылке в первой записи топа(ибо его объяснение мне мягко говоря не нравится), но судя по вашим комментариям у вас что-то аналогичное с алгоритмом ниже.
Код в первом приближении
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
	int a[1000000];

	int min = 1, max = 1000000, res;
	while (max > min)
	{
		int l = 0, r = 0;
		int middle = min + (max - min) / 2;
		for (int i = 0; i<1000000;i++)
		{
			if (*(a + i)>=min && *(a + i) <= middle)  //*a in [min;middle]
			{
				l++;
			}
			else if (*(a + i) > middle && *(a + i) <= max)  //*a in (middle;max]
			{
				r++;
			}
		}

		//Если все элементы уже есть, частный случай
		if (l==(middle-min+1) && r==(max-middle)) 
		{
			res = max + 1;
			break;
		}
		//(Все элементы слева есть )? меняем минимальное значение: меняем максимальное значение;
		(l == (middle - min + 1)) ? min = min + (max - min) / 2 + 1 : max = min + (max - min) / 2;

		//проверка на выход
		if (max == min)
		{
			res = min;
			break;
		}
	}
	printf("%i", res);
...
Рейтинг: 0 / 0
14.05.2014, 08:47
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640517
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Если не ошибаюсь, количество проходов log_2 (1 000 000). То есть не должно превышать 20, тоже встречал это число.

Так как это частный случай, то всё равно эту задачу можно решить за один проход. Только надо подумать как
...
Рейтинг: 0 / 0
14.05.2014, 08:53
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640544
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
SashaMercuryРебята, вы издеваетесь ?

Я уже единственное нормальное, и с большой долей вероятности самое быстрое решение привёл вышел.

такая постановка решается очень просто :), код примерно такой:
SS
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
//поиск единственного отсутствующего
	int res = 1 ^ *(a + 0);
	for (int i = 2; i < 1000001; i++)
	{
		res = res^(*(a + i - 1)^i);
	}
	res = res ^ 1000001;


если индексы не напутал, но смысл думаю понятен :)

Програмёркак уже говорил... автор предоставил избыточное решение (делается больше чем надо). Очевидно, что пропуск находится в одной из первых 1000001 позиций. А значит и 1000 000 000 проверять не надо... достаточно начинать делить интервалы начиная с миллиона (точнее начиная с 0xFFFFF = 1048576, тогда все операции легко сводятся к битовым, а потому идёт экономия времени и упрощение логики).

автор предоставил порнографическую постановку задачи, и аналогичное решение задачи.

Удивлён что mayton участвовал в этой вашей дискуссии. Хотя, судя по тому как он тонко намекнул остальным на XOR..
код на коленке можно приводить любой
рабочей проги, которую можно проверить нету
вот например, при чём здесь последняя i (...^i) ?
Код: plaintext
1.
res = res^(*(a + i - 1)^i);
...
Рейтинг: 0 / 0
14.05.2014, 09:24
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640553
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
SashaMercuryЕсли не ошибаюсь, количество проходов log_2 (1 000 000). То есть не должно превышать 20, тоже встречал это число.

Так как это частный случай, то всё равно эту задачу можно решить за один проход. Только надо подумать как
вот фактически вы сами и пришли к методу деления пополам

а вот за один проход вопрос открыт ...
...
Рейтинг: 0 / 0
14.05.2014, 09:35
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640582
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)код на коленке можно приводить любой
рабочей проги, которую можно проверить нету
вот например, при чём здесь последняя i (...^i) ?
Код: plaintext
1.
res = res^(*(a + i - 1)^i);


Код рабочий, только Саша его написал в своем любимом стиле нечитабельных указателей. Читай *(a + i - 1) как a[i - 1].
 
Вот чуть улучшенная модификация готовая для запуска
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
#include <stdio.h>
#define DATA_SIZE 10
int main(int argc, char** argv)
{
	int a[DATA_SIZE] = {1,9,3,10,5,7,6,8,2,11};
	int res = 0;
	for (int i = 1; i <= DATA_SIZE; i++)
	{
		res = res ^ a[i - 1] ^ i;
	}
	res = res ^ (DATA_SIZE + 1);
	printf("%d\n", res);
	return 0;
}


Так думаю понятней принцип работы. Только этот алгоритм к данной задаче отношения не имеет.

PS SashaMercury, не издевайся над указателями :) твоя запись действительно трудно читается.
...
Рейтинг: 0 / 0
14.05.2014, 10:00
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38640618
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)SashaMercuryЕсли не ошибаюсь, количество проходов log_2 (1 000 000). То есть не должно превышать 20, тоже встречал это число.

Так как это частный случай, то всё равно эту задачу можно решить за один проход. Только надо подумать как
вот фактически вы сами и пришли к методу деления пополам

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

По моему алгоритм двоичного поиска непрерывного интервала тут будет самый эффективный. Только реализации выше кривоваты, т.к. при min >= 2 можно сразу дать ответ 1.
...
Рейтинг: 0 / 0
14.05.2014, 10:24
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641046
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Значит для 1 и для 2 дырок достаточно одного прохода.
А для трёх?.... Только биткарта или сортировка.
...
Рейтинг: 0 / 0
14.05.2014, 14:39
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641076
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
maytonЗначит для 1 и для 2 дырок достаточно одного прохода.
А для трёх?.... Только биткарта или сортировка.

Тут не понял, а по какому алгоритму в один проход определяется меньшая из двух дырок?
...
Рейтинг: 0 / 0
14.05.2014, 14:49
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641084
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЗначит для 1 и для 2 дырок достаточно одного прохода.
А для трёх?.... Только биткарта или сортировка.
Про одну понятно, а две как? Вроде выше про две не было предложений

Биткарта - массив, сортировка по большому счету тоже использование файла как "иные структуры данных, заменяющие массив".
...
Рейтинг: 0 / 0
14.05.2014, 14:52
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641542
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima TmaytonЗначит для 1 и для 2 дырок достаточно одного прохода.
А для трёх?.... Только биткарта или сортировка.
Про одну понятно, а две как? Вроде выше про две не было предложений

Вот такая идейка есть на два выброса из интервала 1..N, a и b
найти
Код: pascal
1.
2.
   a+b
   a^2+b^2   или a*b


сумма 1..N = N*(N+1)/2
сумма 1^2..N^2 = N*(N+1)(2N+1)/6 64-битного целого должно хватить
произведение можно найти на основании ln(a*b)=ln(a)+ln(b)

можно даже найти и 3 выброса: a,b,c
найти
Код: pascal
1.
2.
3.
 a+b+c
  a^2+b^2+c^2
  a*b*c


система довольно легко преобразуется к кубическому уравнению корни которого и будут a,b,c

можно и дальше, но будет попахивать мазохизмом :-)
...
Рейтинг: 0 / 0
14.05.2014, 21:41
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641666
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
вчера придумал аналогичную систему
a + b = const
a XOR b = const
Правда не смог доказать что у неё единственное решение.

Но это не очень интересно,2,3,4 это частный случай
...
Рейтинг: 0 / 0
15.05.2014, 02:11
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641688
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
SashaMercuryвчера придумал аналогичную систему
a + b = const
a XOR b = const
Правда не смог доказать что у неё единственное решение.

Но это не очень интересно,2,3,4 это частный случай
Код: pascal
1.
2.
a   +   b = A1
a XOR b = A2



Код: pascal
1.
2.
a= b XOR A2
b XOR A2 + b =A1



и у него по идее должно быть два гарантированных решения
...
Рейтинг: 0 / 0
15.05.2014, 06:09
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641695
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)
Код: pascal
1.
2.
a   +   b = A1
a XOR b = A2


и у него по идее должно быть два гарантированных решения
Порешай A1 = 1023 и A2 = 1023
 
Тут ответы :)
ab23100024999259982699727996289952999430993319923299133990349893598836987379863898539984409834198242981439804497945978469774797648975499745097351972529715397054969559685696757966589655996460963619626296163960649596595866957679566895569954709537195272951739507494975948769477794678945799448094381942829418394084939859388693787936889358993490933919329293193930949299592896927979269892599924100923101922102921103920104919105918106917107916108915109914110913111912112911113910114909115908116907117906118905119904120903121902122901123900124899125898126897127896128895129894130893131892132891133890134889135888136887137886138885139884140883141882142881143880144879145878146877147876148875149874150873151872152871153870154869155868156867157866158865159864160863161862162861163860164859165858166857167856168855169854170853171852172851173850174849175848176847177846178845179844180843181842182841183840184839185838186837187836188835189834190833191832192831193830194829195828196827197826198825199824200823201822202821203820204819205818206817207816208815209814210813211812212811213810214809215808216807217806218805219804220803221802222801223800224799225798226797227796228795229794230793231792232791233790234789235788236787237786238785239784240783241782242781243780244779245778246777247776248775249774250773251772252771253770254769255768256767257766258765259764260763261762262761263760264759265758266757267756268755269754270753271752272751273750274749275748276747277746278745279744280743281742282741283740284739285738286737287736288735289734290733291732292731293730294729295728296727297726298725299724300723301722302721303720304719305718306717307716308715309714310713311712312711313710314709315708316707317706318705319704320703321702322701323700324699325698326697327696328695329694330693331692332691333690334689335688336687337686338685339684340683341682342681343680344679345678346677347676348675349674350673351672352671353670354669355668356667357666358665359664360663361662362661363660364659365658366657367656368655369654370653371652372651373650374649375648376647377646378645379644380643381642382641383640384639385638386637387636388635389634390633391632392631393630394629395628396627397626398625399624400623401622402621403620404619405618406617407616408615409614410613411612412611413610414609415608416607417606418605419604420603421602422601423600424599425598426597427596428595429594430593431592432591433590434589435588436587437586438585439584440583441582442581443580444579445578446577447576448575449574450573451572452571453570454569455568456567457566458565459564460563461562462561463560464559465558466557467556468555469554470553471552472551473550474549475548476547477546478545479544480543481542482541483540484539485538486537487536488535489534490533491532492531493530494529495528496527497526498525499524500523501522502521503520504519505518506517507516508515509514510513511512
...
Рейтинг: 0 / 0
15.05.2014, 06:53
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641698
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
вот про это я и говорил. Но так вроде-бы будет с любой степенью двойки без единицы, и не только ) Сейчас проверю
Дмитрий, вот наверняка через цикл прогнали ? ;)
...
Рейтинг: 0 / 0
15.05.2014, 07:07
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641702
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryДмитрий, вот наверняка через цикл прогнали ? ;)
Конечно. Все варианты a и b до 1000. На бумажке долго доказывать :)

 
Вот код на фоксе поиска количества пар (a,b) для конкретного значения A1,A2
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
create Cursor test (a i, b i, A1 i, A2 i)

for i = 1 to 1000
	for j = i to 1000
		insert into test (a, b, A1, A2) values (i, j, bitxor(i,j), i + j)
	endfor
endfor

select A1, A2, count(*) as nCnt from test group by A1, A2 order by nCnt desc


 
Результат
A1A2Количество пар (a b)10231023489511511255767767255895895255959959255991991255100710072491015101524810191019245102110212451022102224510191027244102110252441022102424410151031241100710392405111535233767127923389511512339591087233991105523325576712825512791283836391283831407128447575128447147112847954312847915031284955271285035191285075151285095131285105121286398951286391151128703831128703121512873579912873512471287517831287597751287637711287657691287667681288319591288311087128863927128863111912887991112888790312889189912889389712889489612892799112892710551289439751289519671289559631289579611289589601289751007128983999128987995128989993128990992128255255127383383127447447127479479127495495127503503127507507127509509127510510127639639127703703127735735127751751127759759127763763127765765127766766127831831127863863127879879127887887127891891127893893127894894127927927127943943127951951127955955127957957127958958127975975127983983127987987127989989127990990127999999127.........
...
Рейтинг: 0 / 0
15.05.2014, 07:18
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641712
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
значит XOR не вариант, надо юзать другие агрегаты :-)
...
Рейтинг: 0 / 0
15.05.2014, 07:47
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641714
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)значит XOR не вариант, надо юзать другие агрегаты :-)
Умножение (a*b) уникально по определению, но большие цифры будут. Главное не масштабируется до N пропусков
...
Рейтинг: 0 / 0
15.05.2014, 07:57
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641717
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima_TГлавное не масштабируется до N пропусков
вот-вот
...
Рейтинг: 0 / 0
15.05.2014, 08:02
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641745
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima Tkealon(Ruslan)значит XOR не вариант, надо юзать другие агрегаты :-)
Умножение (a*b) уникально по определению, но большие цифры будут. Главное не масштабируется до N пропусков

не надо умножать все цифры, это невозможно
нужно суммировать логарифмы, точности double хватит для разделения Ln(N-1) и Ln(N)
Сумма (ln(1)..ln(N)) - ln (каждого значения)
в итоге получится ln(a*b)

если вы найдёте решение для всех случаев то там без массива уже не обойтись
...
Рейтинг: 0 / 0
15.05.2014, 08:56
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38641765
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Можно еще взять матлибу для работы с большими числами и использовать систему счисления с основанием миллион (миллионричная система счисления) дальше писать в каждый разряд - формально это не массив, а одно очень большое число :)
...
Рейтинг: 0 / 0
15.05.2014, 09:22
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642033
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima TМожно еще взять матлибу для работы с большими числами и использовать систему счисления с основанием миллион (миллионричная система счисления) дальше писать в каждый разряд - формально это не массив, а одно очень большое число :)
это же олимпиадная задачка
вы знаете реальную задачу где нужно искать пропуски :-)?

массив имелся виду для хранения агрегатов A1,A2,A3 ...

а вот для развития ума и расширения кругозора олимпиадные задачки самое то
их решение позволяет нестандартно смотреть на вещи, которые решаются эн-ным количеством трудодней
постоянно лепить лапшу из сортировок, поиска, форматирования текста и прочей пакости - скучно да и деградируешь быстро
...
Рейтинг: 0 / 0
15.05.2014, 12:03
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642055
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)вы знаете реальную задачу где нужно искать пропуски :-)?
Знаю. Генерация ID при интенсивной вставке/удалении в таблицу. Ключ обычно int делают.
...
Рейтинг: 0 / 0
15.05.2014, 12:16
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642067
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima Tkealon(Ruslan)значит XOR не вариант, надо юзать другие агрегаты :-)
Умножение (a*b) уникально по определению, но большие цифры будут. Главное не масштабируется до N пропусков
Я думал об аналогии с кодами Хэмминга. Только Хэмминг гарантирует исправление нужного количества бит.
А у нас речь идёт о поиске 32-битного (или меньше) значения. Которое выпало из выборки. Или для общего
случая - добавлено некорректное (шумовое) значение числа.
...
Рейтинг: 0 / 0
15.05.2014, 12:22
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642129
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЯ думал об аналогии с кодами Хэмминга. Только Хэмминг гарантирует исправление нужного количества бит.
Хэмминг для того и нужен чтобы добавить избыточную инфу для восстановления исходного значения.
maytonА у нас речь идёт о поиске 32-битного (или меньше) значения. Которое выпало из выборки. Или для общего
случая - добавлено некорректное (шумовое) значение числа.
Я так думаю о решении в один проход: промежуточную инфу надо где-то хранить, минимально - битовая карта, т.е. 1 млн. бит или 12500 байт. Возможно есть более компактное решение, но не намного. В обычных языках нет типов данных размером 10-12Кб (строки не учитываем), отсюда вывод - за один проход не решается.
...
Рейтинг: 0 / 0
15.05.2014, 12:54
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642131
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima Tkealon(Ruslan)вы знаете реальную задачу где нужно искать пропуски :-)?
Знаю. Генерация ID при интенсивной вставке/удалении в таблицу. Ключ обычно int делают.

ну наверное сложность O(N) не самый лучший вариант в данном случае
...
Рейтинг: 0 / 0
15.05.2014, 12:55
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642172
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonЯ думал об аналогии с кодами Хэмминга. Только Хэмминг гарантирует исправление нужного количества бит.
Хэмминг для того и нужен чтобы добавить избыточную инфу для восстановления исходного значения.

Хэмминг работает в условиях неопределённного (шумового) потока битов. А у нас - детерминизм.
В некотором простом случае мы ищем функцию вида:

F(n) = Hamming(Sequence(0,n))

Или

F(n) = Hamming(RandomShuffle(Sequence(0,n)))

и используя свойство функции указывать на номера инвертированных битиков - восстанавливаем дырку.
Но в данном ТЗ нас интересует не восстановление а порядковый номер int в этой последовательности
который также вычисляем от номера испорченного битика.
...
Рейтинг: 0 / 0
15.05.2014, 13:24
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642181
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonХэмминг работает в условиях неопределённного (шумового) потока битов. А у нас - детерминизм.
...
Хэмминг работает с блоками конкретной длинны.

Хэмминг требует подготовки данных перед отправкой (добавление служебной инфы для контроля и восстановления), а мы имеем поток рандомных значений без какой-либо доп.инфы.

ИМХУ Хэмминга тут никак не задействовать.
...
Рейтинг: 0 / 0
15.05.2014, 13:32
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642291
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
С учетом большого числа дырок, лично мне кажется оптимальный алгоритм - сначала поиск интервала с дыркой от единицы вверх, затем поиск непрерывного вниз двоичным поиском.
т.е. берем 1 - сканируем весь поток, затем 2,4,8 и т.д.
как получили дырку - продолжаем между предыдущим и текущим, т.е. дальше чистый двоичный поиск.
вероятность что нет первого составляет 10^3 к 1, нет второго 10^6 к 1 и т.д. (если теорию вероятностей правильно помню), т.е. скорее всего за один проход все найдется. В худшем случае 40 сканов для непрерывной последовательности в миллион. Т.е. тут сложность O(log2(n) + log2(n)) но по сравнению с чистым двоичным поиском высока вероятность решить в один проход. Двоичным от миллиона поиск значения 1 потребует 20 проходов.

Также получается универсально, т.к. тут нет ограничения сверху, т.е. без разницы сколько значений хоть миллион, хоть олимпиард :)
...
Рейтинг: 0 / 0
15.05.2014, 14:41
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642713
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima TС учетом большого числа дырок, лично мне кажется оптимальный алгоритм - сначала поиск интервала с дыркой от единицы вверх, затем поиск непрерывного вниз двоичным поиском.
т.е. берем 1 - сканируем весь поток, затем 2,4,8 и т.д.
как получили дырку - продолжаем между предыдущим и текущим, т.е. дальше чистый двоичный поиск.
вероятность что нет первого составляет 10^3 к 1, нет второго 10^6 к 1 и т.д. (если теорию вероятностей правильно помню), т.е. скорее всего за один проход все найдется. В худшем случае 40 сканов для непрерывной последовательности в миллион. Т.е. тут сложность O(log2(n) + log2(n)) но по сравнению с чистым двоичным поиском высока вероятность решить в один проход. Двоичным от миллиона поиск значения 1 потребует 20 проходов.

Также получается универсально, т.к. тут нет ограничения сверху, т.е. без разницы сколько значений хоть миллион, хоть олимпиард :)
а что мешает объединить два этих метода ? пусть будет бинарный поиск с нижним расширением :-)
...
Рейтинг: 0 / 0
15.05.2014, 18:54
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642717
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)а что мешает объединить два этих метода ? пусть будет бинарный поиск с нижним расширением :-)
распиши подробнее
...
Рейтинг: 0 / 0
15.05.2014, 18:59
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642718
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,
ну в бинарном поиске ты всё равно весь файл читаешь
что мешает вести
L,R бинарного поиска
и попутно считать число значений меньше L+степени двойки

чтение из файла ведь всё равно затратнее
...
Рейтинг: 0 / 0
15.05.2014, 19:03
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642736
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
kealon(Ruslan)Dima T,
ну в бинарном поиске ты всё равно весь файл читаешь
что мешает вести
L,R бинарного поиска
и попутно считать число значений меньше L+степени двойки

чтение из файла ведь всё равно затратнее
можно параллельно считать обоими способами, потом переходить к двоичному поиску, только польза будет при большой искомой непрерывной последовательности 1...N, а вероятность изначальной генерации такой последовательности 1 из 10^(N*3), т.е. практически невозможно, поэтому можно не усложнять.
...
Рейтинг: 0 / 0
15.05.2014, 19:38
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38642791
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Dima T,

задача олимпиадная, проверяют такие вещи самыми неудобными наборами
...
Рейтинг: 0 / 0
15.05.2014, 21:21
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38643558
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Задумался как сделать Shuffle последовательности без временных массивов.
По сути речь идёт об ограниченном ГПСЧ "без повторений" только для решения
данной задачи.

Для последовательности кратной 2^N вроде-бы всё просто. А вот для произвольного size = 1 000 000 000
пока не знаю как такой Shuffle сделать.
...
Рейтинг: 0 / 0
16.05.2014, 15:03
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38643625
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДля последовательности кратной 2^N вроде-бы всё просто. А вот для произвольного size = 1 000 000 000

тогда делаешь последовательность 2^30 и все что больше 1 000 000 000 пропускаешь

Для 2^N ты как хотел сделать просто?
...
Рейтинг: 0 / 0
16.05.2014, 15:36
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38643650
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima T, перестановкой битов в целом числе. Я до этого так делал псевдо-ГПСЧ
с уникальностью.
...
Рейтинг: 0 / 0
16.05.2014, 15:54
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38643656
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Для миллиарда думаю можно взять 30 битиков и использовать тот-же самый алгоритм
но проверять что результат попадает в диапазаон [0..999 999 999]
...
Рейтинг: 0 / 0
16.05.2014, 15:57
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38644667
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Не получился у меня ГПСЧ. Вобщем сходу энтропия плохая. Глазом видно что все чётные - меньше.

А ну его в болото.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
1073741824
536870912
1610612736
268435456
1342177280
805306368
1879048192
134217728
1207959552
671088640
1744830464
402653184
1476395008
939524096
2013265920
67108864
1140850688
603979776
1677721600
335544320
1409286144
872415232
1946157056
201326592
1275068416
738197504

Вобщем лучшее решение у kealon(Ruslan).

Фух ... надоёло всё.
...
Рейтинг: 0 / 0
18.05.2014, 21:59
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38644758
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНе получился у меня ГПСЧ.
Ну и отлично, а то я весь мозг сломал как можно последовательность из неповторяющихся чисел сгенерить :)
...
Рейтинг: 0 / 0
19.05.2014, 06:25
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38644952
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Можно легко. Только я себе ограничение поставил. Не использовать массивы и сортировки.
Надо-б еще сдвиговый регистр с хорём попробовать но уже лень и у него тоже энтропия плохая.
...
Рейтинг: 0 / 0
19.05.2014, 11:23
| Ответить | Цитировать | Написать  
Выборка из миллиарда
    #38645095
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
maytonМожно легко. Только я себе ограничение поставил. Не использовать массивы и сортировки.
Надо-б еще сдвиговый регистр с хорём попробовать но уже лень и у него тоже энтропия плохая.

А мне кажется, как не крути, псевдослучайная генерация без повторов уже не является ни случайной, ни даже псевдослучайной.

Всё очень просто.... в таком алгоритме появляется чёткая закономерность. И скажем например, сгенерировав 999'999 значений, я точно буду знать следующее генерируемое значение (хотя конечно всего одно значение можно и не брать в счёт). При этом мы не можем взять какой либо генератор энтропии с хорошими параметрами, так как тогда мы автоматически исключаем пункт "без повторений" пока просто не начнём явно определять (с помощью массива), что это значение уже показывали и надо выбрать случайное среди оставшихся.

Потому без массивов, думаю, задача не решаема.
...
Рейтинг: 0 / 0
19.05.2014, 13:27
| Ответить | Цитировать | Написать  
88 сообщений из 88, показаны все 4 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Выборка из миллиарда
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=16&tid=1341363]:
 0ms
get settings:
 7ms
get forum list:
 13ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 157ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 74ms
get tp. blocked users:
 1ms
others: 209ms
total:  474ms
созд. / загр.: 474ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]