Информативный заголовок: задачка на оптимизацию
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Информативный заголовок: задачка на оптимизацию - 2009-03-01 23:42:40.133333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
есть несортированный массив из 1000000000 элементов (вещественные числа), записанный на read-only диск, задача - определить значение элемента, который стоял бы на n-ном месте, если бы массив был отсортированным по возрастанию. разрешено использование не более 640KiB RAM, задача должна решаться за обозримое время на машине ~386 (иными словами - выполнять сортировку нельзя, непозволительная роскошь)
господа хацкеры, вам слово
задача боянистая, но хорошая. ограничений на используемый язык программирования нет. решившему ++, что уж там :)
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 00:07:48.940000
|
|
|
unconnected2
Сообщений: 332
Оценки: 0
Присоединился: 2009-01-16 17:56:12.400000
|
Denaturat претворяет свой план по порке лжеучителей в жизнь:D
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 00:11:01.490000
|
|
|
Mkey
Сообщений: 3426
Оценки: 0
Присоединился: 2006-03-08 14:32:13
|
выскажу первое что в голову пришло… кодить не бу…. каму ахота раомнет мозги…
берем наше число (X) и присваеваем ему "вес" (M)
далее попорядку дергаем числа из массива (Y)
иф X>Y вен M++ елсе M–
по окончании от 1000000000 отнимаем вес (ну там в принципе могут быть казусы с одинаковыми числами и када мы свой вес мерим… исключить энто не сложно)….
зы. Denaturat - брр, лучше б тя спирт звали….
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 00:17:42.186666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Mkey
берем наше число (X) и присваеваем ему "вес" (M)
далее попорядку дергаем числа из массива (Y)
иф X>Y вен M++ елсе M–
по окончании от 1000000000 отнимаем вес (ну там в принципе могут быть казусы с одинаковыми числами и када мы свой вес мерим… исключить энто не сложно)….
ты решаешь обратную задачу - "на каком месте в отсортированном массиве находилось бы число со значением X". она неинтересна. внимательней читай условие
quote:
ORIGINAL: Mkey
зы. Denaturat - брр, лучше б тя спирт звали….
не для сопливых ;)
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 00:21:55.096666
|
|
|
Mkey
Сообщений: 3426
Оценки: 0
Присоединился: 2006-03-08 14:32:13
|
quote:
ORIGINAL: Denaturat
quote:
ORIGINAL: Mkey
берем наше число (X) и присваеваем ему "вес" (M)
далее попорядку дергаем числа из массива (Y)
иф X>Y вен M++ елсе M–
по окончании от 1000000000 отнимаем вес (ну там в принципе могут быть казусы с одинаковыми числами и када мы свой вес мерим… исключить энто не сложно)….
ты решаешь обратную задачу - "на каком месте в отсортированном массиве находилось бы число со значением X". она неинтересна. внимательней читай условие
quote:
ORIGINAL: Mkey
зы. Denaturat - брр, лучше б тя спирт звали….
не для сопливых ;)
пардон… чича покумекаем…
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 02:22:49.873333
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Мне вот интересно, как можно выполнить сортировку, если диск read-only :) ? Хотелось бы конкретики в задаче, касательно специфики считывания данных, т.к. на x86 такий массив ну никак не влезет в виртуальное адресное пространство.
—–add
P.S. дочитал, что всего 640 кбайт, как в старые добрые времена…. их должно хватить всем :D
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 02:29:38.130000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
В лоб:
найти максимальное fMax;
1000000000 - n раз искать максимальное, меньшее fMax, и fMax присваивать это значение
имхо быстрее отсортировать :D. будем думать на трезвую голову.
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 02:33:25.923333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: _SaZ_
Мне вот интересно, как можно выполнить сортировку, если диск read-only :)
а её не надо выполнять. более того, при поставленных ограничениях её выполнить невозможно
quote:
ORIGINAL: _SaZ_
Хотелось бы конкретики в задаче, касательно специфики считывания данных, т.к. на x86 такий массив ну никак не влезет в виртуальное адресное пространство.
там где-то говорится, что его обязательно надо весь считать в память?
quote:
ORIGINAL: _SaZ_
P.S. дочитал, что всего 640 кбайт, как в старые добрые времена…. их должно хватить всем :D
задача вполне жизненная, кстати - даже если памяти на железе есть больше, остальная может уже быть занята под другие цели
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 02:36:16.433333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: _SaZ_
В лоб:
найти максимальное fMax;
1000000000 - n раз искать максимальное, меньшее fMax, и fMax присваивать это значение
асимптотику сам посчитаешь или подсказать? есть мнение что Солнце потухнет раньше, чем ты получишь ответ
quote:
ORIGINAL: _SaZ_
имхо быстрее отсортировать :D. будем думать на трезвую голову.
думай-думай. решение у задачи есть, оно известно и весьма элегантно
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 02:39:45.613333
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
Как обращаться к элементам скажи плз, чтобы легче думалось?… Например так? -
double GetValue( const unsigned long hiPos, const unsigned long lowPos );
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 03:03:38.483333
|
|
|
Mkey
Сообщений: 3426
Оценки: 0
Присоединился: 2006-03-08 14:32:13
|
отподает сортировка… точнее полная сортировка отподает.. её скорее динамически нуна выполнять… или хВормулу Зашибись-Лейбница какогонить вставлять…..
требую подсказки… точнее сужения вариантов поиска…
хВормулы Зашибись-Лейбница тама нужны?
или трюки там с мантиссами.. (блин чую закавыка именно в вещественных числах и мат хВормулой с ними)
или достаточно какихнить неочевидных трюков со сдвигами, хорами и т.п.?
и перед тем как провалиться в алкогольную кому….. вариант но пока без конкретики…
взять и поделить? (с)ШарикоФФ… слева, направА, сверху, вниз (с)Менты…
разбить массив на NN диапазонов, найти там примерное число в данном положеннии/NN а так же мин и макс из каждого диапазона… индексы искомых чисел складываем в массивчик опер памяти MOP[NN,3]
далее средне статистическое…..
(*чешет репу*) хоть пальцем в жо… ну хоть бум знать "приметы" разыскиваемого…
———————————-
quote:
Как обращаться к элементам скажи плз, чтобы легче думалось?
да по их индексам… они и так уже отсортированны….. 3b 9a ca 00 - 4х байт (слов двойных слов?…уже туплю) unsigned long int хватит с лихвой? а если long int взять то положительную часть на индексы, а отрицательную пока в запас (1пишем 2 в уме)
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 03:06:26.030000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: _SaZ_
Как обращаться к элементам скажи плз, чтобы легче думалось?… Например так? -
double GetValue( const unsigned long hiPos, const unsigned long lowPos );
несущественно. тестировать алгоритм можно на меньших наборах данных. в контексте важно лишь то, что операция получения элемента по индексу (неважно, насколько сложному) требует константного ненулевого времени
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 03:13:16.250000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Mkey
хВормулы Зашибись-Лейбница тама нужны?
нет. задача не требует знаний высшей математики
quote:
ORIGINAL: Mkey
разбить массив на NN диапазонов, найти там примерное число в данном положеннии/NN а так же мин и макс из каждого диапазона… индексы искомых чисел складываем в массивчик опер памяти MOP[NN,3]
ты про пик Баллмера слышал когда-нибудь?
http://www.xkcd.ru/323/
в том плане что направление мысли верное. однако направлениями сыт не будешь
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 03:54:28.986666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Ну если не долго думая, то можно попробовать так: пишем функцию поиска позиции данного числа (позицию числа в массиве можно узнать за один проход). Затем берём два случайных числа и вычисляем их позиции в отсортированном массиве. Допустим, что позиция одного из чисел ниже искомой позиции n, а другого - больше. Если это не так, повторям пока они не станут таковыми (в это время уже можно понемногу сужать границы, в качестве граничных используя те элементы, позиции которых ближе к искомой). Затем из интервала между двумя граничными элементами выбираем наугад ещё один элемент. Можно не реальный, а просто какое-то число, например, равноудалённое от обоих границ. Дальше в таком же духе бинарным поиском, пока границы не станут достаточно малы и можно будет грубо искать нужно число.
Если предположить, что числа в массиве равномерно распределены на интервале от минимального до максимального элемента, то можно очень хорошо сужать границы, деля интервал на m частей, и выбирая номер части пропорционально положению искомой позиции между двумя граничными позициями. Например, мы нашли два числа - 45 и 255 с позициями 100 и 200, соответственно. А нам нужно число с позицией номер 112. Делим интервал между 100 и 200 на 10 частей, тогда 112 находится во втором интервале. Точно так же делим интервал между 45 и 255 на 10 частей (получается по 21), и берём границы 2-ого интервала, то есть от 66 до 87. Если позиция числа 66 оказалась меньше искомой, а числа 87 - больше, то наше искомое число, соответственно, находится между 66 и 87. (Если мы не угадали с интервалом, то просто сдвигаем номер интервала в нужную сторону и повторяем проверку). Хотя даже с таким делением, это всё ещё будет очень грубо, так что должно быть решение без постоянного использования функции вычисления позиции числа.
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 04:01:37.173333
|
|
|
Mkey
Сообщений: 3426
Оценки: 0
Присоединился: 2006-03-08 14:32:13
|
ладно… немного по другому….
несколько незаконченных вариантов, мож штурмом мозговым Денатурата "выпьем"?
-вычисляем процент положительных чисел (кусками, никаких индексов пока не сохраняем (т.к. можем пережрать памяти)… пока тока анализ тупо Plus++) … далее чешу репу…
-разбить массив на NN диапазонов, но не по порядку например 1 2 3… 10 11 12, а например через определенный шаг… 1 100 2 200…. найти там примерное число в данном положеннии/NN а так же мин и макс из каждого диапазона… а вот далее каким то образом еще с соседними диапазонами их "протереть" … как пока не знаю …. чешу репу….
-вычислить среднее и от него плясать влево вправо? или в комбинации с %….
зы. алкоголе содержащая жидкость….шОб тебе весело было 4 часа а я спать не могу лечь…
——————
2kreol - да врят ли тут будет "академическое" решение…. тут заковыка, что выстроить "салдафонов" по росту низя на одном "платцу"…. стоп…. а по N шеренгам разбить? предварительно выстроив…. блин… крутиться в башке мысль.. поймать немогу…
——————
вумные головы - кумекайте…. наш массив он же возможно множество элементов дискретного типа….. может тут ключик?
——————
раз задачка чисто программерская и прикладная… может CRC у диапазонов вычислить и с ним чтонить творить?
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 04:40:25.656666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: kreol
Затем берём два случайных числа и вычисляем их позиции в отсортированном массиве. Допустим, что позиция одного из чисел ниже искомой позиции n, а другого - больше. Если это не так, повторям пока они не станут таковыми (в это время уже можно понемногу сужать границы, в качестве граничных используя те элементы, позиции которых ближе к искомой)
числа должны быть не просто случайными, а случайными в диапазоне [min, max] - ты этот шаг алгоритма пропустил
а теперь рассмотри случай, когда в нашем массиве 99.99% значений эквивалентны. насколько эффективной будет твоя эвристика?
quote:
ORIGINAL: kreol
Если предположить, что числа в массиве равномерно распределены на интервале от минимального до максимального элемента
никто этого не гарантирует, массив содержит произвольные значения
quote:
ORIGINAL: kreol
должно быть решение без постоянного использования функции вычисления позиции числа
без ограничений на память можно было бы получить O(n) в худшем случае. с ограничениями чуть сложнее
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 04:47:58.473333
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Mkey
мож штурмом мозговым Денатурата "выпьем"?
умная педивикия сообщает:
quote:
Денатуратом называют технический спирт, в который добавлены специальные вещества, исключающие его потребление в пищевых целях; применяется для освещения, варки пищи, лабораторных и промышленных надобностей.
так что не стоит
quote:
ORIGINAL: Mkey
2kreol - да врят ли тут будет "академическое" решение…. тут заковыка, что выстроить "салдафонов" по росту низя на одном "платцу"…
у любого технического решения есть академические корни. CPU в массе своей - всего лишь частичное воплощение в железе универсального вычислителя Тьюринга
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 10:35:11.570000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Denaturat
числа должны быть не просто случайными, а случайными в диапазоне [min, max] - ты этот шаг алгоритма пропустил
а теперь рассмотри случай, когда в нашем массиве 99.99% значений эквивалентны. насколько эффективной будет твоя эвристика?
На всякий алгоритм найдётся такая выборка, что он окажется жутко медленным. Та же быстрая сортировка на тех же 99.99% одинаковых чисел ведёт себя хуже обычной пузырьковой.
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 10:43:42.726666
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: kreol
На всякий алгоритм найдётся такая выборка, что он окажется жутко медленным. Та же быстрая сортировка на тех же 99.99% одинаковых чисел ведёт себя хуже обычной пузырьковой.
не тупи. quicksort скорее исключение, но даже для него худшая асимптотика (на почти отсортированном векторе) будет O(n^2). для своей эвристики посчитаешь худший случай? задача, вообще говоря, нетривиальная
ещё раз - для данной задачи (без ограничений) есть решение на O(n). с ограничениями - на O(n log n). оба раза речь идёт о худшем случае
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 10:44:14.516666
|
|
|
Mkey
Сообщений: 3426
Оценки: 0
Присоединился: 2006-03-08 14:32:13
|
а может с очередью какойто заморот? как уже сказал если long int взять то положительную часть на индексы, а отрицательную пока в запас только "запас" кодировать её будем по хитрому у нас величина массива 3B9ACA00h - то есть 0011 1011 1001 1010 1100 1010 0000 0000b вот те самые старшие 2 бита и будут "флагами" очереди…. напр. 00 - слева и справа числа меньше данного числа, 10 - слева число больше а справа меньше, 01 - NOT 10, 11 NOT 00. размерчик битового массивчика с "флагами" будет 1`000`000`000*2\8=250`000`000 бит …. а мозгов у нас 640`000*8=5`120`000 бит и тем более все их мы не заюзаем…. далее сама идея (кидайтесь тухлыми помидорами - мне пофиг)…. в процессе поблочного построения их паковать каким нибудь хитрым алгоритмом, обеспечивающим возможность макс сжатия и не ресурсоемкого добавления новых данных, а так же оперативной и не ресурсоемкой распаковки лишь нужной части…. теперь допустим, что мой бред выполним и мы имеем массив с "флагами" очереди который благополучно упакован… далее у мну затуп…. не удаляю пока это… может кто рац. зерно увидит….
Denaturat - гад, точнее Яд… мну с работы из за тя выгонят…
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 10:47:13.250000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Mkey
Denaturat - гад, точнее Яд… мну с работы из за тя выгонят…
вот будешь такие задачи в уме решать - тогда точно не выгонят
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 11:13:24.706666
|
|
|
Mkey
Сообщений: 3426
Оценки: 0
Присоединился: 2006-03-08 14:32:13
|
quote:
ORIGINAL: Denaturat
quote:
ORIGINAL: Mkey
Denaturat - гад, точнее Яд… мну с работы из за тя выгонят…
вот будешь такие задачи в уме решать - тогда точно не выгонят
вот немец… ну а намекнуть… в ту сторону вектор заточен или нет?
вот размышляю над имеющимися данными….
задача не требует знаний высшей математики
направление мысли верное (тоесть обрабатывать массив кусками так и так нуна)
а про или достаточно какихнить неочевидных трюков со сдвигами, хорами и т.п.? умолчал…. забыл… или не обратил внимания…. или ?
ну хоть вариант теплее-холоднее, я тут уже стока бредятины нагенерил…. везде туманная загадочность….
——————————–
стоп….
ты решаешь обратную задачу - "на каком месте в отсортированном массиве находилось бы число со значением X"
прогнали любое число узнали на каком месте, прикинули в какую сторону шагать, еще раз прогнали, но с явным отсевом чисел тех которые вше или ниже, потихоньку приблизились к искомому…
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 11:21:47.350000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Mkey
вот немец… ну а намекнуть… в ту сторону вектор заточен или нет?
а это достаточно просто определить и без моей помощи: рациональное зерно рано или поздно приводит к решению - достаточно какое-то время подождать
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 11:25:48.500000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Mkey
ну хоть вариант теплее-холоднее, я тут уже стока бредятины нагенерил…. везде туманная загадочность….
решения среди всей этой бредятины нет. здравая мысль - получить приближённое решение, не требующее большого количества ресурсов - и улучшать его. разбиение на части мысль очевидная - при таком ограничении на память иначе всё равно не получится, хоть как ты эти числа кодируй
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 13:56:30.866666
|
|
|
Mkey
Сообщений: 3426
Оценки: 0
Присоединился: 2006-03-08 14:32:13
|
сомнительны фразы:
задача вполне жизненная
оно известно и весьма элегантно
что операция получения элемента по индексу (неважно, насколько сложному) требует константного ненулевого времени
получить приближённое решение, не требующее большого количества ресурсов - и улучшать его
задача не требует знаний высшей математики
уу мозги кипят… фантазия буйствует…. просю отсечения моих лишних бредовых гипотез….
"записанный на read-only диск" - является обязательным условием? или нет? ну например "зашитый в ооОгромную ПЗУ" - в условии задачи в итоге принципов и сути не изменят? я к тому, что скрытые "резервы" в условии задачки имеются?
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 15:07:04.213333
|
|
|
unconnected2
Сообщений: 332
Оценки: 0
Присоединился: 2009-01-16 17:56:12.400000
|
quote:
сомнительны фразы:
задача вполне жизненная
оно известно и весьма элегантно
что операция получения элемента по индексу (неважно, насколько сложному) требует константного ненулевого времени
получить приближённое решение, не требующее большого количества ресурсов - и улучшать его
задача не требует знаний высшей математики
Про "жизненная" - это значит, что когда он всем расскажет решение, то обязательно приведёт пример или аналогию из жизни:D
Константное время - это значит, что при любом индексе оно всегда будет одинаковым? Интересно..
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 15:44:31.880000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: unconnected2
Про "жизненная" - это значит, что когда он всем расскажет решение, то обязательно приведёт пример или аналогию из жизни:D
данные на read-only сервере, вычисления на очень тонком клиенте - кастомной железке с крайне малым энергопотреблением. достаточно жизненно?
quote:
ORIGINAL: unconnected2
Константное время - это значит, что при любом индексе оно всегда будет одинаковым? Интересно..
это значит, что время доступа не зависит от индекса
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 15:49:28.990000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
quote:
ORIGINAL: Mkey
сомнительны фразы:
задача вполне жизненная
оно известно и весьма элегантно
что операция получения элемента по индексу (неважно, насколько сложному) требует константного ненулевого времени
получить приближённое решение, не требующее большого количества ресурсов - и улучшать его
задача не требует знаний высшей математики
чем же они сомнительные? никакого противоречия в них нет
quote:
ORIGINAL: Mkey
"записанный на read-only диск" - является обязательным условием? или нет? ну например "зашитый в ооОгромную ПЗУ" - в условии задачи в итоге принципов и сути не изменят? я к тому, что скрытые "резервы" в условии задачки имеются?
резервов нет. всё, что есть - это массив, данные из которого можно только считать, и 640 KiB памяти, в которой можно делать всё что угодно. откуда именно у нас исходные данные - несущественно; одинаково можно предполагать сетевую ФС, микросхему с r/o ФС, или r/o носитель. примеров из жизни для любого из вариантов могу накидать
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 16:45:47.876666
|
|
|
Mkey
Сообщений: 3426
Оценки: 0
Присоединился: 2006-03-08 14:32:13
|
quote:
чем же они сомнительные? никакого противоречия в них нет
да не… я "резервы" в сидироме искал (в качестве индексов там еще цилиндры, сектора зацепить)… теперь понятно что нужно ….. но пока туманно - как…
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 20:27:59.880000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
жиденько, господа хацкеры. в боевых условиях грош вам цена с такой скоростью решения
начинаю сомневаться в том, что оно вообще будет
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 21:10:28.956666
|
|
|
koro
Сообщений: 977
Оценки: 0
Присоединился: 2008-08-08 09:39:07.460000
|
я уже мозг сломал, единственное более менее адекватное что приходит в голову - сделать отдельные массивы и сравнивать между ними элементы, что бы найти кол-во одинаковых, затем прибавить к n кол-во одинаковых элементов. Но это конешно глупо и неправильно, во-первых нет гарантий что там есть все числа из диапазона, но тогда получается что надо проверять эти "пустые" места в массиве -> легче сделать сортировку…
может маленькую подсказку?:)
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 21:16:49.880000
|
|
|
unconnected2
Сообщений: 332
Оценки: 0
Присоединился: 2009-01-16 17:56:12.400000
|
Мне сразу вариант в голову пришёл, когда только задачу увидел, сделать второй массив размерностью 500000000, далее если N из первой половины диапазона (n<500000000), то начинаем проходить по первому массиву, находя сначала первый элемент, потом второй(по возрастанию) и записываем по возрастанию их во второй массив. Если же N из второй половины, то ищем по убыванию и с конца, и так же записываем во второй массив. Рано или поздно решение найдётся:D
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-02 23:01:11.460000
|
|
|
Mkey
Сообщений: 3426
Оценки: 0
Присоединился: 2006-03-08 14:32:13
|
quote:
может маленькую подсказку?:)
есть уже подсказка…..
quote:
получить приближённое решение, не требующее большого количества ресурсов - и улучшать его
тем более, что "задача должна решаться за обозримое время"
следовательно, роем способы поиска приближенных значений… я там предлогал - статистика… или тупо проценты… но "решение изящно"…."задача не тривиальна"… нетривиальна, значит не подходит под стандарт… или принцип фунЦиклирования другой…
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-03 01:06:58.886666
|
|
|
Xelle
Сообщений: 20
Оценки: 0
Присоединился: 2008-07-10 23:07:46.580000
|
array[i] - i-ый элемент массива
х - значение заданного элемента
n - искомый индекс
n := 0;
for i := 1 to 1000000000 do
if array[i] < x then
inc(n);
if (n= 1000000000) and (x > array[1000000000]) then
inc(n);
при n = 0 - х меньше всех элементов массива
при n = 1000000001 - х больше всех элементов массива
если элементов = х будет несколько - n = индекс первого элемента = х
если min < х < max но нету элемента = х то индекс искомого элемента был бы равен n+1 если бы он (искомый элемент) был
;)
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-03 01:26:38.486666
|
|
|
m0ney
Сообщений: 4
Оценки: 0
Присоединился: 2009-02-11 17:59:32.476666
|
боюсь предположить, но есть такая мысль: находим max & min в массиве. n-е число должно быть очень примерно min+(max-min)*(n-1)/(1000000000-2). повторяем этот шаг, считая максимальным уже найденное значение, минимальное прежнее. так некоторое число раз пока не найдется))
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-03 01:30:26.730000
|
|
|
_SaZ_
Сообщений: 4329
Оценки: 398
Присоединился: 2008-01-30 02:18:05.553333
|
видоизменённый бинарный поиск… а вот моё подобие мозга уже так сильно отучилось экономить память, что решение совсем не думается.
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-03 03:42:34.830000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: Denaturat
жиденько, господа хацкеры. в боевых условиях грош вам цена с такой скоростью решения
Во-первых, задача решается не круглые сутки, а когда есть время. У меня вот есть время ночью. И то мало.
Во-вторых, задача противоположна большинству подобных, где нужно искать элемент в массиве. А это куча ложных паттернов в голове, на которые постоянно съезжает мысль. Это нормальный процесс мышления.
Есть пара идей, но сейчас не могу сформулировать, утром, если успею, напишу.
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-03 09:47:32.723333
|
|
|
Mkey
Сообщений: 3426
Оценки: 0
Присоединился: 2006-03-08 14:32:13
|
такс… ещё одна бредятина…..
1 вычисляем мин и макс массива
2 вычисляем % от n
3 находим на основании мин, макс и %от n предположительное значение искомого
4 берем "ефрейторский запас" влево и право например на 1%
5 ищем все числа попадающие в этот запас… если их черезчур или нету сдвигаем влево(вправо) или расширяем до 2%
6 допустим мы нашли единственное число по вышеуказанному алгоритму….
7 далее определяем его действительное положение (в 3м посте указано как) - подошло? нет? (например его позиция ниже) сдвигаем диапазон поиска правее дуем на 5 если да задача решена
зы. п7 конечно требует там еще кучу уточнений но вроде должно баботать.
—————————————–
конечно если там 99.9% одинаковых чисел…. или еще какиенить подводые камни нуна буит проанализировать и просто модернизировать алгоритм принятия решения по какому пути идти… но вот вроде костяк…. или у мну уже мозги софсем завязались узлом?
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-03 11:26:14.633333
|
|
|
Xelle
Сообщений: 20
Оценки: 0
Присоединился: 2008-07-10 23:07:46.580000
|
max - переменная для поиска числа большего чем arr[n]
k - переменная для поиска инекса нужного значения в неотсортированном массиве
х - искомое значение n-го элемента
n - заданный индекс массива
arr - array [1..1000000000] of integer;
k:= 0;
max := Low;
for i := 1 to 1000000000 do
begin
if arr[i] > max then
max := arr[i]
else
inc(k);
if k = n then
х := arr[i];
end;
В итоге мы достанем х который = arr[i],
а в отсортированном по возрастанию массиве он и будет значение n-го элемента. ;)
з.ы. алгоритм в Post #: 34 это обратная задача, пардон ))
|
|
|
|
|
RE: Информативный заголовок: задачка на оптимизацию - 2009-03-03 13:03:03.510000
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
Не, ну тут дольше объяснить алгоритм чем придумать. Первое что приходит в голову – это пирамидальная сортировка, которая в принципе лучший выбор для ситуации когда надо не сортируя массива целиком выбрать первые n элементов. Напомню алгоритм. Разбиваем массив на пары чисел и из каждой пары выбираем минимальное. Выбранные элементы (второй слой пирамиды) опять разбиваем на пары, и из каждой выбираем минимальное. И повторяем это пока не останется один самый-самый минимальный (вершина пирамиды). Затем выкидываем элемент с вершины и ищем в нижних слоях следующий (я уж не буду это пояснять в деталях – здесь по-моему уже без обозначений не обойтись, а их можно найти в инете если самостоятельно не удаётся допетрить). Но идея пирамидальной сортировки неудачна. Потому как даже если мы в оперативке будем хранить не числа а лишь результаты каждого сравнения, то есть по одному биту на сравнение, нам всё равно не хватит 640Kb оперативки.
Но Mkey же выдал основную идею – надо разбить на диапазоны. Потом его понесло в какую-то эвристику, зачем непонятно. ЫыЫ. Организуем пирамидальную сортировку, только нижний слой будем разбивать не на пары элементов, а на тысячи, или десятки тысяч, или ещё побольше. Давайте разбивать на группы по M элементов. Тогда второй слой пирамиды займёт n1 = 10^9/M*sizeof(float) байт оперативки. Следующий слой n2 = n1/2. n3 = n2/2… И тп. То есть всего понадобится (2*10^9/M-1)*sizeof(float) байт оперативки. Понятно что можно подобрать такое M, чтобы оперативки хватило. Если мы возьмём M=10^9 то нам хватит одного float'а в памяти.
Развиваем мысль дальше – а может и ну его нафиг из формулы `2*', может лучше не строить поверх второго уровня полноценную пирамиду, зато M поменьше, чтобы поменьше по диску искать?
|
|
|
|
|
|
