Сортировка пузырьком в коде Qualcomm

    Забавной находкой поделился сегодня пользователь fj333 с Reddit. Разбираясь в появившемся год назад проприетарном коде Qualcomm Technologies для Android, он обнаружил, что неизвестный программист решил в production-коде использовать сортировку пузырьком для того, чтобы найти… максимум в массиве.

    Посмотреть исходный файл вы сможете по ссылке на Github или же под катом, а оценить его в работе может любой владелец устройства с Qualcomm Snapdragon 200 MSM8610 под управлением Android.

    Как известно любому, кто знаком с алгоритмами сортировки, сортировка пузырьком — алгоритм учебный, и в промышленном коде обычно не применяющийся в силу своей неэффективности; дело в том, что в наихудшем и среднем случаях он имеет сложность О(n2), к тому же его емкостная сложность в данном случае — O(n). Кого это не убедило — использовать сортировку пузырьком не рекомендует даже Барак Обама.

    И это всё не учитывая того, что для поиска максимума хватило бы и простого перебора.

    #ifndef ABS
    #define ABS(x)            (((x) < 0) ? -(x) : (x))
    #endif
    
    /*==============================================================================
     * Function:           bubblesort
     *
     * Description: Subroutine for sorting 1-D array elements
     *
     * Parameters: double *x    --->   input one-dimensional array
     *             int n        --->   size of input array
     *             int *m       --->   indices of sorted elements
     *============================================================================*/
    void bubblesort(double *x, int n, int *m)
    {
      int i, j, t1;
      double t2;
    
      for(i = 0; i < n; i++)
        m[i] = i;
    
      for(i = 0; i < n; i++) {
        for(j = 0; j <n-1; j++) {
          if(x[j] < x[j+1]) {
            t2 = x[j+1];
            x[j+1] = x[j];
            x[j] = t2;
            t1 = m[j+1];
            m[j+1] = m[j];
            m[j] = t1;
          }
        }
      }
    } /* bubblesort */
    
    /*==============================================================================
     * Function:           absmax
     *
     * Description:
     *
     * Parameters: double *x    --->   input one-dimensional array
     *             int n        --->   size of input array
     *============================================================================*/
    double absmax(double *x, int n)
    {
      int j, *l;
      int index = 0;
      double *y;
    
      l = (int *)malloc(n * sizeof(int));
      if (NULL == l) {
        CDBG("%s: Error mem alloc for l.\n", __func__);
        return -1;
      }
    
      y = (double *)malloc(n * sizeof(double));
      if (NULL == y) {
        free(l);
        CDBG("%s: Error mem alloc for y.\n", __func__);
        return -1;
      }
      for(j = 0; j < n; j++)
        y[j] = ABS(x[j]);
      bubblesort(y, n, l);
      index = l[0];
    
      free(l);
      free(y);
      return ABS(x[index]);
    }

    Проводилось ли Code Review? Об этом история умалчивает…
    Поделиться публикацией
    Похожие публикации
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 120
    • +8
      Отлично!
      • +6
        И было бы совсем замечательно, если бы после сортировки он использовал бинарный поиск для нахождения максимального элемента
          • +1
            А как с помощью ММК можно найти максимум?
              • 0
                Но это ведь немного другая задача) Нам нужно просто найти максимум из выборки. А ММК как бы позволяет создать выборку, с помощью которой можно приближено судить о более сложном, нежели эта выборка, объекте. По вашей же ссылке в самом низу все равно вызываетвся функция max(arg), которая и находит максимум)
                И причем, даже если попытаться приложить ММК сюда, точность метода будет настолько «высока», что эта функция ни одного теста нормально не пройдет) Проще сразу с помощью генератора случайных чисел индекс выбирать)
                • +1

                  Как раз по индусски получается. Из массива на N элементов случайным образом выбираем K, среди которых ищем максимум сортировкой пузырьком. Чтоб тесты почти всегда проходились, делаем K=10*N.

              • 0
                Точно так же как и с помощью сортировки пузырьком найти максимальный элемент )
        • +18
          Проводилось ли Code Review?

          Зачем проводить Code Review для сотрировки методом пузырька? И так сойдёт!
          • +3

            Проводилось, в виде пения и танцев всей командой

            • +2
              Code Review методом сортировки пузырька
              • +1
                Несколько пузырьков (а точнее — пузырей) виновны, что Code Review не сложилось.
              • +3
                Проводилось. Вон как аккуратно всё оформленно, с doxygen-style документацией!
              • +30
                Зато эту сортировку не устают спрашивать на собеседованиях. Вот и прошедший такое собеседование программист отличился.
                • +4

                  Обычно, дальше спрашивают почему не следует его использовать. :)
                  У этого чувака, похоже, не спрашивали ни того ни другого. Сам отличился.

                  • +3

                    Раз такое спрашивают — значит в компании так и кодят :-)


                    А если серьёзно, то для малых массивов пузырёк может оказаться быстрее, за счёт своей простоты. Но для поиска максимум, конечно, никакой пузырёк не нужен.

                    • +1

                      Вроде бы у quicksort не такая большая константа, чтобы скорость пузырька была заметно больше даже на очень маленьких массивах. Или я ошибаюсь?

                      • +1

                        Даже если оно всего в 3 раза медленнее по константе (а там ведь рекурсия, так что, думаю, больше разница), все-равно n log n от n^2 при маленьких n почти не отличается. Так 3 n log n > n^2 при n < 10.

                        • +1
                          Кстати, вы не правы.
                          https://www.wolframalpha.com/input/?i=3*x*log(x),+x%5E2,+x+from+0+to+10
                          Вот если в пять раз то разница действительно есть.
                          https://www.wolframalpha.com/input/?i=5*x*log(x),+x%5E2,+x+from+0+to+10

                          P.S. В целом, мне еще не нравится подход что код для сортировки написан с нуля и нет какой-нибудь отдельной функции вроде sort_little_array которая использовалась бы повсеместно, раз есть задача сортировать маленькие массивы.
                  • +2
                    Вот для того и спрашивают, чтобы программист понимать что там происходит и не радовался хаку вида сортанём и возьмём первый, и париться не надо.
                    • +1
                      Я тоже раньше сортировку спрашивал в контексте медианной фильтрации, а теперь, с подачи Гиктаймс спрашиваю «как проинвертировать три логических сигнала, используя только две операции инвертирования и неограниченное количество „И“ и „ИЛИ“ логики» — это куда как веселее.
                      • 0
                        Del
                        • 0
                          Хорошая задачка. Наверное, даже речь про один инвертор.
                          Сначала не так написал, потом, подумав, исправил.

                          Х =!(A & B & C) // по де Моргану это !A | !B | !C

                          P = X | A | B = !C
                          Q = X | A | C = !B
                          R = X | B | C = !A

                          смета: 1 инвертор, 1 тройной «и» (или два двойных), 5 двойных «или» либо 3 двойных и один тройной…
                          Собственно, по этому принципу можно одним инвертором сколько угодно сигналов инвертировать, надо полагать…
                      • 0
                        так может это как раз тот кто их проводит
                        • +2
                          Да-да, так и видится:

                          "- Расскажите несколько слов о методе сортировки пузылька?
                          — О, хорошо что вы спросили! На прошлом месте я именно так и делал большинство задач. Вот у вас какой телефон? Андроид? Отлично, значит, у вас в руках пример того, как эффективно я решал задачи этим методом!"

                          И ведь впечатлит он этой речью!
                        • +5
                          Не зря на собеседованиях спрашивают пузырек! Нужен! Нужен он! :)
                          • +3

                            "ну наконец-то пригодилось то, что спросили на собеседовании!", — ликовал тот программист ))

                          • +5
                            Работает, ну и ладно!
                            • +2
                              Экий затейник…
                              • +7
                                Как известно любому, кто знаком с алгоритмами сортировки, сортировка пузырьком — алгоритм учебный, и в промышленном коде обычно не применяющийся в силу своей неэффективности
                                Неверно. Для маленьких массивов она более эффективна — вот если нужно сортировать миллион массивов по 10-100 элементов, то пузырёк — прекрасный кандидат. Более того, если производительность не стоит во краю угла, а библиотечная сортировка недоступна по той или иной причине (например, для кода микроконтроллера), то пузырьковая или линейная сортировки будут отличным выбором.
                                • +2
                                  Всё верно там написано. Пузырьковая сортировка — это чисто учебный алгоритм, потому что он предельно понятен на «бытовом» уровне восприятия. Но в реальном коде его не нужно применять нигде, потому что она крайне неэффективна.
                                  И даже если массив мал — все равно не нужно. Для этих случаем есть другие алгоритмы, столь же простые, но все же более эффективные (вставки, сортировка выбором, етц).
                                  • 0

                                    Более эффективные с точностью до константы? :) Ага, а особенно, вставкой.
                                    С другой стороны, если бы этот перец вместо пузырька использовал сортировку выбором то, возможно, догадался бы выкинуть внешний цикл и максимум получил бы естественным образом :).

                                    • +1
                                      Ну да, до константы. Когда данных мало, константа зачастую важнее асимптотики.

                                      Вставки действительно не самый удачный пример, если речь идет про сплошной массив (это скорее метод для списков). А вот выбором отличный метод — очень понятный, естественный и совершенно точно быстрее пузыря.
                                      • +3

                                        Как раз insertion sort самый быстрый для небольших массивов. В большинстве серьёзных алгоритмов сортировки в конце рекурсии переключаются именно на него. Быстрее только сортирующие сети.

                                        • +2

                                          На массивах из трёх элементов? Или на четырёх ещё тоже? ;)
                                          Там проще развернуть циклы любой простой сортировки и выкинуть лишнее. Получится примерно одно и тоже. Полагаю, оптимизатор так и делает иногда :).

                                          • 0

                                            Примерно до 15-20 элементов. Смотреть например тут.


                                            Там проще развернуть циклы любой простой сортировки и выкинуть лишнее

                                            Первое просто, а вот второе совсем нетривиально. Компилятору это не под силу. Даже ученым-людям сети сортировки (опримальный результат выкидывания лишнего) размеров порядка 20-30 стали известны совсем недавно.

                                  • +4

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

                                    • +7
                                      У пузырька все плохо, потому что он делает много лишних перемещений данных. Есть алгоритмы столь же простые и понятные, но все равно гораздо эффективнее.
                                      • +3

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

                                        • 0
                                          Зато он их делает для соседних элементов, которые чаще всего находятся в одной кэш-линии. В итоге десяток «лишних» перемещений в пузырьке на практике могут сработать быстрее, чем одно перебрасывание крайних элементов в quicksort. На массивах до пары сотен элементов вполне может быть практический профит.
                                        • 0
                                          Не всё у него плохо — пузырёк устойчив. В случае почти отсортированного массива на входе, он будет делать очень мало лишних перемещений.
                                          • +1

                                            Зато все такое же огромное количество сравнений.

                                            • +1
                                              Если вход почти упорядочен, то получим много-много чтений из одной кэш-линии, cmpz с переходами (почти) по одной ветке (предиктор ветвлений отработает) и мало-мало записей. По сути — копеечные операции.

                                              На практике не занимался сравнением производительности сортировок в вырожденных случаях, но Сэджвик пишет, что пузырёк решает на почти упорядоченных входах. Склонен ему верить.
                                              • +3
                                                На практике не занимался сравнением производительности сортировок в вырожденных случаях, но Сэджвик пишет, что пузырёк решает на почти упорядоченных входах.
                                                Это если пузырёк нормально написать. В данном случае всё сделано максимально криво и сложность работы всегда такая же, как в «максимально вырожденном случае».
                                      • +1
                                        на сколько помню, второй цикл в другую сторону крутить надо — меньше перестановок. Зависит от направления сортировки
                                        • +1
                                          Это уже шейкерная сортировка
                                        • +8
                                          В играх серии Unreal Tournament (twitch arena shooter) сортировка пузырьком применяется для сортировки скорборда в матче. Причем эта функции вызывается каждую перерисовку экрана, и при этом все работает отлично. Я даже скажу больше: это идеальный алгоритм сортировки для этой задачи (и он останется таковым, даже если сделать чуть умнее и сортировать только при изменении счета у одного из игроков).
                                          • –27
                                            А что за язык такой точказапятоистый?

                                            double absmax(double *x, int n)
                                            {
                                              if (n<1) {
                                                CDBG("%s: Zero array x length.\n", __func__);
                                                return -1;
                                              }
                                            
                                              double xmax=ABS(x[0]);
                                              for(j = 1; j < n; j++) if (ABS(x[j]) > xmax) xmax = ABS(x[j]);
                                              return xmax;
                                            }
                                            
                                            
                                            • +11
                                              Так-то я не спец, но вроде обычный же Си?
                                            • +46
                                              код сортировки пузырьковой
                                              он распознать не смог с листа
                                              ему давали в детстве мало
                                              Кнута
                                              • +7
                                                Коллеги, вот многие обсуждают что используется именно сортировка пузырьком, но я не пойму зачем здесь вообще сортировка, если найти максимум можно за линию?
                                                • +2
                                                  Вот обновление на систему поставшиь, а там из-за одной замены функции все сразу шустрее стало) человеко-часы программистов спасены и пользователи довольны)
                                                  А вообще, чем быстрее становится техника, тем больше пренебрегают оптимизацией, к сожалению
                                                  • +3
                                                    Именно! Зато документация хорошо написана =))
                                                  • +2
                                                    возможно например нужна задержка при чтении из порта, а подобный код компилятор не упростит.
                                                    Кроме того в коде происходит выделение памяти 2 раза (т.е. это можно использовать для проверки)
                                                    Может быть для целей спецслужб нужно хранить x но для целей прохода проверок это не нужно
                                                    Так возникает массив в памяти абсолютных величин.
                                                    Возможно изначально в коде было все немного иначе, но в результате упрощений…
                                                    • +2
                                                      Тут сомнительно, что в результате упрощений, так как это функция absmax в составе какой-то библиотеки. Там либо копипастилось откуда-то, либо программист не думал. Я знаком с целой группой таких программистов из одной жаркой страны, которые тыкают везде библиотечные функции где не надо, даже если они не очень подходят. При этом код проходит ревью на ура, ибо их там целый отдел. Иногда при наличии свободного времени я провожу выборочные внеплановые проверки и выгребаю пдобные перлы пачками. При этом самое сложное — доказать, что так делать не надо. Работает же, а что касается скорости и эффективности — так на это отдельных требований не было.
                                                    • 0
                                                      Это просто прекрасно!
                                                      for(i = 0; i < n; i++) {
                                                        for(j = 0; j <n-1; j++) {
                                                      

                                                      И не важно, что возможно весь массив был уже давно отсортирован, циклы пройдут до конца =)) До полной наихудшей сложности пузырка. Всегда.

                                                      Если абстрагироваться от идиотского решения и рассмотреть функции беспристрастно то можно еще попридираться.

                                                      Например после сортивки вместо того чтобы вытащить первый элемент отсортированного массива ( в котором лежит нужное число ( абсолютная величина ) — берется индекс, а уже по индексу берется оригинальный элемент и к нему снова применятся отбрасывание знака.
                                                      То есть вместо
                                                      bubblesort(y, n, l);
                                                        index = l[0];
                                                      
                                                        free(l);
                                                        free(y);
                                                      return ABS(x[index]);
                                                      


                                                      можно было бы сделать
                                                      bubblesort(y, n, l);
                                                        ret = y[0];
                                                      
                                                        free(l);
                                                        free(y);
                                                      return ret;
                                                      


                                                      Функция absmax() возврщает double == -1 для сообщения об ошибке. Мне вот лично не нравится использовать значения не целочисленных типов для таких целей.
                                                      • –1

                                                        Кстати, есть прекрасные алгоритмы сортировки — отсортировать только M элементов из N.


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


                                                        Но неужели там не было просто max?

                                                        • +2
                                                          Это видимо выходец из C#, привыкший находить максимум посредством LINQ запросов вроде

                                                          var max = items.Sort().Last();
                                                          • +7
                                                            Фиговый какой-то выходец получился в вашей фантазии. Если уж очень хочется LINQ, то во всех смыслах проще вот так сделать:
                                                            var max = items.Max();
                                                            • +2
                                                              Как регулярно выясняется на собеседовании, в 2017 году многие пользователи LINQ не знают аггрегатных функций.
                                                            • 0
                                                              Это некошерный LINQ, Sort не применишь к IEnumerable. Должно быть items.OrderBy(_ => _).Last().
                                                              • +2
                                                                И вообще, Last() для произвольного IEnumerable не очень хорошо, надо вот так:
                                                                items.OrderBy(_ => _).Reverse().First()

                                                                (Sarcasm mode on, если что :) )
                                                              • 0
                                                                Ну я так, принцип показать ;) Я LINQ-подобные вещи в последнее время только в Kotlin в личных проектах использовал, а на работе больше низкоуровневого C++. Но помню где-то видел подобные перлы
                                                            • –1
                                                              Почитал комментарии… впечатление, чуть ли не каждый, пишет используя идеальные решения и алгоритмы.

                                                              И плевать на условия и причины создания обсуждаемого участка кода…

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

                                                              А если серьезно, только что посмотрел, самый дешевый смартфон (около $35) с процом 1.3ГГц, 512МБ озу… смартфоны среднего ценового диапазона — в два раза выше параметрами… с головой достаточно выполнять подобные операции…

                                                              почитал остальной код в репозитарии… там вообще особо не заморачиваются делать оптимально со стороны потребления ЦПУ\ОЗУ, видимо оно им и не нужно… похоже то что написано — делает свою работу…

                                                              … а может начальник дурак… нам не известны причины такого подхода :)
                                                              • +2
                                                                Идеальных решений для инженерных задач, увы, нет. На то они и инженерные.

                                                                А вот в приведенном примере возмущают, собственно, два факта:
                                                                1. Применение явно наихудшего возможного решения: O(n^2) супротив O(n) при сопоставимых константах.
                                                                2. ВременнАя стоимость реализации этого решения примерно равна стоимости реализации любого другого варианта. Тут не требуется никакого исследования, никаких разработок собственных сложных алгоритмов и т.п.
                                                                • 0
                                                                  поленился парень нормально сделать… трудный день… или год =)
                                                                  • +4

                                                                    Если бы поленился, то сделал бы в один проход. Тут скорее наоборот слишком много свободного времени у не самого опытного программиста.

                                                                    • 0
                                                                      Или писал не программист, а то ли математик, то ли железячник.
                                                                      Знаете, как в анекдоте про математиков — как вскипятить чайник? Если чайник пустой, налить в него воды, включить плиту и т.д. А если чаник полный? Тогда вылить воду и тем самым задача сводится к уже известной, решение которой приведено выше.
                                                                      • +1
                                                                        Тогда вылить воду и тем самым задача сводится к уже известной, решение которой приведено выше.
                                                                        Тут «оптимизирующий математик». Который кипятит воду на костре «оптимально сводя её к предыдущей»: выливая воду в костёр и, тем самым, решая сразу две проблемы: костёр потушен, чайник пуст.
                                                                • +1
                                                                  Тот же шейкер пишется немногим сложнее а сортирует эффективнее.
                                                                  Вот только вопрос не в элегантности решения — сортировка для получения максимального не нужна в принципе
                                                                  • 0
                                                                    Написать линейный поиск максимума ну явно быстрее, чем любую, даже самую простую, сортировку.
                                                                  • 0
                                                                    Мне это по степени странности и кол-ву лишних действий напоминает какой-то старый кусок индусского говнокода, там где человек проверял логическую переменную через строковое преобразование и дополнительный перевод из целочисленного. Вроде такого:
                                                                    lValue по типу сишной логической переменной или вроде того.
                                                                    if (lValue == 1) lTmp = True
                                                                    else if (lValue ==0) lTmp = False
                                                                    else че-то там;
                                                                    if lTmp.ToString.ToUpper == «TRUE» return True else return False;
                                                                    • 0
                                                                      Там было if (strlen())>4
                                                                      • 0
                                                                        И такой вариант тоже видел.
                                                                    • 0
                                                                      Copyright © 2013 Qualcomm Technologies, Inc. All Rights Reserved.
                                                                      Qualcomm Technologies Proprietary and Confidential.
                                                                      Это теперь новая мода такая, заливать на Хабр проприетарный код, да еще и вырезая копирайты?

                                                                      Хоть под спойлер бы убрали…
                                                                      • 0
                                                                        Там же есть корректная ссылка на репозиторий, указано авторство. В чем проблема? Кому нужна шапка?
                                                                        • –1
                                                                          Сами себе противоречите. Если есть ссылка на репозиторий, то зачем копипастить код сюда? А если копипастить код сюда, то зачем вырезать важную информацию об авторских правах и лицензии?

                                                                          Статью просмотрели уже примерно 10 тыс человек, потом какая-то часть из них пойдет писать код для своих, или, что хуже, чужих opensource-проектов, создавая совершенно ненужные риски их владельцам. What has been seen cannot be unseen.
                                                                          • 0
                                                                            Если кто-то воспользуется таким решением, то и проблем он заслужил.
                                                                            • +1
                                                                              Нет никакого противоречия. Вы пишете статью, демонстрируя что-то кодом. Зачем вам весь код, особенно мусорные шапки, которые только отвлекают? Незачем. Вы взяли кусок, оставили ссылку на автора и оригинальный репозиторий — авторские права соблюдены: никто себе авторство кода не приписал.

                                                                              или, что хуже, чужих opensource-проектов, создавая совершенно ненужные риски их владельцам. What has been seen cannot be unseen.

                                                                              Если они скопипастят код прямо с хабра, да еще такой, то поделом.
                                                                              • 0
                                                                                Зачем вам весь код, <...&gt Вы взяли кусок,
                                                                                Это не кусок, это и есть весь код по ссылке. За исключением копирайта.

                                                                                особенно мусорные шапки
                                                                                Dura lex, sed lex. Какими «мусорными» бы законы не были, их надо соблюдать.
                                                                                • 0
                                                                                  Это не кусок, это и есть весь код по ссылке. За исключением копирайта.

                                                                                  Потому что он — ненужный для статьи мусор. Это частный случай, когда модуль короток и весь — чистый шик и блеск. Было бы это 10 строк из 1000 — было бы то же самое.

                                                                                  Dura lex, sed lex. Какими «мусорными» бы законы не были, их надо соблюдать.

                                                                                  Автор статьи не приписал себе авторство и оставил ссылку на оригинал. Все корректно.
                                                                                  • 0
                                                                                    Автор статьи не приписал себе авторство и оставил ссылку на оригинал. Все корректно.
                                                                                    Qualcomm Technologies Proprietary and Confidential.
                                                                                    Вы сейчас серьезно? Тем более, что автор не оставил ссылку на оригинал.
                                                                                    • 0
                                                                                      Абсолютно. Автор статьи на хабре не приписывал себе авторство кода, ссылка на полную версию (под оригиналом я имел в виду неурезанную версию) присутствует.
                                                                                  • +1
                                                                                    Dura lex, sed lex. Какими «мусорными» бы законы не были, их надо соблюдать.
                                                                                    Дык, эта:
                                                                                    Допускается без согласия автора или иного правообладателя и без выплаты вознаграждения, но с обязательным указанием имени автора, произведение которого используется, и источника заимствования: цитирование в оригинале и в переводе в научных, полемических, критических или информационных целях правомерно обнародованных произведений в объеме, оправданном целью цитирования, включая воспроизведение отрывков из газетных и журнальных статей в форме обзоров печати
                                                                                    Где вы несоблюдение законов нашли? Хотите сказать этот под был прочитирирован не в «критических целях»?
                                                                                    • 0
                                                                                      Прочитайте сами еще раз то, что вы написали:
                                                                                      Допускается без согласия автора или иного правообладателя и без выплаты вознаграждения, но с обязательным указанием имени автора, произведение которого используется, и источника заимствования: цитирование в оригинале и в переводе в научных, полемических, критических или информационных целях правомерно обнародованных произведений в объеме, оправданном целью цитирования, включая воспроизведение отрывков из газетных и журнальных статей в форме обзоров печати
                                                                                      А потом то, что написал правообладатель, и что MacIn выше назвал «мусором»:
                                                                                      Copyright © 2013 Qualcomm Technologies, Inc. All Rights Reserved.
                                                                                      Qualcomm Technologies Proprietary and Confidential.
                                                                                      • 0
                                                                                        А потом то, что написал правообладатель, и что MacIn выше назвал «мусором»:

                                                                                        Для статьи вида «смотрите какой странный код попадается» это действительно мусор. Здесь обсуждается алгоритм и его некорректное применение. Авторство кода автор хабрастатьи не оспорил, вы загоняетесь и передергиваете. Если вас смущает распространение кода, помеченного как proprietary и confidential, то тогда непонятна претензия по поводу отсутствия этой пометки в статье: что, от того что вставят p&c, пропадет распространение confidential кода? Тут уж точно противоречие — вы определитесь с тем, что именно вас смущает.
                                                                                        • 0
                                                                                          Код этот тут не нужен вообще, достаточно ссылки. Но если автор считает это настолько важным, то предупреждение необходимо. Тогда читатель, исходя из своих личных убеждений и законов страны, в которой он находится, сможет сам решить, нужно ли ему становится соучастником возможного преступления и нужно ли ему читать чужой проприетарный код, ставя под вопрос лицензионную чистоту своих собственных программ.

                                                                                          Авторство кода автор хабрастатьи не оспорил, вы загоняетесь и передергиваете.
                                                                                          И я не оспариваю того, что он не оспорил. Я только отмечаю в дополнение к вышесказанному, что согласно законам РФ (и большинства других стран) этот код тут просто не имеет права находиться. Ни в виде цитаты, ни в какой-либо другой форме. Но это так, на заметку желающим выше процитировать мне гражданский кодекс.
                                                                                          • 0
                                                                                            Я только отмечаю в дополнение к вышесказанному, что согласно законам РФ (и большинства других стран) этот код тут просто не имеет права находиться.
                                                                                            Проблема только в том, что вы не приводите никаких разумных обоснований к этому тезису.

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

                                                                                            Копирование чужого проприетарного кода может быть проблемой — но равно для этого и вводится норма, которая требует чтобы цитата обязательно сопровождалась указанием авторства и была отделена от остального текста. Ссылок на оригинал при этом не требуется.
                                                                                            • 0
                                                                                              Проблема только в том, что вы не приводите никаких разумных обоснований к этому тезису.
                                                                                              Обоснование — четвертая часть ГК (если мы обсуждаем РФ). Вы привели в контр-пример статью о цитировании, но она тут не действует. В коде написано, что он является собственностью «Qualcomm Technologies», и что это часть ее закрытого проекта. Без разницы, предпринимала компания попытки удалить его, или нет.

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

                                                                                              Чтобы у вас не возникло сомнений в адекватности разработчиков, проект действительно крупный. И вы даже наверняка им хотя бы раз в жизни пользовались. А может, даже пользуетесь постоянно.
                                                                                              • 0
                                                                                                В коде написано, что он является собственностью «Qualcomm Technologies»,
                                                                                                Это, извините, ничего не доказывает. На YouTube — тоже полно материалов с пометками о чьём-то авторстве, однако же подавляющее большинство материала размещено там без нарушения чьих-либо прав и именно это и постулирует закон (американский): вы можете пытаться использовать какие-то подобные метки, чтобы, по косвенным признакам, пытаться «угадать» что-то, но по американскому закону этого не требуется. Пока нет заявления от правообладателя — размещение на площадке провайдера информации считается правомерным.

                                                                                                и что это часть ее закрытого проекта.
                                                                                                Эта часть — вообще к авторскому праву отношения не имеет, как я уже сказал — это вообще о коммерческой тайне и судить за нарушение тут можно вообще только работников Quallcomm'а и тех, кто имел доступ к этому тексту до того, как оно перестало быть тайной.

                                                                                                Чтобы у вас не возникло сомнений в адекватности разработчиков, проект действительно крупный. И вы даже наверняка им хотя бы раз в жизни пользовались. А может, даже пользуетесь постоянно.
                                                                                                Охотно верю — но внутренние правила какого-либо проекта, независимо от его размера, не могут быть заменой закону. Я, по той же причине, например, не могу читать и использовать некоторые документы, которые вообще размещены публично на публичных сайтах — тоже из соображений что наши конкуренты могут использовать это как повод… но это же не значит что теперь всему миру туда смотреть нельзя!
                                                                                                • 0
                                                                                                  На YouTube — тоже полно материалов с пометками о чьём-то авторстве
                                                                                                  Верно, а сразу под ними название лицензии, под которой оно размещено. И написано там обычно что-то вроде «Стандартная лицензия YouTube», а не «Proprietary and Confidential».

                                                                                                  Пока нет заявления от правообладателя — размещение на площадке провайдера информации считается правомерным.
                                                                                                  Насколько я понимаю, речь там идет о другом. Если вы владелец GitHub, и некая редиска залила к вам исходники Windows 10, то вы как бы не при делах, пока Microsoft не обратится к вам с требованием это безобразие удалить. Но это не значит, что эти исходники там какое-то время размещены легально, и вы можете цитировать их «посмотрите, какие в MS говнокодеры».

                                                                                                  Эта часть — вообще к авторскому праву отношения не имеет, как я уже сказал — это вообще о коммерческой тайне
                                                                                                  Это в частности о том, что это не открытый OpenSource-проект. В примере с Windows выше, ее исходники уже утекали в сеть, и на GitHub их наверняка тоже кто-нибудь заливал. Но это не значит, что Windows вдруг стала открытым проектом. Более того, Micorosoft через суд добилась удаления кода с большинства сайтов. И ее совершенно не волновало, что вы там цитировали, что вы там знали/не знали, что там у кого утекало и т. д.

                                                                                                  Я, по той же причине, например, не могу читать и использовать некоторые документы, которые вообще размещены публично на публичных сайтах
                                                                                                  Замечательно, тогда я не понимаю, почему мы до сих пор спорим. Как бы вы отнеслись к тому, что некий HotMusicWater залил бы на Хабр эти документы, удалив при этом надпись «Совершенно секретно», мотивируя это тем, что все и так всем доступно, а надпись все-равно потеряла свою актуальность в связи с утечкой? Напомню, мой самый первый комментарий в этой ветке был:
                                                                                                  Это теперь новая мода такая, заливать на Хабр проприетарный код, да еще и вырезая копирайты?

                                                                                                  Хоть под спойлер бы убрали…
                                                                                                  • +1
                                                                                                    Но это не значит, что эти исходники там какое-то время размещены легально, и вы можете цитировать их «посмотрите, какие в MS говнокодеры».

                                                                                                    Почему не значит? Можете рассказать об ответственности за цитирование исходников не прошедших процедуру публичного обнародования? Не публикации, а именно цитирования.


                                                                                                    Это в частности о том, что это не открытый OpenSource-проект.

                                                                                                    Для того, чтобы быть опубликованным (втч совершенно легально) проекту не обязательно быть открытым опенсорсным.


                                                                                                    Как бы вы отнеслись к тому, что некий HotMusicWater залил бы на Хабр эти документы, удалив при этом надпись «Совершенно секретно», мотивируя это тем, что все и так всем доступно, а надпись все-равно потеряла свою актуальность в связи с утечкой?

                                                                                                    Вы, возможно, не поверите, но вы можете цитировать документы с викиликс. Если мне не изменяет память, на хабре периодически появляются такие статьи.
                                                                                                    В сфере публикаций действуют несколько иные правила и законы, нежели в сфере корпоративного патентного права. Давайте я вас ещё больше шокирую — таким образом совершенно легально иногда можно обойти ограничения на распространение закрытых технологий — почитайте любопытную историю PGP и Циммермана.


                                                                                                    да еще и вырезая копирайты?

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

                                                                                                    • 0
                                                                                                      Замечательно, тогда я не понимаю, почему мы до сих пор спорим.
                                                                                                      Потому что вы пытаетесь внутренние правила некоего проекта превратить, каким-то образом, в закон. Так это не работает.

                                                                                                      Как бы вы отнеслись к тому, что некий HotMusicWater залил бы на Хабр эти документы, удалив при этом надпись «Совершенно секретно», мотивируя это тем, что все и так всем доступно, а надпись все-равно потеряла свою актуальность в связи с утечкой?
                                                                                                      Если бы не было указано авторство? Плохо отнёсся бы — так же как и закон. Если авторство было бы указано и там была бы только цитата? Скорее всего не стал бы читать соответствующую статью, только и всего.

                                                                                                      Напомню, мой самый первый комментарий в этой ветке был:
                                                                                                      Это теперь новая мода такая, заливать на Хабр проприетарный код, да еще и вырезая копирайты?

                                                                                                      Хоть под спойлер бы убрали…
                                                                                                      Именно. И ответ, с которым вы ну никак не можете примириться, таков: нет — это не новая мода, это — нормальное поведение.

                                                                                                      Но это не значит, что эти исходники там какое-то время размещены легально, и вы можете цитировать их «посмотрите, какие в MS говнокодеры».
                                                                                                      Значит. Посмотрите сюда. Что мы тут видим? Кусок совершенно секретного документа. И не просто какого-то там «исходного кода», на который ярлык «confidential & proprietary» навесили «для перестраховки», а документа секретной службы, которая, ну при всём желании, не может быть интерпретирована как «open-source project». И что? А ничего: это цитата с целью критики — а потому ничего с этим сделать нельзя. И даже на секретность ссылаться нельзя, так как документ «утёк» на WikiLeaks и, соответственно, никаких секретов больше содержать не может…

                                                                                                      Почему вдруг Хабр должен быть «святее папы римского»?
                                                                                          • 0
                                                                                            Если оно лежит на GitHub'е и правообладатель не озаботился его отзывом, то по умолчанию считается, что оно там расположено правомерно. И в этом смысле удалённые строки действительно являются «мусором» скорее способным ввести в заблуждение, чем что-либо прояснить. То, что вас возбудило является уведомлением об авторских нравах и «ни о чём таком», несмотря на грозную форму, не говорит.

                                                                                            Фраза «Proprietary and Confidential» — это вообще отсылка к коммерческой тайне, а эта защита, в отличие от авторского права, перестаёт действовать если соответствующий документ «утёк», никакого отношения к авторскому право она не имеет вообще.
                                                                                            • 0
                                                                                              Если оно лежит на GitHub'е и правообладатель не озаботился его отзывом, то по умолчанию считается, что оно там расположено правомерно.
                                                                                              Ух ты, может, у вас еще и ссылочка на закон имеется? Пойду тогда скачивать WRK. И пофиг, что Microsoft запрещает — не удалили за год, значит, правомерно.

                                                                                              перестаёт действовать если соответствующий документ «утёк»
                                                                                              Никакая утечка не отменяет того, что произведение могло быть выложено в нарушение авторских прав.
                                                                                              • 0
                                                                                                Ух ты, может, у вас еще и ссылочка на закон имеется?
                                                                                                Разумеется.

                                                                                                Пойду тогда скачивать WRK.
                                                                                                Я бы не советовал.

                                                                                                И пофиг, что Microsoft запрещает — не удалили за год, значит, правомерно.
                                                                                                Размещение на github'е — правомерно, пока правообладатель не заявил об обратном. А вот создание своих, личных, копий (а не цитат «в целях критики») — таки требует лицензии.
                                                                                                • 0
                                                                                                  Разумеется.
                                                                                                  Вы точно ту ссылку скопировали? У меня по ней открывается статья о DMCA на Википедии. И там нет ни слова о том, что если компания не успела обнаружить нелегальный репозиторий на Github, то он автоматически становится легальным. Да, возможно, пользователя, клонировавшего себе репозиторий, и не заметившего «мусор» в комментариях (либо «мусор» был вырезан тем, кто разместил код), признают пострадавшим и не станут привлекать к ответственности, но это не значит, что репозиторий был легальным. Он им не был, поскольку правообладатель не давал своего согласия на его размещение там.

                                                                                                  Я бы не советовал.
                                                                                                  Я и не собирался. К счастью, у меня есть своя голова на плечах, чтобы не верить всему, что пишут в Интернетах.
                                                                                                  • 0
                                                                                                    И там нет ни слова о том, что если компания не успела обнаружить нелегальный репозиторий на Github, то он автоматически становится легальным.
                                                                                                    А там этого нет — и быть не может. Вы, почему-то, рассматриваете GitHub только как набор Git-репозиториев. А это, кроме всего прочего, ещё и web-сайт, который позволяет вам публиковать текстовые материалы. И как любая площадка он защищён заявкой 512. Её недостаточно для того, чтобы дать вам права на использование кода как, собственно, кода — но достаточно для того, чтобы текст программ, размещённый непосредственно на GitHub'е — мог считаться правомочно там размещённым.

                                                                                                    И этой, ограниченной и урезанной, роли GitHub'а — достаточно для того, чтобы из правомерно опубликованных на нём материалов можно было дёргать цитаты «с целью критики».

                                                                                                    Он им не был, поскольку правообладатель не давал своего согласия на его размещение там.
                                                                                                    Это можно выяснить только пост-фактум. До заявления правообладателя размещение считается законным. Принцип тот же, что и с публикацией комментариев на Хабрахабре: пока нет какого-либо заявления считается, что всё что мы тут понаписали — опубликовано законно и, соответственно, Хабрахабр имеет право наши каракули показывать всему миру не испрашивая у нас с вами письменного разрешения.

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

                                                                                                    А что мне за это будет?
                                                                                                    • 0
                                                                                                      Если просто скачаете — скорее всего ничего. Если начнёте как-то использовать и вас захотят «прощущить» — то штраф до $150'000.
                                                                                • 0
                                                                                  Так а в чем вина кодера? Это менеджерский состав толжен быть покаран. Наверняка времени на просто подумать даже не дали. И потом — под такими постами я вижу десятки разработчиков, которые «нууу, дурачок, мы-то так точно бы не факапнулись». И вот только я читаю такое где-то, как сразу в недрах департамента нахолится какая-нибудь очередная SOAP-апи, с которой надо работать и которая передает внутри себя шифрованный сатанинскими способами JSON-объект.

                                                                                  И вот вопрос — где же все эти гении? Вася, пишущий «ну дурачок» под таким постом и кто-то, кто присылает мне внутри XML шифрованный каким-то сатанинским RIJNDAEL_256 JSON-объект уж не одно ли лицо? Не знаю, но думаю, что без пузырька точно не обошлось.
                                                                                  • 0
                                                                                    Жму руку =)
                                                                                    • +1
                                                                                      Так а в чем вина кодера?

                                                                                      В том, что он идиот?


                                                                                      Это менеджерский состав толжен быть покаран.

                                                                                      За то, что взяли на работу идиота? Вполне возможно.


                                                                                      Наверняка времени на просто подумать даже не дали.

                                                                                      Вы это знаете или просто придумали? И, простите, как вы думаете, сколько времени ему дали? 38 секунд? Полторы минуты? Как вы себе это представляете? "чтобы через полторы минуты был написан код поиска максимального элемента!" И рядом стоит менеджер с секундомером и линейкой, чтобы бить по рукам при выходе за "дедлайн", ага. Ну, что за бред.

                                                                                      • 0
                                                                                        Идиот — возможно это грубо и несправедливо. Может быть просто слишком малоопытный человек, которого насильно здесь и сейчас заставили кодить. А он способен прочитать и понять правильные книги и стать новым Линусом Торвальдсом.
                                                                                        Может это сказка про ASAP?
                                                                                        Да не даёт Богатырю победить Зло лютое одно клятое слово «ASAP». Сколько-то златых монет семье надо ASAP, постоянно. Дабы заработала машина чёртова супостатная, что царь Менеджер требует — ASAP, постоянно. Всю силушку богатырскую ASAP вытягивает, конца да края не видать…
                                                                                        Сказку ту мы пока продолжаем писать, да правнукам, коли сами себя не погубим, будет что рассказать.
                                                                                        • +1
                                                                                          Существует общая обстановка. Я же прекрасно знаю, что можно манипулировать и жонглировать доводами как захочется — сам сто раз так делал и еще тысячу раз сделаю. К примеру, дается вагон задач, из которых большая часть признается несущественной и время пошло. А потом в удобный момент можно предъявить «ты уже простейший функционал Х делаешь полгода». Это просто пример. Но обычно в плохом коде вина именно что менеджеров — лично я сталкивался только однажды с ситуацией, когда виноваты были программисты, а не менеджеры. И вина менеджеров, что я с этим столкнулся.
                                                                                          • –1
                                                                                            и время пошло

                                                                                            Какое прекрасное самооправдание для говнокодинга!


                                                                                            Но обычно в плохом коде вина именно что менеджеров

                                                                                            А, главное, сам говнокодер в этом не виноват. Это всё мееенеджер. Ага. И ещё в подъезде он же нассал. Ой, нет, это же был Обама/Трамп...

                                                                                      • 0
                                                                                        Если бы все программисты писали качественный, быстрый и оптимальный код — нафига было бы столько ядер и гигагерц вы телефонах?

                                                                                        Хотя это мне напомнило код (который я лично разбирал) одного программиста который при поиске строки в текстовом файле даже не удосужился вставить выход из цикла после ее нахождения, при чем ради того, что бы вернуть ровно первые пять символов из уже найденных строкой программы выше, он написал вторую функцию поиска в текстовом файле, так же без досрочного прекращения операции… Ну правда, а что может быть такого в поиске по 10к строкам.
                                                                                        • 0
                                                                                          Если бы все программисты писали качественный, быстрый и оптимальный код — нафига было бы столько ядер и гигагерц вы телефонах?

                                                                                          Для игр и действительно тяжёлых приложений.
                                                                                          • 0
                                                                                            Для игр

                                                                                            Хотелось бы посмотреть количество проданных требовательных игр хотя бы для топов (причем, надо понимать, что программисты не только в обычных программах пишут вот так, в играх им тоже ничто особо не мешает так писать) и сравнить их с объемами продаж топовых смартфонов
                                                                                            действительно тяжёлых приложений

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

                                                                                            Потому что без цифр всегда можно ответить в духе: «Окей, а зачем они остальным, примерно, 99% людей?».
                                                                                        • 0
                                                                                          И что тут такого?
                                                                                          Попробуйте отсортировать по дате ~1000 файлов в диалоговом окне проводника Windows 7.
                                                                                          • 0
                                                                                            Еще и макрос ABS криво сделан.
                                                                                            • 0
                                                                                              Когда я слышу фразу «софт от Квалкома» то сразу вспоминаю вот этот текст https://copypaste.d3.ru/pochemu-moi-telefon-ne-obnovitsia-do-novogo-androeda-1174470

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