Все уже украдено до нас

    image

    Думаю, у многих хоть раз была мысль — я родился слишком поздно, все уже открыто, придумано и т. д.

    Хорошо Декарту, или, тем более, всяким древнегреческим математикам, доказывать простенькие теоремки и вписывать свое имя в историю. Сейчас далеко не каждый (да что там, единицы на тысячи человек) физически способны добраться до переднего края науки, не выбросившись из окна главного корпуса МГУ по пути.

    Хорошо ушлым ребятам в начале девяностых, поднимали миллионные бизнесы буквально с полоборота. Хорошо тем, кто вовремя прочухал перспективность интернета и открыл сайты в очевидных пустующих нишах. Брину и Пейджу, ведь когда они запускали Гугл, еще не было Гугла.

    Джобс собирал компьютеры в гараже и продавал. Сейчас запуск нового техпроцесса обходится Интелу в миллиарды долларов.

    Короче, слишком сложно нынче пробиться. Очень высокая конкуренция, куда ни плюнь.

    У меня есть для вас обнадеживающая новость. В мире разработки ПО это абсолютно не так. Нерешенные задачи россыпями валяются на дороге, некому взять и сделать.

    Косвенно это доказывается тем, что в большинстве программ, систем, библиотек, которые кому-то нужны, количество тикетов и интенсивность разработки только растет. То есть, ширина проблемы только раскрывается на данный момент. Положительная производная. Примеры: ядра операционных систем, популярные языки программирования (т. е. их компиляторы, виртуальные машины и стандартные библиотеки), базы данных, системы управления сайтами, код мобильных платформ, фронтенд-фреймворки.

    Насчет графического сектора (движки игр, рендеринг, все это) я знаю мало, не буду врать, но, кажется, там тоже куча движухи.

    Есть, конечно, и системы, которые уже прошли пик активной разработки. Их код достиг некого локального оптимума (для их задач) и безбажности, его трудно хоть как-то улучшить. Примеры: jQuery, LaTeX, dlmalloc. Тут я имею ввиду именно активно используемые вещи, конечно, потому что бессмысленно упоминать, что никому не нужное говно бросается и не развивается.

    Но в таком «золотом» состоянии заметное меньшинство проектов, это практически исключения.

    Повторюсь, даже гребень волны еще не пройден. Хотя в большом масштабе уже многое решено, в детали только-только начали углубляться. Если сравнивать с золотой лихорадкой, то самородки с куриное яйцо из ручьев уже повытаскивали (хотя и не все), но большая часть золота, по весу, еще не намыта.

    Примеры

    Алгоритм быстрой сортировки уже придуман достаточно давно, лет 50 назад. Почти лежащая на поверхности его оптимизация (два опорных элемента вместо одного) был реализован в стандартной библиотеке Java (пожалуй, самая популярная платформа, на данный момент) каких-то лет 5 назад. В стандартной библиотеке языка Си, насколько я помню, до сих пор не оптимизировали сортировку.

    Моя тема: хеш-таблицы. На всякий случай обрисую, для тех кто не знает, это очень базовая структура данных, огромное количество алгоритмов, целых классов программ в первую очередь зависят от их эффективности. Во многих популярнейших языках программирования (включая те же Java и С++) хеш-таблицы реализованы удручающе неэффективно безо всякого оправдания. Вот просто можно прямо сейчас пойти, заменить их и станет лучше по всем показателям.

    Еще моя тема: базы данных. Проблемы с производительностью и несоответствие заявленным характеристикам (durability) популярнейших баз давно стали притчей во языцех. За этим не кроется никаких принципиальных проблем, просто плохой код, который некому править. Пойдите и исправьте, это суммарно сэкономит миллионы долларов (натурально).

    Разработчики изнывают от кривых, небезопасных, переусложненных языков программирования. Абсолютно обычные ребята идут и пишут свои языки (Rust, Kotlin, Julia), которые для определенных задач лучше всего, что существовало до этого, поэтому справедливо занимают свою нишу. Пойдите и помогите ребятам, они утопают в задачах, рук не хватает никогда.

    Вспомните, что каких-то 3 года назад не существовало AngularJS, сейчас его используют десятки тысяч людей.

    На написание этого поста меня сподвиг случай в Яндексе, про который я сегодня узнал: их инженеры серьезно улучшили поведение ядра Linux, если на севере в основном крутится какая-то персистентная структура, которая занимает почти всю физическую память. А это довольно широкий круг серверных задач. У меня возник немой вопрос: а почему Linux, который вообще-то под сервера и заточен, не имел эту оптимизацию раньше? Потому что еще не все украдено до нас.

    Резюме

    Чтобы вписать свое имя в историю разработки ПО, как бы пафосно это не звучало, сейчас не надо быть гением или везунчиком. Это алгоритмизируемая задача с детерминированным результатом, в отличие, скажем, от задачи заработать миллиард долларов или открыть новый закон физики.

    1. Выберите область, в которой нравится ковыряться.

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

    3. а. Станьте контрибьютором популярной штуки. Для этого не надо проходить тайный обряд инициализации или оплатить крупный членский взнос, просто шлите хороший патч. На вас будут молиться, потому что большинство проектов, в том числе очень популярных и спонсируемых, задыхается от недостатка разработчиков. Чтобы точно войти в историю, постепенно расширяйте свое влияние в проекте. Со временем станьте ключевым разработчиком.

    3. б. Вычлените коренную проблему в своей области и решите ее. Такие проблемы есть в каждой области, и будут через пять лет. Это не то, что можно пойти в лес и не найти клад.

    4.…

    5. PROFIT!

    Если за пункты 2-3 вам не платят, что случается, придется работать параллельно где-то, и идти к цели только по вечерам. Куча примеров, когда большие проекты начинались как подспорье к основной работе. Или вот: Con Kolivas, анестезиолог(!), который разрабатывал ядро Linux.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 154

      +12
      --Брину и Пейджу, ведь когда они запускали Гугл, еще не было Гугла

      Была Altavista.com

      — AngularJS, сейчас его используют десятки тысяч людей.

      Это из серии бабло побеждаeт зло. Тот же C# был втиснут в маркет глядючи на Java.
        –14
        Альтависта (надо полагать) была примитивнейшим поделием, раз простенький алгоритм PageRank ее тут же побил. Да что вообще можно было серьезное написать, интернету было пару лет от роду.

        А что, Гугл лил в Angular какое-то бабло?
          +16
          > А что, Гугл лил в Angular какое-то бабло?
          Конечно лил. Angular написан не энтузиастами, а разработчиками которые получают ЗП в гугл. Так что как минимум оплата работы программистов. А еще всякие презенташки, раскрутка и так далее. Вот и получается очень круглая сумма.
            0
            Нет, ну помимо этого, ясное дело. Это копейки. Яндекс разработчикам тоже платил, и вообще разработка ядра Linux ведется в основном людьми на ЗП. Суть не в этом.

            Вопрос в том, был ли Angular новым словом, достоин ли того, чтобы выстрелить, если бы его написали, допустим, вы. Или, если бы не Гугл, его бы никто не стал использовать.
              +10
              Или, если бы не Гугл, его бы никто не стал использовать.

              Не стоит откидывать эту мысль. Основным критерием выбора сложного инструмента остается производитель и поставщик, а не функциональность.
              Конечно, молоток можно купить китайский, без гарантии и сервисной поддержки, без сертификатов качества, но вот процессоры или медицинские приборы?

              Поэтому, люди мучаются и используют AngularJS или ReactJS, хотя, возможно, есть куча более подходящих инструментов под их цели.
                0
                Основным критерием выбора сложного инструмента остается производитель и поставщик, а не функциональность.
                Это где так? Кроме госзаказа или больших корп. закупок с таким не сталкивался.
                  +2
                  Даже в быту ни разу не сталкивались с выбором в пользу менее навороченного но именитого изделия, против подозрительно навороченного ноунейма?
                    0
                    Вы правы, в быту да. Даже среди аналитически настроенных гиков.
                    0
                    ИМХО: Что в быту, что в бизнесе всегда был основным поставщик/производитель. Если конечно не ССЗБ.
                    Что мне этот 100Мбитный интернет от школьника (который то есть то нет, или как было — отключили в связи с закрытием нелегальной фирмы), если у меня стабильный 5Мбитный ADSL от нормального поставщика.
                    Доставка товаров, создание изделий по запросу, даже заказывая в фирму сайт в итоге перешли на именитого поставщика через: фриланс, намем чувачка, а тут мой друг такое же делает.
                    Даже банальный крем для сухой кожи непонятно чей даёт раздражение, тогда как брендовый — нет. Или капли в глаза? Пробовали лишь бы какие купить? Или лекарство? (Ну этот и тот можно принимать, только вот от нормального производителя вы дополнительно не ослепнете — был случай =) )
                    Сколько раз я покупал так называемые более функциональные вещи, в отличии от именикого поставщика/производителя и они не справлялись с назначением, шли в мусорку и на их место приходили от более именитого производителя.

                    А в бизнесе «влитали» многие… Типография взяла оборудование не через нормального поставщика, а через «по дешевле и по больше». В итоге они были готовы платить любые деньги… и платили.
                    Купленый Мерседес(который не предназначен для них изначально) для коммерческих пасажироперевозок стал раем, по сравнению с Газелями (более предназначенными — уже всё имелось для этой деятельности).
                    И так далее…
                      +1
                      Во многом вы правы. Я наверное больше думал про опыт в разработке. Ни разу мы не выбирали сторонние компоненты или фреймворки или внешние сервисы только потому что они от известных вендоров. Изучали прежде всего функционал, поддержку, производительность и прочие объективные факторы.
                    0
                    Люди мучаются не потому что, Angular или React плох, а потому что не умеют выбирать инструменты для задачи и ведутся на маркетинг и хайп. Для своих задач и Angular, и React отлично подходят. Но когда вы молоток начинаете использовать, чтобы закручивать гайки, а не гвозди забивать — то тут конечно мучения начинаются.
                    +1
                    Могу привести пример из моей жизни:
                    Когда (совсем недавно) встал выбор какой javascript MVC использовать в новом проекте — факт того что AngularJS разрабатывается и сапортиться гуглом сыграл не последнюю роль.
                    • НЛО прилетело и опубликовало эту надпись здесь
                        +4
                        Поскорей бы Google+ оказался там же.
                          +1
                          Что-то я не понял, что это? Список закрытых проектов?
                          • НЛО прилетело и опубликовало эту надпись здесь
                            0
                            В случае AngularJS чуть другая ситуация. Если гугл даже решит его слить — то подхватит уже комъюнити. Даже если и не подхватит, ничего не будет мешать пользоваться тем что есть сейчас. Исходники то никто не отберет.
                              +1
                              Исходники то никто не отберет.
                              Ну вот сделали мы крупный проект на YUI 2 — продукте именитого разработчика. Теперь приходится самим патчить исходники, потому что с современными браузерами уже есть проблемы, YUI 3 до ума так и не довели, и Yahoo прекратил поддержку старых и разработку новых версий.
                        +1
                        Он начинался вроде бы как part time project, который не оговаривается с начальниками.
                          0
                          Ну сам гугл тоже начинался с маленького стартапа, но это же не значит что в него не лили бабло)
                    +2
                    Вы путаете не решенные задачи с доступностью этих решений широкой публике.

                    Пример яндекса очень показателен, единственное что они поделились с коммьюнити своими наработками, а сотни других компаний этого не сделали и не сделают в силу разных причин.
                      +3
                      Это не важно. Молодец не тот, кто накодил для алчной компании, а тот, кто влил в ядро. В научном сообществе приоритет отдается по времени публикации. Тут аналогично.
                        0
                        Проблема в отсутсвии материального профита для вливающего
                          +4
                          Оставить след в истории и заработать много денег — это две разные цели. У человека есть базовая потребность в самоутверждении/реализации. Пост про нее. Но не для всех эта потребность важна, другие реализуют ее другими путями.
                            +13
                            Самореализация — это верхушка ваших потребностей. Если нечего на хлеб намазывать, человек не может нормально думать о самореализации.
                              +5
                              Это согласно Маслоу. А на деле бывают и такие люди, что последнюю рубашку с себя снимут, лишь бы выпендриться. Или остаться в истории.
                                0
                                Бывают конечно. И на самом деле многие живут с ущербной пирамидой. Самореаизуются но не становятся счастливыми, т.к. где-то на нижних этажах чего-то не хватает.
                                  +5
                                  Ну это еще вопрос, насколько эта пирамида отражает реальность. Учитывая, что и сам Маслоу от нее отказался.
                                  0
                                  Значит их потребность в нижних уровнях много меньше, чем кажется вам, или которая принята в обществе. В любом случае они ее уже удовлетворили, в соответствии с Маслоу, и двинулись дальше. Да, возможно они ставят меньший акцент на хлебе, в то же время кто-то хочет еще икры на хлеб и стен уютней. Но и те и другие, прежде чем подниматься выше по пирамиде, всегда удовлетворяют более базовые потребности. Если вам кажется, что пирамида в частном случае не работает — проверьте базовые предпосылки, ошибка где-то там.
                                    0
                                    Если реальность противоречит теории, тем хуже для реальности?

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

                                    Да и вообще вся эта пирамида была умозрительной, не опиралась на опыты, и сам Маслоу от нее в конце концов отказался.

                                    Но раз она вам так нравится, продолжайте ее придерживаться.
                                      0
                                      Реальность как раз теории не противоречит.

                                      Я не понимаю, каким образом возрастные изменения могут опровергать теорию. Пусть, допустим, человеку Х 17 лет, его на первом уровне больше интересует секс, чем еда, безопасность второго ему больше мешает, чем нужна (ну или уровень безопасности общества уже удовлетворил эту потребность, и индивиду кажется, что это настройки по умолчанию, что мир всегда был таким, и всегда будет таким), зато больше интересуют уровни выше (с оговорками понимания их юным мозгом) — коллектив, признание, умение играть баскетбол и верхний уровень — самоактуализация. Акценты смещены по разному на каждом уровне.

                                      Теперь человек спустя 10 лет. Базовый уровень его интересует больше, потому как акценты сместились, и машина/дом стали необходимыми элементами в его понимании базовых потребностей. Спустя еще 10 лет уровень безопасности будет еще больше акцентирован. А вот саморазвитие и познание — вроде как точно нужны, он даже подписался на рассылку онлайн-университета — но какое к черту познание, если первый уровень еще не закрыт, машина еще не куплена?

                                      Где здесь конфликт? Человек никогда не переходит на уровень выше, пока не «закроет» уровни пониже. По его собственной шкале потребностей, в его собственном понимании нужды. Если миру вокруг кажется, что человек игнорирует базовые уровни, при этом «летая в облаках» — значит мир просто ошибается в предпосылках. Человек этот, конечно же, удовлетворил базовые уровни, соразмерно своим потребностям и акцентам. И не его проблема, что мир имеет другие акценты и усредненную шкалу, на какой уровень сколько времени и сил тратить.

                                      Я не могу говорить о законах физики в терминах «нравится» или «не нравится». Они или работают, или нет. Если пирамида Маслоу в «эгоцентричной» системе отсчета работает всегда — меня не спрашивают, нравится ли мне она. Если мне нечего кушать в рамках потребностей лично моего желудка — ни о каких верхних уровнях речь не идет. Это совершенно не значит, что нет людей, в которых аппетит — ошибка измерения возле нуля.
                              +3
                              Конкретно в случае ядра Linux (и многих других крупных проектов свободного ПО) вливание выгодно для вливающего, а говоря более точно, вливание кода компанией выгодно для этой компании. Смотрите: компания реализовала некую фичу для Linux, теперь ей нужно её поддерживать, т. е. следить, чтобы фича продолжала работать с выходом новых версий ядра. Чтобы не заниматься этой рутиной, компания отправляет патч в апстрим. За счёт таких патчей ядро и живёт
                            +18
                            Хотя, вообще-то, сомневаюсь насчет сотен компаний, у которых ядро пропатчено как надо и вообще все круто, а яндекс только в песочницу залез. Пока что я вижу, что если в опен сорсе хотя бы начинают думать о правильности, быстроте, то в энтерпрайзе царит ужасающая неэффективность и некомпетентность.

                            Многие думают, что в том же Гугле, Яндексе, Вконтакте работают полубоги, код выжимает последний такт производительности и недоступен для понимания простыми смертными. Мне кажется, это огромный миф.
                            0
                            В стандартной библиотеке языка Си, насколько я помню, до сих пор не оптимизировали сортировку.

                            Реализаций стандартной библиотеки C довольно-таки много: en.wikipedia.org/wiki/C_standard_library#Implementations
                            Вы о которой?
                              –4
                              Сортировка оптимизирована хоть в одной?
                                +7
                                Ещё как, и не в одной. Из тех которыми я пользуюсь:

                                musl использует smoothsort
                                glibc вот такой комментарий имеет перед qsort:
                                /* Order size using quicksort.  This implementation incorporates
                                   four optimizations discussed in Sedgewick:
                                
                                   1. Non-recursive, using an explicit stack of pointer that store the
                                      next array partition to sort.  To save time, this maximum amount
                                      of space required to store an array of SIZE_MAX is allocated on the
                                      stack.  Assuming a 32-bit (64 bit) integer for size_t, this needs
                                      only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
                                      Pretty cheap, actually.
                                
                                   2. Chose the pivot element using a median-of-three decision tree.
                                      This reduces the probability of selecting a bad pivot value and
                                      eliminates certain extraneous comparisons.
                                
                                   3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
                                      insertion sort to order the MAX_THRESH items within each partition.
                                      This is a big win, since insertion sort is faster for small, mostly
                                      sorted array segments.
                                
                                   4. The larger of the two sub-partitions is always pushed onto the
                                      stack first, with the algorithm then concentrating on the
                                      smaller partition.  This *guarantees* no more than log (total_elems)
                                      stack size is needed (actually O(1) in this case)!  */
                                

                                newlib такой же, как glibc.
                                  –8
                                  Я же имел ввиду ту оптимизацию, о которой речь в посте, неужели не ясно из контекста.
                                    +2
                                    Этот тезис можно задвигать только после бенчмарков предлагаемой оптимизации в сравнении с теми четырьмя, которые входят в glibc.
                                      0
                                      Почему оптимизации надо сравнивать? Они друг друга не исключают, а, напротив, дополняют.
                                        +4
                                        Во-первых, нужно понять, возможно ли все 5 заставить (эффективно) работать вместе. Во-вторых, оптимизация алгоритма может не привести к уменьшению скорости выполнения программы, а даже замедлить ее. В-третьих, не стоит забывать, что при разных условиях (на разном железе, разном наборе данных и так далее) код может выдавать разную скорость работы. То есть, тестировать придется долго и упорно.
                                      0
                                      А оптимизация из поста — это разве не пункт 2?
                                        +1
                                        Нет, это о способе выборе опорного элемента, а не о их количестве. В Java смотрят 2 и 4-й элемент из 5 в качестве опорных, — аналог этой оптимизации.
                                        0
                                        Мне кажется, оптимизировать надо, чтобы было лучше, а не чтобы было как в java.
                                        Кстати, вот тут как раз написано, почему «каких-то лет 5 назад» эта оптимизация появилась в Java.
                                          0
                                          Ок, но это не умаляет заслугу Ярославского, который не стал ориентироваться на авторитеты, перепроверил гипотезы на современном железе и получил улучшение.
                                        +4
                                        Седжвик знает толк в этом, так что говорить о том, что функция не оптимизирована, в таком случае крайне опрометчиво.
                                        P.S. Вот уж где можно увековечить свое имя — прямо в комментариях к реализации квиксорта…
                                          –1
                                          Такой подход я старался развенчать в посте — дескать, есть какие-то небожители, которые уже за нас придумали все оптимизации, все имеет сакральный предопределенный смысл, который, если вам не понятен — значит, не вашего ума дело. Седжвик молодец, но это не значит, что его алгоритм наилучший.
                                            0
                                            все имеет сакральный предопределенный смысл, который, если вам не понятен — значит, не вашего ума дело

                                            Вы описали то, как многие люди относятся к математике и математическим доказательствам. Непонятно, что тут можно развенчать: многим математика действительно сложна и неинтересна.
                                              0
                                              Как раз ошибка относится к коду так же, как математическим доказательствам (если это не код на Агде ;) Теорема либо доказана верно, либо нет. Однако корректный код можно написать миллионом разных путей. Если написано как-то, это еще не значит, что так и надо. Если в Си есть нулевой указатель, это не значит, что так и надо. Если используется какой-то алгоритм сортировки, это еще не значит, что так и надо.
                                                0
                                                Как раз ошибка относится к коду так же, как математическим доказательствам

                                                Долго перечитывал, прежде чем понял, что вы хотели сказать «относиться».

                                                Если написано как-то, это еще не значит, что так и надо.

                                                Не значит, но многим до этого не дела, а многим другим это сложно и неинтересно. Механизм тот же самый.
                                                Т.е. мне кажется что людей, которые считают «если написано как-то, значит так и надо» в вашем смысле исчезающе мало.
                                                  0
                                                  Позор :(

                                                  Какое вам дело до многих? В девяностые тоже многие сидели сложа руки и бизнес не воротили. И в бум доткомов немногие поднялись.

                                                  Я констатирую, что в области разработки ПО возможностей по-прежнему куча. Для одиночек, работающих и семейных в том числе. А новую социальную сеть, допустим, раскрутить сейчас практически невозможно, даже обладая какими угодно возможностями (Google+). Это объективная реальность.
                                                    0
                                                    Какое вам дело до многих?

                                                    Вы написали статью для них. Тем кто шлёт патчи и так понятно что делать.
                                                      0
                                                      Я теряю нить разговора. Ваш вопрос был: «что можно развенчать?» Ответ: развенчать то, что «немногие» — это закрытая каста, куда с меньше чем IQ 200 не берут, или по блату/везению, или вовсе мифическая группа людей. Реальное положение дел: присоединиться к «немногим», сейчас, пожалуй, может любой человек, которому хватило ума стать «просто» программистом. Вот через пару десятков лет, и правда, это может стать уже не так просто.
                                                        0
                                                        Ответ: развенчать то, что «немногие» — это закрытая каста, куда с меньше чем IQ 200 не берут, или по блату/везению, или вовсе мифическая группа людей.

                                                        Ок, ещё раз: мне кажется, что людей которые так думают ничтожно мало.

                                                        То, что в проектах есть дефекты или места для улучшения, к которым никто не прикасается годами говорит не о том, что у проекта слава неприступного/написанного небожителями/..., а о том, что для тех кто занят в проекте эти проблемы имеют низкий приоритет, а те кто не занят делятся на две группы — те, кому это вообще не интересно и те, кому могло бы быть интересно, но слишком сложно.
                                                          0
                                                          Согласен по форме. Да, пост я писал для «людей, которые так думают». Но не думаю, что их ничтожно мало.

                                                          Тысячи людей заглядывают в код glibc. Почему никто не пишет в рассылку «ребят, а почему в вас так неправильно хеш-таблица реализована? Сортировка?» Потому что 99 из 100 думают, что раз так написано аж в такой массовой вещи, как glibc, то «так надо». Чепуха, так не надо.

                                                          Еще забавный пример: вы в курсе, что такая простейшая вещь, как std::vector, реализована очень сильно неэффективно в некоторых случаях? Почему — да ни почему. Просто так. См. habrahabr.ru/company/infopulse/blog/238131/
                                                            +1
                                                            Тысячи людей заглядывают в код glibc.

                                                            Но вовсе не для того, чтобы посмотреть, насколько эффективно там реализован qsort. Из собственного опыта: заглядывают чтобы посмотреть, почему что-то работает не так, как ожидалось. Это как с openssl: кому она нужна, пока всё работает?

                                                            Почему никто не пишет в рассылку «ребят, а почему в вас так неправильно хеш-таблица реализована? Сортировка?»

                                                            Не знаю как в glibc, а в musl пишут.
                                                            Почему так мало — потому что очевидным ответом из списка рассылки на подобное заявление будет: «предложите лучшее и предъявите подтверждения, что оно действительно лучше». Такой ответ наверно отсеет 99% искателей лёгкой наживы: одно дело сказать, что всё плохо, другое дело — исправить, чтобы работало у вас. А чтобы показать, что при этом ничего не сломалось, может потребоваться в разы больше работы, чем чтобы просто исправить.
                                                              +3
                                                              Кстати, автором предлагаемого по ссылке GrailSort является хабраюзер Mrrl
                                                                +2
                                                                Mrrl крут, это факт.
                                                              0
                                                              Почему никто не пишет в рассылку «ребят, а почему в вас так неправильно хеш-таблица реализована? Сортировка?»

                                                              Пишут, постоянно пишут люди: вот я прочитал/придумал новый супер алгоритм, давайте его вставим. С такими библиотеками проблема в том, что они должны одинаково хорошо работать для всех миллионов пользователей, для тысяч типов задач. И значит надо доказать, что новый алгоритм никогда или почти никогда будет не хуже чем старый. Вот тут и начинаются проблемы. Потому что обычно эти алгоритмы показывают сильное улучшение в каком-то классе задач, важном для автора, ценой ухудшения на других классах.

                                                              И вы упомянули хороший пример с хэш-таблицами. Да, во многих классах задач реализация хэш-таблиц из стандартной библиотеки не самая лучшая. Но она универсальна. А другие — нет. У меня была одна программка, производительность которой ограничивалась производительностью хэш-таблицы. Так вот я попробовал несколько «супербыстрых» реализаций, и ни один из них не дал ускорения в моей задаче. А знаете какая структура данных оказалась самой быстрой в итоге? Так ругаемый и считающийся сверхмедленным vector<bool>. Вот такие дела.

                                                              Про вектор:
                                                              Извините, но почему вы считаете, что неэффективно? Есть и другие мнения на этот счет. Разница, если и есть, очень мала. А многие аллокаторы лучше работают на размерах блоков, равных степени двойки. И переиспользование памяти на самом деле довольно маловероятно, потому что для него нужно, чтобы во время роста вектора в этом куске памяти не произошло никакое другое выделение. И FBVector полагается на особенности их аллокатора. И даже они сами не приводят убедительных тестов производительности (или я не нашёл).

                                                              Кстати, с FBVector вы похоже попадаете в ту же самую ловушку. Почемы мы должны верить авторам FBVector что он на самом деле сильно лучше? Только потому что они работают в фейсбуке? Я не нашёл в сети независимых тестов подтверждающих сильное превосходство. То что я видел — прирост производительности на ~5 процентов.
                                                                0
                                                                Пишут, постоянно пишут люди: вот я прочитал/придумал новый супер алгоритм, давайте его вставим. С такими библиотеками проблема в том, что они должны одинаково хорошо работать для всех миллионов пользователей, для тысяч типов задач. И значит надо доказать, что новый алгоритм никогда или почти никогда будет не хуже чем старый. Вот тут и начинаются проблемы. Потому что обычно эти алгоритмы показывают сильное улучшение в каком-то классе задач, важном для автора, ценой ухудшения на других классах.

                                                                Это, кстати, тоже важное (и вредное) искажение: все, что уже закоммичено в основной код, тут же покрывается слоем золота, мол это проверенное временем, гибкое решение… Даже измысливаются сотни клиентов, которые завязались на производительность этого кода в неких специальных случаях, про которые даже никто не знает.

                                                                Допустим, новая сортировка быстрее в 80 случаях из 100 — и что, не менять, потому что оставшиеся 20 могут «пострадать»? Это, простите, шовинизм какой-то, по отношению в новому коду.

                                                                И вы упомянули хороший пример с хэш-таблицами. Да, во многих классах задач реализация хэш-таблиц из стандартной библиотеки не самая лучшая. Но она универсальна. А другие — нет.
                                                                Эти фразы значат то же самое, что «хеш-таблица в стандартной библиотеке, такая, какая она есть, потому что так надо». Яркий пример искажения, которое повлияло и на вас. Чем конкретно она универсальнее других хеш-таблиц?

                                                                У меня была одна программка, производительность которой ограничивалась производительностью хэш-таблицы. Так вот я попробовал несколько «супербыстрых» реализаций, и ни один из них не дал ускорения в моей задаче. А знаете какая структура данных оказалась самой быстрой в итоге? Так ругаемый и считающийся сверхмедленным vector bool. Вот такие дела.
                                                                Ну если вам нужна была прямая адресация, действительно, зачем брать хеш-таблицы.

                                                                Про вектор:
                                                                Извините, но почему вы считаете, что неэффективно? Есть и другие мнения на этот счет. Разница, если и есть, очень мала.
                                                                Опять вы меня незаметными движениями пытаетесь подвести к мысли, что лучше бы я не лез в стандартную библиотеку со своими рацпредложениями.

                                                                А многие аллокаторы лучше работают на размерах блоков, равных степени двойки
                                                                Аллокатор стандартной библиотеки glibc (ptmalloc) к ним не отностится.

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

                                                                И FBVector полагается на особенности их аллокатора.
                                                                В чем полагается?

                                                                Я не нашёл в сети независимых тестов подтверждающих сильное превосходство.
                                                                Вероятно, потому что их просто нет. Некому померять банально. У всех и без этого дел невпроворот. Я же говорю, непочатый край работы. Любой может пойти, сравнить и стать молодцом.

                                                                То что я видел — прирост производительности на ~5 процентов.
                                                                По вашему, это слишком мало? Если нет побочных эффектов (а я их не вижу), даже 0,001% прироста — достаточно.
                                                                  0
                                                                  Во-первых, хочу прояснить свою позицию. Я не считаю, что не стоит улучшать известные библиотеки. Стоит. Но эти улучшения должны быть хорошо обоснованы, и бремя обоснования ложится на предлагающего.

                                                                  И всегда нужно мерить. И я всегда меряю, прежде чем сделать выводы.

                                                                  Эти фразы значат то же самое, что «хеш-таблица в стандартной библиотеке, такая, какая она есть, потому что так надо». Яркий пример искажения, которое повлияло и на вас. Чем конкретно она универсальнее других хеш-таблиц?

                                                                  Тем, что обеспечивает приемлемую производительность на всех типах операций: вставка, удаление, успешный и неуспешный поиск. «Самые быстрые» хэш-таблицы обычно оптимизированы на какой-то один тип операций — как правило поиск. В моей же задаче соотношение вставок к поиску было примерно 1:2. Я хотел написать статью по этому поводу на хабр, но руки не дошли.

                                                                  Пушим элементы в вектор в цикле. Очень частый случай.

                                                                  Не уверен. По моему опыту, если мы просто пушим в цикле элементы, то можно с некоторой точностью предсказать их количество и вызвать reserve.

                                                                  В чем полагается?

                                                                  В справке же написано, ну и в самом коде можете посмотреть. Используются оптимальные для jemalloc размеры блоков, а также используется расширенный интерфейс xallocx, решающий проблему realloc.

                                                                  Некому померять банально.

                                                                  Ну вот я тогда померял на своих задачах (правда, с glibc аллокатором). Никакого прироста не получил, совсем. Разочаровался.
                                                                    0
                                                                    Не уверен. По моему опыту, если мы просто пушим в цикле элементы, то можно с некоторой точностью предсказать их количество и вызвать reserve.
                                                                    Есть такое. Но тогда и текущий std::vector работает точно так же хорошо. Идея, по-видимому, того же FBVector, в том, чтобы подменить реализацию и ускорить большие объемы какого-то стороннего кода, где не так задумывались о производительности.

                                                                    В справке же написано, ну и в самом коде можете посмотреть. Используются оптимальные для jemalloc размеры блоков, а также используется расширенный интерфейс xallocx, решающий проблему realloc.
                                                                    А, ну да, я читал про это, но запамятовал. Тут просто дело в том, что у jemalloc большая internal fragmentation, и их вектор это учитывает, чтобы не тратить память зря. У стандартного аллокатора с этим сильно лучше, поэтому эту оптимизацию fbvector можно просто исключить под ptmalloc, что не умалит других преимуществ fbvector.

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

                                                                    Ну вот я тогда померял на своих задачах (правда, с glibc аллокатором). Никакого прироста не получил, совсем. Разочаровался.
                                                                    Если у вас везде, где надо, есть reserve() — вы и не могли ничего получить. Потому что просто индексацию все-таки невозможно как-то сделать медленнее, чем надо.
                                                                    0
                                                                    Это, кстати, тоже важное (и вредное) искажение: все, что уже закоммичено в основной код, тут же покрывается слоем золота, мол это проверенное временем, гибкое решение… Даже измысливаются сотни клиентов, которые завязались на производительность этого кода в неких специальных случаях, про которые даже никто не знает.


                                                                    Я не знаю, откуда вы берёте свои примеры, надеюсь всё-таки из реальзой жизни, просто из областей, к которым я не имею отношения. В тех областях, которыми я занимаюсь действуют вполне разумные правила. Вот, например, что Торвальдс говорит о регрессиях в ядре: lkml.org/lkml/2015/1/7/807
                                                                      0
                                                                      Я говорю не про ABI а про производительность. Якобы кто-то завязывается на производительность конкретного метода при конкретных входных данных. Что по сути == завязывается на реализацию. То есть, выясняется, что раз кто-то завязывается на реализацию, мы больше не можем ее менять. ок.
                                                                        0
                                                                        Торвальдс приводит изменение ABI как очевидный пример, потому что тред по ссылке начался с изменения файла в /proc. Но он говорит об общем принципе:
                                                                        if it turns out that applications (or hardware) that people use
                                                                        end up breaking noticeably, then *that* is a regression.

                                                                        And the important part there are those weasel-words: «that people use»
                                                                        and «noticeably»


                                                                        У вас есть реальные примеры того, как что-то «измысливается», или аргументации «якобы кто-то завязывается»? Потому что иначе вы сами, получается, прибегаете к подобной аргументации.
                                                                          0
                                                                          Конкретные примеры: сортировка и хеш-таблицы. Которые новыми методами быстрее в большинстве случаев, медленнее — в меньшинстве. Это называется «универсальностью» старых методов. Хотя если бы гипотетически именно новые методы были бы изначально в библиотеке, то менять их на старые даже никто бы не предложил, потому что они давали бы замедление в большинстве случаев.
                                                                    +2
                                                                    Если подходить с точки зрения пользователя, имеющего возможность выбирать между стандартным и своим алгоритмами, то дело выглядит так.
                                                                    В случае сортировки:
                                                                    — если мне надо сортировать большой массив, или маленькие массивы, но редко — то я не буду пользоваться своими алгоритмами. Запущу стандартный Sort, если позволяет ситуация.
                                                                    — если стандартный Sort не очень удобен, например, когда надо отсортировать в C# маленький фрагмент массива по лямбда-выражению (такого вызова они не предусмотрели), то напишу 5 строчек квадратичного алгоритма.
                                                                    — свой алгоритм (не универсальный!) буду писать в трёх случаях:
                                                                    — — когда понятно, что нужна поразрядная сортировка (по ключу, или по всему значению);
                                                                    — — когда потребуется какой-нибудь вариант внешней сортировки.
                                                                    — — когда исходные данные уже находятся в какой-то структуре, позволяющей сделать сортировку более эффективной.
                                                                    Во всех этих случаях алгоритм будет специфичным для конкретной задачи, и предлагать его в стандартную библиотеку смысла не будет.
                                                                    В случае хэш-таблицы:
                                                                    Написать свою реализацию мне захотелось, например, когда ключ был гораздо длиннее значения. Кроме того, они имели фиксированный размер, и хотелось держать их в одном большом массиве (занимавшем почти всю доступную память). Разумеется, использовалось внутреннее разрешение коллизий (тем более, что удаления элементов в программе не было).
                                                                    Про вектор не знаю. Мне либо хватает си-шарпного List (который имеет те же свойства), либо я завожу массив, который при необходимости перезахватывается (копировать старые элементы мне не нужно, а массив хочется иметь под рукой, чтобы не дёргать сборщик мусора).
                                                                    Но если вдруг рабочей структурой окажется односвязный список объектов фиксированного размера, я реализую его на большом массиве (или списке массивов).
                                                                    В общем, всё сильно зависит от того, насколько «центральной» является обсуждаемая структура. И получается, что либо хватает стандартного решения, либо придётся писать что-то с учётом специфики задачи. Осчастливить всё человечество в обоих случаях не получается.
                                                                    0
                                                                    А какую реализацию хэш-таблиц для C или C++ вы могли бы порекомендовать?
                                                                      0
                                                                      Я не особо знаком с ландшафтом библиотек под C/C++. Вот про Java я бы мог вам много чего рассказать…

                                                                      У меня есть довольно четкое представление, как должны быть реализованы таблицы, в зависимости от:
                                                                      — intrusive/linked ключ
                                                                      — intrusive/linked значение
                                                                      — размера ключа, значения, в байтах
                                                                      — размера таблицы
                                                                      — основного паттерна использования (как вы упомянули, put/get соотношение)

                                                                      Не все, но многое из этого можно в принципе сделать шаболонными параметрами, т. е. реализовать прямо в unordered_map.
                                              +4
                                              Что значит по вашему «оптимизирована»? Самый главный уровень оптимизации — это сама суть алгоритма.
                                                0
                                                Тут имеется ввиду конкретная вещь — 2 опорных элемента вместо одного
                                                0
                                                Вот очень интересная статья о том, как оптимизировали алгоритм быстрой сортировки на Си:

                                                Вообще можно придумать бесконечное количество модификаций квиксорта, которые будут предпочтительны в зависимости от языка программирования и железа. Потому что там надо не только считать количество сравнений и перемещений (dual pivot делает меньше сравнений, но больше перемещений, чем классический квиксорт), но и учитывать выпадения за кэш процессора и тому подобные эффекты.

                                                Я не нашел сравнения сишного dual pivot quicksort c хорошо вылизанным one pivot quicksort из первой статьи. Буду благодарен за ссылку.
                                                  0
                                                  Вот письмище Ярославского с реализацией его модификации алгоритма, с доказательствами и ссылками: permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
                                                    0
                                                    Спасибо, познавательно, но я спрашивал про сравнение именно на Си. Там могут возникать хардверные эффекты (кэш процессора, конвейеризация и т. п.), благодаря которым более просто устроенные алгоритмы будут в реальности работать лучше более сложных. Виртуальная машина такие штуки, наверняка, сглаживает.

                                                    Раз dual pivot включен в Java вместо Bentley-McIlroy, то вопросов по производительности в Java нет.
                                                      0
                                                      В Java он сортирует примитивные массивы, работа на индексах компилируется практически в то же самое, что и на Си. Поэтому если сортировка этим алгоритмом массива примитивов на Java быстрее -> с очень большой вероятностью она быстрее и на Си.
                                                        +3
                                                        Написанная на коленке реализация Dual Pivot обходит std::sort с дефолтным сравнением (это самый жёсткий случай — его победить очень тяжело) примерно на 10-15%. Проверялось на случайных массивах случайной длины от 50 до 100 миллионов целых чисел.
                                                        Вот табличка результатов по 10 тестам:

                                                        N        dual  merge std::sort inplace  dual  merge std::sort inplace
                                                        53928959 6485  7088    7315      7168   4.682 5.117   5.281   5.175
                                                        69807231 8483  9386    9640      9300   4.664 5.16    5.3     5.113
                                                        73984767 9069  10012   10234    10123   4.689 5.177   5.292   5.234
                                                        81071871 10322 10995   11294    11309   4.846 5.162   5.302   5.309
                                                        82337663 10112 11170   11443    11351   4.671 5.159   5.285   5.243
                                                        85282815 10491 11622   11820    11592   4.669 5.173   5.261   5.159
                                                        86380287 10609 11758   12096    11753   4.658 5.163   5.311   5.161
                                                        92177919 11373 12626   12927    12831   4.663 5.177   5.3     5.261
                                                        93555143 9555  11478   13087    12834   3.857 4.633   5.283   5.181
                                                        98161567 12179 13406   13735    13701   4.673 5.144   5.27    5.257
                                                                 
                                                        average  9867  10954   11359    11196   4.607 5.106   5.288   5.209
                                                        rel.avg  0.8687 0.9643   1     0.9857  0.8712 0.9656  1       0.985
                                                        


                                                        Сравнивались четыре алгоритма: dual pivot, mergesort (с дополнительной памятью), std::sort и inplace merge sort (тщательно оптимизированный для конкретного компилятора и процессора). В первой колонке — число элементов N, в следующих четырёх — время на сортировку T (в миллисекундах), в последних четырёх — величина T/(N*log_2(N)) (в наносекундах). В двух последних строчках — усреднённые значения: абсолютные и поделённые на среднее для std::sort.
                                                          0
                                                          Ну на случайных и больших массивах dual pivot давит просто асимптотическим обоснованием — потому что 3 ближе к e, чем 2. Все таки совсем случайные и большие массивы — не самый частый случай. Когда говорят об универсальности проверенных решений, обычно упоминают классы полу-граничных случаев, типа частично отсортированные массивы, массивы с малым количеством разных встречающихся элементов, массивов с креном частоты значений, массивов сравнительно маленького размера (но большего, чем порог на сортировку вставками).
                                                            +3
                                                            Вот результат для девяти типов массивов: случайный; с двумя, восемью и 64-мя разными значениями, с отсортированными блоками по 7 и по N/7 элементов, полученный из отсортированного с помощью N/2 и N/64 случайных обменов, и с 256 значениями с вероятностями 1:3:5:...:511.
                                                            Видно, что на самом интересном случае — когда 2 различных элемента — std::sort работает в разы быстрее всех. Так что отказываться от него никто не будет.

                                                            Method       Dual Merge std::sort Inplace
                                                            Random       5316 6849  7528      7381
                                                            2 values      939 2386   344      2927
                                                            8 values     1142 3387   795      3727
                                                            64 values    1557 4018  1569      4314
                                                            Short Blocks 6246 6915  7409      7403
                                                            Long Blocks  3215 2084  3361      5041
                                                            N/2 Swaps    5268 5693  7110      6799
                                                            N/64 Swaps   1577 2321  1874      3659 
                                                            Unbalanced   2103 4382  2078      4609
                                                            

                                                              0
                                                              Про интересный случай — это ирония?
                                                                0
                                                                Ирония, или сарказм — не знаю. Я их не очень различаю.
                                                                0
                                                                Я смотрю, даже с восемью значениями классика быстрее.

                                                                Может во время первого же выбора опорных элементов забацать эвристику — если хотя бы 2 элемента из 5 совпали по значению, переключиться на 1 опорный элемент.
                                                                  +1
                                                                  На самом деле, там была ошибка — считалась не та версия dual pivot, не рассчитанная на одинаковые элементы.
                                                                  То, что было написано в статье — с эвристикой «если средняя часть всего на 13 элементов короче исходного массива, то после разделения ищем опорные элементы по всей средней части», мне показалось странным. Я попробовал по-другому: если опорные элементы различны — то в среднюю часть кладём то, что строго между ними, а если одинаковы — то делим на «меньше — равно — больше». В этом случае при малом числе разных элементов время dual и std::sort совпадает, а в остальных случаях dual выигрывает. Но это всё на массиве фиксированной длины 55555555 элементов. На маленьких я пока не тестировал.
                                                                  +2
                                                                  После нескольких магических пассов табличка приобрела следующий вид:
                                                                               dual       merge     std::sort   inplace
                                                                  Random       5617        7575        7818       7732
                                                                  Two_Values    347        2614         378       3117
                                                                  8_Values      760        3571         820       3999
                                                                  64_Values    1489        4253        1632       4722
                                                                  Short_Blocks 5482        7292        7634       7752
                                                                  Long_Blocks  2332        2353        3498       5374
                                                                  Half_Swaps   5017        6072        7385       7187
                                                                  N/64_Swaps   1499        2487        1904       3845
                                                                  Unbalanced   1796        4564        2159       4899
                                                                  Len=10        513        1767         835       1263
                                                                  Len=100      1289        2142        1764       2558
                                                                  Len=1000     2024        2945        2838       3539
                                                                  Len=10000    2755        3772        3921       4326
                                                                  Len=100000   3506        4797        4943       4856
                                                                  Len=1000000  4248        5843        6035       5926
                                                                  Len=10000000 5008        6746        7017       7085
                                                                  

                                                                  Здесь Len=10,...,Len=10000000 — сортировка фрагментов большого массива, имеющих указанную длину.
                                                                  Что было сделано:
                                                                  1) оказалось, что для dual sort сортировка идёт быстрее, если массив делится (в среднем) в отношении 2:1:3 — т.е. из 5 элементов я беру не 2-й и 4-й, а 2-й и 3-й.
                                                                  2) подглядел, что делает std::sort на коротких массивах. Там идёт сортировка простыми вставками, реализованная не обменами, а перемещениями. Переход на такую сортировку немедленно дал 10% выигрыша.
                                                                  3) операция разделения выполняется в два приёма — и тоже не обменами, а перемещениями. В обычном qsort этот приём не работает, так как приводит к катастрофе в случае одинаковых элементов. В случае dual pivot есть практически бесплатное лечение этой проблемы.
                                                                  Итого — выигрыш во времени у std::sort составляет от 8 до 30%. Единственное, что смущает — что quick sort с одним разделяющим элементом, написанный в том же стиле, работает всего на 1-2% медленнее (в качестве разделяющего берётся второй элемент из 5 — он даёт деление в отношении 1:2). За счёт чего dual pivot работает быстрее, не понимаю. Возможно, из-за того, что два элемента из пяти ищутся в одном блоке из 8 сравнений.
                                                                    +1
                                                                    Кстати, в Boost недавно приняли новую библиотеку Sort. Там пока только один алгоритм — вариант поразрядной сортировки. Мне кажется можно туда предложить вашу GrailSort и вот эту dualpivot тоже.
                                                                      0
                                                                      Деления на 2:1 и 2:1:3 какие-то подозрительные. Ведь с точки зрения математики, асимпотически надо делить как можно ровнее.
                                                                        +1
                                                                        Там фокус в том, что для минимизации числа сравнений надо делить как можно ровнее, а для минимизации числа обменов — наоборот, как можно более криво. Киллер-пример, когда каждый раз отщепляется 1 (или 2, или 3 элемента — в зависимости от стратегии выбора) даёт вообще O(N) обменов.
                                                                        Насчёт разницы 1:2 и 1:1:1 вообще смешно. По числу сравнений один шаг dual pivot работает столько же, сколько два классических шага — сначала делим с помощью первого элемента массив в отношении 1:2, а потом длинную часть как 1:1 — получим те же 5/3*N сравнений, что и в одновременном разделении. По обменам одновременное разделение могло быть лучше, но я пользуюсь более дешёвым способом — пересылками с использованием временной переменной и свободной ячейки. Одновременное разделение в этом случае будет чуть хуже.
                                                                        Парадокс в том, что когда мы разделили массив в отношении 1:2, делить вторую часть именно как 1:1 смысла уже нет — для неё лучше использовать оптимальное (при заданном отношении стоимостей сравнения и пересылки) отношение. Single pivot 1:2 даёт для целых чисел лучшее решение, чем 1:1, поэтому можно было ожидать, что double pivot 3:2:4 будет ему эквивалентен, а остальные хуже. Но такое я реализовывать не стал (пришлось бы искать 3-й и 5-й элементы из 8), а проверил 2:1:3 (для него ничего не надо переписывать) и 2:1:2 (2-й и 3-й из 4). 2:1:3 оказалось лучше, чем 1:2, а 2:1:2 — хуже. Правда, разница там идёт на 1-2%, так что надёжно измерить непросто.
                                                                    +1
                                                                    Кстати, вместо вставок лучше использовать расчёску. Код у неё ненамного длиннее, но работает быстрее. Порог можно поставить, например, 32.
                                                                      0
                                                                      Может, раз массивы фиксированной длины, взять соответствующие оптимальные сортирующие сети?
                                                                        +1
                                                                        Сортирующие сети тоже не всегда эффективны. Они построены на обменах, а обмен — это две пересылки (пары команд Load/Store). И, насколько я понял, число сравнений в них не минимально, даже для 5 элементов.
                                                        +5
                                                        Каких результатов добились Вы в своей области (я так понимаю, в базах данных)?
                                                          –9
                                                          Ахаха, «сперва добейся»? :) Не ожидал почему-то получить такой комментакий к этому посту.
                                                            +10
                                                            Вы в своем после предложили некоторую последовательность действий, которая предположительно приведет к результату. Возникает вопрос — приводила ли она хоть кого-нибудь к нему. Видимо, ваш ответ — нет?
                                                              –8
                                                              Вот с чего вы сделали такой вывод? Мне даже обидно. Джон Ресиг, Рич Хики, Сальваторе Санфиллипо, например, прошли по самому сложному пути. Стать контрибьютором популярного проекта можно вообще даром.
                                                                +7
                                                                Кажется вас хотели спросить не как теоретика, а как практика, лично вами какой метод был испробован и к каким результатам он привел?
                                                                  –3
                                                                  Могу сказать, что иду по этому пути, и не сомневаюсь в успехе, если не случится ничего непредвиденного, не поменяются жизненные приоритеты, не уеду курить бамбук в лес, например.
                                                                    0

                                                                    Если кто-то читает этот пост сейчас: в течение года я стал одним из основных разработчиков одного очень заметного data processing / data store проекта, без какого-то сверхусилия, просто планомерно работая (пусть мне и платили за эту работу).

                                                                      0

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

                                                                0
                                                                Я думаю, что людей должен направлять человек, который основывается на личном опыте. Например, книги для предпринимателей пишут те, кто добился чего-нибудь существенного в этом деле.

                                                                Поэтому, верно, «сперва добейся».
                                                                  +1
                                                                  (Троллинг имеет отвратительное свойство — если на него «не повестись», дураком все равно будут считать тебя. Ну ок.)

                                                                  «Сперва добейся» не имеет оправдания, никогда. Запомните это. Спорьте с тем, что я сказал, а не с моей личностью. При этом, заметьте, я не требую от вас, в свою очередь, быть гуру разработки, чтобы поспорить со мной.

                                                                  Давайте я попрошу Игоря Сысоева, Алексея Степанова, Константина Осипова или Романа Гущина (на ваш выбор; выборка случайна, это первые, кто пришел мне в голову) подписаться под моим постом или опровергнуть его. Может, тогда вам станет спокойнее.

                                                                  Для начала, разберу их возможные опровержения: я добился чего-то, потому что

                                                                  — я гений. (Не отрицаю гениальность в программировании; считаю гениями Митричева, Короткевича, Кармака, если хотите; но не буду их спрашивать)

                                                                  — я положил здоровье, семью и 20 лет жизни на это. (См. «Вы и ваша работа»; В науке надо класть, в разработке — еще нет)

                                                                  — мне изрядно повезло. (Цукерберга спрашивать не буду)

                                                                  — когда я начинал, еще не было такой конкуренции, как сейчас. (не спрашиваю Торвальдса; ага, конкуренция за то, чтобы исправить миллионы недостатков в популярных проектах, просто дикая)
                                                                    +1
                                                                    «Сперва добейся» не имеет оправдания, никогда.

                                                                    Конечно же, имеет, и да, в дискуссиях он вредит. Но уверяю вас, миллионы людей, читающие хабр, хотят видеть ответы, а не поучаствовать в споре (можете с этим поспорить).
                                                                    А личность (и рейтинг) автора позволяет не тратить время на выяснение истинности описанного — просто поверить в этот раз и пользоваться. Так что, вопрос «Был ли у вас (и какой) успешный опыт в предмете обсуждения» — чрезвычайно важен.

                                                                    Однако, вы правы в том, что спорить люди должны основываясь на репликах, а не на личностях.
                                                                    В случае этого поста, казалось бы, ваша личность значения не имеет — так как вы описываете очевидные вещи, однако, ваш вывод четко дает алгоритм действий для «внесения своего имени в историю». Отсюда и вопрос «стоит ли вам поверить, не проверяя истинности суждения следующие 20 лет»?
                                                                      +1
                                                                      Но уверяю вас, миллионы людей, читающие хабр, хотят видеть ответы, а не поучаствовать в споре (можете с этим поспорить).
                                                                      Надеюсь, я открыл глаза некоторым из этих миллионов на возможности, о которых они не подозревали, но которые могут из заинтересовать. Те, кто поворотят нос от этой информации, только потому что я недостаточно авторитетен — ну, ССЗБ.

                                                                        0
                                                                        Те, кто поворотят нос от этой информации, только потому что я недостаточно авторитетен — ну, ССЗБ.

                                                                        От информации не поворотят, а от вывода — точно поворотят. И если цель поста — мотивация всемирным признанием, то считайте ее не выполненной. Если же основная цель — реклама кучи невыполненных задач в IT, то все ок.

                                                                        P.S. И да, вам жалко чтоли?)
                                                                      0
                                                                      Спорьте с тем, что я сказал, а не с моей личностью.

                                                                      Ненене, Дэвид Блэйн. Вы сделали некоторое предположение, а теперь предлагаете читателям его опровергать. Вместо того, чтобы подкрепить его какими-то примерами, показывающими, что хотя бы иногда оно верно. Читатель вполне праве по умолчанию считать, что предположение ложно.

                                                                      Я вот например сомневаюсь в вашем алгоритме, ибо вы предлагаете «решать сложную проблему в популярной софтине из интересующей области» вместо, например, «решать проблему, которая непосредственно мешает и хорошие решения для которой отсутствуют». В моем варианте у решающего более высокая мотивация решение таки найти.
                                                                        +1
                                                                        Ненене, Дэвид Блэйн. Вы сделали некоторое предположение, а теперь предлагаете читателям его опровергать. Вместо того, чтобы подкрепить его какими-то примерами, показывающими, что хотя бы иногда оно верно. Читатель вполне праве по умолчанию считать, что предположение ложно.
                                                                        Я привел больше дюжины примеров в посте и комментариях.

                                                                        Я вот например сомневаюсь в вашем алгоритме, ибо вы предлагаете «решать сложную проблему в популярной софтине из интересующей области» вместо, например, «решать проблему, которая непосредственно мешает и хорошие решения для которой отсутствуют». В моем варианте у решающего более высокая мотивация решение таки найти.
                                                                        Это пункт 3. б
                                                                        +1
                                                                        «Сперва добейся» не имеет оправдания, никогда.


                                                                        Да, но можно узнать о причинах, по которым «сперва добейся» не произошло.

                                                                        Может, вы не ставили перед собой цели «вписать свое имя в историю разработки ПО». Тогда почему вы вдруг решили об этом написать?

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

                                                                        А может, вы пошли в точности описанным способом, но в результате оказалось, что задачу он не выполняет. И тогда ваш пост вообще вреден.
                                                                          +1
                                                                          Может, я пока не потратил достаточно времени?) Много вы знаете программистов, которые стали известны в 21 год?
                                                                  +3
                                                                  Мануал «как рейдернуть опен-сорс проект» :)
                                                                    +11
                                                                    Хорошо Декарту, или, тем более, всяким древнегреческим математикам, доказывать простенькие теоремки

                                                                    Вам только кажется, что им было легко, мы все просто стоим на их плечах и пользуемся их достижениями.
                                                                      +4
                                                                      Мне не кажется, что им было легко, это небольшое преувеличение для иллюстрации хода мысли. Джобс тоже не продавал прямо собранные в гараже компьютеры, и это некорректно сравнивать с разработкой чипа. И когда Гугл начинался, уже были некоторые другие ПС. И т. д.
                                                                      +3
                                                                      Полно таких задач.
                                                                      Самый простой пример: в PHP нет нормальной ORM корпоративного уровня. Поэтому люди пользуются Doctrine.
                                                                      Написать аналог можно, и по моим подсчетам это будет стоить около $1.2m. Это копейки для компаний, но практически неподъемная сумма для одиночек.
                                                                        +36
                                                                        А еще можно построить машину времени, вернуться в 1995, познакомить Расмуса Лердорфа с какой-нибудь девушкой и, тем самым, спасти мир от PHP.
                                                                          +4
                                                                          Мне кажется, построить машину времени выйдет чуток дороже $1.2m.
                                                                            0
                                                                            Может иноплонетяни хотели отбросить человечество в развитии. Похоже было у Лукьяненко в книге «Лорд с планеты Земля» (только наоборот, там люди использовали машину времени, что бы победить).
                                                                          –11
                                                                          leventov всё правильно я согласен с Вашей статьёй. У меня такая же ситуация нашему правительству ничего не надо. Я создал первую детскую поисковую систему naibox.ru, ходил к губернаторам писал и объяснял что она нужна и полезна для детей, но увы меня никто не услышал. Правительству нужна прибыль и реклама, а я хочу оградить детей от этого и от всяких слежек. Я сейчас работаю и попутно поддерживаю проект. Но потенциала много и есть над чем работать.
                                                                            +43
                                                                            Отличное название.
                                                                              +2
                                                                              дети придумали
                                                                              +1
                                                                              А с чего вы взяли что губернатор вам что то должен? С чего вы решили что ваш поиск лучше того же «спутника»?
                                                                                +1
                                                                                мой проект был реализован на много раньше спутника. когда его даже ещё и не планировали. Сколько потратили на спутник, а я один
                                                                                +3
                                                                                Если бы ваш продукт был востребован, то им бы пользовались. Если им никто не пользуется, значит продукт никому не нужен, и никакой губернатор тут не поможет.
                                                                                  +1
                                                                                  им пользуются он нужен людям и я это вижу. Мне хочется участвовать в программах для молодых специалистов вот я и обращался к губернатору причём денег не прошу сам всё оплачиваю.
                                                                                  +6
                                                                                  Не получилось — обвини плохой мир. Отличная стратегия!
                                                                                    +1
                                                                                    Ну вот, смотрите, Ваш комментарий тут резко заминусован. Вы, я думаю, этого не хотели, но так получилось. А можно было бы проанализировать (хотя бы банальным «этим людям, наверное, не интересно мое нытье») целевую аудиторию (читателей хабра, читателей этого поста по комментариям) и писать в других выражениях и с другим посылом и настроением. К чему это я? А вот к этому: маркетинг, целевая аудитория, психология… Может быть, и проекту Вашему чего-то подобного не хватает? Может быть, Вы неверно себе представляете, как нужно просить деньги, может быть, просите не у тех людей, может быть, на текущий момент этого вообще невозможно добиться, и нужно сначала заработать достаточно денег, а потом тратить их на Ваш проект? Поизучать, что такое бизнес, стартапы, понять, что такое госпрограммы, поискать денег за границей…
                                                                                      0
                                                                                      Пускай минусуют. Мне не жалко. Просто бывает в жизни так что эти минуса им вернуться, но позже, а у кого то будет много плюсов. Но не один + не поставил, а жаль делал и старался для всех хотя бы за разработку. Я пришёл не жаловаться сюда и это главное. Я не ною проект реализован. Вы слышали про программы для ит специалистов например субсидии? Маркетинг конечно нужен согласен, я один. Вот я и хотел собрать аудиторию чтобы мне указали на что то над чем бы я мог работать.
                                                                                        +2
                                                                                        Вот Вам здесь указали — а Вы в ответ опять ноете… Вместо «спасибо, пошел учить матчасть»…
                                                                                      +1
                                                                                      первый раз слышу про данную систему. В чем полезность этой системы для детей я не понимаю. Почему вас должен был услышать губернатор тоже. И более того, не очень понимаю, что губернатор должен был сделать с этим поиском.
                                                                                        +1
                                                                                        Специально в помощь родителям, которые занимают активную жизненную позицию и обучают своих детей современным информационным технологиям, но одновременно стремятся оградить своего ребёнка от нежелательной, негативной информации. Конечно есть недоработки но по мере их устраняю. С поиском делать ничего не надо. То что они по телевизору каждый день отчитываются что ит технологии в регионе процветают, есть инкубаторы в которые можно обратиться, везде отписки только. я лично не вижу
                                                                                          +1
                                                                                          а я не вижу, что вы сделали в этом проекте. Вот вообще не вижу. По мне подобная фильтрация — чушь. Этот поиск — средство защиты от того, чтобы ребенок не узнал значение слова секс и порно? или что? Мат он не фильтрует, берет стандартную выдачу гугла. Стоимость вашего проекта — 0р.
                                                                                            +2
                                                                                            В том же гугле вполне есть режим безопасного поиска. Я его включил на компьютерах/планшетах детей и он вполне приемлемо с задачей справляется (сомнительный контент не появляется в результатах поиска по безобидным запросам). Ну а к тому возрасту, когда они они умышленно захотят поискать что-нибудь этакое, во-первых, им уже будет родителями объяснено что к чему, а во-вторых, никакие фильтры не остановят.
                                                                                          +1
                                                                                          Яков, я правильно понял, что первая детская поисковая систем тупо гуглит (через ajax.googleapis.com/ajax/services/search/web)? Неожиданно.
                                                                                            0
                                                                                            -
                                                                                              +1
                                                                                              попробовал ввести запрос «телки». В чем смысл этого поисковика?
                                                                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                  +1
                                                                                                  мат еще, в именительных падежах и без словоформ
                                                                                              +7
                                                                                              Места для новых стартапов и будущих миллиардных историй, конечно же, полно.

                                                                                              Два момента изменились по сравнению с 90-ми и даже началом нулевых:

                                                                                              — объём кода, который необходимо написать для минимально работающего стартапа, сильно превысил физические возможности одного человека; проще говоря, нужно изначально находить сотрудников, т.е. идти не по пути «пилю по ночам в гараже», а открывать контору со всеми вытекающими;

                                                                                              — самые перспективные тренды — биоинженерия, Internet of Things, дроны-роботы — имеют сильную оффлайн-составляющую; стартап должен, во-первых, иметь человека с компетенцией именно в оффлайн-части, а во-вторых, взаимодействовать в той или иной степени с государственными органами и/или устоявшимися игроками офлайн-рынка; и то, и другое в режиме «пилим ночью в гараже» опять-таки невозможно.

                                                                                              Отсюда, единственное оставшаяся делянка для стартапа — социальщина (мессенджеры, игрушки, приложеньки для вконтакта), но там уже так тесно, что без миллионых маркетинговых бюджетов особо не сунешься.
                                                                                                +1
                                                                                                В стартапы тяжело сунуться, потому что уже все простое есть, нужна команда, и т. д., все что вы описали.

                                                                                                Идея поста в том, что в разработке ПО как раз еще легко завоевать место под солнцем. Вот лет через 30, оглядываясь как сейчас легко было сделать что-то большое, вы будете кусать локти.
                                                                                                  0
                                                                                                  Скажите, а сколько человек разработало тот же jQuery и Angular?
                                                                                                    +2
                                                                                                    jQuery один Ресиг, Angular пара-тройка изначально, потом уже народ подцепили, наверное, еще.
                                                                                                  0
                                                                                                  Концепция стартапов уже приелась. Если хочешь сделать что-то новое и полезное, совсем не обязательно смотреть на это как на стартап. Мы со знакомым, например, как раз «пилим ночью в гараже». Не совсем ночью и не прямо в гараже, конечно, но смысл примерно тот же. Стоит ли делать из этого стартап или что-то другое уже зависит от результата, и вообще это вопрос вторичный.

                                                                                                  Разумеется, процесс разработки отличается от того, как это делалось несколько лет назад. Но необходимость в высокой квалификации как была, так и осталась. К примеру, я не вижу дилетантов среди основателей Apple, Microsoft, Facebook и т.п.

                                                                                                  Объем кода важен, но не критичен. А перспективных трендов нынче десятки, если не сотни. Насчет «социальщины» согласен полностью.
                                                                                                    0
                                                                                                    2048 всунулся без миллионных маркетинговых бюджетов.

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

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

                                                                                                    Если почитать полную биографию большинства инженеров, создавших что-то новое в технологиях и гаджетах, то можно обнаружить, что именно так взлетело очень много.
                                                                                                      +4
                                                                                                      2048, Flappy Bird и подобные поделия — обычный лак.
                                                                                                      0
                                                                                                      объём кода, который необходимо написать для минимально работающего стартапа, сильно превысил физические возможности одного человека; проще говоря, нужно изначально находить сотрудников, т.е. идти не по пути «пилю по ночам в гараже», а открывать контору со всеми вытекающими;

                                                                                                      Прекрасно чувствуют себя многие стартапы, которые были созданы и одним человеком. Тем более в РФ, где конкуренции заведомо меньше.
                                                                                                      +1
                                                                                                      Уведу разговор немного в сторону.

                                                                                                      В посте упоминается ЯП Kotlin как пример современной инновации. Отбросив тот факт, что его пилят не одиночки, а контора под названием JetBrains, и в первую очередь для своих нужд, хочу спросить у знающих людей: а в чём профит использования конкретно этого решения вместо, скажем, Groovy?

                                                                                                      В декабре прошлого года проект vJUG проводил серию видеопрезентаций нескольких JVM-based языков, в рамках которой были представлены как Groovy, так и Kotlin. Презентации велись людьми, близкими к ядру группы разработчиков языков, в частности, Groovy представлял Гийом Лафорж.
                                                                                                      Так вот, из тех презентаций было совершенно не ясно, какова киллер-фича Kotlin и почему стоит бросаться на эту технологию, отвергая более распространённый и уже доказавший свою жизнеспособность Groovy.
                                                                                                        +1
                                                                                                        Статическая типизация.
                                                                                                          +2
                                                                                                          Насколько мне известно, Groovy также поддерживает возможность компиляции с использованием статической типизации. Для этого, если не ошибаюсь, используется специальная аннотация.
                                                                                                          +1
                                                                                                          Kotlin было бы корректнее сравнивать со Scala, а с не с Groovy. Но как написано в документации Kotlin: «Если вы пользуетесь Scala, то Kotlin вам ни к чему».
                                                                                                            0
                                                                                                            Интересное сравнение. Из того, что я понял из упомянутой мной презентации, разработчики Kotlin как раз не хотят позиционировать своё детище как конкурент Scala, вместо этого напирая на компактность рантайма и производительность. Впрочем, наверное, вам виднее.
                                                                                                        –1
                                                                                                        А можно примеры спонсируемых проектов? И можно ли в них зарабатывать столько (конкретно — $150К+ в год), чтобы отказаться от основной работы (по причине нудности последней)? Вопрос не риторический, мне действительно интересно.
                                                                                                          +1
                                                                                                          Любое software as company. Чуть менее, чем все базы данных. Та же самая Java (разработка опен-сорсного проекта OpenJDK спонсируется компанией Oracle). Тот же самый Linux. Те же самые языки программирования (Scala, Go, Rust, Kotlin, Clojure, Groovy).

                                                                                                          Честно говоря, не знаю ни одной конкретной зарплаты в таком проекте, поэтому голое предположение: чуть ниже среднего по рынку платят. Это если чистый наемник в такой проект, или проект большой конторы, типа Mozilla/Oracle/Intel/Google. Понятно, что если стоять рядом с истоками, что-то типа опционов или совладения будет.

                                                                                                          Предположение исходя из того, как раз, что за счет интересности позиции ЗП может быть меньше.
                                                                                                          0
                                                                                                          Про хэш-таблицы соглашусь, mysql совместимая база TokuDB выросла на этой теме, заменим B-Tree более современным алгоритмом.
                                                                                                            0
                                                                                                            После
                                                                                                            Java (пожалуй, самая популярная платформа, на данный момент)
                                                                                                            полез сразу в коменты.
                                                                                                              0
                                                                                                              А какая? Ну, если считать Linux/native платформой, то, может, она и популярнее… Смотря что считать популярностью. Это особого значения не имеет, в glibc, получается, неоптимальностей не меньше, чем в стандартной библиотеке Java.
                                                                                                              +2
                                                                                                              Всегда можно найти новые пути для стартапов. Нужно немного оторваться от того, что уже сделано, и искать новые ниши. Посмотреть где совсем плохо, попробовать там.
                                                                                                              Просто не всегда следует искать стартапы исключительно с миллионными прибылями.

                                                                                                              Если просто есть возможность дать одним людям регулярную зарплату, а другим людям — пользу от вашей деятельности, то количество сфер, где можно что-то сделать увеличивается на порядок.

                                                                                                              Те же социальные сервисы, ну например вебсервис, когда обычный гражданин может подать жалобу на проблемный участок дороги, приложив аттач. Это может быть и проблема с покрытием, и идея по поводу переноса/установки/снятия каких-то знаков. Финансирование такого проекта не слишком высоко, но основная фича — связь с официальными службами, когда 1-2 оператора на основании этих жалоб могут создать корректную юридическую заявку, отправить на аппрув, а получив решение проблемы опубликовать.

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

                                                                                                              В общем в плане электронизации и повышения комфорта коммунальных и гражданских услуг еще просто непочатый океан идей для стартапов. И в каждом городе свой океан.
                                                                                                                0
                                                                                                                Я как-то думал: а что, если сделать систему распознавания дорожных знаков/разметки на записях видеорегистраторов. В идеале — «вшить» её в видеорегистраторы и связать с навигационной системой типа Яндекс-карт. Для Яндекса это будет хорошим сервисом, а для народа — бесплатный GPS-навигатор.
                                                                                                                <Шутка>
                                                                                                                А потом, ещё сделать автоматическое распознавание постов ДПС.
                                                                                                                </Шутка>
                                                                                                                И тут уже — всё украдено до нас — для андройда есть RoadAR.

                                                                                                                Есть теория, что одна и та-же идея приходит одновременно нескольким людям (чаще всего одновременно, иногда с разницей в несколько лет). Поэтому, главное — не сидеть сложа руки, а действовать!

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

                                                                                                              Самое читаемое