Ах да, чуть не забыл… точность в данном случае определяется сугубо выбором вспомогательной точки, которая, например, заведомо вне треугольника. Ее выбор тоже лежит за рамками описанной узкой задачи.
Но тут как раз можно повлиять и, например, в случае возникновения погрешности выбрать ее заново. И вообще, тут столько еще инженерных оптимизаций сделать можно в некоторых случаях… Например, как не делать никакой лишней алгебры-геометрии вообще для заведомо не подходящих треугольников, которых большинство. Типа если координаты x точек отрезка меньше, чем все координаты x точек треугольника. Да при правильном выборе референсной точки… Вот это было бы круто и интересно.
Я, может быть, не правильно акценты расставил. Суть первого абзаца была в том, что в данном алгоритме тоже перемножаются числа с плавающей запятой, а результаты вычитаются, что может привести к вычитанию близких чисел и накоплению погрешности, как и в случае с системой уравнений.
Более того, из-за симметричности системы уравнений мы, например, можем сначала решить ее относительно одного «наиболее точно известного» неизвестного и отсечь таким образом часть ложно-положительных результатов. Ведь на каждое неизвестное у нас будет строгое ограничение: оно должно быть от 0 до 1. В указанном алгоритме мы вроде бы так гибко поступать не можем.
Во втором абзаце я имел в виду то, что, при данной формулировке, погрешность в любом случае неизбежна. Но можно избежать ее, выйдя за рамки задачи: например, навскидку, не давать камере подходить слишком близко к поверхности (наблюдатель все-равно увидит экран, залитый одним большим градиентом). Или, например, изменить алгоритм и построить BSP-дерево. В таком случае мы, по крайней мере, для подавляющего большинства моделей сможем гарантировать отсутствие дырок, хоть и ценой дорогих предварительных обсчетов и, возможно, ценой точности самой модели. (может быть, конечно, с деревьями, я и не прав)
В общем, желание дать точный ответ вполне понятно — не понятно, чем громоздкость алгоритма помогает улучшить его точность.
Но способ с системой из 3-х уравнений, который упоминался выше и по сути является тем же самым, отлично позволяет решить задачу в целых числах, а его суть не выходит за рамки первых пары месяцев изучения векторного подхода к стереометрии в школе. К тому же он гораздо нагляднее, т.к. уж проблема решения системы 3-х уравнений-то изучена хорошо и ей даже можно не заниматься, а взять что-то готовое (вряд ли вся математика в приложении ограничивается этим алгоритмом, авось еще где поможет избежать велосипедизма).
Еще, раз речь об оптимальности, то, если решать систему методом Гаусса, то мы, например, можем остановиться уже на этапе, когда мы, например, поняли, что точка пересечения прямой с плоскостью выходит за пределы отрезка и сэкономить половину вычислений, которые в данном алгоритме производятся безусловно.
В любом случае, решать задачу в целых числах в данном контексте выглядит странно, равно как и решать достаточно несложную школьную задачу _таким_ образом.
Если же говорить о точности, то, вообще говоря, погрешность появляется уже на 1-м этапе, когда мы вычитаем координаты точек, и накапливается еще при вычислении «alpha», и сравнение ее с нулем уже само по себе должно производиться с неким эпсилон во избежание иллюзий. Кроме того, в алгоритме еще уйма последующих сравнений с нулем, где погрешность накопилась еще больше.
Но думаю, что, скорее всего, все эти погрешности не должны быть принципиальными. Погрешность же появляется в основном в случае либо если какие-то координаты векторов очень малы (вычитаем 2 больших числа), либо если отрезок проходит слишком близко от треугольника и почти параллелен ему (имеем кучу близких коэффициентов в уравнении). Данный алгоритм их не решает и вообще эти проблемы не решить, если не выходить за рамки данной задачи или не улучшать представление данных.
Ну заголовки — это тоже может быть достаточно много, особенно, в случае, если это автогенеренные текстовые письма. А заголовки 100-200 тыс писем — это уже прилично данных само по себе. Их надо уметь прилично индексировать, с чем не всегда клиенты справляются.
Мобильные клиенты такой кучи информации стараются не хранить, а получают только последние сообщения, что мне и нравится.
Как раз в те годы, когда там внедряли имап, эти сервисы были достаточно популярны, не только сейчас. Навскидку: у меня именно в 2001-м основной ящик был на newmail.ru, как и у многих моих друзей.
Актуальность имапа тогда была достаточно высока: веб-интерфейсы были убогие по современным меркам, почтовые программы были бесспорно удобнее. Интернет был дорогой и слабый, возможность не качать весь свой ящик, работать с папками на сервере выглядела достаточно привлекательно. Поддержка имапа этими сервисами в своем роде даже большее достижение, чем имап на гмейле в 2008-м.
Но если говорить именно про «сейчас», так в современном своем виде имап более актуален для мобильных клиентов, которые в силу своих ограничений по объему persistent-хранилища просто не могут адекватно работать с pop3. Если посмотреть на графики, то мобильных клиентов больше половины.
Но нормальная поддержка имапа, более-менее соответствующая RFC и работающая не только с gmail-ом и еще парой серверов, например, в андроиде появилась чуть позже появления версии 2.2, а это был уже 2010 год. В 2008-м не было такого рынка устройств, корректно поддерживающих imap, соответственно актуальность самого протокола была не так высока.
С 2008 года поменялось многое: команда почты mail.ru поменялась практически целиком, как поменялись и приоритеты. К сожалению, я не мог написать имап в 2008 году, как бы ни хотел, т.к. я еще тогда не работал в команде почты и в mail.ru вообще, а Денис тогда как раз делал поддержку имапа в яндексе :)
В своем посте я систематизировал технические нюансы реализации imap-а. Возможно, кому-то это будет просто любопытно, кому-то подкинет мыслей, скажем, при написании imap-клиента. Если бы я что-то в этом роде прочитал перед написанием сервера — мне это бы сэкономило некоторое количество времени. Если вам это неинтересно и вызывает лишь скептицизм — простите меня за то, что вы решили прочесть эту статью.
В плане .NET — я на нем писал давно и не очень много. Но об этих улучшениях написано в release notes, друзья говорили, что стало удобнее. Это был просто пример того, что есть и другие интересные технологии, которые в принципе можно попробовать :)
Получат позже — потому что непосредственно написание кода заняло реально малый процент времени. Я знаю, что на новом для себя языке я бы писал не так быстро и код был бы хуже, как минимум, первые полгода. На нормальное овладение технологией, имхо, уходит не один месяц и не один проект.
Я лично, как инженер, считаю, что язык программирования — не главное. На практически любом языке можно сделать удобную для проекта и задач платформу. Главное — хорошо владеть выбранным инструментом.
Консультанты — это хорошо, но я помню, что в Parallels, например, по совету консультантов начали пытаться переписывать всю автоматизацию на java. Имхо, это был очень странный шаг, который стоил компании нескольких толковых специалистов и отнял порядочно времени. С любым подходом главное — не перестараться :)
Хм, ну уж нет. Я, например, лично не готов :) Толстовато, в общем)
Вообще, это странная тема… я могу более-менее читаемо, быстро и лаконично писать на C++(надеюсь, что так). Вы — на erlang. Если мы поменяемся местами, то, скорее всего, наша продуктивность резко снизится (во всяком случае, моя уж точно). Хуже от этого будет только пользователям mail.ru, которые получат имап позже :) При этом, при всех прелестях erlang-а, вряд ли я сразу напишу maintainable код.
А кроме erlang-а еще много интересных технологий. Говорят, в последнем .NET-е интересные фишки в плане асинхронности добавили, а еще он тоже быстро компилируется. Scala тоже интересный и красивый язык с функциональными плюшками.
Но если все пробовать, то кто и когда код писать-то будет? Да и по мне, так добавление еще одного языка, даже самого передового, в любой корпоративный зоопарк технологий только усложняет интеграцию.
Насчет качества кода — тут уж не мне судить, извините. Мне он, естественно, большей частью нравится :) Там в основном именно работа с протоколом, парс-форматирование, код достаточно простой и без rocket-science-а. C++ — довольно лаконичный язык, но, к сожалению, только если уметь его готовить.
Ну, т.е. с_port подразумевает еще один процесс-проксю? Не думаю, что наших админов бы это обрадовало :)
А на самом деле, я думаю, что описанный вами способ написания сервера — просто другой подход, который вполне хорош и имеет право на жизнь. Он имеет, как плюсы, так и минусы.
Вообще же, как показала практика, написать код сервера — это не так уж и сложно, независимо от языка. Повторюсь, но специфики имап там всего лишь 5к строчек. Правильно подружить все это дело с нашей инфраструктурой, с множеством разных клиентов — это было куда более сложной задачей, а тут уже язык не важен, важен подход.
Там основная проблема в том, что у нас другие требования к индексам. Как пример: imap-сервер может позволить себе сохранить в индексе уже готовый ответ на fetch bodystructure, для нас это было бы слишком дорого как в смысле избыточности, так и в смысле переиндексации. У нас структура письма в индексах хранится в виде дерева, и используется imap-ом, веб-интерфейсом, и даже pop3.
Кроме того, письма у нас хранятся не по RFC, а в другом, чуть более компактном виде.
Фактически нам надо было бы научиться формировать на лету ответы bodystructure/envelope из данных в нашем формате, прикрутить какие-нибудь хаки для того, чтобы без лишних оверхедов на I/O отдавать части письма, попутно преобразуя их к RFC-виду. Потом надо было бы прикрутить общение с нашей базой юзеров.
На самом деле, примерно этим и занимается 80-90%% кода нашего имап-сервера.Т.е. какую часть dovecot-а мы реально смогли бы переиспользовать? По сути, только работу с сокетами и парсинг протокола. И то, ее, скорее всего пришлось бы патчить, чтобы не есть лишнего CPU.
Кроме того, dovecot — сторонний для нас проект, он живет своей жизнью и любые плагины и правки нам надо будет мерджить с новыми изменениями самого сервера, либо взять на себя поддержку проекта из 300 тыс строк.
В результате плюсы от написания своего сервера перевесили минусы.
Если говорить про написание просто абстрактно хорошего имап сервера, оно, наверное, так и есть: проще взять очень высокоуровневый, возможно функциональный, язык программирования, написать на нем лаконичный, красивый и аккуратный код без хаков.
Но у нас сервер, к сожалению, писался не совсем абстрактно: есть уже хранилище с достаточно громоздким C-шным API, кроме того, внутри проекта почты сервер-сайд сейчас пишут на С/C++, perl-е и python-е. Программистов на эрланге у нас в команде просто нет. Т.е. даже если сервер на нем и написать, то читать его код будет потом некому. Плюс, надо изобретать какие-то обертки для C-шного кода в эрланг, либо поддерживать 2 версии клиентской библиотеки к стороджу.
В общем тут как обычно, для нас самым большим ограничением было то, что у проекта почты уже большая история, очень много всего уже написано. Не хотелось, во-первых, плодить зоопарка из технологий, а во-вторых, дублировать уже существующий код.
Да и на самом деле, на C++ при правильном подходе, код оказался довольно лаконичным: со всеми хаками для всех клиентов, там имапной специфики около 5000 строк. :)
Думаю, что тут вряд ли дело в клиенте, т.к. SMTP — очень агностичный протокол по отношению к телу письма, smtp-клиенту редко нужно уметь парсить mime письма дальше нескольких хэдеров и вообще разбираться, что там внутри. Исключение составляет только разве что binary extension.
Хоть я сам лично и не фанат, но очень многие хвалят outlook :) Он вроде бы нормально работает с большой базой писем. Еще как вариант есть the bat и opera. Друзья использовали the bat + imap на довольно больших аккаунтах.
Для меня идеален был бы десктопный клиент с моделью работы мобильных клиентов: не качать ничего лишнего, всякие аттачи и картинки fetch-ить по запросу. Особенно это было бы актуально в случае слабого internet-канала. К сожалению, я таких клиентов не встречал, поэтому для десктопа использую веб-интерфейс. Он примерно соответствует моим требованиям не качать ничего лишнего.
Ага, т.е. речь все-таки об SMTP сервере. Я слишком плохо знаком с erlang-ом, чтобы суметь легко попробовать этот пример. Не могли бы вы сгенерить тела этих двух писем (с глюком и без), положить их в zip-архив и прислать мне на v.starodub {собака} corp.mail.ru? Мы разберемся, где именно глюк — в телах писем, или же в SMTP/веб-интерефейсе, если у нас — то с радостью починим.
Как я понимаю, генерацию производит вызов mimemail:encode(), а gen_smtp занимается уже отправкой?
К хранилищу пришлось прикрутить imap-ные uid-ы и uidvalidity, а также их обновление в случае модификаций писем. Это теоретически несложно, но нужно было быть аккуратным и поправить достаточное кол-во кода. Также там была прикручена пара оптимизаций для ускорения частичной отдачи письма в RFC-формате, это не было нужно pop3 и веб-интерфейсу.
Вообще, одна из целей написания собственного сервера — не менять сильно хранилище, т.к. переиндексировать все письма — очень «дорого», в наших объемах это может занять до полугода. Мы обошлись только довольно «дешевой» раздачей uid-ов, которую мы делаем при первом доступе по imap к ящику.
Хранилище у нас на отдельных серверах, имап является таким же клиентом хранилища, как и pop3, smtp и веб-интерфес. Они все дергают один API по одному протоколу.
К сожалению, не совсем понял, о чем речь. Плюс, полгода назад у нас имап, насколько помню, еще был только на внутреннем тестовом сервере и проблем там было море :)
Если речь об ответах BODY/BODYSTRUCTURE, то, согласно RFC, мы там возвращаем все поля из письма, которые клиенты могут использовать для работы с вложениями: content-id, content-type с полями charset и name, content-disposition с полем filename.
Но тут как раз можно повлиять и, например, в случае возникновения погрешности выбрать ее заново. И вообще, тут столько еще инженерных оптимизаций сделать можно в некоторых случаях… Например, как не делать никакой лишней алгебры-геометрии вообще для заведомо не подходящих треугольников, которых большинство. Типа если координаты x точек отрезка меньше, чем все координаты x точек треугольника. Да при правильном выборе референсной точки… Вот это было бы круто и интересно.
Более того, из-за симметричности системы уравнений мы, например, можем сначала решить ее относительно одного «наиболее точно известного» неизвестного и отсечь таким образом часть ложно-положительных результатов. Ведь на каждое неизвестное у нас будет строгое ограничение: оно должно быть от 0 до 1. В указанном алгоритме мы вроде бы так гибко поступать не можем.
Во втором абзаце я имел в виду то, что, при данной формулировке, погрешность в любом случае неизбежна. Но можно избежать ее, выйдя за рамки задачи: например, навскидку, не давать камере подходить слишком близко к поверхности (наблюдатель все-равно увидит экран, залитый одним большим градиентом). Или, например, изменить алгоритм и построить BSP-дерево. В таком случае мы, по крайней мере, для подавляющего большинства моделей сможем гарантировать отсутствие дырок, хоть и ценой дорогих предварительных обсчетов и, возможно, ценой точности самой модели. (может быть, конечно, с деревьями, я и не прав)
В общем, желание дать точный ответ вполне понятно — не понятно, чем громоздкость алгоритма помогает улучшить его точность.
Но способ с системой из 3-х уравнений, который упоминался выше и по сути является тем же самым, отлично позволяет решить задачу в целых числах, а его суть не выходит за рамки первых пары месяцев изучения векторного подхода к стереометрии в школе. К тому же он гораздо нагляднее, т.к. уж проблема решения системы 3-х уравнений-то изучена хорошо и ей даже можно не заниматься, а взять что-то готовое (вряд ли вся математика в приложении ограничивается этим алгоритмом, авось еще где поможет избежать велосипедизма).
Еще, раз речь об оптимальности, то, если решать систему методом Гаусса, то мы, например, можем остановиться уже на этапе, когда мы, например, поняли, что точка пересечения прямой с плоскостью выходит за пределы отрезка и сэкономить половину вычислений, которые в данном алгоритме производятся безусловно.
В любом случае, решать задачу в целых числах в данном контексте выглядит странно, равно как и решать достаточно несложную школьную задачу _таким_ образом.
Если же говорить о точности, то, вообще говоря, погрешность появляется уже на 1-м этапе, когда мы вычитаем координаты точек, и накапливается еще при вычислении «alpha», и сравнение ее с нулем уже само по себе должно производиться с неким эпсилон во избежание иллюзий. Кроме того, в алгоритме еще уйма последующих сравнений с нулем, где погрешность накопилась еще больше.
Но думаю, что, скорее всего, все эти погрешности не должны быть принципиальными. Погрешность же появляется в основном в случае либо если какие-то координаты векторов очень малы (вычитаем 2 больших числа), либо если отрезок проходит слишком близко от треугольника и почти параллелен ему (имеем кучу близких коэффициентов в уравнении). Данный алгоритм их не решает и вообще эти проблемы не решить, если не выходить за рамки данной задачи или не улучшать представление данных.
Мобильные клиенты такой кучи информации стараются не хранить, а получают только последние сообщения, что мне и нравится.
Актуальность имапа тогда была достаточно высока: веб-интерфейсы были убогие по современным меркам, почтовые программы были бесспорно удобнее. Интернет был дорогой и слабый, возможность не качать весь свой ящик, работать с папками на сервере выглядела достаточно привлекательно. Поддержка имапа этими сервисами в своем роде даже большее достижение, чем имап на гмейле в 2008-м.
Но если говорить именно про «сейчас», так в современном своем виде имап более актуален для мобильных клиентов, которые в силу своих ограничений по объему persistent-хранилища просто не могут адекватно работать с pop3. Если посмотреть на графики, то мобильных клиентов больше половины.
Но нормальная поддержка имапа, более-менее соответствующая RFC и работающая не только с gmail-ом и еще парой серверов, например, в андроиде появилась чуть позже появления версии 2.2, а это был уже 2010 год. В 2008-м не было такого рынка устройств, корректно поддерживающих imap, соответственно актуальность самого протокола была не так высока.
С 2008 года поменялось многое: команда почты mail.ru поменялась практически целиком, как поменялись и приоритеты. К сожалению, я не мог написать имап в 2008 году, как бы ни хотел, т.к. я еще тогда не работал в команде почты и в mail.ru вообще, а Денис тогда как раз делал поддержку имапа в яндексе :)
В своем посте я систематизировал технические нюансы реализации imap-а. Возможно, кому-то это будет просто любопытно, кому-то подкинет мыслей, скажем, при написании imap-клиента. Если бы я что-то в этом роде прочитал перед написанием сервера — мне это бы сэкономило некоторое количество времени. Если вам это неинтересно и вызывает лишь скептицизм — простите меня за то, что вы решили прочесть эту статью.
Получат позже — потому что непосредственно написание кода заняло реально малый процент времени. Я знаю, что на новом для себя языке я бы писал не так быстро и код был бы хуже, как минимум, первые полгода. На нормальное овладение технологией, имхо, уходит не один месяц и не один проект.
Я лично, как инженер, считаю, что язык программирования — не главное. На практически любом языке можно сделать удобную для проекта и задач платформу. Главное — хорошо владеть выбранным инструментом.
Консультанты — это хорошо, но я помню, что в Parallels, например, по совету консультантов начали пытаться переписывать всю автоматизацию на java. Имхо, это был очень странный шаг, который стоил компании нескольких толковых специалистов и отнял порядочно времени. С любым подходом главное — не перестараться :)
Вообще, это странная тема… я могу более-менее читаемо, быстро и лаконично писать на C++(надеюсь, что так). Вы — на erlang. Если мы поменяемся местами, то, скорее всего, наша продуктивность резко снизится (во всяком случае, моя уж точно). Хуже от этого будет только пользователям mail.ru, которые получат имап позже :) При этом, при всех прелестях erlang-а, вряд ли я сразу напишу maintainable код.
А кроме erlang-а еще много интересных технологий. Говорят, в последнем .NET-е интересные фишки в плане асинхронности добавили, а еще он тоже быстро компилируется. Scala тоже интересный и красивый язык с функциональными плюшками.
Но если все пробовать, то кто и когда код писать-то будет? Да и по мне, так добавление еще одного языка, даже самого передового, в любой корпоративный зоопарк технологий только усложняет интеграцию.
А на самом деле, я думаю, что описанный вами способ написания сервера — просто другой подход, который вполне хорош и имеет право на жизнь. Он имеет, как плюсы, так и минусы.
Вообще же, как показала практика, написать код сервера — это не так уж и сложно, независимо от языка. Повторюсь, но специфики имап там всего лишь 5к строчек. Правильно подружить все это дело с нашей инфраструктурой, с множеством разных клиентов — это было куда более сложной задачей, а тут уже язык не важен, важен подход.
Кроме того, письма у нас хранятся не по RFC, а в другом, чуть более компактном виде.
Фактически нам надо было бы научиться формировать на лету ответы bodystructure/envelope из данных в нашем формате, прикрутить какие-нибудь хаки для того, чтобы без лишних оверхедов на I/O отдавать части письма, попутно преобразуя их к RFC-виду. Потом надо было бы прикрутить общение с нашей базой юзеров.
На самом деле, примерно этим и занимается 80-90%% кода нашего имап-сервера.Т.е. какую часть dovecot-а мы реально смогли бы переиспользовать? По сути, только работу с сокетами и парсинг протокола. И то, ее, скорее всего пришлось бы патчить, чтобы не есть лишнего CPU.
Кроме того, dovecot — сторонний для нас проект, он живет своей жизнью и любые плагины и правки нам надо будет мерджить с новыми изменениями самого сервера, либо взять на себя поддержку проекта из 300 тыс строк.
В результате плюсы от написания своего сервера перевесили минусы.
Но у нас сервер, к сожалению, писался не совсем абстрактно: есть уже хранилище с достаточно громоздким C-шным API, кроме того, внутри проекта почты сервер-сайд сейчас пишут на С/C++, perl-е и python-е. Программистов на эрланге у нас в команде просто нет. Т.е. даже если сервер на нем и написать, то читать его код будет потом некому. Плюс, надо изобретать какие-то обертки для C-шного кода в эрланг, либо поддерживать 2 версии клиентской библиотеки к стороджу.
В общем тут как обычно, для нас самым большим ограничением было то, что у проекта почты уже большая история, очень много всего уже написано. Не хотелось, во-первых, плодить зоопарка из технологий, а во-вторых, дублировать уже существующий код.
Да и на самом деле, на C++ при правильном подходе, код оказался довольно лаконичным: со всеми хаками для всех клиентов, там имапной специфики около 5000 строк. :)
Нужно смотреть в тело письма.
Для меня идеален был бы десктопный клиент с моделью работы мобильных клиентов: не качать ничего лишнего, всякие аттачи и картинки fetch-ить по запросу. Особенно это было бы актуально в случае слабого internet-канала. К сожалению, я таких клиентов не встречал, поэтому для десктопа использую веб-интерфейс. Он примерно соответствует моим требованиям не качать ничего лишнего.
Как я понимаю, генерацию производит вызов mimemail:encode(), а gen_smtp занимается уже отправкой?
К хранилищу пришлось прикрутить imap-ные uid-ы и uidvalidity, а также их обновление в случае модификаций писем. Это теоретически несложно, но нужно было быть аккуратным и поправить достаточное кол-во кода. Также там была прикручена пара оптимизаций для ускорения частичной отдачи письма в RFC-формате, это не было нужно pop3 и веб-интерфейсу.
Вообще, одна из целей написания собственного сервера — не менять сильно хранилище, т.к. переиндексировать все письма — очень «дорого», в наших объемах это может занять до полугода. Мы обошлись только довольно «дешевой» раздачей uid-ов, которую мы делаем при первом доступе по imap к ящику.
Хранилище у нас на отдельных серверах, имап является таким же клиентом хранилища, как и pop3, smtp и веб-интерфес. Они все дергают один API по одному протоколу.
Если речь об ответах BODY/BODYSTRUCTURE, то, согласно RFC, мы там возвращаем все поля из письма, которые клиенты могут использовать для работы с вложениями: content-id, content-type с полями charset и name, content-disposition с полем filename.