Здравствуйте, Pavel Dvorkin, Вы писали: PD>Если бы мы имели равномощные аэропорты (примерно одинаковое количество прилетов-вылетов в день), да еще и разбросанные примерно равномерно, то это действительно смахивает на NP-полную задачу. Но ничего подобного в реальности нет.
Совершенно верно. В реальности есть настоящие аэропорты, а не Омск из которого ничего не летает. В европе, к примеру, средненький аэропорт типа той же Анталии с сезон через себя прогоняет больше рейсов в день, чем Омск, Новосибирск и Кемерово вместе взятые.
Между хабами типа JFK и FRA летает чудовищное количество разных рейсов.
А полететь, к примеру, из Москвы напрямую в IAD ты пожадничаешь — потому что прямые стоят дорого. Полетишь со стыковкой. И вот там будет столько вариантов, что мозг может лопнуть. Ты просто привык к своей Омской реальности, где есть ровно один способ попасть в Москву, а больше попадать и некуда. Не везде так.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Совершенно верно. В реальности есть настоящие аэропорты, а не Омск из которого ничего не летает. В европе, к примеру, средненький аэропорт типа той же Анталии с сезон через себя прогоняет больше рейсов в день, чем Омск, Новосибирск и Кемерово вместе взятые.
Но не больше, чем ДМД.
S>А полететь, к примеру, из Москвы напрямую в IAD ты пожадничаешь — потому что прямые стоят дорого. Полетишь со стыковкой. И вот там будет столько вариантов, что мозг может лопнуть. Ты просто привык к своей Омской реальности, где есть ровно один способ попасть в Москву, а больше попадать и некуда. Не везде так.
Омская реальность тут ни при чем. Из Омска, точно, есть один способ попасть в Москву, а вот из Москвы вариантов сколько ? В Лондон amadeus дает 310, это включая разные цены на одном рейсе и включая совсем уж экзотические варианты полета. Реальных не так уж много, 10-20. Никто из Москвы в Лондон через Стамбул летать не будет.
PD>Омская реальность тут ни при чем. Из Омска, точно, есть один способ попасть в Москву, а вот из Москвы вариантов сколько ? В Лондон amadeus дает 310, это включая разные цены на одном рейсе и включая совсем уж экзотические варианты полета. Реальных не так уж много, 10-20. Никто из Москвы в Лондон через Стамбул летать не будет.
Зато из Москвы в Сиэтл через Лондон — запросто. И через JFK, и через CDG, и через ATL, и ещё через много чего.
И то, что ты видишь через amadeus — это уже отфильтрованный список. Сколько он там вариантов за кадром перебирает и отбрасывает — ты знаешь?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Зато из Москвы в Сиэтл через Лондон — запросто. И через JFK, и через CDG, и через ATL, и ещё через много чего.
Конечно.
S>И то, что ты видишь через amadeus — это уже отфильтрованный список. Сколько он там вариантов за кадром перебирает и отбрасывает — ты знаешь?
По-видимому, ничего не отбрасывает за пределами 2 пересадок. Если он выдает в качестве варианта полета Москва -Киев полет с пересадкой в Стамбуле, то есть не отбросил его, то что он мог выбросить ? Разве что полет через Гонконг
Ты вот на такой вопрос мне ответь. За последние 20 лет количество рейсов если и возросло, то раза в 2 в среднем, не больше. Рейсов из Омска в Москву сейчас 5, а лет 20 назад было 3, но в Омске тогда садились многие рейсы, идущие на восток (Чита, Иркутск..., я ими любил летать из Москвы — багаж ждать не приходилось), а сейчас их нет. Вообще, я думаю, что потребное количество рейсов зависит в основном от населения города и популярности направления (например, к вам из Омска многие ездят , а в Барнаул — гораздо меньше, я думаю) Так вот — как же 20 лет назад с этой проблемой справлялись ? Без Интернета, без чудовищных переборов ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ты вот на такой вопрос мне ответь. За последние 20 лет количество рейсов если и возросло, то раза в 2 в среднем, не больше. Рейсов из Омска в Москву сейчас 5, а лет 20 назад было 3, но в Омске тогда садились многие рейсы, идущие на восток (Чита, Иркутск..., я ими любил летать из Москвы — багаж ждать не приходилось), а сейчас их нет. Вообще, я думаю, что потребное количество рейсов зависит в основном от населения города и популярности направления (например, к вам из Омска многие ездят , а в Барнаул — гораздо меньше, я думаю) Так вот — как же 20 лет назад с этой проблемой справлялись ? Без Интернета, без чудовищных переборов ?
Справлялись руками и очень медленно. Раньше даже и не пробовали решать такую задачу компьютером. Сейчас — пробуют. Вот тебе и возросшие требования. Раньше такое считалось вообще невозможным. Это раз.
Два — вырос объём перевозок. У меня нет данных за 1990, но с 1996 по 2010 пассажиропоток за месяц вырос с 42M до 58М.
Ещё значительнее выросло количество людей, которые напрямую делают запросы через интернет. Двадцать лет назад ты вставал в очередь в кассу (или звонил турагенту и оставлял заявку), не ожидая ответа в течение 5 секунд. И тебе давали вовсе не оптимальный маршрут, а первый, какой придётся. Что тут можно не понимать?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, Sinclair, Вы писали:
S>Справлялись руками и очень медленно. Раньше даже и не пробовали решать такую задачу компьютером. Сейчас — пробуют. Вот тебе и возросшие требования. Раньше такое считалось вообще невозможным. Это раз.
Ненужным
S>Два — вырос объём перевозок. У меня нет данных за 1990, но с 1996 по 2010 пассажиропоток за месяц вырос с 42M до 58М.
Ну я и говорил,что раза в 2, не более
S>Ещё значительнее выросло количество людей, которые напрямую делают запросы через интернет. Двадцать лет назад ты вставал в очередь в кассу (или звонил турагенту и оставлял заявку), не ожидая ответа в течение 5 секунд. И тебе давали вовсе не оптимальный маршрут, а первый, какой придётся.
Насчет первого — это ты поосторожнее. Расписания были (пусть отпечатанные), цены были, выбрать можно было. Не за 5 секунд, верно. Но, честно говоря, никакой особой необходимости за 5 сек нет. Вполне за час-два сойдет. А насчет оптимальности маршрута — да, возможно, не именно оптимальный, а близкий к нему. На $5 дороже
>Что тут можно не понимать?
А тут и понимать нечего. Никто не утверждает, что лучше вручную, а не с Интернетом и компьютерами. Но когда мне говорят. что без компьютеров будет полный затык в решении задач,которые еще при Юлии Цезаре как-то умели решать, то что тут скажешь...
PD>А тут и понимать нечего. Никто не утверждает, что лучше вручную, а не с Интернетом и компьютерами. Но когда мне говорят. что без компьютеров будет полный затык в решении задач,которые еще при Юлии Цезаре как-то умели решать, то что тут скажешь...
Тебе никто такого не говгорил. Хотя нет, может голоса в голове тебе такое говорили...
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Насчет первого — это ты поосторожнее. Расписания были (пусть отпечатанные), цены были, выбрать можно было. Не за 5 секунд, верно. Но, честно говоря, никакой особой необходимости за 5 сек нет. Вполне за час-два сойдет.
До внедрения "Сирены" человек перед кассой мог час-два простоять. Это сойдет?
PD>А тут и понимать нечего. Никто не утверждает, что лучше вручную, а не с Интернетом и компьютерами. Но когда мне говорят. что без компьютеров будет полный затык в решении задач,которые еще при Юлии Цезаре как-то умели решать, то что тут скажешь...
Так и был, в общем-то, затык. Интересно, как при Юлии Цезаре велась продажа авиабилетов?
Здравствуйте, gandjustas, Вы писали:
G>Я на 4 курсе вполне мог написать парсер и интерпретатор математических выражений. А преобразованием ast вполне можно было сделать "символьное" дифференцирование и\или интегрирование.
да-да. у тебя — самый длинный.
посиди в уголке пока.....
>>Что тут можно не понимать?
PD>А тут и понимать нечего. Никто не утверждает, что лучше вручную, а не с Интернетом и компьютерами. Но когда мне говорят. что без компьютеров будет полный затык в решении задач,которые еще при Юлии Цезаре как-то умели решать, то что тут скажешь...
Мне интересно ты реально не понимаешь или все-таки прикидываешься?
Вот другая реальная задача которую приходится решать. Куда дешево поехать на майские/новогодние/выходные/любые другие праздники. то есть ищется минимум функции от (интересность места, время в пути, время отправления, время прибытия, цена, цена отеля, расстояния от аэропорта прибытия до центра города, возможно какие-то еще параметры, например сезонность).
как решение этой задачи выглядит сейчас? Я выписываю список потенциально интересных мест, долго ищу дешевые билеты на нужные мне даты, составляю табличку для каждого пункта назначения. итд. это может занимать очень много времени. реально к майским праздникам я начинаю готовиться в январе. чтобы не спешить и спокойно все просчитать.
И, внимание, когда я все-таки решаю эту задачу я не имею ни малейшего представления правильно ли я ее решил. Потому что я физически не в состоянии учесть все факторы и варианты и просто выбираю тот который меня максимально устраивает в тот момент когда я уже задолбался выбирать.
Как должно выглядеть решение этой задачи в идеале тебе надо описывать?
Количество переменных в задаче представляешь?
M_>>>Однако это не так: число Ω строго определено и имеет вполне конкретное значение, но рассчитать его невозможно, поскольку это позволило бы решить проблему останова, у которой действительно нет решения.
FR>>А что тут не так? M_>бог непознаваем по определению, поэтому любые рассуждения о нем по определению ересь
Ничего подобного. Проблема останова это совершенно независимая давно доказанная теорема, полный расчет же Ω позволяет разрешить проблему останова, что невозможно.
Здравствуйте, Privalov, Вы писали:
PD>>Насчет первого — это ты поосторожнее. Расписания были (пусть отпечатанные), цены были, выбрать можно было. Не за 5 секунд, верно. Но, честно говоря, никакой особой необходимости за 5 сек нет. Вполне за час-два сойдет.
P>До внедрения "Сирены" человек перед кассой мог час-два простоять. Это сойдет?
Из-за того, что в касcе перебирали сотни вариантов или по другой причине ?
Для обеих задач можно в принципе составить программу и попробовать найти минимум функции, но скорее всего результаты не будут удовлетворительными из-за неточности и волатильности модели — здесь слишком много неформализуемых или плохо формализуемых элементов.
Что касается меня, то я бы предпочел (и предпочитаю) в таком случае получить только список возможных вариантов по наиболее важным критериям с тем, что дальнейший подбор я буду проводить вручную.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ненужным
Лично тебе ненужным, Павел, лично тебе. Ты интересовался, откуда берутся более жёсткие задачи в туризме? Я тебе объяснил. Хочешь вживую увидеть "разницу в требованиях" — посмотри на сайт Трансаэро и сравни, скажем, с Expedia.com.
Про веб-магазины я тебе даже ничего объяснять не буду — поскольку ты ими не пользуешься, то для тебя ничего не изменилось.
Для остального мира всё изменяется. И разработчикам всегда приходится крутиться, потому что с них требуют больше.
Те задачи, которые "уже решены", не попадают к программистам. Если устраивает такой электронный магазин, который был десять лет назад — можно просто пойти и развернуть готовый магазин. Если пришли к разработчикам — значит, готовые решения не подошли, надо писать. Ну, иногда бывает так, что вся "новизна" — это новые картинки. Тогда это "тип 1", задача, заведомо разрешимая в наших ресурсах.
А иногда бывает так, что веб-магазин позволяет тебе нанести свой собственный текст на выбранные в одной из тридцати цветовых комбинаций кроссовки, и покрутить результат в 3d.
И всё это — на любом веб клиенте, включая телефоны. Допускаю, что лично тебе вообще кроссовки не нужны, ни с надписями, ни без. Более того, возможно, ты вообще в веб-магазинах не отовариваешься. Но это же не означает, что программисты всего мира должны говорить компаниям типа Nike "нет, то, что вы требуете — ерунда. Павел Дворкин прекрасно покупал себе кеды ещё до изобретения интернета".
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S>Про веб-магазины я тебе даже ничего объяснять не буду — поскольку ты ими не пользуешься, то для тебя ничего не изменилось. S>Для остального мира всё изменяется. И разработчикам всегда приходится крутиться, потому что с них требуют больше. S>Те задачи, которые "уже решены", не попадают к программистам. Если устраивает такой электронный магазин, который был десять лет назад — можно просто пойти и развернуть готовый магазин. Если пришли к разработчикам — значит, готовые решения не подошли, надо писать. Ну, иногда бывает так, что вся "новизна" — это новые картинки. Тогда это "тип 1", задача, заведомо разрешимая в наших ресурсах. S>А иногда бывает так, что веб-магазин позволяет тебе нанести свой собственный текст на выбранные в одной из тридцати цветовых комбинаций кроссовки, и покрутить результат в 3d. S>И всё это — на любом веб клиенте, включая телефоны. Допускаю, что лично тебе вообще кроссовки не нужны, ни с надписями, ни без. Более того, возможно, ты вообще в веб-магазинах не отовариваешься. Но это же не означает, что программисты всего мира должны говорить компаниям типа Nike "нет, то, что вы требуете — ерунда. Павел Дворкин прекрасно покупал себе кеды ещё до изобретения интернета".
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Эта задача в действительности столь же хорошо формализуема, как задача о составлении расписания в институте PD>http://rsdn.ru/forum/philosophy/4076407.aspx
PD>Для обеих задач можно в принципе составить программу и попробовать найти минимум функции, но скорее всего результаты не будут удовлетворительными из-за неточности и волатильности модели — здесь слишком много неформализуемых или плохо формализуемых элементов.
Эта задача прекрасно формализуема.
PD>Что касается меня, то я бы предпочел (и предпочитаю) в таком случае получить только список возможных вариантов по наиболее важным критериям с тем, что дальнейший подбор я буду проводить вручную.
Это ты предпочел бы. Ты. А я точно знаю, что задача "дешево провести выходные в европе" имеет решение, но не имею возможности этим решением воспользоваться, потому что у меня не хватает вычислительных мощностей.
Но не уводи разговор в сторону. Ты согласен, что решение этой задачи требует серьезных вычислительных мощностей?
Я еще раз объясню в чем задача. В начале надо взять все доступные (с любым количеством стыковок) перелеты из СПб с 18-00 пятницы, которые прилетят в аэропорт назначения не позже 10 утра субботы по местному времени, но не позже 16-00 по Москве. Тут уже количество вариантов огромно. А далее появляются гостиницы итд.
Здравствуйте, Pavel Dvorkin, Вы писали:
P>>До внедрения "Сирены" человек перед кассой мог час-два простоять. Это сойдет?
PD>Из-за того, что в касcе перебирали сотни вариантов или по другой причине ?
Прочитал твой ответ. Краткий, непонятный, чем-то похож на вопрос. Не мог бы ты как-нибудь попроще, чтобы простому смертному понятно стало, объяснить, что ты имел в виду?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Хм... Когда ракету строили — были уверены, что она первую космическую наберет ?
Нет.
PD>Прототипов-то не было.
Были и много. Сначала были феерверки китайцев. Потом мечты Циалковского. Потом опытные прототипы. Потом Катюши и Фау-2. Фау-2 на орбиту ничего вывести не могла (те самые космические скорости недобирала), но она стал прототипом для Р-1, которая тоже в космос не летала. Королева. Р-1, в свою очередь, стала прототипом для Р-7, которая уже стала прототипом для тех ракет что стали на вооружение и на которых были запущены первые спутники.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, WolfHound, Вы писали:
WH>Программисты от ракетчиков отличаются только тем что в нашем случае стоимость и время изготовления изделия ничтожны. WH>Это приводит к тому что мы сначала делаем что-то похожее на конечное изделие после чего итеративно доводим до кондиции.
Кстати, от части это не так. Если продукт начинает компилироваться/запускаться вместо секунд, скажем, минуты, то скорость его разработки резко снижается. А если компиляция или запуск начинают занимать часы, то продукт может просто застрять.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Pavel Dvorkin, Вы писали:
WH>>Но задача была. Я сел и провел исследования на тему как эту задачу решать.
PD>Вот это интереснее. То есть ты все же оценил, как эту задачу решать и пришел к выводу, что она решается. Способ оценки ? (естественно, мне твои секреты ни к чему, общие принципы)
В основе логических рассуждений был простой факт. Уже есть рукописные и сгенерированные парсеры которые обеспечивают приемлемую для IDE скорость работы. Иначе бы не было современных IDE.
Так же была научная работа по поводу ПЕГ-а и алгоритма Пакрат. По словам автора Пакрат офигительный алгоритм обеспечивающий линейную скорость парсинга. Лично я сразу заподозрил в тут подвох. И правда, на практике оказалось, что хотя скорость теоретически и линейная, но на практике она линейно-медленная (не приемлемо медленная для IDE). Однако сама идея использованная в Пакрат и некоторые прототипы (да, да), такие как !Rats показывали, что есть вероятность добиться приемлемой производительности.
Логика и эксперименты показали, что если отказаться от тотальной мемоизации (изюминки алгоритма Пакрат), то скорость существенно возрастает.
Далее, как уже говорил Вольфхаунд, последовала куча экспериментов (итераций) некоторые из которых давали прирост производительности. Где-то в середине пути стало ясно, что предполжение о том, что ПЕГ может обеспечить необходимую производительность были верными. Но до этого мы не могли это утверждать.
Вольфхаунд действительно был уверен. Но его уверенность скорее была слепой верой. Слава богу он не упертый баран (как многие неплохие программисты) и увидев на тестах, что тотальная мемоизация приводит только к тормозам начал копать в другие области.
Некоторые из наших предположений оказались верными. Некоторые — нет. Конечно все предположения делались на основе анализа, логики и имеющихся данных (в том числе и научных). Но в реальности никто не мог точно предположить, что за оптимизация даст нужный прирост производительности.
Интересно, что некоторые здравые предположения, например, что нужно использовать ДКА для разбора листовых правил грамматик дали выигрыш далеко не сразу. Первые реализации оказались примерно равными по скорости тем, что не работали в лоб. Но путем вылизывания, усложнения и использования более шустрых последовательностей кода решение на ДКА стало давать значительный выигрыш в скорости.
Так что нужно признать, что ты полностью не прав. Рассчитать что-то заранее невозможно в принципе. А рулят тут эксперименты и грамотные предположения. В предположениях конечно есть некоторая доля просчитанности, так как используются и имеющиеся данные, и результаты других экспериментов, но все же эксперимент решает все. Очень часто бывает так, что казалось бы очевидное предположение (основанное на научных данных) не оправдывается в реальных условиях.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
