LINUX.ORG.RU

Повышение квалификации: посоветуйте литературу

 ,


14

6

Добрый день. Умею говнокодить на C++, хочу развиваться и получать больше денег. Иду смотреть вакансии яндекса и вижу вопрос:

Какие из следующих стандартных контейнеров позволяют найти в них элемент (по его значению) за O(ln(n))?

std::vector

std::list

std::deque

std::set

std::multiset

std::hash_set

сортированный std::vector

сортированный std::list

сортированный std::deque

сортированный std::set

сортированный std::multiset

сортированный std::hash_set

Аргументируйте ответ, прокомментируйте правильность постановки вопроса

И понимаю, насколько я еще ничтожен. Что такое O(ln(n)) я еще понимаю, но какие алгоритмы используются в стандартной библиотеке - могу только догадываться. Хотя, возможно, вопрос на самом деле не сложный и я даже знаю как на него ответить, не углубляясь в детали реализации. Но всё равно хочется поднять свой уровень. В связи с этим посоветуйте литературу, чтобы углубить знания стандартной библиотеки C++ и вообще знания алгоритмов и с этими знаниями смочь устроиться в нормальное место.

Пожалуйста, не предлагайте перейти на другой язык, это слишком долго.

Ну и заодно пусть развернется дискуссия по поводу решения задач от яндекса:

Перемещено mono из talks



Последнее исправление: Hrenomoto (всего исправлений: 1)

Почитай Мейерса (Эффективное использование STL) или Джосаттиса (Стандартная библиотека С++). Ну и основа в виде того же Кормена не помешает, например.

yoghurt ★★★★★
()
Ответ на: комментарий от yoghurt

Кстати, обе две книжки были выпущены в бородатые годы и я не уверен, что они обновлялись с учётом последнего стандарта (не слежу). Но если да - то круто.

yoghurt ★★★★★
()

сортированный std::set

Интересный троллинг.

no-such-file ★★★★★
()
Ответ на: комментарий от yoghurt

обновлялись с учётом последнего стандарта

Книжки не обновлялась, но в контексте вопроса ТСа они вполне годные.

no-such-file ★★★★★
()
Ответ на: комментарий от no-such-file

The C++ Standard Library от Джосаттиса в обновленном варианте выпущена ещё два года назад.

mkam
()

Завтра ищешь в интернете книжку Categories for the Working Mathematician. Похуй если ничего не поймешь. Затем идешь на haskell.org и изучаешь стандартную библиотеку от корки до корки. Потом зубришь, именно, сука, вызубриваешь определения языка и стандартных библиотек - The Haskell 2010 Report, чтобы от зубов отскакивало. Когда напишешь свой первый катаморфизм, по пути изучив теорию типов на уровне TaPL-а, скачиваешь и изучаешь любую хаскеллевскую библиотеку с первоклассными функторами и морфизмами, рекомендую category-extras или recursion-schemes. Как переделаешь стандартную прелюдию, чтобы по крайней мере все рекурсивные схемы были выражены через комонады, можешь идти дальше - тебя ждет увлекательный мир теории категорий. Катаморфизмы, параморфизмы, зигоморфизмы, хистоморфизмы, препроморфизмы, анаморфизмы, апоморфизмы, футуморфизмы, постпроморфизмы, хиломорфизмы, крономорфизмы, синкрономорфизмы, экзоморфизмы, метаморфизмы, динаморфизмы алгебра и коалгебра Калвина Элгота наконец. Успех хиккующих выблядков / просто быдлокодеров типа рейфага или сисярп/джава-девелоперов, которые работают в Люксофте не будет тебя волновать и уже через пол года ты будешь получать такие гранты, что любой профессор будет теч при одном упоминании списка твоих публикаций.

anonymous
()

Алгоритмы в STL ХОРОШИЕ. По крайней мере, асимптотическая сложность у них наилучшая из возможных.

А теперь прикинь. У тебя есть набор каких-то объектов. Что тебе нужно, чтобы отыскать в этом наборе нужный тебе объект за O(ln n)? Ответ: тебе нужна сортировка или что-то более сильное. Что более сильное? Ну, скажем, хэш-таблица, она тебе даст даже O(1). Кроме того, если уж у тебя есть сортировка, то тебе нужен O(1)-доступ к элементу.

Вот и смотри, кто из этих контейнеров отсортирован (и для кого это вообще имеет смысл), кто даёт O(1)-доступ, кто даёт хэш-таблицу.

Miguel ★★★★★
()
Ответ на: комментарий от Miguel

кто даёт O(1)-доступ, кто даёт хэш-таблицу.

Яндекс троллит соискателей, спрашивает за O(ln n), а не O(ln n) или быстрее. К тому же, по поводу хеша, сложно сказать какая сложность гарантируется, т.к. неизвестно есть ли коллизии и как они обрабатываются.

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

прокомментируйте правильность постановки вопроса

Основной вопрос закопан тут.

no-such-file ★★★★★
()

Ну по вопросу из оп-поста про O(ln(n)) понятно, спасибо. Хотелось бы узнать мнение уважаемых по вопросам, которые по ссылкам, про рефакторинг кода, например.

Hrenomoto
() автор топика

Вот еще в догонку вопрос: попалась мне тут «Книга Дракона» - «Компиляторы. Принципы, технологии, интрументарии». Стоит ли её прочитать для развития? Догадываюсь, что нет.

Hrenomoto
() автор топика

Сходи на cppreference.com, там для алгоритмов из STL указана сложность.

anonymous
()
Ответ на: комментарий от anonymous

Разработка компиляторов для платформы .NET
И. Аппель

Этот чтоли? Дрэгонбук так-то тоже обновляется.

yoghurt ★★★★★
()
Ответ на: комментарий от Hrenomoto

Стоит ли её прочитать для развития? Догадываюсь, что нет.

Для общего развития может и стоит, для поднятия скилла в крестах - прямого профита не будет.

no-such-file ★★★★★
()

посоветуйте литературу

Стандарт. Там явно указаны требования к сложности алгоритмов. Формально даже «не углубляясь в детали реализации».

const86 ★★★★★
()

Начала программирования А.Степанов П.Мак-Джоунс.

ps. на яндекс видео есть его(Степанова) 2 лекции которые он давал в яндексе когда сюда приезжал. посмотри.

qulinxao ★★☆
()

По твоему вопросу, - Кормен, ЕМНИП, первые 4 главы. Упражнения делать обязательно.

anonymous
()
Ответ на: комментарий от anonymous
Ответ на: комментарий от no-such-file

Ну ну. Половина книги про устаревшие и не используемые на практике техники парсинга, а оставшаяся половина - про устаревшие и неэффективные методы кодогенерации. Ну очень «отличная». Только вот ни gcc, ни llvm ты на знаниях из этой книжонки не напишешь.

anonymous
()
Ответ на: комментарий от mkam

Программист срр.
Сегодня сделали офер, так что буду есть тортик и радоваться.

trex6 ★★★★★
()

Итак, список литературы, в порядке убывания приоритета:

  • стандарт
  • Кормен — Алгоритмы: построение и анализ
  • Мейерс — Эффективное использование STL
  • Николай Джосьютис — C++ Стандартная библиотека.
  • А.Степанов П.Мак-Джоунс — Начала программирования
  • про компиляторы: дрэгонбук или Аппель — Modern Compiler Implementation

Так же пришла в голову мысль, что было бы очень полезно ознакомиться с Boost. Какой наиболее эффективный способ это сделать можете посоветовать?

Hrenomoto
() автор топика
Ответ на: комментарий от Hrenomoto

Прочитай первые главы Кормена сначала. Если не будешь филонить, через несколько месяцев сложность алгоритмов и валидность итераторов в std будет понятна без тупой зубрёжки.

Про буст. Там штук 100 или 200 библиотек. По некоторым книжки на сотни страниц (asio, spirit, например). Открой главную страницу, почитай хотя бы Гетин стартд. Ознакомься с составом. Попробуй собрать хелловорд с program_options, variant, filesystem, regexp.

anonymous
()
Ответ на: комментарий от Hrenomoto

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

anonymous
()
24 января 2015 г.

И понимаю, насколько я еще ничтожен. Что такое O(ln(n)) я еще понимаю, но какие алгоритмы используются в стандартной библиотеке - могу только догадываться.

ох… Кнута открой, личинка говнокодера.

Hint: Названия алгоритмов «скрыты» в названиях STL-шаблонов.

Да, правильный ответ: сортированный vector. Доступ там O(1), но тебе нужно «найти», т.е. у тебя есть некий x, и тебе нужно пробежаться по коллекции, и найти нужный x(или доказать, что такого x там нет). Надо разделить vector пополам, и сравнить средний эл-т, затем опять пополам и так далее. Сложность будет как и заказывали C*log₂(N).

Такую же сложность даёт дерево, но только если приняты меры против вырождения. (нету такого варианта)

В принципе, «сортированный list» частично подходит, т.к. задачу можно решить в процессе сортировки, которая занимает O(N*log(N)), но проверить можно почти бесплатно.

И да, пишется log(n), а не ln(n).

emulek
()
Ответ на: комментарий от alegz

Сбалансированного дерева хватит.

это и есть «сортировка». Дерево отсортировано by design, т.к. каждый эл-т встаёт на своё место сразу.

«Сбалансированное» не нужно, главное — не вырожденное. (т.е. что-бы число уровней не росло быстрее, чем какой-нить log(N)).

emulek
()

А очевидный вариант почитать исходники библиотеки тебе в голову не пришел? Что за поколение выросло, любители по «литературе» учиться?!?

anonymous
()
Ответ на: комментарий от alegz

Это и есть «более сильное, чем сортировка».

Miguel ★★★★★
()
Ответ на: комментарий от anonymous

Что за поколение выросло, любители по «литературе» учиться?!?

Предыдущее поколение «одаренных» хакеров постаралось. Дохакались, теперь хрен разберешься в их говнокоде.

anonymous
()
Ответ на: комментарий от Miguel

Ну, скажем, хэш-таблица, она тебе даст даже O(1).

О боже, о божечки. Эти нули. Ты понимаешь, что хештаблица - это массив, а хеш она лишь потому, что в массиве индекс должен быть целочисленный. Хеш даёт только индекс с равномерным распределением по твоему ключу.

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

Длину массива можно уменьшить делением массива - на этом основаны все хеш-массивы. Но деление массива покупается за ещё один поиск по подмассиву.

Т.е. это уже не O(1). Длину можно уменьшить коротким хешом, но короткий хеш это коллизии, а коллизии это тот же самый ещё один поиск.

Т.е. в реальном хеше нет единицы, так же как в бревне нет логарифма. То, о чем ты балаболишь - это перфектхеш.

TrueTsarC
()
Ответ на: комментарий от emulek

ох… Кнута открой, личинка говнокодера.

А скажи мне, пж, в кнуте тоже дефолтный хешмассив O(1), либо он не такой конченный как рандомный эксперт?

TrueTsarC
()
Ответ на: комментарий от TrueTsarC

А скажи мне, пж, в кнуте тоже дефолтный хешмассив O(1), либо он не такой конченный как рандомный эксперт?

может быть ты откроешь какую-нить книжку (того же Кнута), узнаешь, что такое O-большое, и перестанешь позориться?

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

при вычислении O-большого размер массива принято считать _фиксированным_, т.е. ОЧЕНЬ БОЛЬШОЙ, но всё равно — константой. Т.е. мы СНАЧАЛА фиксируем N скажем 1`000`000, и считаем время. Потом фиксируем N на 1`000`000`000, и опять считаем, ну и так далее, в пределе N→∞. Если при этом время не меняется, то принято говорить о вычислительной сложности ≡O(1).

Для хеша в 1`000`000`000 элементов _максимум_, время доступа не различается, хоть у тебя там 1 эл-т, хоть 1`000`000, хоть все 1`000`000`000, потому сложность ≡O(1).

А коллизии, это не проблема, если размер хеша НАМНОГО больше размера чисел. К примеру, если у тебя числа uint32_t, и ты юзаешь md5 хеш, то вероятность коллизии не более 2¯⁹⁶ (1/79`228`162`514`264`337`593`543`950`336), что на время поиска НИКАК не сказывается. Кстати, таких маленьких коллизий в 32 бита, для md5 НЕ НАЙДЕНО, найденные коллизии намного больше. Я так вангую, что можно доказать, что таких коллизий не бывает, но мне лениво.

emulek
()
Ответ на: комментарий от emulek

может быть ты откроешь какую-нить книжку (того же Кнута), узнаешь, что такое O-большое, и перестанешь позориться?

В чем конкретно я позорюсь? Я не собираюсь читать говно, которое обсирается даже на примитивном хешмассиве.

Для хеша в 1`000`000`000 элементов _максимум_, время доступа не различается, хоть у тебя там 1 эл-т, хоть 1`000`000, хоть все 1`000`000`000, потому сложность ≡O(1).

Датычё. Ну пойдём чтоли запилим темку и посмотрим как эсперты напишут мне хешмассив с контантным временем. Кукарекать это конечно хорошо, но раз ты не понимаешь примитивного базиса, то объяснять тебе что-то бесполезно, а вот когда ты обосрёшься, то хотябы кукарекать перестанешь.

O(1) Будет только на mass[32bitmax]; get(key) {return mass[perfecthash(key)];}

А коллизии, это не проблема, если размер хеша НАМНОГО больше размера чисел.

А ширину хеша ты чем будешь резать? mass[32bitmax]; mass[48bitmax]; mass[64bitmax]; будешь юзать?

Либо будешь делить массив? А делить - это 2-й поиск, который не O(1).

что на время поиска НИКАК не сказывается.

Алёша. Ты понимаешь, что суть хешмассива в хеш==индекс. Какой длинные массивчик у тебя будет, если индекс будет сотни бит? Будешь делить?

Ещё раз - O(1) - это во-первых только для хеша, который НИКОГДА НЕ ДАЁТ КОЛЛИЗИЙ. Во-вторых только для случая, в котором хеш является напрямую индексом массива. На практике хеши больше 16бит не могут использоваться напрямую, а хеши на 16бит говно дырявое. Т.е. O(1) реализация в днище стл невозможна.

TrueTsarC
()
Ответ на: комментарий от TrueTsarC

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

Miguel ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.