ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Выборка из миллиарда
25 сообщений из 88, страница 3 из 4
  3  все
Выборка из миллиарда
    #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
| Ответить | Цитировать | Написать  
25 сообщений из 88, страница 3 из 4
  3  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Выборка из миллиарда
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=38642055&tid=1341363]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 411ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 64ms
get tp. blocked users:
 2ms
others: 237ms
total:  761ms
созд. / загр.: 761ms
x
x
Закрыть


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