Re[3]: Зацените bubble_sort (только сильно не ругайтесь) - C/C++

Здравствуйте, _DAle_, Вы писали:

K_O>>Простейший пузырек для собеседования вполне может быть примерно таким:
K_O>>

K_O>>for (int i = 0; i < count; i++)
K_O>>  for (int j = 0; j < count - i; j++)
K_O>>    if (array[i] < array[j])
K_O>>    {
K_O>>      T t = array[i];
K_O>>      array[i] = array[j];
K_O>>      array[j] = t;
K_O>>    }
K_O>>

_DA>Только вот этот код ничего не сортирует )

Откуда такой вывод?

Здравствуйте, Kh_Oleg, Вы писали:

K_O>Здравствуйте, _DAle_, Вы писали:

K_O>>>Простейший пузырек для собеседования вполне может быть примерно таким:
K_O>>>

K_O>>>for (int i = 0; i < count; i++)
K_O>>>  for (int j = 0; j < count - i; j++)
K_O>>>    if (array[i] < array[j])
K_O>>>    {
K_O>>>      T t = array[i];
K_O>>>      array[i] = array[j];
K_O>>>      array[j] = t;
K_O>>>    }
K_O>>>

_DA>>Только вот этот код ничего не сортирует )

K_O>Откуда такой вывод?

Хм, ну если на код посмотреть, то это вроде бы очевидно. Но если нужны доказательства, то вот http://codepad.org/mB3a5ULK.

K_O>>>for (int i = 0; i < count; i++)
K_O>>>  for (int j = 0; j < count - i; j++)
K_O>>>    if (array[i] < array[j])
K_O>>>    {
K_O>>>      T t = array[i];
K_O>>>      array[i] = array[j];
K_O>>>      array[j] = t;
K_O>>>    }
K_O>>>

_DA>>Только вот этот код ничего не сортирует )

K_O>Откуда такой вывод?
Ну, начало обоих циклов от 0 уже означает что-то не то.
Далее, возьмем первые шаги: i=0, j=1. И если array[i] < array[j] (что нормально для отсортированного массива), то эти элементы меняются местами.

На первый взгляд могу предположить, что:
1) диапазон i должен был быть 0...count-1
2) диапазон j должен был быть i+1...count-1
3) знак в сравнении должен быть "больше", а не "меньше"

Здравствуйте, slava_phirsov, Вы писали:

_>На одном собеседовании, проходившем в популярном ныне формате ~~опускания соискателя~~ энергичного интервью предложили написать "какую-нибудь сортировку", ну и я, чтобы меньше думать, накарябал простейший "пузырек" (все равно ничего другого я толком и не помню

):

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

А что касается приведённого кода, то он весьма избыточен и запутан. Из особых перлов "for (i = j = start, ++j; j != end; ++j, ++i)". Тут достаточно одного итератора. j всегда равно i + 1.

Здравствуйте, любой, Вы писали:

Л>Слово "какой-нибудь" нельзя понимать буквально. Например, если клиент приходит в парикмахерскую и говорит: "Подстрегите как-нибудь на ваш вкус", то это не значит, что можно взять машинку и под ноль его обрить.

- Скажите, а куда мне идти?
— Это зависит от того, куда ты хочешь попасть.
— Но мне все равно, куда попасть!
— Тогда тебе все равно, куда идти.

Л>А что касается приведённого кода, то он весьма избыточен и запутан. Из особых перлов "for (i = j = start, ++j; j != end; ++j, ++i)". Тут достаточно одного итератора. j всегда равно i + 1.

~~Типа~~ оптимизация, в духе кода из незабвенной статьи "банды трех"(TM) "Fast patttern matching on strings". i+1 должно вычисляться четырежды, потому использована новая переменная. Ну и чтобы было что обсуждать при разборе кода.

Здравствуйте, March_rabbit, Вы писали:

M_>Ну, начало обоих циклов от 0 уже означает что-то не то.
с чего бы это?
так тоже не то?

  for (int i = 0; i < count; ++i)
    for (int j = 0; j < count - 1 - i; ++j)
      if (array[j] > array[j+1])
      {
        int t = array[j+1];
        array[j+1] = array[j];
        array[j] = t;
      }

Здравствуйте, slava_phirsov, Вы писали:

Л>>А что касается приведённого кода, то он весьма избыточен и запутан. Из особых перлов "for (i = j = start, ++j; j != end; ++j, ++i)". Тут достаточно одного итератора. j всегда равно i + 1.

_>~~Типа~~ оптимизация, в духе кода из незабвенной статьи "банды трех"(TM) "Fast patttern matching on strings". i+1 должно вычисляться четырежды, потому использована новая переменная. Ну и чтобы было что обсуждать при разборе кода.

Заниматься оптимизацией производительности алгоритма со сложностью N**2, когда есть масса алгоритмов со сложностью N*log(N) довольно странно. И почему ты решил, что интервьюеру хотелось увидеть оптимизацию именно производительности, а не понятности кода. Но вообще, чтобы оптимизировать на подобном уровне, надо и ассемблер знать и оптимизационные возможности компилятора. Между C кодом и командами процессора нет однозначного обратимого соответствия. *(i + 1) и *i в большинстве случаев выливаются в равнозначные по времени машинные инструкции. А вот наличие ненужных переменных нежелательно, т.к. количество регистров процессора, в которых их можно хранить, ограничено.
Интервьюеры, конечно, не испытывают энтузиазма каждому претенденту всё это рассказывать.

Л>*(i + 1) и *i

в коде топикстартера используются forward iterators. Для них нельзя писать (i+1), только ++i или i++

Здравствуйте, dilmah, Вы писали:

D>в коде топикстартера используются forward iterators. Для них нельзя писать (i+1), только ++i или i++

В таких случаях пишут std::advance(i, 1), а не ++.

Здравствуйте, любой, Вы писали:

Л>Заниматься оптимизацией производительности алгоритма со сложностью N**2, когда есть масса алгоритмов со сложностью N*log(N) довольно странно.

Заниматься написанием давно написанного алгоритма вообще довольно странно. Интересно, кому-нибудь когда-нибудь приходилось самостоятельно писать сортировку для рабочего кода? Просто вижу лес рук.... Тем не менее — на собеседованиях любят мусолить эту тему. Такова реальность, коллега.

Л>*(i + 1) и *i в большинстве случаев выливаются в равнозначные по времени машинные инструкции.

Хм, для указателей — да, для итераторов — не уверен. Ибо *(i+1) выливается в создание нового объекта-итератора. Хотя

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

Л>Интервьюеры, конечно, не испытывают энтузиазма каждому претенденту всё это рассказывать.

- Что-то вы мне, милочка, не нравитесь...
— Да и вы, доктор, не Аполлон.

Здравствуйте, slava_phirsov, Вы писали:

_>Заниматься написанием давно написанного алгоритма вообще довольно странно. Интересно, кому-нибудь когда-нибудь приходилось самостоятельно писать сортировку для рабочего кода? Просто вижу лес рук.... Тем не менее — на собеседованиях любят мусолить эту тему. Такова реальность, коллега.
Тестовые задания в обычных фирмах придумывать некогда и некому. Большинство из них рождается в недрах монстров вроде MS. И соответствует позиции продвинутого разработчика, который сортировку слиянием может просто придумать находу. Но постепенно задание становится достоянием всё более широкой общественности. Его берут на вооружение самые занюханные конторы. И тут уже проверяется, знает ли кандидат о таком задании. Если знает, значит не последний человек в программировании. Всё-таки профильные форумы читает.

Л>>*(i + 1) и *i в большинстве случаев выливаются в равнозначные по времени машинные инструкции.

_>Хм, для указателей — да, для итераторов — не уверен. Ибо *(i+1) выливается в создание нового объекта-итератора. Хотя

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

Компиляторы сейчас inline код сносят практически подчистую. Но даже если какие-то прециденты и остались, то они на месте не стоят, совершенствуются. Тягаться с компилятором без какой-то весомой причины бессмысленно.

Здравствуйте, любой, Вы писали:

Л>Компиляторы сейчас inline код сносят практически подчистую. Но даже если какие-то прециденты и остались, то они на месте не стоят, совершенствуются. Тягаться с компилятором без какой-то весомой причины бессмысленно.

Еще раз: насколько я понимаю, грубо говоря, i + 1 порождает временный объект-итератор (если конечно i — объект, а не указатель), после чего он инкрементируется. На это требуется затратить определенное время, и inline подстановка тут не спасет: она может дать экономию за счет вызова конструктора, но код конструктора все равно должен будет выполниться. Кстати, где-то слышал, что вроде бы конструкторы (или деструкторы?) вообще не встраиваются (могу ошибаться, поправьте, если что). Да, а потом еще надо будет вызвать еще и деструктор временного объекта. Эээх, ~~навыков и желания~~ времени нету поковыряться в дизасме и проверить приведенное ИМХО для разных компиляторов, с разными ключами оптимизации...

Здравствуйте, dabeat_bf, Вы писали:

_>Здравствуйте, March_rabbit, Вы писали:

M_>>Ну, начало обоих циклов от 0 уже означает что-то не то.
_>с чего бы это?
_>так тоже не то?
_>

_>  for (int i = 0; i < count; ++i)
_>    for (int j = 0; j < count - 1 - i; ++j)
_>      if (array[j] > array[j+1])
_>      {
_>        int t = array[j+1];
_>        array[j+1] = array[j];
_>        array[j] = t;
_>      }
_>

тут совсем другое дело. Может быть, алгоритм и рабочий

Здравствуйте, slava_phirsov, Вы писали:

Л>>Заниматься оптимизацией производительности алгоритма со сложностью N**2, когда есть масса алгоритмов со сложностью N*log(N) довольно странно.

_>Заниматься написанием давно написанного алгоритма вообще довольно странно. Интересно, кому-нибудь когда-нибудь приходилось самостоятельно писать сортировку для рабочего кода? Просто вижу лес рук....
я писал

сортировка списка строк из 5-10 строк максимум 1 раз в день. Даже не захотелось заморачиваться с поиском способа сортировки имеющего списка. 5 минут и готово.

_>Тем не менее — на собеседованиях любят мусолить эту тему. Такова реальность, коллега.
смотрят на код. Чтобы оценить код лучше всего смотреть на известную задачу. Сортировка неплохо подходит ИМХО.

Здравствуйте, March_rabbit, Вы писали:

M_>Здравствуйте, slava_phirsov, Вы писали:

Л>>>Заниматься оптимизацией производительности алгоритма со сложностью N**2, когда есть масса алгоритмов со сложностью N*log(N) довольно странно.

_>>Заниматься написанием давно написанного алгоритма вообще довольно странно. Интересно, кому-нибудь когда-нибудь приходилось самостоятельно писать сортировку для рабочего кода? Просто вижу лес рук....
M_>я писал

M_>сортировка списка строк из 5-10 строк максимум 1 раз в день. Даже не захотелось заморачиваться с поиском способа сортировки имеющего списка. 5 минут и готово.

_>>Тем не менее — на собеседованиях любят мусолить эту тему. Такова реальность, коллега.
M_>смотрят на код. Чтобы оценить код лучше всего смотреть на известную задачу. Сортировка неплохо подходит ИМХО.

Смотрят на код, это да. Но еще, очень часто ожидают вопросов. А зачем эта сортировка? А что она будет сортировать? А какие есть ограничения? Память, скорость, место на жестком диске. И если ты их задаешь, то сама сортировка уже и не так важна.

Здравствуйте, Acteon, Вы писали:

A>Смотрят на код, это да. Но еще, очень часто ожидают вопросов. А зачем эта сортировка? А что она будет сортировать? А какие есть ограничения? Память, скорость, место на жестком диске. И если ты их задаешь, то сама сортировка уже и не так важна.

Закидать, закидать их вопросами, чтобы они сразу почувствовали мощь настоящегопрофи(TM)

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

	От:	vpchelko
	Дата:	20.05.10 00:30
	Оценка:	1 (1)

	От:	Kh_Oleg
	Дата:	20.05.10 06:34
	Оценка:

	От:	_DAle_
	Дата:	20.05.10 06:55
	Оценка:

	От:	March_rabbit
	Дата:	20.05.10 06:55
	Оценка:

	От:	любой
	Дата:	21.05.10 05:33
	Оценка:

	От:	slava_phirsov
	Дата:	21.05.10 06:01
	Оценка:	1 (1)

От:	dabeat_bf	http://alexmogurenko.com
Дата:	21.05.10 06:47
Оценка:	+1