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

Эээ, ну практически. :) Только этот умеет шикарной статься на Лоре, пожалуй это и все. :)

иди в жопу. В свою.

Что же ты мне не отвечаешь, эксперт?

Гляжу тут все решили блеснуть знаниями си плюс плюшечки :-) У меня все знакомые c++ разработчики уже лет 10 как ушли на java. Нафига он вообще нужен, этот си плюс плюс? Есть же D, Objective-C, и Go? Разве что Qt...

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

ну БУДЕТ жеж, чем ты недоволен?

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

man uint128_t

Алёша.

иди нахрен.

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

я?! не, не буду.

Ещё раз - O(1) - это во-первых только для хеша, который НИКОГДА НЕ ДАЁТ КОЛЛИЗИЙ.

придурок, ИНОГДА даёт коллизии — не считается(статистически).

На практике хеши больше 16бит не могут использоваться напрямую

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

тычо! этож Царь!

не, не царь. Царь не так говорил.

Что же ты мне не отвечаешь, эксперт?

слово «эксперт» Ъ царь писал как «иксперт».

У меня все знакомые c++ разработчики уже лет 10 как ушли на java.

и нахренаж ты сюда пишешь?

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

ну БУДЕТ жеж, чем ты недоволен?

Причем тут говностл? Там не будет.

man uint128_t

Причём тут это? К чему ты это написал?

я?! не, не буду.

Т.е. ты кукарекал, обосрался и съехал? Пошел перечитал кнута и понял, что обосрался?

придурок, ИНОГДА даёт коллизии — не считается(статистически).

Считается. Не считать ты можешь на 32битных хешах, но тогда у тебя уже деление массива, а это постоянный 2-й поиск.

придурок, я использую.

И? Привет сотни метров на 100елементов? Куллстори. Да и мы говорим не о тебе, а об говностл.

А ты идёшь себе в жопу, стройными рядами.

Ну что мы видим, а видим мы тотальный обсёр и слив, ибо нету ни одного ответа по теме и явно поменялась риторика. Я могу сделать вывод, что ты погуглил, либо перечитал кнута и понял, что обделался, но признаться - зачем?

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

http://web.engr.illinois.edu/~jeffe/teaching/algorithms/

http://people.cs.vt.edu/~shaffer/Book/

https://sites.google.com/site/algoxy/

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

кулинксяо, залогиньтесь

http://lib.ru/CTOTOR/KNUT/

Мне реально интересно, почему нулёвая балаболка, которая меня даже под анонимусом не узнаёт, позволяет себе делать такие выводы?

Какбэ любой модератор тебе подтвердит, что я Царь по мылу. Ибо мыло у царьблогов и текущего царя составлено по одному шаблону, только там были номера меньше. А царь мыла с царьблогов нигде не светил.

Ну и обоссанный емулек - первый признак царя.

...и никто не заметил, что там ln вместо log.

O(ln x) = k * ln x = k * 1 / (lg e) * lg x = k * lg x = O(lg x)

Ну, да — такой ответ и ожидался на

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

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

ИМХО — писать на php выгоднее по деньгам.

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

я?! не, не буду.

Т.е. ты кукарекал, обосрался и съехал? Пошел перечитал кнута и понял, что обосрался?

настоящий цъарь никогда так дёшево не опускался, как ты сейчас.

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

уныло и безблагодатно.

Какбэ любой модератор тебе подтвердит

что ты у модератора отсасал? Извини, я не в курсе. Я жеж не модератор, у меня отсасёшь, я тебе ещё и не то подтверждать буду.

почему тебя так интересует моя жопа? Не толерант ли ты часом?

Атеперь, Алёша, о главном. Давай покажи мне реальный пример хеш-таблицы, которая дает O(1) на любых типах данных. Со всеми доказательствами асимптоматики (хотя, я уверен, что ты даже близко ниосилишь). Любой левый ответ равносилен сливу.

Стесняюсь спросить, а есть ли хоть какая-то отрасль, в которой ты не разбираешься или в которой у тебя нет знакомых, которые разбираются, а через них и ты? All-around прям.

У меня все знакомые c++ разработчики уже лет 10 как ушли на java

Это не лучшим образом их характеризует.

Нафига он вообще нужен, этот си плюс плюс? Есть же D, Objective-C, и Go?

В Linux их нет. В том смысле, что софта на них нет. В лучшем случае можно найти трупик GNUstep и заняться с ним некрофилией.

Не разбираюсь в области сантехники. Сантехников знакомых тоже нет. Ракетостроении. Нейробиологии. Уже ищу знакомую нейробиологичку.

Так может стОит сесть и написать софт? Из D легко и прекрасно вызываются .so шки c/c++, на go уже проектов 40 на гитхабе открытых, все собираются под линукс. В основном это субд/nosql/сетевой софт. Кстати, качественные вещи попадаются. Свой go код можно статически линковать с .a си плюс плюс, т.ч. то, что под линь нет софта на гоу и ди - это ещё бабушка надвое сказала.

Царь, да не трать ты силы на спор с людьми, которые при разговоре о производительности хэш таблиц не упоминают об обычном а не амортизированном времени, не говорят о лоад факторе и какими усилиями его приходится поддерживать ограниченным, и т.д.

Для них хэш эквивалентно О(1) и на остальное можно забить болт.

Иди в глубокую жопу со своей убогой гуетой. На чем ты всякие компиляторы и СУБД писать собрался, лось? На Ябе?

хеши больше 16бит не могут использоваться напрямую

Почему?

O(1) реализация невозможна

Ты хотел сказать, что время работы на нышешнем железе таки растёт с кол-вом элементов? Ну, да. Это не отменяет того факта, что алгоритм(да, в случае «сферы в вакууме») требует O(1) - что, как мне кажется, доказано математически, т.е. является абсолютно истинным, если мы продолжаем обсуждать абстрактные материи типа «O()».

Apache Flex видел? Там компилятор MXML написан на яве, т.ч. не *изди. Субд на яве ты тоже не знаешь? А я знаю, и несколько.

Там компилятор MXML написан на яве,

Ох, ну и убогое ты говнище, однако! Ты на настоящие компиляторы посмотри, шалава. Например, на тот же HotSpot.

Субд на яве ты тоже не знаешь?

Таких, для которых TPC/$ показать не стыдно? Не, не знаю. И ты, шалава, тоже не знаешь.

Успокойся уже и прими феназепам. Компилятор скалы?) компилятор Jython? Пока ты борщ мамкин хлебаешь - люди работу работают на java.

Царь возможно беспокоится, что математически доказана не О(1) а иная оценка - или О(1+f) или О(1/(1-f)), или какая-то другая, но тем не менее, включающая f - лоад фактор. Эти оценки будут эквивалентны O(1) только при условии, что лоад фактор ограничен сверху (для некоторых реализаций - константой меньшей единицы). Затраты на поддержание этого свойства в приведенных оценках не учитываются, не усредняются. Но они реальны. Поэтому и говорят об амортизированной оценке, подразумевая, что почти всегда будет быстро и хорошо, но изредка - реорганизация и плохо. А если вам повезло с данными - то может быть плохо почти всегда.

Несознательные граждане могут провести эксперимент. Выбрать хорошую на их взгляд функцию хэширования, заранее не зная данных, скажем, с 20 битными значениями хэш кода. Поместить в хэш таблицу, скажем, три тысячи записей, и убедиться что есть коллизии. Даже при малом лоад факторе. Но это пол беды. Вторая половина беды обнаружится, когда мы попытаемся в эту таблицу загнать миллион различных ключей, распределеных равномерно в множестве, из которого они берутся. Мы убедился, что наша функция плоха. ЕМНИП, даже есть теорема такая, если по простому: для любого заранее неизвестного набора данных почти все функции хэширования плохие.

у тебя в легких рак и ты хочешь его увеличить?

Modern
1998

ого-ого

Modern
1998

ого-ого

Изъясняйся понятнее.

Компилятор скалы

Тормозное угребище

компилятор Jython?

Тормозное угребище

люди работу работают на java.

Дешевые макаки отсиживают жопы за миску риса.

Да, и что там про СУБД, ничтожество? Нашел уже СУБД на ябке, за которую не стыдно? А HotSpot на ябку переписал уже?

Не разбираюсь в области сантехники.

До первого ремонта =)

Ракетостроении.

Проще пареной репы. Частный случай физики. Аэродинамика, материаловедение, сопромат, теормех etc. Не вдаваясь особенно.

Нейробиологии.

Поживёшь с моё, прознаешь :-D

Апо поводу жабка vs. си++, вопрос относительный. Классных плюсовиков меньше и они днём с огнём, ИМХО.

Знакомых нет, промышленным программированием не занимаюсь. Но пытаюсь сменить сферу деятельности и задаю вопросы экспертам. В основном, онлайн. В т.ч. по плюсам. Но на вкуривание плюсов нужно время, чтобы тренироваться «на кошечках», а с временем пока тяжело.

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

что тебе непонятно?

Непонятно, почему претензия к Эппелю предъявлена, а к Ахо - нет.

книга написана в 98, какой нахрен модерн?

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

даже если это когда-то было модерном, щас-то зачем это сюда тащить?

Расскажи мне, в чем устарел материал книги. Просто для справки - это вузовский учебник по основам конструирования компиляторов, а не справочник по bleeding edge алгоритмам оптимизации .

Тормозное угребище

Где пруфы?

Почему?

Патамучто память пойдёт в жопу?

Давай я ещё раз объясню.

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

Ты хотел сказать, что время работы на нышешнем железе таки растёт с кол-вом элементов?

О боже, очередной нулец мне будет что-то там рассказывать. Железо тут непричем. И в каком месте оно растёт? И причем тут вообще железо?

Ты же мне расскажешь почему же оно растёт, высрав что-то поумнее дефолтных «кешмисов»?

Это не отменяет того факта, что алгоритм(да, в случае «сферы в вакууме») требует O(1)

Алгоритм. Школьникчтоле? Какой ещё нахрен алгоритм. Чего алгоритм? Прямого доступа по индексу массива?

Я уже говорил нулям - O(1) - это один елемент на бакет. Гарантирует это только перфектхеш и то с вменяемым диапазоном значений.

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

требует O(1) - что, как мне кажется, доказано математически

Требует МИНИМУМ O(1), почему же вы такие рачины.

Мне уже лень объяснять что-то балаболам, которые о реальном мире нихрена не знают. Вот у тебя доказано для математической модели, но вот какая штука - реальная реализация не соответствует той модели, в которой это доказывалась.

Давай я тебе ещё раз бъясню. Есть абстрактная хештаблица, которая может быть какой угодно. Это та, о которой ты слушал за партой и о которой написано в говнокниженках. А есть конкретная и реальная реализация, которая НИКАКОГО отношения к тому, о чем тебе втирали не имеет.

Здесь девелопмент, а не парта. Здесь обсуждаются ттх реальных реализаций, а не абстрактных коней в вакууме. Я конечно понимаю, что вчера сбежавший из-за парты балабол ничего не знает кроме абстрактного говна, ибо он проще паренной репы. И таких тут 90%. При этом ладно бы этот балабол говорил о реальных конях - нет жешь, он мне транстлирует мифы и легенды со днища некомпетентного окияна. Мне не нужно такое счастье.

И ещё одно. Стойкость юзабельных хешей к коллизиям в районе нуля. Т.е. коллизии будут и чем больше будет данных - тем больше будет коллизий - т.е. никакой математический O(1) невозможен не на перфектхеше.

Почему не O(1) тебе наверное не надо объяснять? Это второй поиск по бакету. Его время зависит от кол-ва елементов в бакете, а их кол-во зависит от кол-ва елементов в хештаблице.

т.е. является абсолютно истинным, если мы продолжаем обсуждать абстрактные материи типа «O()».

А дайка мне пруфец на это мистическое доказательство.

На shootout пруфы, ничтожество ты убогое.

И в каком месте оно растёт?

Это же ты утверждаешь, что что-то знаешь про >O(1). Вот и поведай нам - я только пытался угадать, что ты имеешь в виду. Пока за шумом услышано 3 полезных слова:

увеличивается потребление памяти ... реальная реализация не соответствует модели ... второй поиск по бакету

Итого, ничего нового ты, пока, не выорал, все эти слова всегда ходили в учебниках рядом с доказательством O(1)ности.

пруфец на это мистическое доказательство

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

Затраты на поддержание этого свойства в приведенных оценках не учитываются

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

Или весь этот крик только от того, что первый не понимает, что второй не понимает, что первый, в отличии от второго, говорит о худшей/средней/лучшей оценке? Типа первый раз спорим? Невероятно.

Забаньте уже этого отморозка по айпишнику.

Так где ссылки?)

Именно, убогий, где ссылки? Где твои СУБД на ябке, которые оракл уделывают? Где HotSpot на ябке? Про jikes-rvm я в курсе, это игрушка.

http://benchmarksgame.alioth.debian.org/u64q/java.html - ябка твоя в 3-4 раза на релевантных задачах тормознее сишки.