How to become an author
Search
Write a publication
Pull to refresh

Comments 538

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

Другое дело какие-нибудь пирамидальные сортировки:), это я не напишу, хотя бы потому что не помню алгоритма, да и насколько помнь реализация не сильно короткая.
Total votes 25: ↑16 and ↓9+7
Серега, я тоже думал что напишу. Вот написал. Конечно, если пишешь его по 10 разу то никаких проблем не будет. Пост для тех, кто не писал двоичный поиск, но считает себя годным программистом.
Total votes 6: ↑4 and ↓2+2
Мне кажется годный программист, как раз этим и отличается, что может разобраться и реализовать незнакомый алгоритм. А время затраченное на это, определяет годность.
Total votes 20: ↑17 and ↓3+14
Ну так и я о том же. Конечно задача покажется легкой, если её проходили в универе и реализовывали на доске всей группой.
Total votes 1: ↑1 and ↓0+1
Помню, как мы с товарищем ее на уроке информатики разбирали)
This comment wasn’t rated yet0
Этот алгоритм у меня был домашним заданием в 9 классе.Эти строки кода запомнятся, наверное, на всю жизнь, так как потратил минут 30, чтобы написать + ещё часа 3 на отладку.)
Total votes 1: ↑1 and ↓0+1
В детстве, на олимпиадах мы писали и двоичный поиск и волновой в графе и даже строковую арифметику «с закрытыми глазами», по памяти. При этом ни разу не обошлось без пары-тройки-четверки отладочных прогонов и обидных багов.
Так что гарантированно будут проблемы и на 10й раз и на 50й. Людям свойственно ошибаться. :)

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

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

По сути это из самых незначительных багов. В стандартных условиях он и не появится. Но тем не менее — про вашу рализацию нельзя сказать, что она совсем без багов :)
This comment wasn’t rated yet0
Сорри, может я туплю, но я абсолютно не понимаю о чем Вы:) Примерчик данных нельзя привести?:), реально не врубаюсь:)
This comment wasn’t rated yet0
Не очень жизненный)
Возьмите массив из 2^39 элементов, нужный — последний.
This comment wasn’t rated yet0
А понял, действительно очень жизненный пример:)
This comment wasn’t rated yet0
Зачем же 2^39? Достаточно 2^31 )
Total votes 1: ↑1 and ↓0+1
Затем, что это PHP)
$ php -r «echo pow(2, 39). ' '. pow(2, 40);»; echo
549755813888 1.09951162778E+12
Total votes 1: ↑1 and ↓0+1
Баг с переполнением — это уже тонкие вещи, все остальное похоже правильно. Необычный способ.
Total votes 1: ↑1 and ↓0+1
ДА сколько же на хабре невменяемых:) Комменты плюсуют, а карму наоборот. Объясняйте хоть чего не так или просто радость слить кого-то. Обиженные с детства?:)
Total votes 6: ↑3 and ↓30
Это зависть мужик, не парься!
Total votes 5: ↑4 and ↓1+3
UFO just landed and posted this here
Как на счёт таких данных:
$array = array(10,3,0,2,1);
echo BSinArray($array, 10);

Результат -1. А должно быть 0.
Total votes 1: ↑0 and ↓1-1
По условию массив упорядочен. То есть array(0, 1, 2, 3, 10)
Total votes 2: ↑2 and ↓0+2
Напишете сразу и без ошибок? Без единого прогона? Я вот честно признаюсь — с ходу не напишу. С одного-двух-трех прогонов — напишу. И не думаю, что вы как программист сильно круче меня :-Р
Total votes 7: ↑5 and ↓2+3
Вообще то я и написал, что с первого раза без ошибок наверное не напишу, но в принципе напишу, ничего сложного там нет:)
Total votes 2: ↑2 and ↓0+2
Как минимум одна нетривиальная вещь есть, которая долгое время крутилась в библиотеке JDK. Автор кода работает в Google.
Total votes 2: ↑2 and ↓0+2
О каком коде, пардон, речь? И о котором авторе?
Total votes 1: ↑1 and ↓0+1
Простой то он простой. Вот только написать его без ошибок на различных частных случаев сходу без тестирования практически невозможно
This comment wasn’t rated yet0
Вместо «алгоритмов сортировки» — стоит читать «алгоритмов поиска». Хотя изучали и то, и другое и много чего еще:)
This comment wasn’t rated yet0
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
Total votes 10: ↑5 and ↓50
Что-то покоцалось, лучше на Pastie, там сохраняется форматирование.
Total votes 1: ↑1 and ↓0+1
Мм, это не совсем двоичный поиск. У вас просто одна из границ плавно ползет к искомому числу, как если бы вы листали в словаре страницы. А здесь именно нужно именно на каждом шаге брать половину от предыдущего набора. Сначала есть весь массив, на слеющем шаге остается половина, потом четвертина, восьмерина. То есть: ...else if(arr[k] < num) j = k;
Total votes 4: ↑4 and ↓0+4
Да, заметил уже.
Total votes 3: ↑2 and ↓1+1
Имхо, ошибочка. Вместо --j и ++i должно быть j=k и i=k, в этом суть половинного деления, а вы сдвигаете на одну позицию крайние позиции.
This comment wasn’t rated yet0
Первая ошибка:
k = (i + j) / 2;

Если элементов в массиве непарное количество, будет нехорошо )
Total votes 4: ↑2 and ↓20
Ошибся, беру слова обратно. Будет использоваться только целая часть.
Total votes 2: ↑2 and ↓0+2
если не парное количество, все будет нормально

плохо будет, если индексы будут большими и на втором шаге алгоритма они попадут в дальнюю часть интервала
Total votes 2: ↑2 and ↓0+2
а еще i+j может перевалить за max_int и вот тогда будет реальная бяка
This comment wasn’t rated yet0
Язык — Javascript, если что…
This comment wasn’t rated yet0
На вот таком массиве повиснет: [1,2]
У меня то же самое было, а потом еще долго думал над костылем. Правильное решение красиво в этом смысле, там без костыля.
Total votes 1: ↑1 and ↓0+1
Подправил свой код. 3 ошибки. 2 тестовых прогона. Вроде, без костыля.
Total votes 1: ↑1 and ↓0+1
Да, вот это оно :)
А если еще while перенести наверх, то этот if не нужен: if (pos >=0 && pos < arr.length), и получаем почти классическое решение. В классическом еще защита от переполнения целого тут: pos = Math.floor((start+end)/2);
This comment wasn’t rated yet0
UFO just landed and posted this here
Это типа умный прагматичный подход?
Вот скажем, я хочу взять программера на задачи по коллаборативной фильтрации. Хочу знать, годен ли он. Или лучше — он хочет знать, потянет ли он. Что ему, бесплатно потратить неделю своего времени на реализацию практической задачи? Нет конечно. А вот такие игрушечные задачи прекрасно позволяют оценить уровень.
Total votes 17: ↑11 and ↓6+5
UFO just landed and posted this here
Если Вам нужно что-то написать:
1. Посмотрите, возможно ли реюзать ваш старый код.
2. Если реюзать старый код нельзя, посмотрите, можно ли купить.
3. Если купить нельзя, напишите реюзебл решение.

по-моему из Совершенного Кода.
Total votes 2: ↑2 and ↓0+2
pastie.org/927546

Два прогона. Первый раз сглюкнула интендация в TextMate. Второй раз сообразил что во второй строке надо дописать +indexFrom :)
Total votes 2: ↑1 and ↓10
и да. Я никогда не писал двоичный поиск потому что не было необходимости изобретать велосипед. Времени потратил на написание… ну минуты три вместе с двумя прогонами.
Total votes 3: ↑2 and ↓1+1
Что произойдет в случае what = 8? :)
Total votes 5: ↑5 and ↓0+5
Ха. Хороший момент, спасибо! Лишний доказывает, что все мы люди и всем нам свойственно ошибаться.
Total votes 1: ↑1 and ↓0+1
Ну, рекурсивно неинтересно.
Total votes 3: ↑1 and ↓2-1
Почему? это всего лишь один из способов реализации. Ну хотите я разверну рекурсию с парой индексов начало-конец и заверну это в цикл while fromIndex < toIndex? Ну и так можно, это всего лишь вариант решения, а по сути — идентичный алгоритм (однако рекурсия в этом случае гораздо выразительнее, т.к. алгоритм рекурсивен по своей сути).
Total votes 3: ↑3 and ↓0+3
Просто в классическом варианте без рекурсии проще запутаться, на мой взгляд. А так — да, идентичный, никто не спорит. Правда требует O(log N) памяти, если компилятор/интерпретатор не оптимизирует хвостовую рекурсию.
Total votes 2: ↑2 and ↓0+2
Рекурсию в таком алгоритме стыдно.
Total votes 1: ↑1 and ↓0+1
Если искомого числа нет в массиве, то…
Total votes 1: ↑1 and ↓0+1
А если $lookingFor отсутствует в масиве?
Total votes 1: ↑1 and ↓0+1
ать, попался :)
там нужна еще проверка на пересекаемость границ
Total votes 1: ↑1 and ↓0+1
Как-то так думаю pastie.org/927664
Вот только сейчас закончил)) Правда не программист, а админ и отвлекают постоянно на работе(
Total votes 1: ↑1 and ↓0+1
Если длина массива = 1, то… выйти
This comment wasn’t rated yet0
Верно, если длина масива == 1, то выйти, но перед этим проверяется равен ли единственный елемент масива искомому и если равен, то задача решена)
Total votes 1: ↑1 and ↓0+1
Что будет если размер массива равен нулю? (подсказка: оно вылетит с диким грохотом).
Total votes 1: ↑1 and ↓0+1
Прочитал заголовок, думал будет какой-то жутко умный алгоритм с битовыми операциями. А оказалось речь про банальную дихотомию :)
Total votes 16: ↑8 and ↓80
вот у меня от слова дихотомия сводит скулы. а от фразы binary search мне становится все очень быстро понятно. не надо умничать.
Total votes 18: ↑11 and ↓7+4
А почему бы не называть вещи своими именами? Прям вот от давнего греческого слова скулы сводит, а от английского не сводит. Фраза на русском «двоичный поиск» ничего не сводит?
Total votes 10: ↑8 and ↓2+6
От binary search и двоичный поиск у меня скулы не сводит, потому что по-английски и по-русски я говорю свободно, в отличии от греческого.
Total votes 10: ↑7 and ↓3+4
я не умничаю, мне действительно слово «дихотомия» ближе и понятнее, чем «бинарный поиск». Видимо, тяжелое детство в физмате сказывается :)
Total votes 22: ↑19 and ↓3+16
По Вашему нику заметно, что вы с особым трепетом относитесь к греческому :)
Total votes 4: ↑1 and ↓3-2
если судить по нику, то скорее к латыни
Total votes 8: ↑8 and ↓0+8
Мне, кстати, тоже «дихотомия» как-то ближе ;-)
This comment wasn’t rated yet0
минуту или 2
ну 5 чтоб дописать красиво

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

Умение или неумение написать двоичный поиск с первого раза правильно — не есть формальный признак хорошего программиста.
Total votes 10: ↑8 and ↓2+6
Согласен. Но умение написать широко известный алгоритм, воплотив его в исходном коде — это есть то качество, которое отличает программистов от не-программистов.
Total votes 11: ↑10 and ↓1+9
Никто не умеет всего. Если человек делает сайты даже, ему нужно решать алгоритмические задачи посложнее двоичного поиска. Хорошо ли он их решает? Как узнать? Сравнить не с чем. А тут просто, пишешь за 5 минут, сравниваешь свою реализацию с классической, оцениваешь свой уровень.

Совсем не странная идея, если не подходить к этому как к упражнению или к тесту.
Total votes 1: ↑1 and ↓0+1
Если человек не знает элементарных вещей, то хорошо ли он будет понимать сложные?
Total votes 4: ↑2 and ↓20
«Умение или неумение написать двоичный поиск с первого раза правильно»
Представляете веб-дизайнера, который умеет рисовать только темно-синие квадраты?

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

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

Тут отличительная особенность — надо написать _правильный_ код, а не тот, который «вроде работает», при этом действительно у всех вокруг он работает, но где-то в Урюпинске у кого-то не работает (наверное потому что сам дурак). Потом багрепорт еще откудато. И еще. Потом наконец-то проблема отлавливается. Это нормальный процесс в наше время (обычный). А здесь необычно требуется самому закодить хоть и не очень сложный алгоритм, но сделать это правильно. И не «с первого раза» — можно хоть сто раз переписывать, но «хоть с миллионного» раза, но ДО того момента, как показал код и назвал его решением.
Total votes 3: ↑3 and ↓0+3
Очень хорошо сказал.
This comment wasn’t rated yet0
Дети, ей Богу!

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

А реализовывать поиск делением попалам надо где-то там, в школе. И тогда же читать книги Кнута, жаль что из всего 3.
Total votes 14: ↑12 and ↓2+10
И тогда же читать книги Кнута, жаль что из всего 3

Уже 4.
Total votes 4: ↑4 and ↓0+4
А ты много вспомнишь из книг Кнута, читая их в школьном возрасте? Или высшая математика плавно перебралась в школу?

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

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

ARRRGH!!!
Быдлокодеру не пригодится, программисту — обязательно пригодится.
Total votes 14: ↑9 and ↓5+4
Как бы тебе это сказать… O(log2n * sqrt(n + n2)) = O(n * log2n)

Боюсь ты сам себя только что записал в быдлокодеры. Надеюсь твой работодатель этого не узнает.
Total votes 16: ↑9 and ↓7+2
Окружающие не виноваты в том, что не бросаются сразу исправлять ваши ошибки.
Total votes 6: ↑5 and ↓1+4
Я про принцип, а не про формулу, на которую даже не посмотрел.
Total votes 2: ↑2 and ↓0+2
антикульт быдлокодера уже достал. к месту и не к месту.
даже отличные программисты пишут быдлокод во многих случаях в реальной жизни.
Total votes 1: ↑0 and ↓1-1
Слово некрасивое, да. Но по сути-то верно.

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

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

Это по поводу того, насколько актуально знать программисту сей факт.
This comment wasn’t rated yet0
5% из настоящих программистов = идиоты :)
Total votes 2: ↑1 and ↓10
* ворчит *
Из приходящих на собеседование «программистов» только 10% вообще знают, что такое двоичный поиск.
Total votes 8: ↑8 and ↓0+8
Я помню в 14 лет пришел в контору собеседоваться. Они так снисходительно, у нас информационная система, нужно хранение документов, редактирование, доступ с любого компьютера. Как будешь делать? Я говорю, ну, хранить в XML, отдавать буду HTML (как раз только начал интересоваться вебом). Они — хаха! Да нет друг, здесь база данных нужна, Delphi. Вот ты знаешь что такое реляция? Переспрашиваю: корелляция? — Нет, ре-ля-ция. — Не знаю. — Ну иди гуляй.

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

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

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

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

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

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

2) Перечисление таблиц во From, c точки зрения MySQL, ничем не отличается от inner join
Total votes 1: ↑1 and ↓0+1
А просветите, в чем такой явный минус от 8 летф джойнов? Недостаток денормализации? Или вы думаете, он мержит промежуточные resultsets на диске, и возрастает нагрузка на IO? Я не уверен, что согласен с вашим высказыванием (И что я его правильно понял).
This comment wasn’t rated yet0
А было бы еще лучше для таких целей нанимать БДА :)
This comment wasn’t rated yet0
Ну так наняли в итоге. Меня :)
This comment wasn’t rated yet0
Не, те кто просто не знают — это еще нормальные.
Хуже всего те, кто мало того что не знает, так еще и знать не хочет!
This comment wasn’t rated yet0
Минуты 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);
Total votes 9: ↑5 and ↓4+1
вы уверены что это python? :D
Total votes 13: ↑12 and ↓1+11
Не нужно так писать на питоне :)
Total votes 25: ↑25 and ↓0+25
Согласен, но я же писал не компонент для использования, а быстрое решение конкретной задачи.
Писать на продакшн так не нужно, согласен =)
Total votes 5: ↑3 and ↓2+1
Ну вы писали для людей, поэтому можно было бы и понятнее расписать.
Total votes 1: ↑1 and ↓0+1
Я, скорее, писал для проверки — сколько времени мне потребуется чтобы написать подобный алгоритм. =)
Total votes 2: ↑1 and ↓10
Чистосердечное признание
После первого написания содержало два бага:
— вместо step сначала проверялась на положительность i — исправил по ходу написания
— вместо строки возвращалось число — зацикливание, если искомый элемент имеет индекс 0.
This comment wasn’t rated yet0
Теперь по повожу распространенных ошибок из спойлера:
— не работает с массивом из 0/1/2 элементов
Работает. При нулевой длине отлично возникает исключение — обрабатывайте.
— не находит первый или последний элемент
Находит
— некорректно работает, если элемента в массиве нет
Это есть. Нужно после проверки на равенство добавить: or (step==1 and '-1')
— некорректно работает, если в массиве есть повторяющиеся элементы
Корректно. Возвратит индекс первого, на который наткнется
— обращение к элементами за пределами массива
Не особо понял, но есть такая замечательная вещь — исключения.
This comment wasn’t rated yet0
На любом языке могу писать как на Хаскелле? :)
Total votes 7: ↑7 and ↓0+7
Если мне на собеседовании пишут такой код (были красавцы), обычно именно на этом я и ставлю точку.
Total votes 10: ↑4 and ↓6-2
Вы на собеседовании требуете написания на листочке красивого кода с комментариями?
Total votes 6: ↑5 and ↓1+4
На доске, комментариев не надо ;-) И красивого тоже не надо — надо понятного.
Total votes 10: ↑4 and ↓6-2
Код вполне понятен. Тем более на доске условие в lambda-функции было бы расписано на несколько строк (в каждой по or). Вас смущают названия переменных?
Total votes 2: ↑2 and ↓0+2
Понимаете, есть такая закономерность — какой у программиста первый позыв в плане стиля, так примерно и будет выглядеть его код, который будет создаваться в моменты стресса, под давлением сроков, production failure — то есть когда нет времени сделать все красиво, надо сделать быстро чтобы работало. Это делается временно и потом остается на века. Поэтому лучше делать сразу все правильно.

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

На самом деле меня больше не претензии к коду смутили, а то, что за подобный код на собеседовании можно попрощаться с кандидатом.
Total votes 1: ↑1 and ↓0+1
У меня отлично работает на массивах порядка 100000 элементов (больше не проверял), я думаю хаскель способен соптимизировать тут рекурсию в хвостовую (обычно так и бывает), хотя стоит проверить.

А насчет собеседований, у меня довольно большой опыт по набору, и я бы такого человека спросил во-первых почему он так написал, во-вторых если решение работает это уже плюс, а если он еще сможет переписать по-другому в более традиционной форме это бы для меня был еще больший плюс, так что такой товарищ имел бы однозначное преимущество перед тем кто сразу выдал стереотипное решение.
Те, кто выдает шаблонные решения на собеседованиях обычно потом хуже работают по моему опыту.
Total votes 2: ↑2 and ↓0+2
не «соптимизировать рекурсию в хвостовую», а соптимизировать хвостовую рекурсию в цикл.
This comment wasn’t rated yet0
Хаскель делает из рекурсии циклы?
This comment wasn’t rated yet0
любой компилятор Хаскелля обязан выполнять оптимизацию хвостовых вызовов (и не только рекурсивных). Если это хвосторекурсивный вызов, то скорее всего оптимизатор преобразует его именно в цикл
Total votes 1: ↑1 and ↓0+1
он не обязан. Он просто это сделает, ради повышения производительности.
This comment wasn’t rated yet0
да нет. он как раз обязан. по стандарту.
This comment wasn’t rated yet0
мда… опять надо было сначала обновить. извините
This comment wasn’t rated yet0
беру слова обратно. похоже что, в отличии от SML и Ocaml, в стандарте хаскелля этого нету. и это печально
This comment wasn’t rated yet0
в CL кстати тоже это не требуется, но всячески было бы круто иметь. А вот в schema например это чуть ли не must have.

Кстати, а разве есть стандарт на O'Caml?
This comment wasn’t rated yet0
вот в Scheme точно есть :)
ocaml нет стандарта, но там есть «стандартная» реализация и она дефакто стандарт.
This comment wasn’t rated yet0
Это не печально, из-за ленивости Хаскелю нет нужды оптимизировать хвостовую рекурсию.
This comment wasn’t rated yet0
не совсем понимаю как это связано с ленивостью. можно подробней?
This comment wasn’t rated yet0
Совсем нет, есть рекурсия хвостовая, а есть не хвостовая, но которая может быть преобразованна в хвостовую, тут как раз этот случай.
А то что хвостовая рекурсия на самом деле потом превратится в цикл это всем понятно.
This comment wasn’t rated yet0
если вы про этот код #, то там все вызовы на хвостовых позициях, ничего преобразовывать не надо.
This comment wasn’t rated yet0
Правда ваша, я просто думал про другой код который я писал паралелльно и думал, что тут у меня также, а счас глянул, а там оказывается все проще, действительно хвостовая. Как говорится написал и забыл :)
This comment wasn’t rated yet0
А можете показать пример не хвостовой рекурсии, в хвостовую?
This comment wasn’t rated yet0
Один из способов это аккумулирование результата

factorial 0 = 1
factorial n = n * factorial(n-1)

tailFactorial n = helper n 1
where
helper 0 a = a
helper n a = helper (n-1) (n*a)
Total votes 1: ↑0 and ↓1-1
Нет, это понятно.

Я хотел пример рекурсии, которую компилятор сам так прооптимизирует!
This comment wasn’t rated yet0
Не думаю что-то есть такие компиляторы. К тому же в некоторых случаях в ленивых языках от такого преобразования может стать хуже)
This comment wasn’t rated yet0
собственно я о том же. Вот и хотел увидеть код, который компилятор сможет соптимизировать
This comment wasn’t rated yet0
Знаете, проблема сроков — это проблема менеджмента. И если у вас давление сроков и т.п. — то у вас, наверное, лучше не работать, ибо менеджмент у вас слаб.
Total votes 5: ↑3 and ↓2+1
Не в менеджменте дело (то есть и в менеджменте, но не всегда в нем). В компании, где я сейчас работаю, проблемы со сроками случаются реже на порядок, чем во всех остальных, в которых я работал до этого — но они случаются, и когда они случаются, надо уметь достойно выходить из таких ситуаций.
Total votes 1: ↑0 and ↓1-1
Кто называет сроки?
This comment wasn’t rated yet0
Вы не поверите — иногда они образуются сами, вообще без какого бы то ни было участия с нашей стороны. Если интересно — расскажу об одном из наших проектов, который пришлось завершать в супер-пожарном режиме.
This comment wasn’t rated yet0
Вот когда «оно само» — это точно просчёт менеджмента.
This comment wasn’t rated yet0
Не, это не просчет. Это повод уволить его. Если технический специалист говорит что А делать 2 недели, то это проблема менеджера, что он заложив почку, пообещав счастья через 3 дня.
Total votes 1: ↑1 and ↓0+1
А если технический специались говорит, что это делать три дня, а делает это три недели? Это тоже просчет менеджера?
This comment wasn’t rated yet0
Это проблемы уже тех. специалиста.

Вообще хороший менеджер умножает на коэффициент программиста, а потом результат на 2.
This comment wasn’t rated yet0
С радостью выслушаю. Но это проблема менеджмента!
Total votes 1: ↑1 and ↓0+1
> код, который будет создаваться в моменты стресса, под давлением сроков, production failure — то есть когда нет времени сделать все красиво, надо сделать быстро чтобы работало. Это делается временно и потом остается на века. Поэтому лучше делать сразу все правильно.

Какие-то у вас стрессы и сроки «детские» видимо. :-)

Когда реально сроки давят и бизнес-процесс стоит — тогда надо написать «грязно», но чтобы работало. Чтобы падало раз в полчаса, но шелловый скрипт автоматом перезапускал. В общем, чтобы через 2 часа после постановки задачи бизнес процесс пошел. А не так, что код красивый, комменты на месте и внятные, ошибок нет, но готово только послезавтра, когда заказчик уже застрелился.
Total votes 1: ↑1 and ↓0+1
Добавлю, что после таких «кредитов» в ущерб архитектуре обязательно должен идти этап восстановления и наведения красоты. Только вот этот этап обычно пропускают. Из-за менеджмента, который не видит целесообразности, и из-за программеров, которые исповедут принцип «работает — не трожь». В результате мусор накапливается, работа замедляется, сами себе же роют могилу, вместо исправления багов патчат битые данные в базе.
Total votes 1: ↑1 and ↓0+1
Сейчас один проект как раз на такой фазе.

И с вашим комментом я согласен, разумный он. И оплату получаю почасовую (так что за причесывание кода отдельно можно деньги получить). И… все равно сомневаюсь — надо ли? Потому что да — работает — не трожь. Тем более, прямо перед самым запуском проекта, после всех долгих тестов.
This comment wasn’t rated yet0
Перед самым запуском не стоит, и времени может не хватить на переделку, и тесты придется прогонять по новой. Риск слишком велик.

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

Вроде бы, вопрос только в том, насколько быстро все рухнет. И вот здесь реальность меня удивила. Оно никогда не рухнет. Просто превратится в помойку, а удовольствия от жизни на помойке никакого.
This comment wasn’t rated yet0
А можно узнать маштабы команды?
This comment wasn’t rated yet0
Да небольшая — 2-3 человека (смотря кого считать человеком :-))

И проект тоже не очень большой, но замудреный — некоторые алгоритмы писались на «интуитивно-анальном понимании принципа работы», поэтому без комментариев там через год уже не разобраться, а лишний if или лишняя вложенность и без того замудреный алгоритм делают совсем непонятным.
Total votes 2: ↑2 and ↓0+2
Хм. Знаете, у вас маленькая команда.

Я говорил про системы несколько большего объема и которые разрабатывают не один десяток человек.

При длине проекта в полгода и размере команды в 3, его можно за полгода повторить, с нуля.
This comment wasn’t rated yet0
«смотря кого считать человеком» — вижу, накипело :)
This comment wasn’t rated yet0
да нет, все не так мрачно :-)
просто роли у всех разные и техническая вовлеченность в реализацию — тоже.
This comment wasn’t rated yet0
а с этого момента я хочу больше деталей!
This comment wasn’t rated yet0
не очень понимаю любопытство — проект не столь интересен с технической точки зрения. еще один проект на 2-3 человека. совсем не яндекс или mail.ru по интересности реализации. Возможно вы где-то не так меня поняли и представляете какой-то мегапроект.

А что касается «человечности», раз уж спросили, то «человек под вопросом» — это менеджер, который участие в проекте принимает (обсуждает фичи напр), но код не пишет.
This comment wasn’t rated yet0
Вот таким способом и получается антипаттерн «многослойный говнокод», который в итоге хрупок и нереюзабелен настолько, что его проще выкинуть в мусор целиком.
This comment wasn’t rated yet0
Все верно.
Но дилемма в том, чтобы выбрать одно из двух
1) выпустить стабильный продукт (который дествительно стабильный, оч хорошо оттестированный итд)
2) причесать код, и зарелизить нетестированную версию (либо еще месяц тестировать все с нуля)
где-то случайно сделать что-то вроде:

исходный код:
if(a)
b
c

ошибка при причесывании:
if(a){/*comment*/
b /*comment*/
c /*comment*/
}

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

у любого действия есть свои плюсы и минусы, и то, что вроде как right way с точки зрения программиста, который любит работать с красивым кодом — не всегда right way с точки зрения успешности проекта.
Total votes 1: ↑1 and ↓0+1
«у любого действия есть свои плюсы и минусы, и то, что вроде как right way с точки зрения программиста, который любит работать с красивым кодом — не всегда right way с точки зрения успешности проекта.»
У кода есть следующие достоинства (в порядке убывания приоритета):
1. Работоспособность (в идеале — корректность).
2. Читабельность.
3. Гибкость.
4. Красота (получается, что в случае чего красотой жертвуют в первую очередь).
Проблема в том, многие менеджеры и разработчики, пожарящие перед релизом забывают простую истину — недоработки при исполнении увеличивают общие трудозатраты.
Надо заранее иметь в виду, что запуск первого релиза за счет недели аврала — это минимум две недели отставания от запуска второго. Если после выхода промежуточного релиза нет готовности безжалостно сносить пожарный говнокод, то отставание может составить месяц и более. Более того: чем больше пожарного кода — тем менее предсказуемы сроки выхода следующих релизов.
This comment wasn’t rated yet0
тут немного другая ситуация.
Да, как и везде, «надо — вчера». И чем раньше будет релиз — тем лучше, тем более, что первоначальные оптимистичные сроки уже прошло. НО нет пожара. Пишется «обвязка», мелочи-красивости, не затрагивающие само ядро проекта. А оно и оттестировано уже очень хорошо, и изменения в него практически не вносятся. Именно по этой причине (то что код там не очень читаем, но при этом очень надежен — насколько только можно судить об этом на основании долгих тестов) и не хочется делать с ним ничего, что хоть как-то изменит md5sum исходников :-). Потому что если это сделать — то мы получим не только удобочитаемый код, но и саму программу, которая черт знает как работает — вроде по идее наши правки были только в области «красивостей» и никак не должны влиять на логику программы, но ведь кто знает — так что по хорошему, после месяца тестирования и дописывания комментария /* this function does something */ — чтобы убедиться что все в порядке, надо б еще месяц тесты погонять.
This comment wasn’t rated yet0
Знаете, после того как вы один раз наступите в в дорожку с таким кодом, вы оттуда не вернетесь. Ваш менеджмент познает, что деля ваши сроки на два, то получается результат.

Вообще есть интересная проблема, что красивый дизайн приложения подразумевает что оно будет жить 100500 лет. Только вот, не факт, что компания доживет пока вы будете делать красивый дизайн.
This comment wasn’t rated yet0
Обратная ситуация: говнокод, хотели продать проект побыстрее, потом кризис, невыгодная ситуация, да и конкуренты как-то рванули вперед, приходится продолжать свой бизнес. В результате теперь любая новая фича требует нечеловеческих усилий на реализацию, а несколько программистов вычерпывают говна full-time.

Но всем похуй. Менеджмент не способен понять ситуацию (не успеваете? сколько людей добавить?), программеру комфортно и так, лишь бы платили.
This comment wasn’t rated yet0
Грань тонкая, да.

Ситуация когда приходиться программистов делать говно, много лучше, чем когда они это хотят делать.
This comment wasn’t rated yet0
Еще есть такое заблуждение, что красивый дизайн садятся, делают, сдают готовый.

Красивый дизайн кристаллизуется в течение 100500 лет, неудачные решения отмирают, удачные остаются. Это работает только в том случае, если находятся люди, способные отличить одно от другого.

Красивый дизайн красив не маникюром и педикюром, а тем, что эффективно решает поставленные задачи.
This comment wasn’t rated yet0
Хе-хе. Только переписать это не получается, ибо всегда есть такой бардак в голове у менеджера, и это становится стилем работы.

Сказать что это плохо? Нет. Это жизнь. Но все-таки это проблема менеджмента.
Total votes 1: ↑1 and ↓0+1
Поддерживаю. А то потом будут такой же production-код лепить.
Total votes 3: ↑1 and ↓2-1
Зачем на доске? Стиль псевдо-академичности чтоли придать?
This comment wasn’t rated yet0
Не совсем. Чтобы кандидат объяснял, что он пишет. Если он уткнется в лаптоп, хрен ты из него что выбьешь, а вот у доски он волей-неволей начнет вслух рассуждать и объяснять. А мне именно это и надо.
Total votes 1: ↑1 and ↓0+1
Не примите близко к сердцу, но что-то странное у вас там, то вам лямбда функции не нравятся, то у доски писать заставляете… Многие люди вообще на доске в жизни код не писали, мне вот например сложнее мыслить с доской, нежели «уткнувшись в лэптоп», так зачем же ставить претендента, у которого и так стресс в виде собеседования, ещё и в дополнительно неудобное положение у доски?

И вообще, зачем кандидат должен объяснять что он пишет в процессе? Вот написал, если не работает, тогда пусть объясняет, а если всё ок, то к чему лишнии слова? Код — куда красноязычнее чем любая вербальная речь.
This comment wasn’t rated yet0
хм, спрашивать на собеседование код? Это же моветон. Все передовые рекуртеры просят спарвку из психдиспансера! Настоящий программист без справки не программист!
Total votes 4: ↑3 and ↓1+2
Ну вот мы как-то так любим чтобы наши программисты умели программировать, да.
Total votes 4: ↑0 and ↓4-4
программист должен уметь держать в голове много абстракций. Научить его питону или другому языку — это дело пары недель. А вот научить его держать в голове кучу абстракций — нельзя. Это уже состояние психики и оно граничит с шизофренией. Собственно из-за этого и стоит спрашивать справку.

На собеседование можно понять только ширину кругозора. И прикинуть, сможете ли вы заинтересовать такого кадра, или нет.
Total votes 2: ↑1 and ↓10
А кто говорит про кучу? Я же не требую его вкратце рассказать мне про то, как работает collaborative filtering или чем maximum entropy классификатор отличается от баесовского? (хотя в каких-то случаях буду требовать именно этого, но это очень особые ситуации). Я всего лишь прошу знания основ. Вы же не считаете, что знание, сколько битов в байте, что такое сортировка и что такое двоичный поиск чем-то запредельно сложным и абстрактным?

Ну а если вы знаете это, и вы действительно хороший программист, для вас не составит ни малейшего труда написать код. Да, на доске, да, возможно, с ошибками — но написать, а не рассуждать о своем кругозоре и огромном опыте.
This comment wasn’t rated yet0
Сколько битов в байте. Это факты. Мы с вами можем знать разные факты, как нам быть?

Какой код? Давай те пример задачи?
This comment wasn’t rated yet0
Пример задачи? На что? На сколько битов в байте? Ну посчитайте что ли сколько битов установлены в байте, а сколько — нет ;)
This comment wasn’t rated yet0
>Ну посчитайте что ли сколько битов установлены в байте, а сколько — нет ;)

И не просто посчитайте, а с минимальным использованием памяти. А потом — с минимальным использованием времени ;)
This comment wasn’t rated yet0
Давай те больше условий! Язык реализации, например. Ну и платформу, например.
This comment wasn’t rated yet0
UFO just landed and posted this here
Вам отказали на собеседовании? Не переживайте. У вас еще будет шанс.

А я не имею права принимать или не принимать — я лишь имею право сказать, понравился мне кандидат или нет. Если кандидат пишет спагетти-код, то он мне сразу перестает нравится.
Total votes 6: ↑2 and ↓4-2
вам нужен человек который думает и имеет мозги, или кодогенератор?
Total votes 4: ↑2 and ↓20
Мне нужно чтобы человек не только умел думать, но и умел писать код. К сожалению, сейчас очень мало внимания уделяется умению именно хорошо кодить, слово «кодер» стало чуть ли не ругательным — все менеджеры, лидеры, и прочая, кодеры — быдло. А я кодер. Очень хороший кодер, который умеет кодить эффективный код, который работает быстро и надежно. И на собеседовании я требую от людей того же самого — а именно, умения писать красивый, чистый, хорошо и быстро работающий код. Я что, чего-то странного хочу?
Total votes 5: ↑3 and ↓2+1
Точно так же считаю. Я в роли лидера начал немного терять связь с реальностью. — «Че? Вот на это ты потратил 2 дня? Да это же шаблончики, тут полчаса максимум». А потом сам сел за эти шаблончики, и за день до ума не довел.
Total votes 2: ↑1 and ↓10
Что есть эффективный код? Где его можно посмотреть?
Total votes 2: ↑1 and ↓10
Хватит троллить. Эффективный код — это код, который работает быстро, надежно, легко поддерживается, и содержит минимальное количество ошибок.
Total votes 4: ↑2 and ↓20
Код либо работает быстро, либо выглядит красиво, либо его легко поддерживать.

А про ошибки, все проще, их более менее const. И этот показатель не зависит не от чего.
Total votes 3: ↑3 and ↓0+3
Вы какой-то скучный тролль. Просто чтобы поддержать беседу, сообщу, что бывает код, который красиво выглядит и быстро работает. А еще его легко поддерживать, потому что когда программист писал его, он думал, что этот код после написания станет частью проекта, которому жить много-много лет.
Total votes 5: ↑2 and ↓3-1
Знаете, бывают ситуации когда, например, boxing/unboxing тормозит. Или арифметические операции.

Я не скучный троль, мы просто с вами в разных нишах.
Total votes 4: ↑2 and ↓20
Эффективный код — это код, который достигает желаемого эффекта.

Если желаемый эффект — по-быстрому преобразовать набор данных и выкинуть код на помойку — то можно писать в одну строку, с goto и переменными lolcat и loldog.

Если желаемый эффект — производительная, надежная и масштабируемая система — то нужно писать так, как говорит sigizmund.
Total votes 2: ↑1 and ↓10
Ага, знаю я одну систему, так ее девелопит команда в 100 человек. Архиекторы и оптимизаторы перфоманса и т.д.

Вы думаете ей от этого легче? Ой нет. Тоже самое сделает 1 человек закрывшись на полгода.

Есть такая штука промышленное программирование, а есть жизнь. Почему-то они ортогональны.
Total votes 3: ↑1 and ↓2-1
Не, архитекторов и оптимизаторов нафиг. Были, знаем. Нужно чтоб каждый кодер знал свое дело. Команда в 100 человек на один репозиторий — это медленная смерть проекта от ожирения.
Total votes 2: ↑1 and ↓10
Нет, это интересная жизнь. В таких коммандах можно годами получать зп и ничего не делать!
Total votes 3: ↑2 and ↓1+1
Архитекторов и оптимизаторов нафиг — и кодеры сразу потеряют свою ценность. Потому что они не будет знать, что делать.
Total votes 2: ↑2 and ↓0+2
Тут могут быть вопросы интерпретации, кого вы называете архитектором и кодером. Если архитектор — это средний чувак с гордым словом «architect» в названии должности и горой UML диаграмм на столе, а код он в глаза видел 5 лет назад, то кодерам без него будет гораздо лучше. Все равно вменяемой архитектуры с таким подходом он в жизнь не родит.
This comment wasn’t rated yet0
Такой «архитектор» — только в кавычках.
This comment wasn’t rated yet0
а какой архитектор, по вашему мнению, должен быть в контексте индустрии?
This comment wasn’t rated yet0
Кодирующий прототипы и каркасы, владеющий используемыми командой средствами разработки. В противном случае архитектор превращается в эрзац менеджера, скрещенного с экс-разработчиком, причем обе половины — худшие.
Total votes 1: ↑1 and ↓0+1
Не сделает. Линус бы тоже не сделал нормальное, полноценное ядро один.
This comment wasn’t rated yet0
Если выкинуть дрова — то вполне.
This comment wasn’t rated yet0
Если выкинуть дрова, то он нафиг никому не был бы нужен, кроме самого Линуса (ну, может ещё полдесятка человек).
This comment wasn’t rated yet0
знаете, я вспоминаю времена, когда фактор использования Linux говорил о том, что у человека есть мозг. И, не сказать, что я был против. Мне они нраивлись… И да. я бы их сохранил!
This comment wasn’t rated yet0
Да, хорошие были времена.

>И да. я бы их сохранил!

Зачем?
This comment wasn’t rated yet0
Сейчас приходиться делать все тоже самое. Просто сложностей и прослоек стало больше.
This comment wasn’t rated yet0
ГМ, да ну? 5-6 лет назад, как помню, KDE были совершенно неюзабельным продуктом. Полтора года назад — гораздо, гораздо лучше.

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

Если есть ностальгия по тем временам, подскажу. Возьмите Solaris/AIX/NetBSD, и вспомните те времена. Если хочется хардкора, возьмите QNX :-D
This comment wasn’t rated yet0
Предчувствую возможное негодование и упрек в троллизме. Я просто не согласен, что сейчас стало сложней и хуже. Я считаю, в этом плане линукс )особенно убунту) взял совершенно новую планку для себя за последние 3-4 года.
This comment wasn’t rated yet0
хм, какую планку? планку что его нельзя понять? Планку что ушло сообщество и к тебе относятся как к говну, написавшему патчи? Планку про то, что в lkml приходят люди, у которых не получается собрать ядро?

Мне в этом подходе нравится netbsd. Там на этапе установки, хорошая такая, планка.
This comment wasn’t rated yet0
>5-6 лет назад, как помню, KDE были совершенно неюзабельным продуктом. Полтора года назад — гораздо, гораздо лучше.

Категорически не согласен!
6 лет назад было КДЕ 3.3 (если мне память не изменяет, то в Debian Sarge было как раз 3.3.2), за которым я просидел довольно долго (пока не апгрейднулся до Etch).
1.5 года назад было КДЕ 4.1, за которым я не смог просидеть и дня — валилось на каждый чих, глючило повсеместно.
This comment wasn’t rated yet0
Я помню KDE первых версий. Помню gnome 1.4

Знаете, лучше особо с тех времен не стало. Хуже стало.
Total votes 1: ↑0 and ↓1-1
Дык, и ни нужны обычные пользователи, как вы говорите. Я гик — и хочу назад свою игрушку!
This comment wasn’t rated yet0
Java Effective Programming, Джошуа Блоха, например :) если вы яваист.
This comment wasn’t rated yet0
Ну или бессмертный Effective C++ Programming ;)
This comment wasn’t rated yet0
эти книги учат меня как готовить инструменты. Инструмент, язык, это удел подмастерья. Мастеру, творцу, все-равно на чем писать.
This comment wasn’t rated yet0
Было бы классно, если бы мастер и творец научился писать сперва по-русски.
Total votes 5: ↑3 and ↓2+1
Ха. Если перефразировать чуть-чуть, то быдлокодеру абсолютно все равно, на каком языке писать быдлокод (на любом языке можно написать программу на фортране). Это я к тому, к чему приводит такой подход — думать, что инструмент не важен.

Понимание общих философских принципов не отменяют необходимость хорошо знать инструмент (если вы все еще программист, а не архитектор/менеджер).
Total votes 1: ↑1 and ↓0+1
Знаете, я программист.

Изучить основы использования новой библиотекой это от дня до недели. Почему? Потому что я знаю много библиотек, и обычно хватает прочесть example или философскую байду.

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

Кстати, вы можете называть меня быдлокодером. Я не против.
Total votes 1: ↑1 and ↓0+1
Если это библиотека типа Log4J — да. Если это Spring / Hibernate / JBoss / ..- нет. А люди, знания которых по упомянутым монстрам ограничиваются однодневным чтением философской байды, конечно же есть. И они нужны. Называются — менеджеры :-D
А программисты с таким уровнем знаний, извините, на хрен не нужны.
Total votes 3: ↑1 and ↓2-1
Скажите мне, а что сложного в hibernate? Нет, ну вот правда? Большой, сложный ORM…
Далее, не понятно, что вы имеете ввиду знание про технологию или библиотеку.

Далее, вы путаете менеджеров и руководителей группы. Менеджер, его больше интересуют бюджеты, сроки и риски, чем библиотеки и прочие средства ограничение.
Total votes 2: ↑1 and ↓10
Скажите мне, а что сложного в hibernate? Нет, ну вот правда? Большой, сложный ORM…
— Сложного концептуально — сам подход ORM. В нем есть концептуальные сложности и проблемы, преобразования объектной модели в реляционную, ну вы сами отлично знаете.

Но даже если оставить их в стороне, то сам хибернейт, за один день вы не изучите. И за неделю не изучите. Требуется разработать на нем пару крупных проектов, чтобы стать знатоком его. Я бы сказал, требуется стать знатоком БД (ошибочное, уродское заблуждение, что можно писать хороший код на ORM, не понимая хорошо работы СУБД!!!), потом изучить хибернейт и набить шишек в нем, и потом в своем мозгу слить две эти вещи воедино, тогда можно эффективно использовать Hibernate, и достигать производельности И простоты и удобства.

Я знаете ли, видел людей, которые освоили хибейнтейт быстренько, «а че, он же несложный, и с базой не надо работать, он сам все сделает».
Они потом удрученно рассказывали, что у них тормозят все сложные экраны, и они переписывают их на HQL-запросы (!!!), т.е. по сути, отходят от Java-программирования. Граф объектов может выглядить стройно, но не все понимают, что при неправильном использовании хибернейта он раскладывается в обращения к десяткам и десяткам таблиц.

Это к тому, что людям, которые понимают общий подход, а детальные знания о багах, фичах, потенциальных проблемах, наиболее частых ошибках, собираются приобрести потом, в процессе, и за один день, техлидам в сложном и напряженном проекте делать нечего, ИМХО.

Это все разумеется, не в укор Вам, я просто привел пример.
— «Далее, не понятно, что вы имеете ввиду знание про технологию или библиотеку»
— То, что вы называете «инструмент», и хотите быть выше этого.

— Далее, вы путаете менеджеров и руководителей группы. Менеджер, его больше интересуют бюджеты, сроки и риски, чем библиотеки и прочие средства ограничение.
— А руководитель группы — это не менеджер?

Я не путаю, я намеренно упрощаю. Иные менеджеры очень любят лезть в технические мелочи и читать про технические новинки. Если хотите, можем разбить их на тимлидов, техлидов, PM-ов и прочих, в данном случае не суть.
This comment wasn’t rated yet0
Хорошо, я понял вашу позицию. Если коротко — вам не приятна не компетенция в IT. Что же, понимаю. Мне она так же не приятна.

Далее, про hibernate и другие ORM. Странно, но я не понимаю что сложного в моделе ORM, да и зачем вообще нужна ORM. Это лишняя абстракция, хотя она не скрывает, особо сильно, кишки СУБД, зато создает проблемы.
This comment wasn’t rated yet0
Да я вас и не называл и не собираюсь. Просто заметил, что выше мнение не совпадает с моим.
This comment wasn’t rated yet0
UFO just landed and posted this here
Тогда я не понимаю, о чем мы с вами спорим! Я тоже за элегантный код и строгие собеседования, а те еще перцы мне совершенно не нужны.
Total votes 2: ↑0 and ↓2-2
А собственно, зачем вы постите какой-то код на питон (похоже на поиск), в обсуждение оптимизации join-ов?
Total votes 3: ↑1 and ↓2-1
Я тоже иногда забываю ставить смайлики. Не минусуйте человека.
This comment wasn’t rated yet0
Писал много раз. Очень сильно его его невзлюбил, когда на первом курсе моя курсовая программулина работала не совсем корректно, долго грешил на поиск, оказалась банальность с поиском не связанная отделяла меня от счастья… Потом снова повторения мать учения на третьем курсе, и вот тут совсем недавно на питоне и то с первого раза не заработал. Кнут прав :)
Total votes 1: ↑1 and ↓0+1
Action script 3
Писал давно гдето минут 15-20.
Насчет «без тестирования», то не получилось так как написал юнит тест.

package com.kavalok.utils.sorting {
import com.kavalok.collections.ArrayList;
import com.kavalok.interfaces.IComparer;
import com.kavalok.interfaces.ISorter;
import com.kavalok.utils.comparing.ComparingResult;
public class QuickSorter implements ISorter {
public function sort(list: ArrayList, comparer: IComparer): void {
_list = list;
_comparer = comparer;
executeSort(0, list.length);
}
private function executeSort(begin: uint, length: uint): void {
var i: Number = begin;
var j: Number = begin + length — 1;
var currentElement: Object;
var temp: Object;
var centerIndex: uint = uint(begin + length/2);
currentElement = _list.getItemAt(centerIndex);
do {
while (_comparer.compare(_list.getItemAt(i), currentElement) == ComparingResult.SMALLER) i++;
while (_comparer.compare(_list.getItemAt(j), currentElement) == ComparingResult.GREATER) j--;
if (i <= j) {
temp = _list.getItemAt(i);
_list.setItemAt(_list.getItemAt(j), i);
_list.setItemAt(temp, j);
i++; j--;
}
} while ( i<=j );
if ( j > begin ) executeSort(begin, j — begin + 1);
if ( begin + length > i ) executeSort(i, begin + length — i);
}
private var _list: ArrayList;
private var _comparer: IComparer;
}
}
Total votes 3: ↑1 and ↓2-1
… и мой код на питоне перестал казаться мне таким уж жутким.
Total votes 26: ↑26 and ↓0+26
Любой код без форматирования выглядит жутковато)
ну и половину текста — импорты и всякая хна.
+ немного портит впечатление интерфейс IComparer — в АС3 нет перегрузки операторов, к сожалению.
Total votes 4: ↑4 and ↓0+4
Можно вставлять код
  <pre>вот так</prе>
Тогда отступы сохранятся.
Total votes 4: ↑4 and ↓0+4
у меня такое ощущение, что здесь быстрая сортировка, а не бинарный поиск
Total votes 1: ↑1 and ↓0+1
ууупс. затупил. читал статью по диагонали. прошу простить или заминусовать.
This comment wasn’t rated yet0
public int BinarySearch(int[] data, int asked)
{
if(data!=null && data.Length>0)
{
int leftEdge = 0;
int rightEdge = data.Length-1;
int index = 0;
bool work = true;
do
{
index = rightEdge — leftEdge;
if(index/2 > 0)
{
if(data[index]>asked)
{
rightEdge = index;
}
else if(data[index]<asked)
{
leftEdge = index;
}
else if(data[index] == asked)
{
return index;
}
}
else return null;
}while(work);
}
}

//С#
Total votes 3: ↑1 and ↓2-1
Ваш код зацикливается вот на таких данных:
массив: [2, 4, 6, 8, 10]
поиск числа 2
This comment wasn’t rated yet0
Да, уже понял… все же сходу сложно оказалось.
This comment wasn’t rated yet0
если можно, немного не по по теме топика вопрос: а в C# допустим return null, если тип функции int? Просто интересно, т.к. с С# практически не знаком :)
This comment wasn’t rated yet0
Нет, не допустим. null только для ссылочных типов.
Total votes 1: ↑1 and ↓0+1
спасибо! я так и думал :)
тогда, правильно ли я понимаю, что код работать не будет для случая массива из 1-го элемента?
This comment wasn’t rated yet0
можно поиграться с nullable ;)
int? x;
This comment wasn’t rated yet0
да, действительно, но я бы все же вернул число, например, -1 в качестве индекса несуществующего элемента.
This comment wasn’t rated yet0
pastie.org/927590
похапе, 10 минут. не уверен, что без ошибок :) тяжело писать и не тестировать :)
Total votes 1: ↑1 and ↓0+1
нда, действительно :) вместо ceil нужно floor и вместо 1 — 0. а так всё работает :)

зы: посмотрел на википедии, там развёрнуто в цикл. рекурсивное решение считается правильным? ;)
This comment wasn’t rated yet0
Разве для (1,2,3,4,5) и искомого числа 4 или 5 вернется правильное значение?
This comment wasn’t rated yet0
>> рекурсивное решение считается правильным?

А пхп умеет оптимизировать хвостовую рекурсию?
Если нет — то я бы не засчитал.
Total votes 1: ↑1 and ↓0+1
Двоичный поиск и без ошибок писал совсем давно. Еще в эпоху паскаля. Но смысл в нем не вижу, есть более оптимальные алгоритмы поиска.
Total votes 2: ↑1 and ↓10
Возможно первое правильное решение здесь.
Total votes 1: ↑0 and ↓1-1
кстати, думал что управлюсь за минуту — две. включая вторую версию — минут 10 точно уже прошло :)
This comment wasn’t rated yet0
UFO just landed and posted this here
Содержат ошибки — хорошо?
Total votes 3: ↑2 and ↓1+1
UFO just landed and posted this here
В универе писал на ассемблере около часа, не сразу но заработало.
This comment wasn’t rated yet0
C#
pastie.org/927603
5 минут, алгоритм не реализовывал лет 7.

P.S. массив arr — объявлен переменной класса.
This comment wasn’t rated yet0
умирает, когда 0 элементов.
This comment wasn’t rated yet0
Часто использую разные вариации (под определенный тип исходных данных) бинарного поиска.

Вот вариант на Objective-C — расширение класса NSArray
pastie.org/927604

Минут 10 ушло по памяти написать. Обычно копи-пастом удобнее :).
This comment wasn’t rated yet0
Процент программистов спосбных написать тернарный поиск еще меньше.
Total votes 5: ↑5 and ↓0+5
кстати, тоже базовый алгоритм.
This comment wasn’t rated yet0
учитывая, что с двоичным возникли проблемы, про тернарный и не стоит заикаться. :)
This comment wasn’t rated yet0
а я смотрю, Дональд Кнут — оптимист…

«Только 10% программистов способны написать.» — правильнее?
Total votes 1: ↑1 and ↓0+1
int binsearch(int* a, int n, int key)
{
    int lo = 0;
    int hi = n - 1;

    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (key > a[mid])
            lo = mid + 1;
        else
            hi = mid;
    }

    return a[hi] == key ? hi : -1;
}
Total votes 4: ↑3 and ↓1+2
Черт, не работает при n = 0. Ну ладно, остальное вроде бы выглядит правильно.
This comment wasn’t rated yet0
BinarySearch proc ;params: array (of integers), length, target
push ebp
mov ebp, esp

mov ebx, [ebp + 8]
mov ecx, [ebp + 12]
xor edx, edx
dec ecx
jmp LoopCond
LoopStart:
mov eax, edx
add eax, ecx
shr eax, 1
push ecx
mov ecx, [ebp + 16]
cmp [eax * 4 + ebx], ecx
pop ecx
je Exit
jl UpperHalf
mov ecx, eax
dec ecx
jmp LoopCond
UpperHalf:
mov edx, eax
inc edx
LoopCond:
cmp ecx, edx
jge LoopStart
mov eax, -1

Exit:
pop ebp
ret
BinarySearch endp
Total votes 32: ↑31 and ↓1+30
Тоже вроде бы при n = 0 не работает:
если [ebp + 12] = 0, тогда после dec ecx получается ecx = -1, edx = 0. После shr eax, 1 получается eax = 0x7fffffff, ну и потом eax*4 + ebx указывает на непонятное место в памяти.
Total votes 4: ↑4 and ↓0+4
Я не понял, сделал выводы :(
Total votes 2: ↑1 and ↓10
Черт, залип. Уже ничего не помню на асме (
грустно
This comment wasn’t rated yet0
и вам привет от спектрумистов (Z80 assembler): pastie.org/927781

; Input:
; HL = pointer to sorted array
; BC = array length (must be less than 32767, not tested, but just for case)
; A = search value
;
; Output:
; HL = pointer to value or 0 if not found
; BC = undefined
; DE = undefined

binary_sort:
push hl
add hl,bc
ld b,h: ld c,l
dec bc
pop hl

binary_sort_1:
ld d,h: ld e,l
and a: sbc hl,bc
jp nc,binary_sort_2

ld hl,0
ret

binary_sort_2:
ld h,d: ld l,e
add hl,bc
and a: rr h: rr l

cp (hl)
ret z

jp c,binary_sort_3

ld b,h: ld c,l
dec bc
ex de,hl
jp binary_sort_1

binary_sort_3:
inc hl
jp binary_sort_1

(если убрать двоеточия после меток и поставить убранные парсером табы перед коммандами, то должно компилироваться в ALASM (на самом спеке) либо в sjasmplus (кросскомпилер). естественно, не проверял :))
Total votes 4: ↑4 and ↓0+4
А еще вот это подозрительное место:
add eax, ecx
shr eax, 1

Наверно, лучше бы было сделать вот так:
shr eax, 1
shr ecx, 1
add eax, ecx

дабы избежать переполнения при больших массивах.
This comment wasn’t rated yet0
//А че-то лень писать…

0 минут. Не тестировал.
Total votes 15: ↑2 and ↓13-11
не компилируется вот эта строчка

return A[first] == val? first: null;

val типа int, а Вы используете вместе с ним null
This comment wasn’t rated yet0
Ну, val тут не причем))
А так?
int? getIndexOf(int[] A, int val)
{
     int first = 0;
     int count = A.Length;

     while(count>1)
     {
         count=count/2;
         int i = first+count-1;
         if (A[i]== val) return i;
         if (A[i]<val) first+=count;
     }

    if (count==1)
        return A[first]==val? (int?)first : null;

    return null;
}
This comment wasn’t rated yet0
ну это так… мелочь.

также не работает поиск последнего числа в массиве
This comment wasn’t rated yet0
забыл написать, язык С#
This comment wasn’t rated yet0
> есть упорядоченный массив, берем число из середины массива, сравниваем с искомым. Если оно оказалось больше, значит искомое число в первой половине массива, если меньше — во второй

Т.е. массив был заранее отсортирован и на это было потрачено время?

И зачем оно такое надо вообще?
Total votes 9: ↑0 and ↓9-9
в большинстве случаев массив сортируется 1 раз для многократных поисков по нему…
This comment wasn’t rated yet0
Вообще то бинарный поиск работает только в упорядоченном массиве. Вот незнание этого факта, да, настораживает.
This comment wasn’t rated yet0
function array_search($needle, $haystack) {
    if (!is_numeric($needle)) {
        trigger_error('Invalid argument needle. Numeric expected.');
        return false;
    }
    if (!is_array($haystack)) {
        trigger_error('Invalid argument haystack. Array expected.');
        return false;
    }

    sort($haystack, SORT_NUMERIC); // это тестировал

    $length = count($haystack);

    $from = 0;
    $to = $length - 1;

    $result = false;
    while ($result === false) {
        if ($to > $length - 1 || $from < 0) {
            $result = null;
        } else {
            $index = floor(($from + $to) / 2);
            if (!is_numeric($haystack[$index])) {
                trigger_error('Invalid value of argument haystack. Only numeric values allowed.');
                return false;
            }
            if ($haystack[$index] > $needle) {
                $to = $index - 1;
            } elseif ($haystack[$index] < $needle) {
                $from = $index + 1;
            } else {
                $result = $index;
            }
        }
    }

    return $result;
}

echo array_search(5, array(3, 76, 8, 4, 2, 2, 1, 5, 2, 3, 1, 2, 5, 7, 2, 3)) . "\n";


Пыхапе. Пол часа. И что-то мне подсказывает что с первого раза не взлетит…
Total votes 2: ↑1 and ↓10
перепутал
if ($from > $length — 1 || $to < 0) {

надо
if ($to > $length — 1 || $from < 0) {

и возвращает индекс отсортированного массива а не исходного, хотя в задаче массив изначально отсортирован.
А, и ещё — Fatal error: Cannot redeclare array_search()
Total votes 1: ↑0 and ↓1-1
pastie.org/927632
C#, 15 минут, 1 тест. Упал с оверфлоу — ошибку пофиксил и остальные две проверки прошли нормально.
This comment wasn’t rated yet0
Блин, пока писал тут коментов то понабралось. Сразу вопрос — а почему у всех массив сортированный? Я что не правильно помню алгоритм? Мне казалось, что сортированные данные — это частный случай…
This comment wasn’t rated yet0
А как вы будете искать в случайном несортированном массиве кроме как полным перебором?
This comment wasn’t rated yet0
Полным перебором с постоянный разбиением на подсэты — грубо говоря проход по бинарному дереву. Вообщем то это и реализованно в сорсе на пасте.
Total votes 1: ↑0 and ↓1-1
Интересно на это посмотреть, ведь формирование бинарного дерева из произвольного массива само по себе требует операций больше, чем O(n).
Total votes 2: ↑1 and ↓10
Сорс приложен и перед комментированием могли бы и посмотреть. Ваше замечание про формирование дерева и O(n) не имеют никаких оснований.
This comment wasn’t rated yet0
По эффективности ваш метод ничем не отличается от простого перебора.
На рекурсию только ресурсы тратятся и все.
This comment wasn’t rated yet0
Как и любой другой поиск в не сортированном массиве
This comment wasn’t rated yet0
Просто привычки вчитываться в постановку задачи:
С массивами так: есть упорядоченный массив, берем число из середины массива, сравниваем с искомым.
Total votes 1: ↑1 and ↓0+1
Да, точно — мой промах.
This comment wasn’t rated yet0
Мне нравится Ваш подход с рекурсией. Красиво и наглядно. :)
This comment wasn’t rated yet0
с современными компьютерами производительность часто оказывается менее важной, чем легкость восприятия кода.
This comment wasn’t rated yet0
А потом мы удивляемся, почему сиране браузер, в котором открыт пяток страниц, отъедает аж 350!!! Mb оперативной памяти.
Total votes 3: ↑2 and ↓1+1
Я согласен с Вами, что производительность важна.
Просто в некоторых ситуациях производительность — не самая важная характеристика программы.
This comment wasn’t rated yet0
Да, надо было этим быдлокодерам писать на асме, вот тогда бы он летал!
This comment wasn’t rated yet0
Не должно быть медленнее любой другой реализации на C# для не сортированного массива…
This comment wasn’t rated yet0
Накладные расходы на вызов метода всегда намного больше, чем на итерацию цикла.
This comment wasn’t rated yet0
Красивая реализация без рекурсии и при отсутствии условия сортировки вряд ли получиться. Рекурсия лишь тем и хороша — краткостью и доступностью к пониманию.
Total votes 1: ↑0 and ↓1-1
sorry, пропустил про «не сортированного»
This comment wasn’t rated yet0
Теоритически да. Но хотелось бы профайлинг репорт и ассемблерный листинг.
This comment wasn’t rated yet0
По секрету скажу… Как-то проводил собеседования, никто из проходивших не смог навскидку даже «пузырька» написать. И тоже все серьезные люди.

p.s. Целесообразность таких вопросов на собеседовании — отдельная тема.
This comment wasn’t rated yet0
Как-то проходил собеседоваение… навскидку смог написать на доске один довольно сложный динамический алгоритм, с использованием стека и прочих радостей жизни. В жизни с первого раза я бы его написать не смог. Собеседование прошел.
Total votes 2: ↑1 and ↓10
import java.util.*;
public class Main{
   public static void main(String[] argv){
      int[] a=new int[] {1, 4, 12, 15, 18, 22, 26, 37};
      System.out.print(Arrays.binarySearch(a, 18)); //4
   }
}
1 минута
Total votes 6: ↑5 and ↓1+4
Слишком долго для такой реализации :3
This comment wasn’t rated yet0
До 2006 года ваша реализация содержала ошибку, о которой и пишет Блох в статье по ссылке из поста :)
Total votes 5: ↑5 and ↓0+5
Руби
pastie.org/927639
Правда, не совсем без тестов — две строки внизу меня хоть успокоили…

Дальше можно вылизывать
Total votes 2: ↑2 and ↓0+2
Да, конечно кусок
arr = [1,2,3,4,5]
(arr+[7]).each{|z| p bis(arr,z)}

должен быть вложен в
begin

end if (__FILE__ == $0)


Забыл про собственные сниппеты.
This comment wasn’t rated yet0
Выдалось ещё 7 минут — вылизал.
pastie.org/928137
Добавил весьма обнадёживающий бенчмарк:
user system total real
Built-in Array::index 6.950000 0.020000 6.970000 ( 7.735154)
My own binary search 0.900000 0.030000 0.930000 ( 1.195101)
This comment wasn’t rated yet0
Неудивительно — index делает перебор, а не бинарный поиск.
Total votes 1: ↑1 and ↓0+1
Извините, на первый взгляд показалось что это python
Насчет ruby не знаю. Но судя по времени — предположил бы, что так же.
This comment wasn’t rated yet0
Ну да.
Но встроенного бинарного нету, насколько я знаю.

Понятно, что существует NArray и всякие другие полезные либы.
This comment wasn’t rated yet0
Так а кто ему виноват? Или я не понял фишки.
This comment wasn’t rated yet0
Насчет ruby и python сразу не скажу (ruby вообще не знаю, python только изучаю)
В С++ недаром есть алгоиртмы find и binary_search.
Иногда нужно найти элемент перебором, иногда — бинарным поиском. Встроенный метод не предполагает, что массив отсортирован.
Total votes 1: ↑1 and ↓0+1
В руби конечно стек приличный, но все же не бесконечный. А код симпатичный, читается.
Total votes 1: ↑1 and ↓0+1
Спасибо.

Да, писать на Руби имеет смысл именно чтобы алгоритм в коде читался.
Понятно, что секунда для 10000 поисков в 10000 — это не серьёзно, если речь про большие числа и большие скорости.
Зато писать приятно и быстро. И даже кому-то ещё потом за тобой это переписывать.
This comment wasn’t rated yet0
1. Жуткий боян
Было даже на developers.org.ua в 2007-м году: www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
Оригинал датируется 2006-м: googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
2. Про JDK вспомнили а про .NET забыли
3. В чём мораль? Есть что-то новое, что не было сказано в оригинальных статьях?
Total votes 5: ↑0 and ↓5-5
Ну мораль как бы не в том, что почти везде всё сломано, а в том, что это могло бы является неплохой задачкой для кандидатов в программисты. На первый уровень.

На второй уровень задачки по сложнее — есть задача, алгоритма нет.

На третий — есть задача, хрен сформулируешь.
This comment wasn’t rated yet0
На четвертый — есть заказчик, что ему надо — хрен поймешь.
Total votes 3: ↑3 and ↓0+3
И нужно его убедить, что ему нужен двоичный поиск.
Total votes 3: ↑3 and ↓0+3
Хорошего программиста пишушего подобные алгоритмы без тестирования я бы прав доступа к репозиторию лишил. Ибо за ошибку, которую он допустит на третью попытку, придётся платить.

Действительно хороший программист должен, во вторую очередь, понять, какие бывают граничные случаи поведения алгоритма, и как их нужно отработать либо задокументировать (это не баг, это фича, ага). То, что в конце топика.
This comment wasn’t rated yet0
PHP
pastie.org/927648
Время — 30 минут / финальный вариант достигнут после 3го запуска
с достаточным набором тестов для чисел. Строки не тестил, но теоретически поддерживаются =)

Решение возможно не совсем стандартное т.к. использовал рекурсию (мне так захотелось) и возможность сравнивать строки, а вариант из википедии или другие варианты не смотрел ибо было бы читерством =)
Total votes 1: ↑0 and ↓1-1
— binsearch(null, 1)
(хотя, возможно, NullPointerException можно считать тут допустимым)

— про переполнение в строке 26 уже выше было сказано
This comment wasn’t rated yet0
Это да, но раз уж Сам Блох 10 лет ее не находил, думаю мне простительно :)
Кстати посмотреть как все ломается при переполнении можно, если память есть:
pastie.org/927751
запускал с -Xmx4096m
Total votes 1: ↑1 and ↓0+1
Мне кажется, главное это понимание. Все знать не возможно.
Умный не тот кто все знает, а тот кто знает где найти ответы.
This comment wasn’t rated yet0
function bins(a,n) {
    var res=null, l=0, r=a.length, s;
    do {
        s=Math.floor((l+r)/2);
        if (n<a[s]) {r=s;} else {l=s;}
        if (a[l]==n) {res=n;s=r=l;}
        if (a[r]==n) {res=n;s=l=r;}
        if (r-l==1) l=r;
    } while (l<r);
    return [res,s];
}

var ar=[1,2,3,6,8,10,13,14,17,18,19,25];

bins(ar,1) // ok
bins(ar,6) // ok
bins(ar,4) // null

* This source code was highlighted with Source Code Highlighter.


20 мин работы.

Предусмотрены случаи:
1) чётн/нечётн/нулевая размерность массива
2) искомое меньше первого или больше последнего элемента
3) на всякий случай вывожу позицию, на которой нашлось число или остановился алгоритм

Мне не очень нравится косяк с двумя проверками на равность, но это — мелочь, наверное.
This comment wasn’t rated yet0
вы про проверку аргументов перед началом алгоритма? это я опустил. Примем за правду, что передан массив (возможно пустой)
This comment wasn’t rated yet0
Не знаю что за язык, но должно быть переполнение в вычислении среднего )
This comment wasn’t rated yet0
Язык — Javascript.
Вроде бы все переполнения обработаны :)
Если не прав — приведите пример
This comment wasn’t rated yet0
Переполнение не смотрел, НО… алгоритм немного не такой как в условии:

например, при поиске первого элемента массива (bins(ar,1)), все необходимые действия не производятся и функция отрабатывает в одну итерацию.

Далее, в любом из вариантов одна из границ остаётся в 7 элементе массива (с индексом 6), например ищем число 9 в вашем примере, и проверяется 7й элемент, а по условию он не должен участвовать вообще, так как в массиве 12 элементов и он должен делится на 0..5 и 6..11 половины.

А в остальном алгоритм хорош… у меня менее изящно получилось, сейчас свой вариант дотестирую и выложу.
This comment wasn’t rated yet0
3й абзац я написал не подумав, там никакой проблемы нет.
This comment wasn’t rated yet0
видимо все решили попасть в эти 10%
Total votes 2: ↑2 and ↓0+2
Видимо сейчас нет работы поважнее :)
Total votes 5: ↑5 and ↓0+5
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
Если new int[0], то NullPointerException, но этим грешат практически все.
findPos(new int[] {0}, 0, 0, 0); выдает ок.
This comment wasn’t rated yet0
Мой выше не грешит :)
На самом деле findPos(null, 0, 0, 0) это одно, а пустой массив это другое
П.С. Ну и в вашем случае будет не NPE, а ArrayIndexOutOfBoundsException
This comment wasn’t rated yet0
Ок, добавил array != null в первый if, теперь все ок.
This comment wasn’t rated yet0
Да нет же, вы не поняли: на пустом массиве (new int[0]) будет ArrayIndexOutOfBoundsException
This comment wasn’t rated yet0
Да, действительно) Тогда пардон муа)
This comment wasn’t rated yet0
если я не ошибаюсь, то это сродни дихотомии. Когда ищется максимум или миниум функции
This comment wasn’t rated yet0
после этого топика 99% программистов причислят себя к элитарным 10 процентам что справились с задачей =) Всех поздравляем=)
Total votes 1: ↑1 and ↓0+1
Так то процентов 10 программистов и сидят на Хабре.
This comment wasn’t rated yet0
UFO just landed and posted this here
(defun dixotomy (obj vector) 
   (let ((len (length vec)))
   (and (not (zerop len))
(finder obj vec 0 (- len 1)))))
Total votes 1: ↑1 and ↓0+1
Сорри, начал причесывать имена и нажал ctrl-enter
 (defun bin-search (obj vec)
  (let ((len (length vec)))
    (and (not (zerop len))
         (finder obj vec 0 (- len 1)))))


(defun finder (obj vec start end)
  (let ((range (- end start)))
    (if (zerop range)
        (if (eql obj (aref vec start))
            obj
            nil)
        (let ((mid (+ start (round (/ range 2)))))
          (let ((obj2 (aref vec mid)))
            (if (< obj obj2)
                (finder obj vec start (- mid 1))
                (if (> obj obj2)
                    (finder obj vec (+ mid 1) end)
                    obj)))))))
Total votes 2: ↑2 and ↓0+2
Судя по количеству скобочек, это Lisp. ))))
Total votes 1: ↑1 and ↓0+1
Ну и что? Не каждый может на память прочитать всю таблицу умножения ни разу не сбившись. В чем смысл зазубренного знания? В чем смысл статьи? Что хотел сказать автор? Не вижу.
Total votes 3: ↑0 and ↓3-3
Дело не в зубрежке, а в способности сходу выдать корректный алгоритм )
Total votes 2: ↑1 and ↓10
В статье предлагается поучаствовать именно тем, кто никогда не писал этот алгоритм. О какой зубрежке может идти речь? Что хотел сказать комментатор? Не вижу.
Total votes 1: ↑0 and ↓1-1
Комментатор хотел сказать что автор плохо читал оригинальную статью, в которой не было строгого ограничения на «никогда не писал этот алгоритм». После этого появляется резонный вопрос: 10% не реализовывавших алгоритм могут написать его с первого раза без ошибок или 10% программистов вообще?

Разница огромна. 10% программистов и 10% программистов до сих пор никогда не писавших бинарную сортировку это значения даже не разных порядков, это значения с разных сторон шкалы измерений!
This comment wasn’t rated yet0
Конечно же я хорошо читал оригинальную статью, и не вижу интереса писать алгоритм, который и так знаешь. Это не перевод, я изложил задачу так, как считаю целесообразным.

Реальная доля программистов здесь тоже не очень интересна. Ну, допустим, 70% могут написать, и что? А если 10%? Главное:
a) считаешь ли ты этот алгоритм простым как дважды два (я считаю)
б) можешь ли ты корректно и элегантно написать его без напрягов (я не могу)

Выводы у каждого свои. Мне задачка позволила немного опуститься на землю.
This comment wasn’t rated yet0
Ну так самое интересное здесь в том, что даже зная алгоритм и реализовав его ни единожды 9 из 10 программистов не смогут его реализовать без ошибок! Разве нет?

Никто не идеален — вот итог вашей статьи. Только какой вывод из этого можно сделать? Какое конструктивное решение это поможет принять? Вот это было бы интересно узнать.
Total votes 1: ↑1 and ↓0+1
А, теперь понимаю аргумент. Да, для кого-то вывод будет такой.

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

Умом, что это реально необходимо — не понять. Только на своей шкуре.
This comment wasn’t rated yet0
int binary_find(int pattern,int *arr,int length) {
int step=0,x;
x=length/2;
while(step+x < length) {
if(arr[step+x] < pattern) step+=x;
else if(arr[step+x] == pattern) return step+x;
if(x <= 1) break;
x-=x/2;
}
return -1;
}
This comment wasn’t rated yet0
словил баг
if(x <= 1) break;
x-=x/2;
терь
if(x < 1) break;
x-=x == 1? 1: x/2;

вообще наверное надо схему составлять сначала…
This comment wasn’t rated yet0
Не флейма ради, а пользы для:
— не пишите однострочных ифов без скобок
— всегда ставьте пробел после запятой
— знак присваивания, сложения и проч. отделяйте пробелами
Total votes 3: ↑3 and ↓0+3
min = 0
max = n-1
While(1)
{
mid = min+max;
If(a[mid]>need)
min = mid;else
If(a[mid]<need)
max =mid;else
Break;
}

Ответ: a[min] ближайший по значению элемент массива
This comment wasn’t rated yet0
Мда, словил последний баг из списка, переполнение на среднем )
Значит надо бы mid = min+((max-min)>>1); :-D
This comment wasn’t rated yet0
И зациклится, если числа нет в массиве.
This comment wasn’t rated yet0
Отличный пример, почему нельзя называть переменную строчной латинской L :)
Total votes 3: ↑2 and ↓1+1
Топик явно задевает =) Трудно пройти мимо такого, не проверив: «а могу ли я?».
Что касается меня — написать-то написал, но не с первого раза. =)

Тем не менее не ясна мораль данного топика. Тут либо намек на то, что не все программисты хорошо знакомы даже с простейшими алгоритмами, либо на то, что без отладки только hello-world выходит с первого раза (и то не всегда).
Но ни одно из этих двух утверждений и так не вызывает никаких сомнений =)
This comment wasn’t rated yet0
А вот код. В переполнение не верю, на премию за оригинальность не претендую.
Total votes 1: ↑1 and ↓0+1
Красиво, классический способ, по памяти или правда сходу так придумал?
Total votes 1: ↑1 and ↓0+1
Я его уже писал. И не раз. И не раз не с первого раза =)
This comment wasn’t rated yet0
Морали никакой нет, а цель есть, опустить гениев на землю. Когда понимаешь, что не можешь написать с первого раза даже такой простой алгоритм — это отрезвляет.
Total votes 1: ↑1 and ↓0+1
Морали никакой нет, а цель есть, опустить гениев на землю
Видимо меня уже давно опустило =) А гении и не такое с первого раза пишут. Те гении, что за 5 минут сочиняют алгоритм на олимпиаде, еще за 5 пишут и сдают с первой попытки. Хотя там уже скорее автоматизм и привычка правильно писать. И, конечно, огромный опыт и куча изученных алгоритмов.
This comment wasn’t rated yet0
Насчет олимпиадников и гениев — не согласен )
Олимпиадник никогда не отправит задачу не прогнав тесты+граничные условия, а потому там условия совсем другие ) С первого раза писать невыгодно, надо писать быстро и быстро исправлять ошибки :-)
This comment wasn’t rated yet0
Ну такую задачу олимпиадник напишет мизинцами ног, по пьяни, в проруби, смской.
Я имел в виду обычных программистов, которые считают себя если не гениями, то уж лучшими в своей команде наверняка. То, что таким себя мнит каждый первый — феномен заслуживающий отдельной статьи.
Total votes 1: ↑1 and ↓0+1
До этого ни разу не писал бинарный поиск — использовал библиотечные реализации языков.

10 мин — первый вариант
потом 5 минут мысленного тестирования — обнаружил один баг — добавил + 1 для правой ветки поиска.
И вот:
pastie.org/927876

Касательно типичных ошибок.
Если использовать указатели, а не индексирование массива, то практически не используется ни одна конструкция приводящая к этим ошибкам.

Мне например никогда бы не пришло в голову находить средний указатель путем (a+b)/2 поскольку операция сложения для указателей бессмысленна. А вот вычитание и сложение с числом — типичный шаблон применения указателей: a + (b — a)/2

Много упрощения в коде дает обозначение конца интервала не последним его элементом, а следующим за ним. Т.е. длина интервала end — begin, а не end — begin + 1.

Total votes 1: ↑1 and ↓0+1
Все верно говорите :) Я бы еще писал сразу return pos вместо break, и return null в конце для надежности (а то можно протерять зануление pos в конце итерации)
This comment wasn’t rated yet0
Я просто не хотел привлекать внимание фанатов единой точки выхода :))

А так — да. Когда писал, не сразу вписал pos = NULL. Но опыт не пропьешь :) Краем глаза заметил что чего-то не хватает и добавил.
Впрочем с return тоже не все ветки можно обработать, т.ч. тут скорее личные предпочтения и опыт играют роль, а не потенциальная проблемность техники.
This comment wasn’t rated yet0
Баг переполнения присутствует)
This comment wasn’t rated yet0
На пифоне — нет. На С — да. Классе в 10 решил потратить полтора часа на придумывание как можно лучшего варианта. С тех пор помню, как обходить все стандартные камни.
Кстати, проблема с переполнением не так уж и актуальна. Массивы из 2^30 элементов встречаются довольно редко.
This comment wasn’t rated yet0
pastie.org/927971
На Java за 40 минут. Изучаю джаву два месяца на досуге, такая вот проба вскрыла отсутствие знаний по многим статьям.)
Total votes 1: ↑1 and ↓0+1
Про 10% раньше не слышал, но феномен известный. Лично я показывал этот феномен своим студентам на примере алгоритма КВУР (квадратное уравнение). Ситуация аналогичная. Алгоритм простой, но редко кто может обработать все исключительные случаи за один проход.
Total votes 2: ↑2 and ↓0+2
UFO just landed and posted this here
Есть. Но цель не в том, чтобы написать ей замену, а в том, чтобы проверить себя, сможешь ли написать простой алгоритм без ошибок. Если нет — что уже тогда говорить о сложных алгоритмах. Не все же функции есть в библиотеке, иногда приходится и самому мозгами пораскинуть.
This comment wasn’t rated yet0
UFO just landed and posted this here
Просто выше уже писали об этом без всякой иронии.
This comment wasn’t rated yet0
UFO just landed and posted this here
pastebin.org/165926
Не тестировал.
Судя по спойлеру в статье — присутствует переполнение целого.
This comment wasn’t rated yet0
Если middle будет округляться в большую сторону, то там будет выход за пределы массива при отсутствии искомого элемента. Если в меньшую — будет бесконечный цикл.
Рассмотри массив из двух элементов, каждый из которых меньше или больit искомого.
This comment wasn’t rated yet0
Это целочисленное деление, в C# (и не только) результат округляется в меньшую сторону.
Если ищем больше либо меньше всех, то выходит по условию from == to на соответствующем краю массива. Ну, по крайней мере при расчёте в уме.
This comment wasn’t rated yet0
UFO just landed and posted this here
С первого раза дал сбой на краевых.

поправил в итоге получилось за 11 минуток
pastebin.com/7hvxDebu
This comment wasn’t rated yet0
Повисает на input_string = 12
У меня был в точности такой же вариант, потом еще долго пилил, пока сделал костыль для случая когда среднее заканчивается на 0.5, а потом над ним делается Math.floor. В классической реализации это красиво решено.
This comment wasn’t rated yet0
Потратил пол-часа, чтобы убедиться, что статья — развод :)
Вот, что вышло pastie.org/928188
Язык — Python
This comment wasn’t rated yet0
Да почему развод, почитайте комменты выше. Если пишете этот алгоритм в первый раз, и он сразу запустился — поздравляю, вы в 10%
This comment wasn’t rated yet0
Тогда я требую, чтобы меня взяли в гугл )))
Честно, до этого не реализовывал подобных алгоритмов. Ну, минут 5-10 на базовый цикл и еще минут 10-15 на отладку. Не знаю, лично для себя ничего сложного не увидел…
This comment wasn’t rated yet0
Ищем число 1 в массиве [2]
l = 0, r = 1 ( в этом ошибка, должно быть arr.size — 1)
в конце первой итерации получаем l = 1, r = 0, и пошло плясать.

Правильно? Или уже гоню под конец дня.
This comment wasn’t rated yet0
Но зато ошибка в другом: r = arr.size — 1
Все, я не из 10%
This comment wasn’t rated yet0
Лезем по индексу -1 если массив пустой
This comment wasn’t rated yet0
Мда, поспешные выводы дают о себе знать.
Тогда думаю в начале
return nil if arr.nil? or arr.empty?
This comment wasn’t rated yet0
[][-1] как раз вернёт nil и не является проблемой.

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

И да,
>> find([],5)
NoMethodError: undefined method `<' for nil:NilClass
This comment wasn’t rated yet0
Так, опять меня подводит незнание ruby
Python выдаст exception — и это, ИМХО, правильно.
Я бы предложил
return nil if l == r and arr[l] != value

заменить на
return nil if l >= r and arr[l] != value

Заодно убрать последний else из цикла и поставить по завершении цикла
return m
This comment wasn’t rated yet0
А мне наоборот, очевидно, что массив должен вести себя так же как хэш. И вернуть nil при запросе к элементу, не входящему в список ключей.:)
Но это, согласитесь вкусовщина.

Зато есть оператор <=>, который возвращает -1,0 или 1, в зависимости от. И он заметно упрощает восприятие кода в подобных случаях. Плюс — меньше разадресации массива, то есть более быстрый код.
This comment wasn’t rated yet0
Не получилось с первого раза, без отладки. Написал вот что.

size_t lt = 0;
size_t rt = N;

while (lt<rt)
{
size_t m = (lt+rt)>>1;
if (a[m]==aItemToFind) return m;
if (a[m]<aItemToFind) lt = m;
else rt=m+1;
}

return NOT_FOUND;

Надо было:
if (a[m]<aItemToFind) lt = m+1;
else rt=m;
This comment wasn’t rated yet0
ну, можно ещё немного улучшить…
size_t m = (static_cast(lt) + static_cast(rt)) >> 1;

или size_t m = lt + ((rt-lt)>>1);

А так вроде правильно.
This comment wasn’t rated yet0
size_t m = (static_cast<long long>(lt) + static_cast<long long>(rt)) >> 1;
This comment wasn’t rated yet0
В любом случае, проверка, что всё работает, длилась больше, чем собственно написание.
This comment wasn’t rated yet0
perl
pastie.org/928287

10 минут, тест для проверки что обрезав массив до двух элементов, виснет. после чего еще минута.
This comment wasn’t rated yet0
и еще две чтобы увидеть что не туда добавил +1 в одном месте :)
This comment wasn’t rated yet0
«10% программистов могут решить эту задачу»
Давайте разделять, решить, или решить с первого раза не запуская (т.е написать код и чтоб сразу работало) это немного разные вещи…

Со времён 40-60 годов многое изменилось, и скорость компов в том числе. На сегодняшний день работа программиста отличается от тех времён. Появилось не мало хороших инструментов позволяющих не выбивать дырки на перфокартах по откомпилированному в голове коду (потому что вторая попытка займёт весь рабочий день) а «писать-запускать-править-писать дальше» и всё это за считанные секунды.
Total votes 1: ↑1 and ↓0+1
Да уш, меня к перфокартам лучше не подпускать тогда, наверн )))
У меня обычно все, что сложнее print «hello world» с первого раза не запускается. Почти всегда есть хотя бы опечатки, а иногда и ошибки в логике, поэтому я обычно пишу по несколько строк и сразу проверяю, что все верно.
This comment wasn’t rated yet0
UFO just landed and posted this here
Это так, согласен. Но это не значит, что от решения таких задач нет толку. Смотрите, если все простые задачи уже решены за нас в стандартной библиотеке, значит нам остались только более сложные задачи, которых там нет. Как мы будем решать эти более сложные задачи, если мы не умеем решить даже простую задачу из стандартной библиотеки?

Я вам скажу как, опыта на этот счет достаточно. Очень хреново. Я делал проверку кода, когда работал в команде. Многие программисты не могли родить простейший код даже с 20 попытки! Они привыкли сидеть на готовом, они не способны написать что-то сложнее простой композиции foo(bar())
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
На C# 20 минут потратил на реализацию и 25 мин. на прогонку различных вариаций, в результате, которой заметил, что не правильно резал пополам, т.е. пока 1-у ошибку допустил, не считая бага на переполнение
pastie.org/928396
This comment wasn’t rated yet0
Еще думаю, что в принципе неправильно решать эту задачу копированием/модификацией исходного массива. Представим, что массив едва помещается в память. Я не в курсе, как работает RemoveRange в C#, но память, по-видимому, отъедается.
This comment wasn’t rated yet0
Я в школе на паскале такое фигачил :)
This comment wasn’t rated yet0

НЛО сьело длинную ссылку на картинку
Total votes 2: ↑2 and ↓0+2
Классно, спасибо. Выходит, не все так уныло в нашем царстве.
This comment wasn’t rated yet0
Может, цифры проставить? Было бы ещё нагляднее.
И Ruby с AS3 слились.
This comment wasn’t rated yet0

Цвета были сгенерированы одной строчкой случайнные, поэтому такие проблемы.
Оффтоп: кто-нибудь знает хорошие средства для работы с google char api? 10 минут гугленья ничего удобоваримого не выдали, а каждый раз руками URL формировать как-то невесело.
Total votes 1: ↑1 and ↓0+1
На своём я последний раз gRaphael использовал — удобно
g.raphaeljs.com/
Что-то типа можно делать.
This comment wasn’t rated yet0
А, виноват, вообще не разобравшись ответил, совсем не в ту степь.
This comment wasn’t rated yet0
def bin(xs, x):
  if not(xs and len(xs)): return None
  start, end = 0, len(xs) - 1
  while(start != end):
    newend = mid = (start + end) // 2
    newstart = newend if newend != start else end
    start, end = (newstart, end) if (xs[mid] < x) else (start, newend)
  return start if (xs[start] == x) else None

python. 6минут на хвосторекурсивную, минута на прогон тестов, минута на конвертацию в цикл
This comment wasn’t rated yet0
еще чуть подумал, и решил что можно красивее внутренность цикла сделать :)
def bin(xs, x):
  if not(xs and len(xs)): return None
  start, end = 0, len(xs) - 1
  while(start != end):
    mid = (start + end) // 2
    start, end = (mid + 1, end) if (xs[mid] < x) else (start, mid)
  return start if (xs[start] == x) else None
Total votes 3: ↑3 and ↓0+3
Если вместо start != end поставить start >= end
То можно (в предположении что нам передали массив, пустой или нет) избавиться от первого if'а.
This comment wasn’t rated yet0
ну как ты да :) только смысл. могут ведь передать и None
This comment wasn’t rated yet0
Смысл — меньше действий и короче (=>яснее) код.
This comment wasn’t rated yet0
ну. в 1) короче наверно не станет. потому что нужно будет return внутрь цикла вносить и проверять там на == (возможно и нет, но надо думать, а мне лень :) )
в 2) возможно кому-то и яснее, но не мне :) мне более понятно когда явно отметаются крайние случаи (None и []), чем думать о том что там в условии. да и (start != end) мне больше понятно чем (start >= end). я просто читаю код как «пока начало не совпало с концом» и не думаю о том что там есть порядок.
но опять же. это мой код, потому мне понятней. вам, наверно, другой код понятней.
This comment wasn’t rated yet0
Не разбираюсь в Perl, но попробуйте на массиве (1,2), не уйдет ли в бесконечный цикл.
This comment wasn’t rated yet0
Хотя в ваших тестах есть такой случай
This comment wasn’t rated yet0
UFO just landed and posted this here
Захотелось как то поизвращаться, поэтому получился вот такой вариант — C#, более получаса, 2 строчки:
  1. public static int Dichotomy(int[] data, int subject)
  2. {
  3.   if(data!=null)
  4.     for (int step = (data.Length - 1) / 2, stop = (int)Math.Sqrt(data.Length), lim = data.Length;
  5.          stop > -1 && step >= 0 && step < lim;
  6.          step = step + (data[step] > subject ? -1 : 1) * ((step + 1) / 2), stop--)
  7.       if (data[step] == subject)
  8.         return step;
  9.   return - 1;
  10. }
* This source code was highlighted with Source Code Highlighter.
This comment wasn’t rated yet0
Оно точно корректно работает?
Массив 0,1,...,10
Ищем число 7.
step принимает значения 4, 6, 9, 4,…
Какой смысл несет переменная stop?
Total votes 1: ↑1 and ↓0+1
Ну конечно не работает! Я ещё подумал, зачем я ввёл индекс… Ща верну :)
Ну а стоп — это стоп, чтоб корректно работало с 0 и не уходило в бесконечный цикл ((0+1)/2 =0)…
This comment wasn’t rated yet0
Тогда надо не sqrt, а Log2, иначе алгоритм будет работать за O(sqrt(n)), а не O(log(n))
И все равно некрасиво это как-то, ИМХО...)
Total votes 2: ↑2 and ↓0+2
А, да — надо бы лог, но так как в моих проверках всё работало, то я как то и не задумался. Madskillz r 4 fun. Просто в начале треда проскакивала lambda в Python — захотелось как то одной строчкой в Java, но под рукой пустой C#. Вышло «не красиво», но я доволен ^_^
This comment wasn’t rated yet0
В очередной раз убеждаюсь в том, что если автор проверяет те случаи, которые он учёл в коде — ну или это обратная зависимость, но результат тот же. Как то так:
public static int Dichotomy(int[] data, int subject)
{
  if (data != null)
    for (int step = (data.Length - 1) / 2, index = step, stop = (int)Math.Sqrt(data.Length);
      stop > -1 ; step = ((step + 1) / 2), index += (data[index] > subject ? -1 : 1) * step, stop--)
      if (data[index] == subject)
        return index;
  return -1;
}

* This source code was highlighted with Source Code Highlighter.
Шаг постоянно падает, поэтому нет смысла проверять, что он в пределах массива. Получается, что и индекс в пределах массива, так как скачок ограничен шагом. Стоп — обратный отсчёт максимального количества шагов, для корректной остановки при шаге в 0. Ну а знак ± указывает в какую сторону шагать. Вроде всё.
This comment wasn’t rated yet0
Нет, индекс надо проверять иначе без костыля никак…
This comment wasn’t rated yet0
Немного оптимизации (и да, мне есть чем заняться на работе):
public static int Dichotomy(int[] data, int subject)
{
  if (data != null)
    for (int len=data.Length, step=(len - 1)/2, index=step, stop=(int)Math.Log(len, 2), sign;
      stop-- > -1 && index > -1 && index < len; step=++step/2, index +=sign * step)
      if (0 == (sign = subject.CompareTo(data[index])))
        return index;
  return -1;
}

* This source code was highlighted with Source Code Highlighter.
This comment wasn’t rated yet0
Вот мое решение поставленной задачи на Python'е: pastie.org/929570

зы: на самом деле я не думал над решением 26 часов =) просто только что узнал о этом топике из Твиттера @ilysenkov'a ;) а решение ~10 минут
Total votes 1: ↑1 and ↓0+1
Массив портить нехорошо:) Но вариант красивый.
This comment wasn’t rated yet0
Вариант странный… Хотя бы по тому, что возвращает искомое значение, а не позицию массива :)
Total votes 3: ↑3 and ↓0+3
Нравится ход мыслей, но на практике портить массив нельзя, потому что он еще может понадобиться. И копировать нельзя, может в память не поместиться. print mas[i] — это считаем что опечатка.
This comment wasn’t rated yet0
На самом деле нет. Сразу не сообразил, но для вычисления индекса нужно еще запоминать, сколько мы вырезали из начала.
Total votes 2: ↑2 and ↓0+2
Даже если и запомним, то это нам не сильно поможет ;) так как от массива нечего и не останется в итоге =)
Total votes 1: ↑1 and ↓0+1
Согласен, в коде накосячил (невнимательно задание прочел)
Нашел число, а не индекс и массив урезал =)

Вот версия #2 все на том же Python'е: pastie.org/931548
This comment wasn’t rated yet0
arr[[m]] < elem, left = m,
arr[[m]] > elem, right = m

При left = 0 и right = 1 quotient будет 0. И если arr[0] не является искомым числом, цикл пойдет по кругу до бесконечности.
This comment wasn’t rated yet0
Не заметил сначала, что в этом языке индексация массивов с единицы, но это вроде бы ничего не меняет.
This comment wasn’t rated yet0
Не могли бы вы привести контр пример, учитывая, что индексация всё-таки с 1.
This comment wasn’t rated yet0
Да, разумеется. Перевел алгоритм в Javascript, чтоб проверить, попробуйте те же данные в Mathematica.

pastie.org/931837
This comment wasn’t rated yet0
pastebin.org/169249
15 минут писал, протом прогнал тесты, получил зацикливание, выделил отдельно обработку массива из одного-двух элементов, в итоге где-то 30 минут
Total votes 1: ↑1 and ↓0+1
var center = Math.ceil((to — from) / 2);

Если это конечный вариант, то в нем есть ошибка. Центр правильно получится только на первой итерации.
search([1,2,3,4,5], 5)
This comment wasn’t rated yet0
Да, накосячил.
var center = Math.ceil((to + from) / 2);
This comment wasn’t rated yet0
Еще можно функцию сравнения передавать колбеком. А в классе заготовить cmpNum и smpStr для самых распростаненных случаев. Типа этого получится: new BinSearch($array, BinSearch:cmpStr)
This comment wasn’t rated yet0
PHP, рекурсия. Уже оттестировано — первая набросанная на коленке версия лишние проверки делала.

pastie.org/4125051
This comment wasn’t rated yet0
тьфу блин. на даты не посмотрел. а в ленте только сегодня почему-то всплыло…
This comment wasn’t rated yet0
Если у меня сейчас попросят нарисовать эпюру сложного напряженного состояния — я скорее всего уже не смогу. А если и смогу — то сделаю кучу ошибок. Хотя всего несколько лет назад я с легкостью их рисовал.

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

Можно ли на основании этого утверждать, что я плохой программист? Можно, вероятно. Но чтобы утверждать, что я плохой программист, не нужно вообще ничего — в том числе и никакого знания обо мне. Если ваша оценка хорошего программиста как человека, что может написать бинарный поиск, соответствует тем задачам, что он будет решать — честь вам и хвала, вы нашли свою silver bullet.
This comment wasn’t rated yet0
Кстати, судя по числу комментариев, примерно 9 из 10%, которые могут написать бинарный поиск, собрались в комментариях к этой статье. Теперь вы можете посмотреть друг на друга и понять, наконец, как выглядят те страшно элитные 10%, в которые вы все входите.

Я лучше войду в оставшиеся 90% — там люди посимпатичнее.
This comment wasn’t rated yet0
Дело не в знании, а в отсутствие желания учиться. Тут многие почему-то думают, что если кто-то не может писать двоичный поиск, то он не программист. Это не так. Если человек не знает, но при этом пробовал написать и изучил правильную версию — респект таким людям. Если может написать — тоже респект. А вот те, кто недоумевают, мол, зачем мне оно надо, если уже есть куча готовых версий — таким не место в программировании. Каким образом они будут решать сложные задачи, если с простыми справиться не способны? Будут писать кривые неоптимальные алгоритмы. Понятное дело, что умение писать двоичный поиск — это не гарант успеха, но у таких намного больше шансов решить сложную задачу.

Никто же не спрашивал, зачем в школе изучать математику. «Математику уже затем учить надо, что она ум в порядок приводит» © Ломоносов. Здесь то же самое.
This comment wasn’t rated yet0
Про неиспользуемые знания правильно, но не относится к теме. Задача не переизобрести алгоритм, а просто перести из слов в код.

Если программист не знает/не может написать двоичный поиск, A*, BFS, то возникает вопрос что он тогда вообще программировал в жизни. Сайты-визитки? Датинги? Я конечно встречал таких senior программистов, но без боли на их творения смотреть нельзя. Это те сумрачные гении, которые, чтобы округлить число до ближайней степени десятки проходятся по строковому представлению этого числа десятью регулярками, заменяющими каждую цифру на 0, а потом дописывают спереди единичку. Те гении, которые за 10 лет не могут научиться экранировать данные перед вставкой в базу (а зачем, это все равно в админке). Их может интересовать кто выиграл в матче/на евровидении/на выставке сраных собак, но что такое BTREE в результате выполнения `SHOW index IN users` они не слышали и не интересовались.

Насчет собравшихся в треде, ну скажем любой программист в Google напишет двоичный поиск. Наверное тоже несимпатичные люди недостойные вашего общества.
This comment wasn’t rated yet0
Язык: перл. Пол часа с перепроверкой, готовая маленькая программа, включающая генерацию массива, сначала поиск всех элементов массива, потом поиск случайных значений. Сделал перепроверку простую — что бы визуально убедиться в правильности поиска. Вроде как все работает. После этого прочитал спойлеры. Действительно, переполнение и неопределенный элемент в массиве сделают прогу нерабочей. Но этого и не было в техзадании: массив то по условию упорядоченный, а как можно упорядочить неопределенные значения?.. :)

Да и еще: зачем искать одним сравнением одно значение по середине, когда можно сравнивать краевые элементы текущего интервала массива? Сравнение — функция не ресурсоемкая, потому не логично ли сделать два сравнения в цикле а не одно? Так можно получить результат за меньшее кол-во циклов (статистически, ессно).

pastie.org/4166519
This comment wasn’t rated yet0
function BinarySearch(value: integer; arr: PIntegerArray; size: integer): integer;
var
  mask: cardinal;
  index: cardinal;
begin
  mask := $80000000;
  while mask > size do
    mask := mask shr 1;

  index := 0;
  while mask > 0 do
  begin
    index := index or mask;
    if (index >= size) then
      index := index and (not mask)
    else if arr[index] > value then
      index := index and (not mask)
    else if arr[index] = value then
      break;

    mask := mask shr 1;
  end;

  if (index < size) and (arr[index] = value) then
    Result := index
  else
    Result := -1;
end;

Решил попробовать использовать не деление массива на 2 части, а постепенный спуск по маске. Скорее всего, это работает медленнее, чем уже приведенные решения.
Написано не сходу. Первые 2-3 прогона вычислял глюки (не искало нулевой элемент). Дальше еще несколько прогонов улучшал читаемость.
Даже близко не приблизился к 10%, которые могут сходу без тестовых прогонов и отладки написать решение.

В качестве развлечения и развеивания скуки на работе отлично подошло.
This comment wasn’t rated yet0
function BinarySearch(value: integer; arr: PIntegerArray; size: integer): integer;
var
  mask: cardinal;
  index: cardinal;
begin
  mask := $80000000;
  while mask > size do
    mask := mask shr 1;

  index := 0;
  while mask > 0 do
  begin
    index := index or mask;
    if (index >= size) or (arr[index] > value) then
      index := index and not mask;
    if arr[index] = value then
      Exit(index);
    mask := mask shr 1;
  end;
  Result := -1;
end;

Заодно проверил время выполнения. В несколько раз больше времени выполнения классического алгоритма. Понял, что я полный нуб и мне еще учиться и учиться. :)
This comment wasn’t rated yet0
А вот и мои пять копеек:

function binarySearch( inputArray , searchValue ){
    
    var RESULT = false;
    var halfLenghtIndex = Math.ceil( ( inputArray.length-1 ) / 2 );
    
    if ( inputArray[ halfLenghtIndex ] === searchValue ){
        
        RESULT = halfLenghtIndex;
        
    } else if ( inputArray[ halfLenghtIndex ] > searchValue ) {
        
        RESULT = binarySearch( inputArray.splice( 0 , halfLenghtIndex ) , searchValue );
        
    } else if ( inputArray[ halfLenghtIndex ] < searchValue && inputArray[ inputArray.length-1 ] >= searchValue ) {
        
        RESULT = halfLenghtIndex + binarySearch( inputArray.splice( halfLenghtIndex , inputArray.length - halfLenghtIndex ) , searchValue );
        
    }
    
    return RESULT;
    
}


Дикое извращение на JavaScript… Изначально думал, что убью на алгоритм минут 10-15, но не тут то было — 50 минут. Видимо, зря в рекурсию полез… Проще надо было быть.

Написание подобных алгоритмов — хорошая самопроверка на адекватность, после бессонной ночи кодинга. :-)
This comment wasn’t rated yet0

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr