Только 10% программистов способны написать двоичный поиск

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

    Алгоритм двоичного поиска похож на то, как мы ищем слово в словаре. Открываем словарь посередине, смотрим в какой из половин будет нужное нам слово. Допустим, в первой. Открываем первую часть посередине, продолжаем половинить, пока не найдем нужное слово.

    С массивами так: есть упорядоченный массив, берем число из середины массива, сравниваем с искомым. Если оно оказалось больше, значит искомое число в первой половине массива, если меньше — во второй. Продолжаем делить оставшуюся половину, когда находим нужное число возвращаем его индекс, если не находим возвращаем null.


    В статье утверждалось, что только 10% программистов могут решить эту задачу. Да не может быть! Вот лохи, подумал я, зарядил Firebug, каких-то 5 минут и… нерабочая версия готова. Еще одна итерация, и еще, и еще. В сумме полтора часа, и в конечном решении все равно 2 ошибки. Стыдно как!

    Если вы никогда не писали двоичный поиск, я предлагаю вам написать этот алгоритм на любимом языке и выложить его в комменты без тестирования. Любой хороший программист сходу напишет этот поистине детский алгоритм. Потратьте столько времени, сколько нужно. В комменте укажите язык, затраченное время, и ссылку на ваш труд на pastie.org.

    На Википедии правильное решение.

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

    Спойлер.
    Распространенные ошибки:
    — не работает с массивом из 0/1/2 элементов
    — не находит первый или последний элемент
    — некорректно работает, если элемента в массиве нет
    — некорректно работает, если в массиве есть повторяющиеся элементы
    — обращение к элементами за пределами массива
    — козырная, которая была в JDK, переполнение целого при вычислении среднего индекса

    P.S.
    Кто-то скажет, что эта функция уже есть в стандартной библиотеке.
    Это так, согласен. Но это не значит, что от решения таких задач нет толку. Смотрите, если все простые задачи уже решены за нас в стандартной библиотеке, значит нам остались только более сложные задачи, которых там нет. Как мы будем решать эти более сложные задачи, если мы не умеем решить даже простую задачу из стандартной библиотеки?

    Я вам скажу как. Очень плохо. Я делал проверку кода, когда работал в команде. Многие программисты не могли родить простейший код даже с 20 попытки! Они привыкли сидеть на готовом, и не способны написать что-то сложнее композиции foo(bar()), а если и напишут, то реализация будет медленная, путанная, и с ошибками.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 538
    • +7
      Ой да ну, ну с первого раза не напишу, а напишу гарантированно. Помню в универе проходили много алгоритмов сортировки. Двоичный написать понимая его просто, а понимают его все кто о нем знает, другое дело, что не все о нем знают, просто потому что не было у них таких дисциплин и сами не интересовались.

      Другое дело какие-нибудь пирамидальные сортировки:), это я не напишу, хотя бы потому что не помню алгоритма, да и насколько помнь реализация не сильно короткая.
      • +2
        Серега, я тоже думал что напишу. Вот написал. Конечно, если пишешь его по 10 разу то никаких проблем не будет. Пост для тех, кто не писал двоичный поиск, но считает себя годным программистом.
        • +14
          Мне кажется годный программист, как раз этим и отличается, что может разобраться и реализовать незнакомый алгоритм. А время затраченное на это, определяет годность.
          • +1
            Ну так и я о том же. Конечно задача покажется легкой, если её проходили в универе и реализовывали на доске всей группой.
            • 0
              Помню, как мы с товарищем ее на уроке информатики разбирали)
              • +1
                Этот алгоритм у меня был домашним заданием в 9 классе.Эти строки кода запомнятся, наверное, на всю жизнь, так как потратил минут 30, чтобы написать + ещё часа 3 на отладку.)
          • +11
            В детстве, на олимпиадах мы писали и двоичный поиск и волновой в графе и даже строковую арифметику «с закрытыми глазами», по памяти. При этом ни разу не обошлось без пары-тройки-четверки отладочных прогонов и обидных багов.
            Так что гарантированно будут проблемы и на 10й раз и на 50й. Людям свойственно ошибаться. :)

            А что до профпригодности программиста, то если он не впал в ступор от слов «бинарный поиск», то и это уже неплохо.
            • +2
              Буквально вот недавно закончил писать реализацию B-дерева. Вроде просто, а в процессе написания багов было отловлена целая куча
              • 0
                тоже в детстве писали реализацию карандашом на бумажке

                кстати, а как это — без тестирования?
                я даже на листике сначала придумываю и пишу тесты, а потом по ним валидный код.
                иначе как, в голове все тесты держать нужно?
                • 0
                  На бумажке — можно.
                • 0
                  А мы с друзьями часть алгоритмов писали просто выключая монитор и печатая на клавиатуре не глядя на то, что получается… Ни разу не получилось полностью правильно. В самом похожем на истину варианте вместо скобки "[" была напечатана "{"… Мелочь, но не компилится…
                  • 0
                    Это мне напомнило как я писал на спектруме программу вывода цветных полос для настройки телека.
                    Естественно, раз телек не настроен, то на нем нифига не видно :)
                    Но ничего, насобачился — раза с пятого уже печатал без ошибок.
                    Но это не показатель — во первых, программка из трех строчек, а во-вторых на спектруме не бывает опечаток в операторах.
                • +1
                  Специально для тех кто сомневался в моих способностях и опустил карму:):
                  pastie.org/927644
                  • +3
                    На вскидку: как минимум баг с переполнением целого там есть )
                    • 0
                      Ммм, что, где?:)
                      • 0
                        Когда размер массива превышает половину макимального значения MAX, допустимого для $m, будет получена ошибка (несмотря на то, что все входные/выходные данные не превышают MAX).
                        • 0
                          * сорри, случайно отправил не дописав до конца *

                          По сути это из самых незначительных багов. В стандартных условиях он и не появится. Но тем не менее — про вашу рализацию нельзя сказать, что она совсем без багов :)
                          • 0
                            Сорри, может я туплю, но я абсолютно не понимаю о чем Вы:) Примерчик данных нельзя привести?:), реально не врубаюсь:)
                            • 0
                              Не очень жизненный)
                              Возьмите массив из 2^39 элементов, нужный — последний.
                              • 0
                                А понял, действительно очень жизненный пример:)
                                • +1
                                  Зачем же 2^39? Достаточно 2^31 )
                                  • +1
                                    Затем, что это PHP)
                                    $ php -r «echo pow(2, 39). ' '. pow(2, 40);»; echo
                                    549755813888 1.09951162778E+12
                        • +1
                          Баг с переполнением — это уже тонкие вещи, все остальное похоже правильно. Необычный способ.
                        • 0
                          ДА сколько же на хабре невменяемых:) Комменты плюсуют, а карму наоборот. Объясняйте хоть чего не так или просто радость слить кого-то. Обиженные с детства?:)
                          • +3
                            Это зависть мужик, не парься!
                            • НЛО прилетело и опубликовало эту надпись здесь
                            • –1
                              Как на счёт таких данных:
                              $array = array(10,3,0,2,1);
                              echo BSinArray($array, 10);

                              Результат -1. А должно быть 0.
                              • +2
                                По условию массив упорядочен. То есть array(0, 1, 2, 3, 10)
                          • +3
                            Напишете сразу и без ошибок? Без единого прогона? Я вот честно признаюсь — с ходу не напишу. С одного-двух-трех прогонов — напишу. И не думаю, что вы как программист сильно круче меня :-Р
                            • +2
                              Вообще то я и написал, что с первого раза без ошибок наверное не напишу, но в принципе напишу, ничего сложного там нет:)
                              • +2
                                Как минимум одна нетривиальная вещь есть, которая долгое время крутилась в библиотеке JDK. Автор кода работает в Google.
                          • 0
                            Простой то он простой. Вот только написать его без ошибок на различных частных случаев сходу без тестирования практически невозможно
                            • 0
                              Вместо «алгоритмов сортировки» — стоит читать «алгоритмов поиска». Хотя изучали и то, и другое и много чего еще:)
                            • 0
                              unsigned int binary_find(int *arr, unsigned int max_index, int num)
                              {
                              int i = 0, j = 0, k = 0;
                              unsigned int ret = 0;

                              j = max_index;
                              do {
                              k = (i + j) / 2;

                              if(arr[k] == num) {
                              ret = arr[k];
                              break;
                              }
                              else if(arr[k] > num)
                              --j;
                              else if(arr[k] < num)
                              ++i;

                              } while ( i
                              • +1
                                Что-то покоцалось, лучше на Pastie, там сохраняется форматирование.
                                • +1
                                  • +4
                                    Мм, это не совсем двоичный поиск. У вас просто одна из границ плавно ползет к искомому числу, как если бы вы листали в словаре страницы. А здесь именно нужно именно на каждом шаге брать половину от предыдущего набора. Сначала есть весь массив, на слеющем шаге остается половина, потом четвертина, восьмерина. То есть: ...else if(arr[k] < num) j = k;
                                    • +1
                                      Да, заметил уже.
                                    • 0
                                      Имхо, ошибочка. Вместо --j и ++i должно быть j=k и i=k, в этом суть половинного деления, а вы сдвигаете на одну позицию крайние позиции.
                                  • 0
                                    Первая ошибка:
                                    k = (i + j) / 2;

                                    Если элементов в массиве непарное количество, будет нехорошо )
                                    • +2
                                      Ошибся, беру слова обратно. Будет использоваться только целая часть.
                                      • +2
                                        если не парное количество, все будет нормально

                                        плохо будет, если индексы будут большими и на втором шаге алгоритма они попадут в дальнюю часть интервала
                                        • 0
                                          а еще i+j может перевалить за max_int и вот тогда будет реальная бяка
                                      • +4
                                        12 минут
                                        Не тестировал

                                        pastie.org/927541
                                        • 0
                                          Язык — Javascript, если что…
                                          • +1
                                            На вот таком массиве повиснет: [1,2]
                                            У меня то же самое было, а потом еще долго думал над костылем. Правильное решение красиво в этом смысле, там без костыля.
                                            • +1
                                              Подправил свой код. 3 ошибки. 2 тестовых прогона. Вроде, без костыля.
                                              • 0
                                                Да, вот это оно :)
                                                А если еще while перенести наверх, то этот if не нужен: if (pos >=0 && pos < arr.length), и получаем почти классическое решение. В классическом еще защита от переполнения целого тут: pos = Math.floor((start+end)/2);
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                            • +5
                                              Это типа умный прагматичный подход?
                                              Вот скажем, я хочу взять программера на задачи по коллаборативной фильтрации. Хочу знать, годен ли он. Или лучше — он хочет знать, потянет ли он. Что ему, бесплатно потратить неделю своего времени на реализацию практической задачи? Нет конечно. А вот такие игрушечные задачи прекрасно позволяют оценить уровень.
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                • +2
                                                  Если Вам нужно что-то написать:
                                                  1. Посмотрите, возможно ли реюзать ваш старый код.
                                                  2. Если реюзать старый код нельзя, посмотрите, можно ли купить.
                                                  3. Если купить нельзя, напишите реюзебл решение.

                                                  по-моему из Совершенного Кода.
                                            • 0
                                              pastie.org/927546

                                              Два прогона. Первый раз сглюкнула интендация в TextMate. Второй раз сообразил что во второй строке надо дописать +indexFrom :)
                                              • +1
                                                и да. Я никогда не писал двоичный поиск потому что не было необходимости изобретать велосипед. Времени потратил на написание… ну минуты три вместе с двумя прогонами.
                                                • +5
                                                  Что произойдет в случае what = 8? :)
                                                  • +1
                                                    Ха. Хороший момент, спасибо! Лишний доказывает, что все мы люди и всем нам свойственно ошибаться.
                                                • –1
                                                  Ну, рекурсивно неинтересно.
                                                  • +3
                                                    Почему? это всего лишь один из способов реализации. Ну хотите я разверну рекурсию с парой индексов начало-конец и заверну это в цикл while fromIndex < toIndex? Ну и так можно, это всего лишь вариант решения, а по сути — идентичный алгоритм (однако рекурсия в этом случае гораздо выразительнее, т.к. алгоритм рекурсивен по своей сути).
                                                    • +2
                                                      Просто в классическом варианте без рекурсии проще запутаться, на мой взгляд. А так — да, идентичный, никто не спорит. Правда требует O(log N) памяти, если компилятор/интерпретатор не оптимизирует хвостовую рекурсию.
                                                  • +1
                                                    Рекурсию в таком алгоритме стыдно.
                                                  • 0
                                                    20 минут — php
                                                    http://pastie.org/927547
                                                    • +1
                                                      Если искомого числа нет в массиве, то…
                                                      • +1
                                                        А если $lookingFor отсутствует в масиве?
                                                        • +1
                                                          ать, попался :)
                                                          там нужна еще проверка на пересекаемость границ
                                                          • +1
                                                            Как-то так думаю pastie.org/927664
                                                            Вот только сейчас закончил)) Правда не программист, а админ и отвлекают постоянно на работе(
                                                            • 0
                                                              Если длина массива = 1, то… выйти
                                                              • +1
                                                                Верно, если длина масива == 1, то выйти, но перед этим проверяется равен ли единственный елемент масива искомому и если равен, то задача решена)
                                                      • +1
                                                        Что будет если размер массива равен нулю? (подсказка: оно вылетит с диким грохотом).
                                                      • 0
                                                        Прочитал заголовок, думал будет какой-то жутко умный алгоритм с битовыми операциями. А оказалось речь про банальную дихотомию :)
                                                        • +4
                                                          вот у меня от слова дихотомия сводит скулы. а от фразы binary search мне становится все очень быстро понятно. не надо умничать.
                                                          • +6
                                                            А почему бы не называть вещи своими именами? Прям вот от давнего греческого слова скулы сводит, а от английского не сводит. Фраза на русском «двоичный поиск» ничего не сводит?
                                                            • +4
                                                              От binary search и двоичный поиск у меня скулы не сводит, потому что по-английски и по-русски я говорю свободно, в отличии от греческого.
                                                            • +16
                                                              я не умничаю, мне действительно слово «дихотомия» ближе и понятнее, чем «бинарный поиск». Видимо, тяжелое детство в физмате сказывается :)
                                                              • –2
                                                                По Вашему нику заметно, что вы с особым трепетом относитесь к греческому :)
                                                                • +8
                                                                  если судить по нику, то скорее к латыни
                                                                  • 0
                                                                    Мне, кстати, тоже «дихотомия» как-то ближе ;-)
                                                          • –4
                                                            минуту или 2
                                                            ну 5 чтоб дописать красиво

                                                            да, раньше не раз такое писал
                                                            • +6
                                                              Ну, как бы, и что? Есть 10% программистов, умеющих писать двоичный поиск. Есть 50% знаючих PHP, есть 0,01% способных создать аналог Windows или Linux с нуля. Никто не умеет всего. Тем более, что писать двоичный поиск с нуля — странная идея при наличии библиотек под любую платформу. Этак можно сказать «только 2% помнят, как пробивать дырки на перфокартах».

                                                              Умение или неумение написать двоичный поиск с первого раза правильно — не есть формальный признак хорошего программиста.
                                                              • +9
                                                                Согласен. Но умение написать широко известный алгоритм, воплотив его в исходном коде — это есть то качество, которое отличает программистов от не-программистов.
                                                                • +1
                                                                  Никто не умеет всего. Если человек делает сайты даже, ему нужно решать алгоритмические задачи посложнее двоичного поиска. Хорошо ли он их решает? Как узнать? Сравнить не с чем. А тут просто, пишешь за 5 минут, сравниваешь свою реализацию с классической, оцениваешь свой уровень.

                                                                  Совсем не странная идея, если не подходить к этому как к упражнению или к тесту.
                                                                  • 0
                                                                    Если человек не знает элементарных вещей, то хорошо ли он будет понимать сложные?
                                                                    • +3
                                                                      «Умение или неумение написать двоичный поиск с первого раза правильно»
                                                                      Представляете веб-дизайнера, который умеет рисовать только темно-синие квадраты?

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

                                                                      Все эти качества — однозначно важны для программиста, и нехватка их вредит во всех проектах.

                                                                      Тут отличительная особенность — надо написать _правильный_ код, а не тот, который «вроде работает», при этом действительно у всех вокруг он работает, но где-то в Урюпинске у кого-то не работает (наверное потому что сам дурак). Потом багрепорт еще откудато. И еще. Потом наконец-то проблема отлавливается. Это нормальный процесс в наше время (обычный). А здесь необычно требуется самому закодить хоть и не очень сложный алгоритм, но сделать это правильно. И не «с первого раза» — можно хоть сто раз переписывать, но «хоть с миллионного» раза, но ДО того момента, как показал код и назвал его решением.
                                                                      • 0
                                                                        Очень хорошо сказал.
                                                                    • +10
                                                                      Дети, ей Богу!

                                                                      Не ошибается только тот, кто ничего не делает. Я например текст набираю с ошибками, но потом их правлю, правда не всегда. :) А вот программы надо просто грамотно тестировать. В этом плане мне нравиться Code Jam, где тебе дают минимальный тест, потом функциональный, а потом еще и тест на производительность.

                                                                      А реализовывать поиск делением попалам надо где-то там, в школе. И тогда же читать книги Кнута, жаль что из всего 3.
                                                                      • +4
                                                                        И тогда же читать книги Кнута, жаль что из всего 3

                                                                        Уже 4.
                                                                      • –1
                                                                        А ты много вспомнишь из книг Кнута, читая их в школьном возрасте? Или высшая математика плавно перебралась в школу?

                                                                        Вряд ли знание того, что алгоритм выполнятся O(log2 n * sqrt(n + n2)), сильно пригодится рядовому программисту.

                                                                        Программист лишь должен пользоваться трудами других. Если стоит задача отсортировать числа, то я возьму справочник и выберу лишь тот алгоритм сортировки, который наиболее пригодный в моем случае и чья эффективность проверена математиками. Не всякий программист является математиком, так же как и не всякий математик — программистом.
                                                                        • +4
                                                                          >Вряд ли знание того, что алгоритм выполнятся O(log2 n * sqrt(n + n2)), сильно пригодится рядовому программисту.

                                                                          ARRRGH!!!
                                                                          Быдлокодеру не пригодится, программисту — обязательно пригодится.
                                                                          • +2
                                                                            Как бы тебе это сказать… O(log2n * sqrt(n + n2)) = O(n * log2n)

                                                                            Боюсь ты сам себя только что записал в быдлокодеры. Надеюсь твой работодатель этого не узнает.
                                                                            • +4
                                                                              Окружающие не виноваты в том, что не бросаются сразу исправлять ваши ошибки.
                                                                              • +2
                                                                                Я про принцип, а не про формулу, на которую даже не посмотрел.
                                                                              • –1
                                                                                антикульт быдлокодера уже достал. к месту и не к месту.
                                                                                даже отличные программисты пишут быдлокод во многих случаях в реальной жизни.
                                                                                • 0
                                                                                  Слово некрасивое, да. Но по сути-то верно.

                                                                                  >даже отличные программисты пишут быдлокод во многих случаях в реальной жизни.
                                                                                  Халтурят в разных ситуациях все. Но хороший программист, в отличие от плохого, может написать хороший код [при желании, разумеется]. =)
                                                                            • +1
                                                                              • 0
                                                                                Ну если Вы такой придира, то стоило хотя бы поменять местами члены выражения: O(n) = O(√ n + n2)

                                                                                Вообще-то это предназначалось для человека, использующего .NET: log2 n O(n) = log2 n O(√n + n2)

                                                                                Это по поводу того, насколько актуально знать программисту сей факт.
                                                                          • +3
                                                                            статья напомнила о числе 95% :)
                                                                            // lurkmore.ru/95%25
                                                                            • 0
                                                                              5% из настоящих программистов = идиоты :)
                                                                            • +8
                                                                              * ворчит *
                                                                              Из приходящих на собеседование «программистов» только 10% вообще знают, что такое двоичный поиск.
                                                                              • 0
                                                                                Я помню в 14 лет пришел в контору собеседоваться. Они так снисходительно, у нас информационная система, нужно хранение документов, редактирование, доступ с любого компьютера. Как будешь делать? Я говорю, ну, хранить в XML, отдавать буду HTML (как раз только начал интересоваться вебом). Они — хаха! Да нет друг, здесь база данных нужна, Delphi. Вот ты знаешь что такое реляция? Переспрашиваю: корелляция? — Нет, ре-ля-ция. — Не знаю. — Ну иди гуляй.

                                                                                А сейчас ни один человек в здравом уме не станет делать это на Delphi. С MySQL на нужном им уровне я научился работать за день. Толку от того, что я знал бы как это называется. Главное по сути понимать, или уметь освоить.
                                                                                • +6
                                                                                  * ворчит опять *
                                                                                  А очень было бы неплохо, если бы программист знал хотя бы основы реляционной алгебры… А то налепят по образцу восемь левых джойнов, а потом у них запрос к таблице в 40 записей пять минут выполняется…
                                                                                  • +1
                                                                                    Основы реляционной алгебры никак не научат его, что каджый DROP TABLE в MySQL лочит все таблицы почти на полсекунды. Я не спорю, вы дело говорите, но есть другая сторона.
                                                                                    • +1
                                                                                      Дела не в джоинах, а в не понимании структуры БД. А даже если и знаешь ее, то с опытом все приходит.
                                                                                      Потом как раз начинаешь «пользоваться» фичами, когда обычный джоин нулюет запись слева, если правая нуль. Повторюсь, опыт решает.

                                                                                      А по теме можно сказать одно. Требовать от программиста знания чего-то просто неверно. Не зря есть такие вещи как испытательный срок. Если видишь, что человечек умненький, но чего-то не знает, это не значит, что ему что-то помешает в этом разобраться и даже стать в итоге лучше тебя… Разные фирмы работают в своих сферах, изучить все не вариант
                                                                                      • 0
                                                                                        Drop table как бы операция, которая должна выполняться на продакшене не чаще, чем раз в раз-в-патч, или лучше раз-в-релиз? Или вы дропаете их настолько часто, что это замедляет производительность?
                                                                                        • 0
                                                                                          CREATE TEMPORARY TABLE, anybody?
                                                                                          • 0
                                                                                            К DROP TABLE никакого отношения пост не имеет =) Я про LEFT JOIN/JOIN =)
                                                                                      • +1
                                                                                        Джоины в СУБД очень оптимизированны. У меня есть запрос с десятком Лефт Джоинов, которые получают пачку данных из таблиц по несколько тысяч записей за доли секунды.
                                                                                        Более того — опытные администраторы БД мне советовали пользоваться Джоинами, а не несколькими мелкими запросами. Они утверждают, что боязнь Джоинов у не очень опытных программистов от непонятия механизмов, которые работают внутри СУБД.
                                                                                        • –2
                                                                                          Замечу, что несколько тысяч записей — это не слишком большой объем БД.
                                                                                          • 0
                                                                                            замечу, что я и не говорил, что это большой объем БД.
                                                                                            человек сказал: 40 записей — 300 секунд
                                                                                            я сказал: тысячи записей — доли секунды (практически столько же, как 10 запросов без джоинов)
                                                                                            • 0
                                                                                              Ладно, ладно. Я лично писал partitioned-wise joins на оракле, 5-6 джойнах, в одной из таблиц 4 миллиарда записей. Работало in reasonable time! :)
                                                                                            • 0
                                                                                              Это смотря какая СУБД. Приведенный случай касался MySQL, у которой, конечно, хороший оптимизатор, но ждать от него гениальности нельзя.
                                                                                              • 0
                                                                                                ну я тоже про MySQL говорил. он отлично оптимизирует работу с Джоинами.
                                                                                                • 0
                                                                                                  Повезло вам с ним :)
                                                                                                  • +1
                                                                                                    Эта, мужики, а давно в mysql оптимизатор то есть?
                                                                                              • –2
                                                                                                Left join — это ещё ничего, а вот когда налепят восемь inner join-ов — вот это да. Или того хлеще, просто перечислят таблицы во from через запятую.
                                                                                                • 0
                                                                                                  Left join — это ещё ничего, а вот когда налепят восемь inner join-ов — вот это да

                                                                                                  А чем плохо 8 inner join'ов?

                                                                                                  Или того хлеще, просто перечислят таблицы во from через запятую.

                                                                                                  Сам факт еще ни о чем не говорит. Если в where указаны условия пересечения этих таблиц, то это равносильно inner join, иначе cross join. Поэтому с таким же успехом вы можете негодовать по поводу использования join'ов вообще.
                                                                                                  • –3
                                                                                                    Inner join-ы плохи тем, что это очень процессороёмкая операция на объёмах данных, отличающихся от самых минимальных. Понятно, что это не означает, что от inner join-ов нужно отказываться совсем, но если есть выбор между inner и left при гарантированно одинаковом результате (например, если у нас все данные гарантированно консистентны, а NULL-ов просто не бывает) — то выбирать надо однозначно left.

                                                                                                    А cross join крайне требователен к памяти.
                                                                                                    • +2
                                                                                                      Не могли бы вы немного по-подробнее рассказать почему «inner join более процессороемкий, чем left join»
                                                                                                      • 0
                                                                                                        Что означает — самых минимальных? Выборка в, скажем, 500 000 строк, это минимальный объем данных? Для веб-приложения на бесплатном хостинге под мускулом? А для Data Warehouse на enterprise-level СУБД, на выделенных серверах с отдельным SAN?
                                                                                                        • 0
                                                                                                          Это на какой СУБД такая разница между inner join и left?
                                                                                                      • +1
                                                                                                        1) Inner Join ничуть не сложнее, чем Left Join, даже, наверно, чуть проще, так как результат меньше

                                                                                                        2) Перечисление таблиц во From, c точки зрения MySQL, ничем не отличается от inner join
                                                                                                        • 0
                                                                                                          А просветите, в чем такой явный минус от 8 летф джойнов? Недостаток денормализации? Или вы думаете, он мержит промежуточные resultsets на диске, и возрастает нагрузка на IO? Я не уверен, что согласен с вашим высказыванием (И что я его правильно понял).
                                                                                                        • 0
                                                                                                          А было бы еще лучше для таких целей нанимать БДА :)
                                                                                                          • 0
                                                                                                            Ну так наняли в итоге. Меня :)
                                                                                                          • 0
                                                                                                            Не, те кто просто не знают — это еще нормальные.
                                                                                                            Хуже всего те, кто мало того что не знает, так еще и знать не хочет!
                                                                                                        • 0
                                                                                                          И даже не все кандидаты в президенты…

                                                                                                          www.youtube.com/watch?v=k4RRi_ntQc8
                                                                                                          Barack Obama — Computer Science Question
                                                                                                        • +1
                                                                                                          Минуты 4, Python:
                                                                                                          a=range(50,200,2);
                                                                                                          bsearch = lambda a,s,i=False,step=False:(not step and bsearch(a,s,len(a)/2,len(a)/4+1)) or (a[i]==s and str(i)) or (s<a[i] and bsearch(a,s,i-step,step/2+step%2)) or (bsearch(a,s,i+step,step/2+step%2));
                                                                                                          bsearch(a,178);
                                                                                                          bsearch(a,54);
                                                                                                          
                                                                                                          • +11
                                                                                                            вы уверены что это python? :D
                                                                                                            • +25
                                                                                                              Не нужно так писать на питоне :)
                                                                                                              • +1
                                                                                                                Согласен, но я же писал не компонент для использования, а быстрое решение конкретной задачи.
                                                                                                                Писать на продакшн так не нужно, согласен =)
                                                                                                                • +1
                                                                                                                  Ну вы писали для людей, поэтому можно было бы и понятнее расписать.
                                                                                                                  • 0
                                                                                                                    Я, скорее, писал для проверки — сколько времени мне потребуется чтобы написать подобный алгоритм. =)
                                                                                                              • 0
                                                                                                                Чистосердечное признание
                                                                                                                После первого написания содержало два бага:
                                                                                                                — вместо step сначала проверялась на положительность i — исправил по ходу написания
                                                                                                                — вместо строки возвращалось число — зацикливание, если искомый элемент имеет индекс 0.
                                                                                                                • 0
                                                                                                                  Теперь по повожу распространенных ошибок из спойлера:
                                                                                                                  — не работает с массивом из 0/1/2 элементов
                                                                                                                  Работает. При нулевой длине отлично возникает исключение — обрабатывайте.
                                                                                                                  — не находит первый или последний элемент
                                                                                                                  Находит
                                                                                                                  — некорректно работает, если элемента в массиве нет
                                                                                                                  Это есть. Нужно после проверки на равенство добавить: or (step==1 and '-1')
                                                                                                                  — некорректно работает, если в массиве есть повторяющиеся элементы
                                                                                                                  Корректно. Возвратит индекс первого, на который наткнется
                                                                                                                  — обращение к элементами за пределами массива
                                                                                                                  Не особо понял, но есть такая замечательная вещь — исключения.
                                                                                                                • +7
                                                                                                                  На любом языке могу писать как на Хаскелле? :)
                                                                                                                • +2
                                                                                                                  За это я и люблю питон!
                                                                                                                  • –2
                                                                                                                    Если мне на собеседовании пишут такой код (были красавцы), обычно именно на этом я и ставлю точку.
                                                                                                                    • +4
                                                                                                                      Вы на собеседовании требуете написания на листочке красивого кода с комментариями?
                                                                                                                      • –2
                                                                                                                        На доске, комментариев не надо ;-) И красивого тоже не надо — надо понятного.
                                                                                                                        • +2
                                                                                                                          Код вполне понятен. Тем более на доске условие в lambda-функции было бы расписано на несколько строк (в каждой по or). Вас смущают названия переменных?
                                                                                                                          • +5
                                                                                                                            Понимаете, есть такая закономерность — какой у программиста первый позыв в плане стиля, так примерно и будет выглядеть его код, который будет создаваться в моменты стресса, под давлением сроков, production failure — то есть когда нет времени сделать все красиво, надо сделать быстро чтобы работало. Это делается временно и потом остается на века. Поэтому лучше делать сразу все правильно.

                                                                                                                            Лямбда-функции, замыкания и прочая — это очень хорошо и классно, и если правильно использовать — вполне читаемо и поддерживаемо. Но если инлайн лямбда-функция занимает больше одной строки — это называется spaghetti code, и такого не надо.
                                                                                                                            • +2
                                                                                                                              В данном случае lambda-функция вполне уместна.
                                                                                                                              Кстати, можно писать и не в одну строку. Единственная причина, почему у меня написано в одну — это то, что все это набиралось в консоли.
                                                                                                                              • –8
                                                                                                                                Видимо, в консоли отсутствуют клавиши перевода строки и пробелы :)
                                                                                                                                • +1
                                                                                                                                  У меня там повыше код на Хаскелле и без лямбд, по-моему вполне читабельно, хотя конечно больше занимает.
                                                                                                                                  Можно конечно в одну строчку написать, чтоб непонятно было, сам так люблю делать, но не в production коде :)
                                                                                                                                  А к вам зря придрались, можно писать ясный код на работе и для себя совсем другой, главное чтоб себе было ясно и удобно.
                                                                                                                                  А программист который пишет всегда в одном стиле — это Junior.
                                                                                                                                  • +1
                                                                                                                                    Выглядит, и правда, куда понятнее.
                                                                                                                                    В вашем решении присутствует та же проблема, что и у меня — переполнение стека функций. Хотя, чтобы ее решить придется отказаться от такой приятной вещи, как рекурсия =)

                                                                                                                                    На самом деле меня больше не претензии к коду смутили, а то, что за подобный код на собеседовании можно попрощаться с кандидатом.
                                                                                                                                    • +2
                                                                                                                                      У меня отлично работает на массивах порядка 100000 элементов (больше не проверял), я думаю хаскель способен соптимизировать тут рекурсию в хвостовую (обычно так и бывает), хотя стоит проверить.

                                                                                                                                      А насчет собеседований, у меня довольно большой опыт по набору, и я бы такого человека спросил во-первых почему он так написал, во-вторых если решение работает это уже плюс, а если он еще сможет переписать по-другому в более традиционной форме это бы для меня был еще больший плюс, так что такой товарищ имел бы однозначное преимущество перед тем кто сразу выдал стереотипное решение.
                                                                                                                                      Те, кто выдает шаблонные решения на собеседованиях обычно потом хуже работают по моему опыту.
                                                                                                                                      • 0
                                                                                                                                        не «соптимизировать рекурсию в хвостовую», а соптимизировать хвостовую рекурсию в цикл.
                                                                                                                                        • 0
                                                                                                                                          Хаскель делает из рекурсии циклы?
                                                                                                                                          • +1
                                                                                                                                            любой компилятор Хаскелля обязан выполнять оптимизацию хвостовых вызовов (и не только рекурсивных). Если это хвосторекурсивный вызов, то скорее всего оптимизатор преобразует его именно в цикл
                                                                                                                                            • 0
                                                                                                                                              он не обязан. Он просто это сделает, ради повышения производительности.
                                                                                                                                              • 0
                                                                                                                                                да нет. он как раз обязан. по стандарту.
                                                                                                                                                • 0
                                                                                                                                                  ссылочку?
                                                                                                                                                  • 0
                                                                                                                                                    мда… опять надо было сначала обновить. извините
                                                                                                                                                  • 0
                                                                                                                                                    беру слова обратно. похоже что, в отличии от SML и Ocaml, в стандарте хаскелля этого нету. и это печально
                                                                                                                                                    • 0
                                                                                                                                                      в CL кстати тоже это не требуется, но всячески было бы круто иметь. А вот в schema например это чуть ли не must have.

                                                                                                                                                      Кстати, а разве есть стандарт на O'Caml?
                                                                                                                                                      • 0
                                                                                                                                                        вот в Scheme точно есть :)
                                                                                                                                                        ocaml нет стандарта, но там есть «стандартная» реализация и она дефакто стандарт.
                                                                                                                                                      • 0
                                                                                                                                                        Это не печально, из-за ленивости Хаскелю нет нужды оптимизировать хвостовую рекурсию.
                                                                                                                                            • 0
                                                                                                                                              Совсем нет, есть рекурсия хвостовая, а есть не хвостовая, но которая может быть преобразованна в хвостовую, тут как раз этот случай.
                                                                                                                                              А то что хвостовая рекурсия на самом деле потом превратится в цикл это всем понятно.
                                                                                                                                              • 0
                                                                                                                                                если вы про этот код #, то там все вызовы на хвостовых позициях, ничего преобразовывать не надо.