Простите, но статья содержит много ошибок. 1. Ничего не рассказано о представляниях графов. На мой вкус, это ошибка с образовательной точки зрения. 2. Представленные реализация DFS и BFS имеют сложность O(V*V), а не указанную в статье. 3. Представленная реализация алгоритма Дейсктры имеет сложность O(V*V), а не указанную в статье. 4. Кроме того, есть смысл обсудить когда реализации O(E*logV) лучше, а когда хуже O(V*V).
Это всё базовые вещи, которые статья не описывает, дальше Дейкстры читать не стал. Мои рекомендации автору и желающим понять эти алгоритмы:
Дасгупта Санджой, Пападимитриу Христос, Вазирани Умеш. - "Алгоритмы". Она выложена в интернете на русском языке (например, тут). Школьникам может быть что-то сложновато, но для начинающих разработчиков/студентов самое то.
WIKI-конспекты ИТМО. Очень хорошие тщательные конпекты, написанные профессионалами. Но это именно конспекты, а не учебник, а потому написано суховато.
Лекции Куликова А. на лекториуме по книге Алгоритмы Дасгупты. Кому-то может понравиться больше, чем сама книга. Кстати, сам Куликов переводчик ее на русский язык, а редактором был Шень.
У меня есть более полный список на github, там есть разные источники на разные вкусы. Не сочтите за саморекламу.
Год назад проблема еще была, у меня есть подтверждение от третьей стороны. Может сейчас TF собирается по другому и работает теперь быстрее после дефолтной сборки. А может вы замеры не так делаете.
Если хотите, могу посмотреть. Можете оформить в виде репо ваши замеры времени на обоих ЯП и приложить список команд для сборки TF. Очень хочется верить, что Вы правы, но мой внутренний скептик кричит, что это не так :)
Отмечу достаточно важный, с точки зрения, конечного результата факт. Так собранный Tensorflowбудет очень медленно работать. Моя команда 2 года назад сравнивала inference и получалось, что на Python работает в 2 раза быстрее. И, вопрос: зачем тогда C++? Так вот, чтобы собрать правильно, есть смысл покапаться в том, как собирают pip-пакет с Tensorflow, взять оттуда настройки bazel и собирать с ними.
Сэр, мне кажется, но вы просто не умеете готовить эти ЯП (C++, Java). Тут у меня два соображения: 1. Ваши примеры "плохого С++" выглядят как примеры "не целевого использования". Вы просто пытаетесь писать простые вещи с использованием сложного функционала. так делать нетсмысла. 2. Обратите внимание какие ЯП используются на топовых соревнованиях по спортивному программированию. Там производительность крайне важна! И организаторы выбрали C++ и Java. Вам не кажется, что люди, которые годами учились писать высокоскоростной код несогласны с тем, что Java имеет плохую производительность? Можете лучше (производительнее)? Покажите на каком-нибудь top coder.
Я за грамотное написание. Позволю себе отметить несколько фактов. 1. Вы пишите об ошибках автора, которые он уже признал. 2. Вы сами совершаете ошибки. Например, во втором абзаце вы пишите "что либо" без дефиса. 3. Пост очень большой, но не по теме и публичный. Лично я (читатель) делаю вывод, что этот пост написан, чтобы самоутвердиться. Пишите в личку!
@honyaki или любой другой представитель skillfactory (спонсоров этой статьи), ответьте, пожалуйста, на пару вопросов. 1. У вас есть курс по C++, на котором правда разбираются такие вещи? Этот курс в вашей системе грейдов для какого уровня (junior, middle, senior)? 2. Есть ли аналогичного уровня материалы по Data Science? Если да, то есть ли у вас курсы, в которых об этом рассказывают?
Автор очень много уделяет внимания базовым командам. На мой взгляд, dvc действительно прост и сходство с git только упрощает с ним механическую работу. Проблема, которую я до сих пор не смог решить сам и не услышал решения от создателей, это как построить процесс разработки для «долгообучающихся» моделей (например, нейросетей).
Поясню. Предположим мы обучаем бустинг, и он учиться 1 мин. Тогда работа выглядит так: 1 — создаем git-ветку под гипотезу, 2 — пушим туда изменения, 3 — затем обучаем модель, 4 — пушим результаты в dvc. Используем, например, mlflow для визуализации всех экспериментов. Красота!
Но это нереально если мы учим модель неделю. Т.к. мы не можем сменить ветку и делать новый эксперимент на шаге 3, т.к. надо дождаться результатов эксперимента. С облаком будет чуть по другому, т.к. там будет репо в котором нет разработки. Но либо у нас в облаке будет несколько копий датасета, либо разработчики будут шарить общую папку для обучения модели. И то и то неудобно.
Поэтому использую dvc только для версионирования датасетов. Периодичекси мерджим в develop эти изменения и тем саммым они доступны всей команде.
Судя по фразе:
Обо всех обновлениях и изменениях нужно сообщать команде где-то еще
, skleg вы используете dvc не так как мы в команде. Можно рассказать об этом?
Автор явно любит свои велосипеды. Не использют, все больше проникающую в стандарт pathlib, обучали собственный каскад сетей вместо попробовать ArcFace. Недавно в ods.ai обсуждалось как ускорить поиск по эмбедингу лица и там было штук 5 решений со ссылками в том числе и на хабр.
O(N*k) — оценка сложности по операциям сложения/умножения, но нужно учесть что OpenBLAS делает операцию вычисления евклидова расстояния векторно, что приводит нас к мысли, что данная оценка сложности не коррелирует с реальным временем. Таким образом, писать про O(N*k) некорректно в рамках поставленноой задачи. А еще можно хранить в БД квадрат длины вектора-эмбединга и за O(1) находить cos угла между БД эмбедингом и входным, а затем теорема косинусов и получаем оценку O(N).
«лабораторку провинциального вуза» — грубо по отношению к 85% жителей не столиц.
А в завершении еще и оказывается (я не знал) k-d в postgres есть. Зато автор дает совет учить алгоритмы пасанам, вместо rtfm, в том числе и для себя.
В результате, пользу от статьи лично я получил (узнал про k-d в postgres), но осадок от подачи остался.
Я за 20 лет писал на разных языках. При этом писать эвристики для NP-полной задачи мне пришлось только на 1С. Так что, не сочиняйте! Там все как и в других ЯП.
Возможно это так в соц сеточках, но не тут. Если комментарий заминусован, то его затемняют/скрывают на хабре. Почему пользователи не должны видеть комментарий, с которым несогласилось 5-10 чел? Пользовтели не должны видеть комментарии не релевантные или токсичные, мусор короче. Я всегда так думал о хабре…
Вот мне интересно кто все те люди, которые минусуют абсолютно не токсичные комментарии? Да, не белые и пушистые, но и не токсичные. Или дизлайки ставятся просто потому что пост не понравился?
Неужели нельзя вдуматься в то, что пишут chapuza и emmibox? Про себя скажу, что никогда так не рассуждал, более того, считаю что зп недостаточно высоки и софтскилы нужны, но черт побери, в словах этих двоих есть не просто зерно истины, а прямо целое поле для раздумий. Очень рад, что прочел эти рассуждения и открыл для себя этот спартанский подход к разработке. Спасибо!
PS: Посмотите, что в профиле у автора статьи про дизлайки сказано.
Полностью осгласен с автором, хотя на 1С не пишу уже лет 8.
Про недоспециалистов, которых легион, и которых шлют к вам учиться, вместо оказания полноценной поддержки. Так извините, пусть представитель ЯП/фреймворка/экосистемы в которой таких недоспециалистов нет, бросит в меня камень. Этот легион везде!!! И бороться надо с безграмотностью, а не с 1С.
В моем сообщении не было ни слова про науку в фильме «Умница Уилл Хантинг». Зато я отметил, что в фильме поднимается тема самообразования. Не помните как Уилл говорит о том, что библиотеки доступны всем и бесплатно? Это же и есть корень самообразования! Доступность бесплатных знаний!
PS: При всем при этом я очень люблю всякого рода коллективные мероприятия (семинары, митапы и пр.). Но это не отменяет необходимости самообразования.
Самостоятельное образование гораздо ценнее, образования в университете. Это мнение программиста и тимлида. А еще эта точка зрения очень хорошо показана в фильме «Умница Уилл Хантинг».
Ну, а то, что есть истории успеха «как я стал программистом в Х лет», автоматически должно означать наличие другой стороны медали — истории провала. Вы как раз такую и описываете, но это не меняет статистику, которая действительно говорит, что на образование далеко не всегда смотрят. А вот на возраст смотрят…
Насколько я понимаю, этот алгоритм имеет ограничения по сравнению с классическим алгоритмом Дейкстры. То что бросается в глаза это необходимость иметь равномерное распределение вершин по бакетам. Прокомментируйте, пожалуйста, т.к. не уверен что уловил все детали вашего подхода.
Полагаю, вы сравнили по времени свое решение и классическое. Хорошая асимптотика может не означать ускорение на практике (пример: умножение матриц методом Штрассена), поэтому хочется увидеть эти сравнения тоже.
Вопрос: когда можно будет провести эксперимент с подобным оборудованием?
Дело в том, что я уже проверял подобные маркетинговые утверждения этой весной. Представитель одной крупной международной компании заявлял, что если взять видеокарту за $500 и сравнить их решение за те же деньги, то разница будет всего в 3 раза в пользу видеокарты. Когда я провел эксперименты с TensorFlow, в соответствии с инструкциями технического специалиста из этой компании, то оказалось в 160 раз. Я не скептик, я действительно хочу найти альтернативу GPU.
Ну а если говорить о практике, а не о математической теории — задача коммивояжера нерешаема уже для 20 локаций (по крайней мере на домашнем пека за разумное время).
Вы очень плохо информированы. Если откроете работу Костюка 2013г., то у него вроде написано про 100 вершин за минуту. Ну, и посмотрите работу 2017г, начиная с 8 слайда (за минуту 150 вершин последовательный алгоритм).
Простите, но статья содержит много ошибок.
1. Ничего не рассказано о представляниях графов. На мой вкус, это ошибка с образовательной точки зрения.
2. Представленные реализация DFS и BFS имеют сложность O(V*V), а не указанную в статье.
3. Представленная реализация алгоритма Дейсктры имеет сложность O(V*V), а не указанную в статье.
4. Кроме того, есть смысл обсудить когда реализации O(E*logV) лучше, а когда хуже O(V*V).
Это всё базовые вещи, которые статья не описывает, дальше Дейкстры читать не стал. Мои рекомендации автору и желающим понять эти алгоритмы:
Дасгупта Санджой, Пападимитриу Христос, Вазирани Умеш. - "Алгоритмы".
Она выложена в интернете на русском языке (например, тут). Школьникам может быть что-то сложновато, но для начинающих разработчиков/студентов самое то.
WIKI-конспекты ИТМО.
Очень хорошие тщательные конпекты, написанные профессионалами. Но это именно конспекты, а не учебник, а потому написано суховато.
Лекции Куликова А. на лекториуме по книге Алгоритмы Дасгупты.
Кому-то может понравиться больше, чем сама книга. Кстати, сам Куликов переводчик ее на русский язык, а редактором был Шень.
У меня есть более полный список на github, там есть разные источники на разные вкусы. Не сочтите за саморекламу.
Год назад проблема еще была, у меня есть подтверждение от третьей стороны. Может сейчас TF собирается по другому и работает теперь быстрее после дефолтной сборки. А может вы замеры не так делаете.
Если хотите, могу посмотреть. Можете оформить в виде репо ваши замеры времени на обоих ЯП и приложить список команд для сборки TF. Очень хочется верить, что Вы правы, но мой внутренний скептик кричит, что это не так :)
К сожалению, нет. Не хватило моей личной организованности, чтобы результаты исследования остались в компании.
Отмечу достаточно важный, с точки зрения, конечного результата факт. Так собранный Tensorflow будет очень медленно работать. Моя команда 2 года назад сравнивала inference и получалось, что на Python работает в 2 раза быстрее. И, вопрос: зачем тогда C++? Так вот, чтобы собрать правильно, есть смысл покапаться в том, как собирают pip-пакет с Tensorflow, взять оттуда настройки bazel и собирать с ними.
Сэр, мне кажется, но вы просто не умеете готовить эти ЯП (C++, Java). Тут у меня два соображения:
1. Ваши примеры "плохого С++" выглядят как примеры "не целевого использования". Вы просто пытаетесь писать простые вещи с использованием сложного функционала. так делать нетсмысла.
2. Обратите внимание какие ЯП используются на топовых соревнованиях по спортивному программированию. Там производительность крайне важна! И организаторы выбрали C++ и Java. Вам не кажется, что люди, которые годами учились писать высокоскоростной код несогласны с тем, что Java имеет плохую производительность? Можете лучше (производительнее)? Покажите на каком-нибудь top coder.
Я за грамотное написание. Позволю себе отметить несколько фактов.
1. Вы пишите об ошибках автора, которые он уже признал.
2. Вы сами совершаете ошибки. Например, во втором абзаце вы пишите "что либо" без дефиса.
3. Пост очень большой, но не по теме и публичный.
Лично я (читатель) делаю вывод, что этот пост написан, чтобы самоутвердиться. Пишите в личку!
Автор, извините, что не по теме поста.
@honyaki или любой другой представитель skillfactory (спонсоров этой статьи), ответьте, пожалуйста, на пару вопросов.
1. У вас есть курс по C++, на котором правда разбираются такие вещи? Этот курс в вашей системе грейдов для какого уровня (junior, middle, senior)?
2. Есть ли аналогичного уровня материалы по Data Science? Если да, то есть ли у вас курсы, в которых об этом рассказывают?
Поясню. Предположим мы обучаем бустинг, и он учиться 1 мин. Тогда работа выглядит так: 1 — создаем git-ветку под гипотезу, 2 — пушим туда изменения, 3 — затем обучаем модель, 4 — пушим результаты в dvc. Используем, например, mlflow для визуализации всех экспериментов. Красота!
Но это нереально если мы учим модель неделю. Т.к. мы не можем сменить ветку и делать новый эксперимент на шаге 3, т.к. надо дождаться результатов эксперимента. С облаком будет чуть по другому, т.к. там будет репо в котором нет разработки. Но либо у нас в облаке будет несколько копий датасета, либо разработчики будут шарить общую папку для обучения модели. И то и то неудобно.
Поэтому использую dvc только для версионирования датасетов. Периодичекси мерджим в develop эти изменения и тем саммым они доступны всей команде.
Судя по фразе: , skleg вы используете dvc не так как мы в команде. Можно рассказать об этом?
O(N*k) — оценка сложности по операциям сложения/умножения, но нужно учесть что OpenBLAS делает операцию вычисления евклидова расстояния векторно, что приводит нас к мысли, что данная оценка сложности не коррелирует с реальным временем. Таким образом, писать про O(N*k) некорректно в рамках поставленноой задачи. А еще можно хранить в БД квадрат длины вектора-эмбединга и за O(1) находить cos угла между БД эмбедингом и входным, а затем теорема косинусов и получаем оценку O(N).
«лабораторку провинциального вуза» — грубо по отношению к 85% жителей не столиц.
А в завершении еще и оказывается (я не знал) k-d в postgres есть. Зато автор дает совет учить алгоритмы пасанам, вместо rtfm, в том числе и для себя.
В результате, пользу от статьи лично я получил (узнал про k-d в postgres), но осадок от подачи остался.
Неужели нельзя вдуматься в то, что пишут chapuza и emmibox? Про себя скажу, что никогда так не рассуждал, более того, считаю что зп недостаточно высоки и софтскилы нужны, но черт побери, в словах этих двоих есть не просто зерно истины, а прямо целое поле для раздумий. Очень рад, что прочел эти рассуждения и открыл для себя этот спартанский подход к разработке. Спасибо!
PS: Посмотите, что в профиле у автора статьи про дизлайки сказано.
Про недоспециалистов, которых легион, и которых шлют к вам учиться, вместо оказания полноценной поддержки. Так извините, пусть представитель ЯП/фреймворка/экосистемы в которой таких недоспециалистов нет, бросит в меня камень. Этот легион везде!!! И бороться надо с безграмотностью, а не с 1С.
PS: При всем при этом я очень люблю всякого рода коллективные мероприятия (семинары, митапы и пр.). Но это не отменяет необходимости самообразования.
Ну, а то, что есть истории успеха «как я стал программистом в Х лет», автоматически должно означать наличие другой стороны медали — истории провала. Вы как раз такую и описываете, но это не меняет статистику, которая действительно говорит, что на образование далеко не всегда смотрят. А вот на возраст смотрят…
Полагаю, вы сравнили по времени свое решение и классическое. Хорошая асимптотика может не означать ускорение на практике (пример: умножение матриц методом Штрассена), поэтому хочется увидеть эти сравнения тоже.
PS: Поправьте, пожалуйста, опечатки («алгоримт», «lon(n)», «20 секунд» на картинке ...)
Дело в том, что я уже проверял подобные маркетинговые утверждения этой весной. Представитель одной крупной международной компании заявлял, что если взять видеокарту за $500 и сравнить их решение за те же деньги, то разница будет всего в 3 раза в пользу видеокарты. Когда я провел эксперименты с TensorFlow, в соответствии с инструкциями технического специалиста из этой компании, то оказалось в 160 раз. Я не скептик, я действительно хочу найти альтернативу GPU.
Вы очень плохо информированы. Если откроете работу Костюка 2013г., то у него вроде написано про 100 вершин за минуту. Ну, и посмотрите работу 2017г, начиная с 8 слайда (за минуту 150 вершин последовательный алгоритм).