D>одно из использований хэшей -- это раскидать объекты детерминистически по bucket'ам D>И тут не имеет никакого значения сколько коллизий, хоть 2^100500, важно чтобы на том распределении объектов которое есть у тебя, этот хэш раскидывал их по бакетам более менее равномерно
А если изначальные значения и так распределены более-менее равномерно?
Здравствуйте, landerhigh, Вы писали:
SD>>Я вступлюсь за контору — к счастью, наличие одного вредного интервьювера не всегда ставит крест на всей конторе.
L>Очень даже может поставить, если вредному интервьюверу позволят вредничать слишком долго, чтобы накопить критическую массу специалистов по обращению списков.
Или постить тупак на профильных форумах, засветив при этом название конторы.
Здравствуйте, Codechanger, Вы писали: C>Ваще, канеш, Паблик подложил своей конторе большую такую свинью.
а что за контора?
пока искал название меня добило, что он по ходу даже не знает, как слово инженер пишется. у него что в профиле, что в посте иженер
Здравствуйте, Философ, Вы писали:
SD>>где надо столько всего сурового знать _заранее_ — и без возможности подучиться на ходу, въезжая в проект.
Ф>практически в любом проекте, от 200 метров кода, особенно если задания разработчикам попадают случайно: сегодня ты пилил DAL, завтра — WEB-сервис, послезавтра гуй.
И в чем там проблема въехать на ходу? Обычно в таких проектах большинство задач уже ранее встречалось, соответственно новые задачи можно делать по аналогии с ранее написанным кодом. Для этого никаких специфических знаний не требуется, достаточно здравого смысла и общего умения программировать. Плюс есть куча народа, у которого можно проконсультироваться, если какой-то момент непонятен.
Здравствуйте, __kot2, Вы писали:
__>Здравствуйте, Codechanger, Вы писали: C>>Ваще, канеш, Паблик подложил своей конторе большую такую свинью. __>а что за контора?
Ф>если не знаешь чем именно отличается List от LinkedList, то профайлер мало чем поможет. Ф>частенько нужно точно знать, где можно List'ом обойтись, а где требуется Dictionary.
Хорошему разработчику достаточно уметь пользоваться профайлером и гуглом. Если он не понимает почему тормозит ккой-то конкретный фрагмент кода — он спрашивает либо коллег, либо stackoverflow. ИМХО, это намного лучшая практика нежели надеяться на то, что ты великий маг и волшебник и сможешь предвидеть будующее и предсказать где будут тормоза.
Здравствуйте, мыщъх, Вы писали:
EOH>>вместо хэша используется список — то контейнер в торжественной обстановке заменяется. М>а ничего, что с хэшем работают совсем не так, как со списком? разверните мне хэш, пожалуйста. заодно объясните в чем все-таки разница. список это элементы А, Б, С. хэш это словарь. А => a, B =>, C => c. бред, короче.
Коллега, при всем моем уважении. И то и другое — контейнеры. На практике линейностью списка пользуются достаточно редко. А хэш, между прочем, бывает направленный — ordered hash, по нему можно ходить влево-вправо. В ruby 1.9 ввели, очень удобно. Так что не надо придираться к словам, вы же прекрасно меня поняли .
EOH>> Большинство попыток преждевременой оптимизации, какие я видел — с хитрыми структурами данных, М>это не преждевременная оптимизация. это -- проектирование. следующая стадия -- прототипирование. или давайте строить здание так -- очень просто. сколько будет у нас этажей -- хз и потому фундамент проектировать мы не можем. да он и не нужен. по мере возведения новых этажей, старые будут планомерно погружаться в землю. и у нас автоматически образуется парковка и гараж, о которой мы забыли.
Вы, как бы так сказать, передергиваете. Отсутствие архитектуры и отсутствие преждевремменой оптимизации — это разные вещи. Фундамент — это архитектура. А преждевременная оптимизация — это битонирование проводки в стенах "чтобы надежно", вместо того чтобы положить в короба. Со всемы вытекающими.
EOH>> Потому что на практике оно тормозит не там (c). Так исторически сложилось. М>исторически сложилось так, что нормальные инженеры сначала проектируют, а потом прототипируют. "тормозит не там" -- это ошибка в расчетах. а без расчетов можно заточить что-то очень сильно типовое и хорошо известное.
Коллега, при всем момем уважении и прочем воздавании почестей вашему опыту реверсинга. Я как бы про большой софт говорю. Крупный, так сказать. У него есть важный критерий — он живет намного дольше, чем написанная одноразовая числодробилка для вирусной аналитики. И меняется — непредсказуемо. Проблемы с преждевременной оптимизацией возникают уже после того, как все спроектировали и прототипизировали — когда проект начинается эволюционировать под воздействием меняющихся требований. Я — об этом. А простой софт все равно как писать — хоть водопадом, хоть агилой, хоть ООП, хоть процедурно. Как говорил один товарищь, очень легко ходить по воде и писать софт на основании требований — если они заморожены .
EOH>>Так что все эти игры с О(йух), ИМХО, от лукавого. Профайлер ответит на этот и многие другие вопросы. М>хороший вы человек. не потерявший веры в чудо. вы знаете сколько стоят комплесы по имитации максимально реалистичного потока данных? поинтересуйтесь.
Хороший вы человек, но смотрите со своей колокольни. Разная у нас с вами специализация — я разрабатываю тяжелые десктопные продукты с продолжительным сроком жизни и меняющимися требованиям. Вы — специалист по реверсингу и аналитике, у вас производительность, ядро, числодробилки, вспомогательные утилиты.
Здравствуйте, vpchelko, Вы писали:
V>Какая разница. Для меня все языки одинаковы, принципы везде одни и те же, вот печаль, что везде одни и те же вещи обзывают разными словами.
Все языки равны, но некоторые языки равнее других (Джордж Оруэлл, кавер-версия
Здравствуйте, hrensgory, Вы писали:
H>Абсолютно ничего, практически пригодного к использованию, теоретическими H>расчётами на основании "O()" и т.п. вы здесь не получите.
Здравствуйте, kaa.python, Вы писали:
>> Спасибо, кэп. KP>Всегда рад помочь >> Но мой главный вопрос, а именно, кому нафиг сдался 32-битный хеш с 2^32 коллизиями, остался без ответа. KP>Ну значит кому-то нужен. Никогда не знаешь кому и что может понадобиться. Это же не причина не предложить решение, пусть и глупого вопроса?
Тому, кому понадобился 32-битный хеш с 2^32 коллизиями на каждое значение, нужно в качестве решения предлагать живительную эвтаназию, честное слово. Тратить даже минуту своей жизни на решение дурацких проблем, придуманных идиотами, мне банально жалко.
>>> Но мой главный вопрос, а именно, кому нафиг сдался 32-битный хеш с 2^32 коллизиями, остался без ответа. KP>>Ну значит кому-то нужен. Никогда не знаешь кому и что может понадобиться. Это же не причина не предложить решение, пусть и глупого вопроса?
L>Тому, кому понадобился 32-битный хеш с 2^32 коллизиями на каждое значение, нужно в качестве решения предлагать живительную эвтаназию, честное слово. Тратить даже минуту своей жизни на решение дурацких проблем, придуманных идиотами, мне банально жалко.
Может я что-то пропустил, но разве в природе существует 32-битный хэш двух 32-битных int-ов с мее чем 2^32 коллизиями на каждое значение?
On 15.03.2012 23:07, Паблик Морозов wrote:
> H>Абсолютно ничего, практически пригодного к использованию, теоретическими > H>расчётами на основании "O()" и т.п. вы здесь не получите. > > Ну если вы этим инструментом не владеете, это еще не значит, что он > непригоден к использованию <http://bit.ly/xiiIHV>.
Это значит именно это. Если бы из такого подхода было бы реально с
разумными трудозатратами выжимать правдоподобные оценки типа "сколько
времени займёт импорт наших документов" и "какое железо нам понадобится
для нашей базы" — я бы об этом знал.
Здравствуйте, Eye of Hell, Вы писали:
EOH>Здравствуйте, мыщъх, Вы писали:
EOH>Коллега, при всем моем уважении. И то и другое — контейнеры.
вот до чего доводят людей абстракции...
> На практике линейностью списка пользуются достаточно редко.
бинарный поиск требует списка. поиск в с интерполяцией N(log log N). сравните с вашими hashmap. кстати, это в худшем случае
> А хэш, между прочем, бывает направленный — ordered hash,
вы в курсе как это устроено? посчитайте мне сложность вашего упорядоченного хэша
> по нему можно ходить влево-вправо. В ruby 1.9 ввели, очень удобно.
алгоритмическая сложность? положите в него хотя бы 6 млн. элементов потом посмотрим
> Так что не надо придираться к словам, вы же прекрасно меня поняли .
список хранит данные, например, строки. хэш это вообще-то словарь. ключ => данные. что предполагается использовать в качестве ключа? сами данные? тогда извините, у нас сложность будет зависеть и от N (кол-во элементов) и от их длины (хэш строки в сто метров быстро не посчитать), а вот упорядочить такие строки в списке -- все же быстрее, т.к. у нас есть шансы, что различия будут не в последнем символе. да и более продвинутые алгоритмы сравнения строк можно использовать...
EOH>Вы, как бы так сказать, передергиваете. Отсутствие архитектуры и отсутствие преждевремменой оптимизации — это разные вещи. EOH>Фундамент — это архитектура. А преждевременная оптимизация — это битонирование проводки в стенах "чтобы надежно", EOH>вместо того чтобы положить в короба. Со всемы вытекающими.
алгоритмическая сложность -- это архитектура. код -- фигня, код можно переписать. а вот публичный контракт и структуры данных -- это фундамент. их не изменишь. если вы на вход пинимаете список, то тупо заменить его на хэш не получится -- надо менять публичный контракт.
EOH>Коллега, при всем момем уважении и прочем воздавании почестей вашему опыту реверсинга. > Я как бы про большой софт говорю. Крупный, так сказать. У него есть важный критерий > он живет намного дольше, чем написанная одноразовая числодробилка для вирусной аналитики.
и потому крупному софту не нужно считать алгоритмическую сложность? ну-ну...
> И меняется — непредсказуемо. Проблемы с преждевременной оптимизацией возникают > уже после того, как все спроектировали и прототипизировали — когда проект начинается > эволюционировать под воздействием меняющихся требований. Я — об этом.
оценка сложности алгоритмической относится к проектированию, а не реализации. хотя бы на примере мониторов. даже если технически кол-во пикселей по горизонтали и вертикали можно увеличить в десять раз, объем данных возрастет в сто раз, что потребует пропускных способностей шин, объема памяти, скорости обработки... а вот кол-во цветов влияет на сложность обработки как O(log N), из чего следует -- мы можем увеличить кол-во цветов в тысячу раз, но это не сильно скажется на.
сейчас популярны социальные сети. можно написать программу, например, для подбора партнеров. если у этой программы сложность O(N!), это означет, что она будет работать только пока сеть только начинается развиваться, а потом ее придется выкидывать и никакая послеродовая оптимизация не поможет в принципе.
> А простой софт все равно как писать — хоть водопадом, хоть агилой, хоть ООП, хоть процедурно. > Как говорил один товарищь, очень легко ходить по воде и писать софт на основании требований — если они заморожены .
как раз в индустрии безопасности требования меняются чуть ли не каждый день.
EOH>Хороший вы человек, но смотрите со своей колокольни. Разная у нас с вами специализация — я EOH>разрабатываю тяжелые десктопные продукты с продолжительным сроком жизни и меняющимися требованиям.
...у многих таких продуктов нет проблемы алгоритмической сложности, потому что в них нет алгоритмов как таковых. есть "сценарии поведения", а это совсем другое. ваш продукт трассирует платы? ищет оптимальный вариант раскройки листа материала? хотя бы P2P протокол вы разрабатывали и реализовали? это -- из десктопных продктов.
> Вы — специалист по реверсингу и аналитике, у вас производительность, ядро, числодробилки, вспомогательные утилиты.
как раз меня при трудоустройстве спрашивали за сетевые протоколы, регулярные выражения... за сложность -- нет, не спрашивали, но даже написать регулярное выражение без учета алгоритмической сложности нельзя. ибо разные подходы дают разную сложность. от O(log N) до O(c^N).
хотя алгоритмическая сложность -- это только вершина айсберга. моя первая программа давала O(N), там где другие давали O(N*c^M) и под это дело выдали патент. но на практике и O(N) это тормоза. что ли подать патент на O(log N) в худщем случае и O(1) в идеале? моя ошибка была в том, что решив одну проблему я породил другую. это типа как -- ок, придумали самолет и обогнали корабли так, что полет в штаты и австралию стал не проблемой. но не учли, что раньше в штаты из европы летали только по большой нужде, а изобретение самолета изменило правило игры и возникла проблема оптимизации перелетов, ибо не всегда есть возможность вылететь из точки А в точку Б в удобное для вас время, да и кол-во самолетов ограничено и с увеличением кол-ва рейсов стоимость билетов возрастает, т.е. решение масштабируется плохо и нам нужно нечто такое -- принципиально новое, что позволило бы вводить неограниченное кол-во рейсов во все города без линейной стороимости издержек.
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Здравствуйте, Eye of Hell, Вы писали:
EOH>Да легко, в целом. Сначала программа пишется (с). Затем она тестируется на тестовых данных, соответствующих тому, что будет при использовании. Затем, если что-то тормозит, запускается такая специальная штука как профайлер, который показывает гда именно тормозит.
Это уже другая крайность. Преждевременная оптимизация это конечно плохо, но преждевременная пессимизация ничем не лучше. Если из логики задачи вытекает использование словаря, а вместо этого используется массив, то за это надо бить по рукам. Другое дело, что если у человека все нормально с программистскими способностями, то обучить его правильно выбирать вид коллекции под задачу не сложно. При этом для правильного выбора коллекции под задачу знание внутреннего устройства коллекции в общем-то не требуется. Поэтому смысла делать упор на этот вопрос на собеседовании я не вижу.
Здравствуйте, gandjustas, Вы писали:
G>Здравствуйте, Паблик Морозов, Вы писали:
G>Напомни, это все еще CRM или как? Если CRM, то они CRM знают или нет? Если знают, то какая разница чем они там в универе занимаются (обычно ничем хорошим в универах не занимаются). Если не знают, то какой смысл оплачивать обучение программиста?
[off]
Любителя (и профессионала тоже) майкрософтовских технологий всегда можно легко отличить по наличию непонятных трёхбуквенных сокращений.
В двух (!) маленьких предложениях три (!!!) раза упомянуто "CRM". Плюс в подписи "MVP". Забаньте меня.
[/off]
U>Это уже другая крайность. Преждевременная оптимизация это конечно плохо, но преждевременная пессимизация ничем не лучше. Если из логики задачи вытекает использование словаря, а вместо этого используется массив, то за это надо бить по рукам. Другое дело, что если у человека все нормально с программистскими способностями, то обучить его правильно выбирать вид коллекции под задачу не сложно. При этом для правильного выбора коллекции под задачу знание внутреннего устройства коллекции в общем-то не требуется. Поэтому смысла делать упор на этот вопрос на собеседовании я не вижу.
Я ни разу не говорил про преждевременную пессимизацию. Если использование словаря вместо списка не увеличивает объем кода в несколько раз и по логике программы искать элементы будут значительно чаще чем добавлять — очевидно, что надо использовать словарь. Это как бы азы программирования, это все знают.
