Программирование это сложно. Людей, которые хотят гораздо больше, тех которые могут. Старайтесь делиться своим временем и энергией с людьми которые потенциально могут. А тем кто не годится можно попробовать показать подводные камни и трудности профессии. Вопрос в том кто потенциально может? На мой взгляд дело не только в складе ума, а в большей степени желании и усердии человека. Программирование для усидчивых.
Ирония судьбы: WebAssembly был создан для ускорения кода в браузерах, а теперь мы движемся к тому, чтобы компилировать JavaScript обратно в WebAssembly!
С осени работаю в индийском стартапе. И работая в их коллективе не заметил большой разницы, уровень их навыков разработки вполне современный и подход тоже. Все шутки про индуский код вдруг стали не актуальны. Английским они хорошо владеют, ниже уровня B2 в коллективе никого нет. Что самое забавное стартап занимается разработкой CAD системы для проектирования микрочипов. Основным клиентом которого являются крупнейшие университеты Индии. Так что Индия в скором времени сама начнет проектировать и производить чипы. Решил поделится поскольку сам был удивлен от всего этого.
Всех кому интересна компьютерная графика и кто устал просто решать задачи, предлагаю принять участие в одном из своих проектов. Например https://github.com/iShape-Rust/iShape-js
Уверен так гораздо интереснее чем просто решать задачи. Сам попробовал rust меньше года назад
Выглядит итерессно, решил попробовать, но на macOS 13.5.1(intel) не запустился (ffmpeg установил). Вышла ошибка что файл поврежден давай перемещай в корзину. Может сходу знаете в чем проблема? И еще вопрос на виртуалке заработает? Решил попробовать на Ubuntu.
Спасибо за статью, раньше тоже много раз пробовал силы в этой задаче, правда меня манило точное решение. Но ваша статья навеяла интересные мысли. Очень уж много времени отнимает эта задача боюсь если честно возвращаться.
Только при делении-сдвиге вправо отрицательных чисел надо быть аккуратнее. Попробуйте сдвинуть вправо -1. Для остальных чисел к слову все правильно получается
10 июня сделал swift перевод на сумму 115k через 2 часа мне написали, что бы я обосновал происхождения денег. Я БЫЛ клиентом банка около месяца. Переводил им деньги с Альфабанк, поэтому я скинул им выписку со счетов в Альфе за год. Скинул им выписки в течении 10 минут после их просьбы. Спустя 10 минут меня заблокировали по п 4.5 и 7.3.9. Больше ни сказали не слова по причине блокировки. Не большая сумма порядка 2.7k оставалась в валюте ее сказали что конвертируют в рубли по своему курсу и вышлют мне на мой счёт в другой банк. Я предложил забрать деньги наличными в рублях по курсу цб. Они попросили время порядка 4 дней, после чего просто поступил отказ. Заявление в цб я написал уже 12 июня, пока ответа нет. Здесь очевидно не желание банка проводить эти переводы, поэтому они будут предотвращать это любыми методами.
Если на руках уже есть готовое решение его всегда можно попытаться оптимизировать убрав так называемые «пересечения». Посмотрите работу алгоритма Bitonic tour. Этот алгоритм итерационный и с каждой перестановкой он приближается к максимально эффективному решению. Конечно он тоже неимоверно медленный, но как минимум до какого-то шага его можно прогнать.
А динамическое программирование для такого числа городов уже не подходит потому что, требует экспоненциального количества памяти. Я сейчас сам увлечен этой задачей и у меня есть пара оригинальных решений на github, но моя цель не столь амбициозна я поставил себе планку в 64 города.
И да хотелось бы услышать больше деталей вашей реализации, спасибо.
Спасибо, кажется, что вы хорошо разбираетесь.
А подскажите еще, пожалуйста, на что влияет количество кубитов в таком компьютере? Интуитивно мне кажется, что например для NP полных задач число кубитов не должно быть меньше N. Если конечно не учитывать тот факт, что можно разбить на под-задачи.
С книгой Скорцова я конечно же знаком, во многих вещах она для меня стала путеводителем.
Да я сам хорошо разобрался с методом монотонного разбиения. И могу вам с ним помочь. По сути там та же идея, что и в вашей имплементации. Вы движетесь вдоль оси заметающей прямой и делаете суждение заканчивается, начинается или продолжается монотонный полигон. Сортировка начальных вершин и порождает N*log(N). Далее идет триангуляция, которая на практике в подавляющем случаи идет за линейное время и в очень редком случаи с откатом к предыдущей или далее вершине. Я к сожалению не могу оценить эту асимптотику (наверное это N*log(N), но доказать не могу). Для дальнейшего приведения к Делоне так же потребуется связать между собой треугольники, те что лежат на ребре разделяющем один монотонный полигон от другого.
У меня есть две имлементации swift и СSharp. Обе написаны в Data-oriented design, что делает их не много громоздкими для понимания. Так же мне почему то было проще рассуждать двигая заметающую прямую по оси oX. Swift версия использует ARC (умный подсчет ссылок), а СSharp версия полагается на ручной механизм управления памятью. Еще стоит наверное сказать, что в swift версии я начал добавлять поддержку дополнительных точек. Точки которые лежат внутри полигона, и обычно нужны для более «красивой» триангуляции.
Спасибо за статью. Больше всего понравилась в ней описание алгоритма триангуляции. С этим методом я не был знаком. Вы случайно не сравнивали этот метод с другими алгоритмами триангуляции? Например, с методом монотонных полигонов. Интересуют полный процесс триангуляции от построения базовой к последующему приведению Делоне. Как я сам вижу оба алгоритма имеют асимптотику базовой триангуляции (без Делоне) n*Log(n). Но возможно у вашего алгоритма базовая триангуляция ближе к Делоне. Плюс у монотонного метода есть шаг с разбиением на полигоны. С другой стороны в вашем алгоритме присутствует излишняя триангуляция «вспомогательных» треугольников. Но это все в теории, а хотелось бы практическую скорость сравнения. Еще из плюсов вашего подхода, как вы сами отметили устойчивость алгоритма к петлям.
Программирование это сложно. Людей, которые хотят гораздо больше, тех которые могут.
Старайтесь делиться своим временем и энергией с людьми которые потенциально могут.
А тем кто не годится можно попробовать показать подводные камни и трудности профессии. Вопрос в том кто потенциально может?
На мой взгляд дело не только в складе ума, а в большей степени желании и усердии человека. Программирование для усидчивых.
Ирония судьбы: WebAssembly был создан для ускорения кода в браузерах, а теперь мы движемся к тому, чтобы компилировать JavaScript обратно в WebAssembly!
С осени работаю в индийском стартапе. И работая в их коллективе не заметил большой разницы, уровень их навыков разработки вполне современный и подход тоже. Все шутки про индуский код вдруг стали не актуальны. Английским они хорошо владеют, ниже уровня B2 в коллективе никого нет. Что самое забавное стартап занимается разработкой CAD системы для проектирования микрочипов. Основным клиентом которого являются крупнейшие университеты Индии. Так что Индия в скором времени сама начнет проектировать и производить чипы. Решил поделится поскольку сам был удивлен от всего этого.
Всех кому интересна компьютерная графика и кто устал просто решать задачи, предлагаю принять участие в одном из своих проектов. Например https://github.com/iShape-Rust/iShape-js
Уверен так гораздо интереснее чем просто решать задачи. Сам попробовал rust меньше года назад
Я думаю тот тот же принцип что и в кругосветном путешествии. Смотря какую систему координат выберем получим различный результат.
Выглядит итерессно, решил попробовать, но на macOS 13.5.1(intel) не запустился (ffmpeg установил). Вышла ошибка что файл поврежден давай перемещай в корзину. Может сходу знаете в чем проблема? И еще вопрос на виртуалке заработает? Решил попробовать на Ubuntu.
Прохладная история. Не боитесь так перегреть космос?
Спасибо за статью, раньше тоже много раз пробовал силы в этой задаче, правда меня манило точное решение. Но ваша статья навеяла интересные мысли. Очень уж много времени отнимает эта задача боюсь если честно возвращаться.
Только при делении-сдвиге вправо отрицательных чисел надо быть аккуратнее. Попробуйте сдвинуть вправо -1. Для остальных чисел к слову все правильно получается
10 июня сделал swift перевод на сумму 115k через 2 часа мне написали, что бы я обосновал происхождения денег. Я БЫЛ клиентом банка около месяца. Переводил им деньги с Альфабанк, поэтому я скинул им выписку со счетов в Альфе за год. Скинул им выписки в течении 10 минут после их просьбы. Спустя 10 минут меня заблокировали по п 4.5 и 7.3.9. Больше ни сказали не слова по причине блокировки. Не большая сумма порядка 2.7k оставалась в валюте ее сказали что конвертируют в рубли по своему курсу и вышлют мне на мой счёт в другой банк. Я предложил забрать деньги наличными в рублях по курсу цб. Они попросили время порядка 4 дней, после чего просто поступил отказ. Заявление в цб я написал уже 12 июня, пока ответа нет. Здесь очевидно не желание банка проводить эти переводы, поэтому они будут предотвращать это любыми методами.
Согласен с автором что задача весьма не тривиальна.
Для себя в свое время решил, что лучше уйти от Float вычислений на Int.
Если интерессно нашел свой репозиторий с этим участком кода, как раз на C#
https://github.com/iShapeUnity/Clipper/blob/master/Runtime/iShape/Clipper/Util/PolygonExt.cs
Подскажите пожалуйста. Если рассматривать построение модели белка с математической точки зрения то она сводится к NP задачи коммивояжёра?
А динамическое программирование для такого числа городов уже не подходит потому что, требует экспоненциального количества памяти. Я сейчас сам увлечен этой задачей и у меня есть пара оригинальных решений на github, но моя цель не столь амбициозна я поставил себе планку в 64 города.
И да хотелось бы услышать больше деталей вашей реализации, спасибо.
А подскажите еще, пожалуйста, на что влияет количество кубитов в таком компьютере? Интуитивно мне кажется, что например для NP полных задач число кубитов не должно быть меньше N. Если конечно не учитывать тот факт, что можно разбить на под-задачи.
Да я сам хорошо разобрался с методом монотонного разбиения. И могу вам с ним помочь. По сути там та же идея, что и в вашей имплементации. Вы движетесь вдоль оси заметающей прямой и делаете суждение заканчивается, начинается или продолжается монотонный полигон. Сортировка начальных вершин и порождает N*log(N). Далее идет триангуляция, которая на практике в подавляющем случаи идет за линейное время и в очень редком случаи с откатом к предыдущей или далее вершине. Я к сожалению не могу оценить эту асимптотику (наверное это N*log(N), но доказать не могу). Для дальнейшего приведения к Делоне так же потребуется связать между собой треугольники, те что лежат на ребре разделяющем один монотонный полигон от другого.
У меня есть две имлементации swift и СSharp. Обе написаны в Data-oriented design, что делает их не много громоздкими для понимания. Так же мне почему то было проще рассуждать двигая заметающую прямую по оси oX. Swift версия использует ARC (умный подсчет ссылок), а СSharp версия полагается на ручной механизм управления памятью. Еще стоит наверное сказать, что в swift версии я начал добавлять поддержку дополнительных точек. Точки которые лежат внутри полигона, и обычно нужны для более «красивой» триангуляции.