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

C>>Или нужно помнить, что хотя хэш-карты имеют в среднем константное время для операций поиска, они при плохой хэш-функции вырождаются в линейное время. Тогда как для сбаллансированых деревьев оно всегда логарифмическое.
S>Вы часом не в Microsoft работаете? Они такую вопросы часто спрашивают, хотя потом такие тормоза как Vista кодят
Нет, даже близко не в MS.

C>>Тогда ему нечего делать на позиции за $5k. Помнить про тонкости поведения контейнеров программист просто обязан, особенно системный программист, которому может потребоваться писать хорошо оптимизированые программы.
S>Вы и в правду думаете, что если человек помнит про всякие там деревья и тонкости поведения контейнеров, то он вам оптимальный код напишет?!
Нет. Однако, человек который НЕ знает этих подробностей напишет нормальный код с намного меньшей вероятностью.

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

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

C>Да, и сам факт того, что программист за многие годы так и не заглянул (хотя бы из любопытства!) во внутренности самой частоиспользуемой библиотеки — уже о чём-то говорит.
И о чем это говорит? Зачем смотреть конкретную реализацию, когда есть стандарт?!

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

C>>Да, и сам факт того, что программист за многие годы так и не заглянул (хотя бы из любопытства!) во внутренности самой частоиспользуемой библиотеки — уже о чём-то говорит.
LM>И о чем это говорит? Зачем смотреть конкретную реализацию, когда есть стандарт?!
Ну да, или Стандарт. Хотя я лично не буду возражать, если кандидат не читал Стандарт в подробностях, а просто посмотрел исходники реализации STL.

Главное, что ему всё-таки было интересно как оно работает внутри.

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

BZ>идея правильна, только перемножать надо в десятичном виде:
я невнимательно прочитал — упустил что числа в строках.

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

C>>>Да, и сам факт того, что программист за многие годы так и не заглянул (хотя бы из любопытства!) во внутренности самой частоиспользуемой библиотеки — уже о чём-то говорит.
LM>>И о чем это говорит? Зачем смотреть конкретную реализацию, когда есть стандарт?!
C>Ну да, или Стандарт. Хотя я лично не буду возражать, если кандидат не читал Стандарт в подробностях, а просто посмотрел исходники реализации STL.
C>Главное, что ему всё-таки было интересно как оно работает внутри.
Смотреть исходники конкретной реализации опасно. Посмотрел std::string из StlPort и решил, что std::string реализовывается через CopyOnWriting

P.S. Для чего мне знать как оно устроено изнутри?

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

BZ>блин, это была бета-версия

Алгоритм мне понять не суждено, но всё равно видны ошибки:

BZ>s3 = malloc (length(s1) + length(s2) + 1);

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

BZ>for (i=0; i<length(s1); i++)
BZ>  for (j=0; j<length(s2); j++)
BZ>    res = (s1[i]-'0') * (s2[j]-'0');
BZ>    for (k=i+j; res>0; k++)
BZ>      res  +=  s3[k]-'0';
BZ>      s3[k] = '0' + res%10;
BZ>      res /= 10;
BZ>strrev(s3); puts(s3);

посерьёзднее: в том, что фигурные скобки всё-тки пропускать не стоит.

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

_>>Про больщие числа — отдельная песня. Это даже целый раздел криптобиблиотеки — за пять минут не напишешь. Да и нужно ли ?
G>как стыдно то... а я программку им написал которая в столбик все это считает
Ну и правильно сделал. Думаю если бы ты им написал умножение через преобразование Фурье то они мягко говоря офигели бы.
И не взяли — резонно решив, что раз чел способен вот так вот как нефиг делать подобные алгоритмы на собеседовании рисовать — денег попросит много

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

C>>Да, и сам факт того, что программист за многие годы так и не заглянул (хотя бы из любопытства!) во внутренности самой частоиспользуемой библиотеки — уже о чём-то говорит.
LM>И о чем это говорит? Зачем смотреть конкретную реализацию, когда есть стандарт?!
Стандарт к сожалению не все оговаривает и не всегда авторы конкретной реализации ему следуют. Вот и получаются такие коленца как STL в VC6.
Реальность как всегда отличается от того, что должно быть в теории.

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

LM>P.S. Для чего мне знать как оно устроено изнутри?

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

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

C>>Ну да, или Стандарт. Хотя я лично не буду возражать, если кандидат не читал Стандарт в подробностях, а просто посмотрел исходники реализации STL.
C>>Главное, что ему всё-таки было интересно как оно работает внутри.
LM>Смотреть исходники конкретной реализации опасно. Посмотрел std::string из StlPort и решил, что std::string реализовывается через CopyOnWriting
С другой стороны, если используется фактически только один компилятор — то знание деталей работы может быть плюсом.

LM>P.S. Для чего мне знать как оно устроено изнутри?
Просто из интереса — если не хочется стандарт читать

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


C>>>Тогда ему нечего делать на позиции за $5k. Помнить про тонкости поведения контейнеров программист просто обязан, особенно системный программист, которому может потребоваться писать хорошо оптимизированые программы.
S>>Вы и в правду думаете, что если человек помнит про всякие там деревья и тонкости поведения контейнеров, то он вам оптимальный код напишет?!
C>Нет. Однако, человек который НЕ знает этих подробностей напишет нормальный код с намного меньшей вероятностью.

Сложность алгоритма к скорости работы программы имет очень отдаленное отношение. Забудь чему вас учили в ВУЗе, при небольших N сложности O(N),O(1),O(log N) и даже O(N*2) примерно равны. Для больших значений N, когда сложность алгоритма становится значимой, стандарные контейнеры вообще не подходят, т.к. все данные хранится в пямяти. Тут уже свое что-то надо лепить, где уже можно предусматреть разные тонкости.

Насамом деле, типичные проблемы производительности лежат не в плоскости сложности алгоритма, в гораздо более тривиальных вещах. К примеру файл открывают больше одного раза, когда можно открыть один раз и хранить/использовать его handle. Или когда из файла читают по 1 байту, в место, того чтобы прочитать в буффер и оттуда черпать, типичное место ошибок макрос NEXT_BYTE(A) в алгоримах копресси, когда его перенаправляют прямо на read. Другая острая тема — синхронизация, точнее болокирование tread-а при чтениях: один thread только читает, а другие его ждут.

Как показывает мой опыт, все эти ошибки реализации исправляют к версии 2.0. Тут вот и выплывают главные проблемы производительности: ощибки архитектуры. К примеру, всместо того, чтобы сделать бинарный файл, пиплы делают модный нынче XML, который парзят. Другой источник проблем — некий кусок кода исполняют M раз. Конечно, можно стремиться к оптимизации этого куска кода (ваш любимый O(N)), но если посмотреть глубще на код, то окажется, что результаты испольнения можно кешировать и эти M становятся константой.

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

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

S>Сложность алгоритма к скорости работы программы имет очень отдаленное отношение. Забудь чему вас учили в ВУЗе, при небольших N сложности O(N),O(1),O(log N) и даже O(N*2) примерно равны. Для больших значений N, когда сложность алгоритма становится значимой, стандарные контейнеры вообще не подходят, т.к. все данные хранится в пямяти. Тут уже свое что-то надо лепить, где уже можно предусматреть разные тонкости.
Угу. Не нравится алгоритмическая сложность? Ладно. Перейдём к другой вещи — локальности в кэше. Она весьма разная для деревьев и хэш-карт.

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

Eщё у хэш-карт есть преимущество в том, что для их объектов не обязательно иметь оператор сравнения. Достаточно только хэш-функции и оператора равенства.

S>Вывод, вместо того чтобы мучить программиста академическими вопросами про сложность алгоритма, лучше посмотреть как он мыслит, какие проблемы оптимизации он рещал, какой опыт у него.
Вопрос далеко не только в сложности алгоритма. Можно ещё рассказать про локальность в кэше, сравнить поведение под нагрузкой, рассказать про разные алгоритмы баллансировки деревьев и т.д.

Простор огромный.

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

pva>Кстати, не вижу ничего подозрительного в управленце, которому 26 лет.

У молодых начальников, как правило, часто встречаются следующие недостатки:
a) Недостаток опыта
b) Считают себя самыми умными
c) С предубеждением относятся к тем, кто старше и опытнее их.

Хотя, конечно встречаются в таком возрасте и адекватные профессионалы.
Беда в том, что очень редко.

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

C>Угу. Не нравится алгоритмическая сложность? Ладно. Перейдём к другой вещи — локальности в кэше. Она весьма разная для деревьев и хэш-карт.

можешь пояснить?

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

C>>Угу. Не нравится алгоритмическая сложность? Ладно. Перейдём к другой вещи — локальности в кэше. Она весьма разная для деревьев и хэш-карт.
BZ>можешь пояснить?
Для хэш-карт при поиске данных нужны обращения к произвольным ячейкам хэш-таблицы. Для больших хэш-таблиц это не очень cache-friendly — так как велика вероятность попасть в разные линии кэша.

Деревья можно сделать очень cache-friendly с помощью специального аллокатора, и даже при использовании стандартного — они часто более дружелюбны к кэшу.

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

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

S>>Сложность алгоритма к скорости работы программы имет очень отдаленное отношение. Забудь чему вас учили в ВУЗе, при небольших N сложности O(N),O(1),O(log N) и даже O(N*2) примерно равны. Для больших значений N, когда сложность алгоритма становится значимой, стандарные контейнеры вообще не подходят, т.к. все данные хранится в пямяти. Тут уже свое что-то надо лепить, где уже можно предусматреть разные тонкости.
C>Угу. Не нравится алгоритмическая сложность? Ладно. Перейдём к другой вещи — локальности в кэше. Она весьма разная для деревьев и хэш-карт.

C>Да, и сложность алгоритма очень даже важна. Для коллекции из 10000 элементов разница между хэш-картой и деревом будет часто весьма значительной (я уж не говорю про линейную скорость). На заре компиляторостроения, например, в компиляторах с помощью правильной хэш-функции для таблицы символов удавалось добиться ускорения в разы.

Все что ты пишешь вещи нужные, но очень узко направленные. Задачи оптимизации очень интересны, для их решения нужно читать книжки, рассматреть разные алгоритмы, погонять профайлер пр. Программист плучает массу удовольсвия от их решения. Очень знакомые ощущения

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

Удачи вам директорствовать. Напишите в личку лет через десять как идут дела.

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

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

LM>>P.S. Для чего мне знать как оно устроено изнутри?

_FR>Как минимум, что бы почитать коментарии тех, кто написал эту реализацию. Весьма оказывается интересно

Не знаю, но MS STL порой выглядит фаршем: очень мало комментариев при сложных условиях, название переменных вроде _Mycont, _Mysize, _Myptr, изобилует неявным приведением типов указалель->ссылка->оператор *.

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

C>>>Угу. Не нравится алгоритмическая сложность? Ладно. Перейдём к другой вещи — локальности в кэше. Она весьма разная для деревьев и хэш-карт.
BZ>>можешь пояснить?
C>Для хэш-карт при поиске данных нужны обращения к произвольным ячейкам хэш-таблицы. Для больших хэш-таблиц это не очень cache-friendly — так как велика вероятность попасть в разные линии кэша.

кстати, ты в курсе, что линейное рехеширование более cache-friendly?

C>Деревья можно сделать очень cache-friendly с помощью специального аллокатора, и даже при использовании стандартного — они часто более дружелюбны к кэшу.

ну а в чём состоит идея этого аллокатора?

я правильно понимаю, что мы сравниваем сбалансированные деревья и закрытый хеш, и говорим о кол-ве хеш-промахов при поиске одного элемента?

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

S>К сожалению, в жизни, задачи низкоуровневой оптимизации не так часто встречаются. Порой задачу ускорения можно решить пересмотром и оптимизации всей архитектуры. Часто, это гораздо более эффективно. Очень важно, чтобы мозги прогера не были забиты низкоуровневой оптимизацией, которую нужно делать в последний момент. Нужно чтобы человек умел думать широко, а не помнить десяток понятий из школьного курса. Необходимое условие, чтобы человек умел создать расширяемую архитектуру, где в последующем можно опитимизировать если нужно. Выбор оптимального STL контейнера не входит в круг первостепенных требований.
Вполне соответствует, особенно в системном программировании. Там часто и архитектурных решений-то не приходится принимать, так как есть только один путь.

S>Удачи вам директорствовать. Напишите в личку лет через десять как идут дела.
Спасибо. Напишу, если не забуду...

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

C>>>Да, и сам факт того, что программист за многие годы так и не заглянул (хотя бы из любопытства!) во внутренности самой частоиспользуемой библиотеки — уже о чём-то говорит.
LM>>И о чем это говорит? Зачем смотреть конкретную реализацию, когда есть стандарт?!
CC>Стандарт к сожалению не все оговаривает и не всегда авторы конкретной реализации ему следуют. Вот и получаются такие коленца как STL в VC6.
CC>Реальность как всегда отличается от того, что должно быть в теории.
А если стандарт чего-то не оговаривает, то на это нельзя полагатся. Грабли в конкретной реализации STL — другое дело. Но это не настолько частая вещь