Поиск в массиве

← →
selesasha (2012-03-15 14:26) [0]

Дано:
1) Неубывающий массив повторяющихся данных, длинной ~15000 возможно имеющий nil среди значений, и почти наверняка имеющий хвост из nil в конце
2) Массив находится на удаленном сервере, каждый запрос одного элемента это post через http с последующим парсингом ответа. Т.е. Чтобы сравнить 2 элемента массива нужно сделать 2 запроса.
3) Функция позволяющая для пары данных однозначно определить какой из аргументов больше, или их равенство, если ни одно из них не nil

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

Поделитесь пожалуйста своими соображениями. Код никакой не прошу, только идеи и Ваши умные мысли.

← →
MBo © (2012-03-15 14:47) [1]

Как соотносится "Неубывающий массив" и наличие nil - посередине, что ли, где попало?

← →
Cobalt © (2012-03-15 15:44) [2]

А если один из элементов - nil, что вернет функция?

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

← →
selesasha (2012-03-15 17:34) [3]

> Как соотносится "Неубывающий массив" и наличие nil - посередине,
> что ли, где попало?

Именно. Сами данные неубывающие, но некоторые элементы массива данных не содержат.

> А если один из элементов - nil, что вернет функция?

Вызовется эксепшн.

> А так, всё просто - методом последовательных приближений
> - узнаешь значение в середине массива, и дальше хватаешь
> элемент из середины остатка.

бинарный поиск тут не подходит - по крайней мере в лоб:
1) Какой поддиапазон выбирать если середина отрезка - nil?
2) Как находить границы окна, если середина отрезка попала в искомое значение?

← →
Jeer © (2012-03-15 17:36) [4]

Очередная идиотская задача.

← →
selesasha (2012-03-15 17:39) [5]

В чем идиотизм?

← →
selesasha (2012-03-15 17:47) [6]

Или если бы я написал конкретную задачу, то избавился бы от подобных комментариев?

← →
brother © (2012-03-15 17:50) [7]

> Вызовется эксепшн.

что за функция?

> я написал конкретную задачу, то избавился бы от подобных
> комментариев

а как ты думаешь?

← →
selesasha (2012-03-15 18:15) [8]

> что за функция?

Самописная функция сравнения двух переменных строкового типа.

> а как ты думаешь?

Думаю что формализованную задачу легче понять нежели реальную.

Но давайте попробуем:
Есть интернет магазин. По запросу он может выдавать информацию о выполненных заказах. Запрос есть номер этого заказа. Номера идут по порядку . В ответе сайта содержится много информации, плюс метка времени, которая есть зашифрованная по определенным законам дата выполнения заказа. Функция занимается раскодированием этих значений,переводом их в формат TDate и сравнением.
Что нужно:
Найти пул номеров всех выполненных заказов на определенную дату.

nil`ы возникают в случае если заказ задержался на этапе оплаты или комплектования. Соответственно номер заказу присвоен, но в выполненных его еще нет.

Магазин не мой, соответственно менять ничего не могу.

← →
Jeer © (2012-03-15 18:20) [9]

> Магазин не мой, соответственно менять ничего не могу.

С этого и надо начинать - корабль не мой, но порулить хочется.
Не зря задача названа идиотской.

← →
brother © (2012-03-15 18:23) [10]

> Самописная функция сравнения двух переменных строкового
> типа.

давай начнем с показа ее реализации...

← →
CRLF (2012-03-15 18:57) [11]

А что, не добавлять в массив нуловые значения -- не катит?

← →
selesasha (2012-03-15 19:00) [12]

Jeer

> С этого и надо начинать - корабль не мой, но порулить хочется.

Рулить хочется не мне, я всего лишь пишу программу.

> Не зря задача названа идиотской.

Я обращаюсь к Вам за помощью, значит давно сижу и думаю над оптимальным решением задачи. Вы второй раз называете то, над чем я работаю идиотизмом, совершенно не аргуметируя. Зачем?
Хотите меня обидеть - у Вас получилось еще в первый раз.
Если хотите донести до меня что программирование это не мое - так я еще учусь.

brother

> давай начнем с показа ее реализации...

Давайте не будем. Функция протестирована и работает.
Вопрос вообще не в этом.
Вопрос в том, как правильно организовать поиск в "неубывающем" массиве с "дырками", использовав наименьшее число обращений к массиву.

Раз реальная задача не прокатила, давайте абстрагируемся до вот такого уровня:
Есть массив целых одноразрядных чисел (а), такой что: а[n]<=a[n+1] при a[n]<>0 и a[n+1]<>0. Можно представить себе массив из нулей, заполненный на 3/4 случайными числами от 1 до 9, потом эти 3/4 отсортировали по возрастанию (получился неубывающий массив с хвостом из нулей), и заменили некоторые из чисел в этих 3/4 на нули.
Задача: найти границы вхождения числа 4, используя минимальное число обращений к массиву. Нули границы вхождения не ограничивают.

← →
selesasha (2012-03-15 19:01) [13]

> А что, не добавлять в массив нуловые значения -- не катит?

Нет, массив не мой, я его только читаю.

← →
CRLF (2012-03-15 19:19) [14]

Отфильтруй массив, чтоб нулов не было, и ищи... Пока не покажешь, какой именно у тебя массив, что-то конкретное предлагать не получится.

← →
CRLF (2012-03-15 19:25) [15]

> > Не зря задача названа идиотской.
> Вы второй раз называете то, над чем я работаю идиотизмом,
> совершенно не аргуметируя. Зачем? Хотите меня обидеть -
> у Вас получилось еще в первый раз.
Скажем так, задача в такой постановке -- неклассическая. Постарайся привести её к классическому виду и решать хорошо известными способами.

← →
selesasha (2012-03-15 19:26) [16]

CRLF
Читали мои посты выше?

> Отфильтруй массив, чтоб нулов не было, и ищи..

Запрос элемента массива идет через интернет, чтобы загрузить все элементы масива понабодится очень долгое время. Все это затевается чтобы время поиска сократить.

> Пока не покажешь, какой именно у тебя массив, что-то конкретное
> предлагать не получится.

Я его прекрасно описал в [12] после слов "давайте абстрагируемся до вот такого уровня:"

← →
selesasha (2012-03-15 19:27) [17]

> Скажем так, задача в такой постановке -- неклассическая.
> Постарайся привести её к классическому виду и решать хорошо
> известными способами.

Опять таки - описал в [12]

← →
CRLF (2012-03-15 19:29) [18]

ок, абстрагируйся...

← →
selesasha (2012-03-15 19:34) [19]

Да причем тут?
Выспрашивается алгоритм. Задачу привел к тому виду, в котором она должна быть понятна, без к.л. погружения в педметную область - привел ее к классическому виду.

← →
Jeer © (2012-03-15 19:52) [20]

> Рулить хочется не мне, я всего лишь пишу программу.

Так я и не в Ваш адрес сделал намек - очевидно же, что Вы нанятый "самодельщик".

И задача названа "идиотской" не потому, что ее начал решать адекватный ей по сути индивидуум.

Ок, используем определение из ответа одного из коллег - "не классическая" задача.

Выхода из этой ситуации, как минимум, два:
- сведение задачи к классической;
- теоретические измышлизмы в поиске оптимального решения в данном конкретном случае.

Первое - уже рекомендовали.
Второе требует усилий, как теоретических, так и практических.
А, на самом деле, исходя из Вашей постановки - задача решается методом Монте-Карло :)

И кому это надо, кроме Вас ?

← →
selesasha (2012-03-15 20:00) [21]

> очевидно же, что Вы нанятый "самодельщик".

Я студент, пытающийся угодить жене преподавателя, дабы посещять его лекции бесплатно.

> - сведение задачи к классической;

Что я собственно и сделал в посте номер 12. Или нет?

> И кому это надо, кроме Вас ?

Вы отвечаете по существу только на вопросы, решение которых нужно не только вопрошающему? нет. Так к чему эта сентенция?

← →
brother © (2012-03-15 20:07) [22]

> Давайте не будем. Функция протестирована и работает.

Удачи!

← →
brother © (2012-03-15 20:10) [23]

> Я студент, пытающийся угодить жене преподавателя,

способы подсказать (к программированию не имеют отношения)?

← →
Jeer © (2012-03-15 20:10) [24]

> Я студент, пытающийся угодить жене преподавателя, дабы посещять
> его лекции бесплатно.

1. Похвально, конечно.. но жен преподов по другому ублажают.
Впрочем, это не моя рекомендация.

2. Сведение задачи к классической, означает использование апробированных, теоретически, практически и статистически эффективных алгоритмов.

3. Неординарные ( не классические ) задачи, в основе которых лежит алогичный не системный поход, будут интересны только "я студент.."

P.S.
Ничего не имею против Вас, просто поясняю ситуацию.

← →
selesasha (2012-03-15 20:19) [25]

Jeer
Спасибо за прояснение, видимо программирование действительно не моё и мне пора отчисляться.

Если можно, просто чтобы еще раз ощутить свою ничтожность в этом мире, просьба: Я задачу описал довольно полно, если не затруднит смогли бы Вы хотябы примерно показать как она будет выглядеть сведенная к классической?

← →
brother © (2012-03-15 20:22) [26]

> Я задачу описал довольно полно,

Это твое мнение, но всеж...

> показать как она будет выглядеть сведенная к классической

В твоем случае классики нет, хотя, начни с цветов и вина)

← →
selesasha (2012-03-15 20:31) [27]

> Это твое мнение, но всеж...

Если Вы можете помочь в приведении, скажите что еще рассказать чтобы задача была описана полно.

> В твоем случае классики нет

Это значит... что? Что нужно искать неклассические алгоритмы решения или что?

> ... начни с цветов и вина)

Давайте пожалуста вот на этом самом месте закончим шутки по этому поводу. Неуместно

← →
brother © (2012-03-16 04:29) [28]

> пытающийся угодить жене преподавателя

> на этом самом месте закончим шутки по этому поводу

тогда меняй формулировку...

← →
selesasha (2012-03-16 06:20) [29]

угодить<>удовлетворить сексуальное желание

А по теме сказать нечего?

Вот у меня вопрос возник:
При применении Монте-Карло, я могу найти стохастическую ширину нужного диапазона, а вот как при применении этого метода мне найти границы этого диапазона?

> угодить<>удовлетворить сексуальное желание

а я об этом и не говорил...

> А по теме сказать нечего?

> > давай начнем с показа ее реализации...
>
> Давайте не будем. Функция протестирована и работает.

> Есть массив целых одноразрядных чисел (а), такой что: а[n]<=a[n+1]
> при a[n]<>0 и a[n+1]<>0. Можно представить себе массив из
> нулей, заполненный на 3/4 случайными числами от 1 до 9,
> потом эти 3/4 отсортировали по возрастанию (получился неубывающий
> массив с хвостом из нулей), и заменили некоторые из чисел
> в этих 3/4 на нули.
> Задача: найти границы вхождения числа 4, используя минимальное
> число обращений к массиву. Нули границы вхождения не ограничивают.

имхо - перебором, возможно оптимизированным, но ПОЛНЫМ перебором...

← →
se (2012-03-16 07:41) [32]

> > А по теме сказать нечего?
> > > давай начнем с показа ее реализации...
> > Давайте не будем. Функция протестирована и работает.

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

Ну это Вы загнули.
Вот что на данный момент оформилось у меня:

поиск идет в условно-бесконечном цикле, стандартным методом дихотомии. С каждой интерацией увеличиваем значение счетчика (count) на единицу.
На каждой интерации проверяем стандартые условия плюс:
1. Если центр - 0, то смещаем центр по принципу cnt:=cnt+IntPower(-1,count)
2. Если центр - искомое значение, то начинаем искать левую и правую границу по тому же алгоритму.
3. если ни одно из этих условий не выполнилось, то вычисляем новые границы диапазона поиска, и новый центр.

Попинайте пожалуста

← →
selesasha (2012-03-16 07:56) [33]

в 1 формула вот так выглядит: cnt:=cnt+IntPower(-1,count)*count

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

> имхо - перебором, возможно оптимизированным, но ПОЛНЫМ перебором.

Ну зачем же ПОЛНЫМ?
Сначала ищем 0<Nmin<4 - верхняя граница
Потом ищем 0<Nmax>4 - верхняя граница
Таблица, как я понял за исключением 0 упорядоченная

P.S. Уточним задачу: при запросе к таблице мы можем:
a) найти элемент, удовлетворяющий условию
б) узнать значение элемента по индексу
???

если а - два обращения
если б - количество обращений = индексу нижней границы. То есть ПОЧТИ ПОЛНЫЙ перебор.

← →
selesasha (2012-03-16 12:03) [35]

> Таблица, как я понял за исключением 0 упорядоченная

Да.

> P.S. Уточним задачу: при запросе к таблице мы можем:
> a) найти элемент, удовлетворяющий условию
> б) узнать значение элемента по индексу

б.

> если б - количество обращений = индексу нижней границы.
> То есть ПОЧТИ ПОЛНЫЙ перебор.

Если использовать тот алгоритм, который я привел в [32], то в самом худшем случае мы можем сократить границы перебора вдвое. В среднестатистическом, процедура бинарного поиска повторится 2-3 раза. А это уже совсем не ПОЧТИ ПОЛНЫЙ перебор, даже если пункт 2 заменить на "Если центр - искомое значение, то начинаем искать левую и правую границу перебором"

Собственно это решение пока что самое лучшее из того, что я смог придумать. Может Вам с высоты вашего полета сразу видны какие-то изъяны?

> selesasha (16.03.2012 12:03:35) [35]

Раз ты можешь определить, что это центр, то несложно повторить это несколько
раз, называется метод постепенного приближения

> selesasha (15.03.12 17:34) [3]
> бинарный поиск тут не подходит - по крайней мере в лоб:
> 1) Какой поддиапазон выбирать если середина отрезка - nil?
>
> 2) Как находить границы окна, если середина отрезка попала в искомое значение?

Ты, конечно, извини, но программист - это человек, который должен уметь строить алгоритм.

Представь, что перед тобой лежит на полу сотня бумажек подряд. На оборотной стороне бумажек написаны числа в убывающей последовательности.
Тебе дается число, и задача - найти диапазон, в который оно будет входить.

Если у тебя бедное воображение - возьми хотя бы 20 бумажек, напиши на некоторых из них числа, отсортируй, переверни, и приступай, записывая каждый шаг в тетрадочку.

← →
selesasha (2012-03-16 12:34) [38]

> Тебе дается число, и задача - найти диапазон, в который
> оно будет входить.

Мне задача - найти все вхождения этого числа

> Ты, конечно, извини, но программист - это человек, который
> должен уметь строить алгоритм.

Агоритм я уже построил в [38], теперь прошу его поругать

← →
Sergey (2012-07-12 10:24) [39]

Всем здравствуйте!
Почитал, конечно, человек принимает близко к сердцу всякие слова со стороны jeer, но мало кто может спокойно относиться к подобному, тем более радоваться..
jeer за всё время в этой теме не написал ничего полезного, ядовитые слова человека характеризуют фигово, зачем нужны такие комментарии?
selesasha - пытаетесь разобраться, студент, угодить супруге преподавателя (нормальным способом), чтобы учиться бесплатно - всё это вполне понятно и критиковать тут нечего. Удачи..
Конечно у Вас есть слабость, к такой тупой критике, как у jeer, но ничего : )) у меня тоже есть, у большенства есть, у jeer тоже есть : )) хотя он это тщательно скрывает )) и плюёт на тех кто его критикует, но это его характеризует ещё фиговей.
просто вам стоило игнорировать его посты, да и всё, и можно ещё попытаться понять почему он так себя ведёт - это тоже интересно, потом можно научиться жалеть таких людей, у них проблемм гораздо больше из-за дурного характера.

← →
Sergey (2012-07-12 10:25) [40]

Удалено модератором
Примечание: Ты получил разрешение на обсуждение личности?

Поиск в массиве Найти похожие ветки