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

Не баньте Царя! Без него скучно!

Зато денег приносит, и ума почти не требует😊

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

ну на 180 (145 после налогов) в год можно купить достаточно много мисок риса 😊

Ну и какой в этом интерес, если с плюсами можно и 300к плюс раза так в три больше в бонусах поднимать?

Так где пруфы про убогость скала компилятора? Ты письки меряешь как в школе, видимо, твой учитель информатики взорвал тебе мозг сишкой. То, что ты будешь писать на сишке месяц - я напишу за 3 дня на java. Т.ч. скорость написания кода рулит, сишка сосёт.

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

Ну, вот, когда на сишке напишут что-нибудь уровня Tomcat+Spring, тогда и поговорим с фанатиками сишек, а так - одни пуки в лужу. Тот же go и то лучше подходит на замену жабки.

Это же ты утверждаешь, что что-то знаешь про >O(1).

Зачем ты пытаешься юлить и съезжать с темы. Ты начал кукарекать, что на железе растёт. Не я, а после того, как тебя спросил - почему же оно растёт - ты слился как 5-тилетка.

Т.е. ты просто так кукарекнул и съехал - номер раз.

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

Ну да, эти эксперты.

Ходили в учебниках вместе с доказательством O(1)ности - ок. Покажи мне это доказательство. В учебниках же есть.

Нет смысла.

Т.е. не можешь, хорошо.

Ты либо ничего не понимаешь в теме(т.ч. продолжишь самоутверждаться воплями)

Ну дак докажи - покажи мне доказательство O(1). Я даже не прошу тебя предоставлять мне O(1)-доказательство для какой-то реализации, ибо ты обосрёшься инстантно. Хотябы для абстрактной матмодели предоставь.

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

Зачем ты оправдываешься? Это ты кукарекал, а не я. Ты получается просто так кидаешься словами «у меня есть пруфцы», «всё доказано», а когда тебя спрашиваешь - где доказательства, ты обсираешься. Это глупо.

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

Я тебе уже 10раз всё обосновал. Откуда взялся O(1) в хештаблице - это чистая таблица, где елемент есть value. Т.е. O(1) возможен только в таблице елементов, ты это способен понять?

Я уже показывал эмулеку, что такое O(1) find - это find(key) {return m[perfrect_hash(key)];}

Реально же используется финд, аля:

find(key) {
  t = m[mod_hash(user_hash(key))];
  return t.find(key);
}

Ты видишь тут 2финда?

Вопервых mod_hash() ограничивает длину масива сверху, а что это значит? Это значит, что в среднем случае кол-во елементов по которому делается 2-й финд растёт на 1 за каждые n елементов, где n - наш делитель в модхеше.

Если мы берём бесконечные велиичины, то наш финдец будет бесконечным, а не O(1) как нам хотелось.

Даже если у нас нет модхеша, то у нас есть коллизии. Собственно поведение тоже, что с модхешом. Только не динамическое.

В стандарте крестов написано:

Complexity: Average case O(1), worst case O(size()).

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

Если принять во внимание это + динамический модхеш, то можно сделать O(1) изи. 1метр кв - это в худжем случае (((1 * 2^20) / (8 + 8)) * 4096) / 2 ^ 20 = 256метров.

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

Видя худшую оценку O(size()) - т.е. O(n), т.е. там используется линейный поиск. Давай я тебе объясню откуда она взялась:

typeof(t)::find(key) {
  for(i : this) {//какбэ линейный поиск, для примера, можешь заменить на что угодно, будет даже в 80% сл тормазнее в общем случае.
    if(i.key == key) return i.value;//это O(n) по бакету.
  }//но ничего не мешает всем елементам быть в одном бакете.
}


find(key) {//лучшая оценка достигается как-то так:
  t = m[mod_hash(user_hash(key))];
  if(t.size() == 1) return t.begin().value;//это лучшая оценка, либо средняя в терминологии крестового стандарта.
  return t.find(key);//лучшая оценка, это когда вот этого нет.
}

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

Но всё это стоит сотни метров памяти на метр кв, не даёт гарантий и один хрен в среднем никогда не O(1).

При этом я не учитывал ещё хеширование и говорил чисто о перфектхеше через модхеш. Реально же есть ещё и говнохеш с мильёном рандомных коллизий, которые уменьшают шанс на O(1) до минимума. Конечно 30-50битный хеш + сбитый в говно лоадфактор тебе дадут в районе среднего O(1) даже в дефолтной хештаблице, но как я уже говорил - привет 10гигов на 1метр кв.

Tomcat+Spring

Что значит уровня? Уровня чего, тормазнутости и избыточности?

У тебя и у сишника разные задачи. Зачем сишнику заниматься написанием тормазной и убогой вебскриптухи. Для этого есть гигантская популяция малоквалифицированных и дешёвых вебговнарей.

То, что ты будешь писать на сишке месяц - я напишу за 3 дня на java.

Ну давай. Выкатывай задачу и пиши её за 3дня. Ах да, я даже не буду говорить про написание задачи с нуля на жабе/сишке юзая только stdlib(т.е. то, что описано в стандарте), ибо ты обосрёшься инстантно, а уж как ты обдришишься, когда я скажу про рандомную область. Поэтому можешь юзать любое говно, балаболка и задачу выбираешь сам, с моими корректировками адекватности.

Потом пишу её я на сишке. Ты обсираешься - мы расходимся. Ах да, условия таргета/работы/перфоманса обговариваются зарание.

Тут уже была одна балаболка, которая кукарекала про «распределённость» и быстронаписание ерланга. Когда же балаболке сказали - выкати конкретную масимальную нагрузку на систему, при этом я даю тебе фору 4ноды. Питушок тут же обосрался и куда-то пропал.

У тебя тоже самое - твой хлебушек не способен понять, что есть область говноваяния и есть уже реализованное готовое говно под неё. В этой области процветает жаба. И в конечном итоге твой хлебушек начинает путать скорость написания на жабе и скорость юза готового говна из той области, в которой доминирует жаба. Естественно для этой области есть больше готового говна под жабу.

Когда же речь заходит об написании с нуля, то тут у пациента начинается лютая жопаболь.

Так же хлебушек не способен понять, что мне не нужен Tomcat+Spring для написания того, что ты на них ваяешь. Моя квалификация позволяет мне писать без них - тебе нет. Всё просто.

айнепиздика. Максималльная цена обезъянки с крестами - 120 тыр.

Когда же речь заходит об написании с нуля

Слыш питушок, а нахер ты кому нужен со своим «с нуля». В принципе «с нуля» это как раз с твоего уровня. Пока ты будешь тупить и вдуплять как сделать парсер для какого-нить финансового протокола, расчехливать конпелятор, открывать сокеты, подсовывать сертификаты и прочую криптографическую муйню, писать for( int i...) и выделять память вручную... Я возьму уже готовую либу на яве, за 15 выкачу обработчик финансовой статистики на насколько сотен элеметов, перелопачу (пусть даже на это день уйдет) сотню гигабайт входных данных, построю графы, деревья, прочую муню, найду петли, выполню пяток сделок, получу профит процента 3 чистыми. И вот так укаждый день.

Моя квалификация позволяет мне писать без них - тебе нет. Всё просто.

Моя квалификация позволяет мне иметь до ~30 штук евро в месяц, просто написав 10 строк кода в неделю, она так же мне позволяет нанимать таких как ты чистить мне корзины на рабочем столе (хоть на сишечке, хоть голом асме). Все просто.

и ты и ты прав.

макс плюсовой обебьянки 120.

макс спеца в том числе могущего в кресты 300+бонусы

ps. аноним лучше того-самого.

И вот так укаждый день.

скучно у вас там.

Причём тут твои нищебродские тыры, свинья? Мы говорим про $300к в год плюс бонусы (т.е., порядка ляма баксов в год). Типичный уровень плюсовика в хедж-фонде в HFT.

Еще раз. Непиздика. максимум для крестовой обеъянки - 120 в год. Это потолок. Крестовые обезянки не нужны. Если только легаси хлам какой поддерживать. 300 это твои влажные фантазии, пока ты хлебаешь мамкин борщЬ.

offtopic

ты действительно считаешь себя единственным, знающим устройство хештаблиц??? невероятно! У меня для тебя плохие новости о багах в прошивке.

почему же оно растёт на железе

Ты же писнул, что знаешь почему. Зачем тратить буквы на то, что всем уже и так известно? Если без технических деталей, (a)при «достаточной» памяти имеем O(1);(b) ограниченность памяти это не свойство алгоритма и не всегда(%руки) свойство реализации → это свойство конкретного внедрения(на конкретном железе). (a)&(b)→ все тормоза должны быть в железе или кривой реализации.

они врут - тут O(1) - это минимальная оценка

Или они знают способ расширения таблицы, укладывающийся в O(1). <Albert Einstein mode>Правда, последнее невозможно - для этого им пришлось бы быть умнее TrueTsarC-а, а при этом квадратный корень в наших уравнениях превращается в какую-то фигню</>

Не трать время на эту Барби. Пластиковые куклы, живущие в своем пластиковом мирке по своим пластиковым фантазиям не могут осознавать своей пластиковости.

Моя квалификация позволяет мне иметь до ~30 штук евро в месяц
до ~30 штук евро в месяц

Так это у каждого первого на данном форуме, даже у нищих прыщявых студентов.

Не трать время на эту Барби

По моим расчётам это, пока, мне выгодно.

Если мы берём бесконечные велиичины, то наш финдец будет бесконечным, а не O(1) как нам хотелось.

слушай, а тебе не тяжело быть таким мудаком? При чём тут «бесконечные величины»? O(1) означает только одно: время НЕ РАСТЁТ с ростом N. А вот размер таблицы естественно растёт.

Ты видишь тут 2финда?

дебилка, это не хеш таблица, а хеш таблица из хеш таблиц. В пределе — дерево некой арности. И время поиска в таком дереве O(log(N)). При этом размер таблицы тут служит основанием логарифма, и в пределе ни на что не влияет(почему его и не пишут в O-нотации).

слушай, а тебе не тяжело быть таким мудаком? При чём тут «бесконечные величины»? O(1) означает только одно: время НЕ РАСТЁТ с ростом N.

Весь тред не отпускает ощущение, что под O(1) он понимает выполнение за 1 секунду/шаг/такт/сигарету.

А у меня ощущение, что его тут тупо тролят, а он ведется, как и положено пластиковой куколке Барби.

этот царь уже не торт. Нормальный царь умел миллиарды float'ов на время складывать на SSE. Я, правда, так и не понял зачем, но всё равно прикольно. А этот…

что его тут тупо тролят

сложно открыть википедию, и почитать про O(1)?

Тут вопрос не в зачем, а в отсутствии на сишке контейнеров веб-приложений, написанных опять таки, на сишке. Потому, что сишка имеет кучу минусов, по которым ей вход на веб закрыт. А так то restful я могу запилить и на сишке, но нафига? Мне для этого и питона с торнадой хватит за глаза, ибо железо дешевле моего времени.

отсутствии на сишке контейнеров веб-приложений, написанных опять таки, на сишке

Лживые ренегатские отступники в треде!! linux с apache-м(и кучей аналогов) написаны в значительной мере именно на c и замечательно контейнят web приложения. в том числе.

Ну ну, лошарик, найди HFT не на плюсах.

Не, тут есть два нищеброда - спуфинг и эдичка.

Ну даже их доход, на сколько я понимаю, не превышает 30К евро в месяц. Или я живу не в той вселенной.

слушай, а тебе не тяжело быть таким мудаком?

Мне тебя о5 смешать с говнецом. Ты уже был обоссан тысячи раз, но ты продолжаешь лезть.

При чём тут «бесконечные величины»? O(1) означает только одно: время НЕ РАСТЁТ с ростом N.

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

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

Т.е. реальный O(1) будет давать тоже время, что на одном елементе, что на бесконечности. Хештаблица априори не может быть O(1), ибо поиск будет бесконечно долгим. Это свойство любого хеша.

А вот размер таблицы естественно растёт.

Причем тут размер таблицы? Я где-то говорил про размер таблицы?

O(1) ни от чего не зависит и не может менять ни от каких величин. К чему ты их высрал?

дебилка, это не хеш таблица, а хеш таблица из хеш таблиц.

Где хештаблица из хештаблиц, покажи мне её. Откуда ты это высрал?

В пределе — дерево некой арности. И время поиска в таком дереве O(log(N)).

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

почему его и не пишут в O-нотации

Как это не на что не влияет - влияет. Алгоритмически с увеличением кол-ва елементов в таблице увеличивается время поиска. Это не O(1), ибо O(1) не зависит от N, а финд с логарифомом по бакету зависит.

Я жду твою задачу. Ты же надеюсь не просто так кукарекал и покажешь пацанам, что ты не балаболка?

Тут вопрос не в зачем, а в отсутствии на сишке контейнеров веб-приложений

Зачем они мне на сишке? Я тебе сказал - они нужны тебе, как неквалифицированнйо говноваялке. Т.е. ты ниже апи говнолибы ничего не знаешь и естественно ничего не напишешь.

В отличии же от тебя вменяемый сишник это знает и понимает.

Потому, что сишка имеет кучу минусов

Сишка не имеет минусов. Минусы имеешь ты, ибо твоя квалификация и интеллектуальные способности не позволяют тебе использовать настолько тонкий и ширикоспециализированный «инструмент».

Понимаешь, то, что управление в самолёте сложнее, чем у трамвая - не делает минусы самолёты. У самолёта больше степеней свободы. И сложнее навигация.

по которым ей вход на веб закрыт

Естественно закрыт, только закрыт - это проблема ЦА, а не сишки.

А так то restful я могу запилить и на сишке, но нафига

Сомневаюсь.

Мне для этого и питона с торнадой хватит за глаза

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

100rps на ведро на хелворде - приемлемо.

ибо железо дешевле моего времени.

Как же любят балаболки об этом кукарекать. Это очередной миф, которым балаболящий нуль пытается как-то придать себе цену. И какое же железо дешевле твоего времени?

У твоей области просто нет потребности в перфомансе, ибо рядовая истинная бигдата в 100килобайт и 1000крпс. Тут ваять можно на каком угодно говне.

Когда у твоей области будет реальная потребность в 1ккрпс, то такой херни ты нести не будешь.

ты действительно считаешь себя единственным, знающим устройство хештаблиц??? невероятно! У меня для тебя плохие новости о багах в прошивке.

Ты не знаешь - я это гарантирую.

Ты же писнул, что знаешь почему. Зачем тратить буквы на то, что всем уже и так известно?

Я конечно рад, что ты прочитал мой пост и осилил только сейчас это высрав, «скопипастив» мой пост, но всё же.

Если без технических деталей

Естественно, ибо ты их не знаешь.

(a)при «достаточной» памяти имеем O(1)

Неправильно читал. Это одно из условий - отсутствие деление массива, а ещё отсутствие коллизий. Слоты в таблице делятся не только для экономии адресспейса, а так же и для нивелирования влияния коллизий.

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

(b) ограниченность памяти это не свойство алгоритма и не всегда(%руки) свойство реализации

А кто говорит об «алгоритме» и алгоритме чего? Про алгоритм начал кукарекать ты, а я говорил и основной контекст темы - stl.

Эмулеку я отвечал на его кукаретинг про stl, мигелю тоже. Ты высрался и начал свичиться на абстрактные мистические доказанные алгоритмы. Ты так и не смог мне высрать конкретный алгоритм, ибо их мильён. Так же ты не смог высрать мне доказательство O(1), которое есть в учебниках.

И о5 ты пытаешься уйти от хеша и свичнуться только на память. Не работает - будешь тыкнут обратно в говно. O(1) мешают коллизии.

А память - это ограничение реального мира, которое учитывают все реализации, в частности стл.

(a)&(b)→ все тормоза должны быть в железе или кривой реализации.

Пруфец O(1) выкатываем.

Ещё раз, O(1) для общего случая на практике не реализуем, точно так же как и математически. Только с граничными и прочими условиями и допусками.

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

Или они знают способ расширения таблицы, укладывающийся в O(1).

О5 игнор хеша.

И делать перфектхеш для рандомных данных? Дефолтный уровень лоадфактора не позволяет stl-реализации иметь O(1).

O(1) способ не юзабелен в реальном мире и в реализациях стл"а его нет.

Задача? Ну вот простейшая задача: web-приложение/сайт для совместной работы сотрудников. Можешь попробовать написать за 3 дня на сишке. Юзать можно любые библиотеки сишные, не используя интерпретаторов и vm других языков по типу lua/python. При этом приложение должно использовать jade как template, и less/stylus аналог.

Я за 3 дня такое наваляю. А ты - нет. А крики твои про производительность я могу легко замять таким ответом: у меня крутится и java и c приложения, абсолютно аналогичные. На них java медленнее си всего в 1.5 раза. Т.ч. пуки про rps не засчитаны. Vert.x выдаёт 5700 req/sec, си сервер на libevent: 7.000.
Смысл людям писать на си и упарываться указателями с памятью? Чтобы выжать 2.000? Смешно.

они нужны тебе, как неквалифицированнйо говноваялке. Т.е. ты ниже апи говнолибы ничего не знаешь и естественно ничего не напишешь.

Ой, ой, я просто в шоке. Думаешь, меня зацепил? Ну да, сейчас побегу плакать к мамке на шею.

Ты переходишь на личности и срёшь какашками в треде по причине безвыходности сишечки. Она никому уже не нужна, все давно на javascript переходят, благо v8 быстр как никогда. И бабосы рубят похлеще чем ты, ибо, если б ты деньги зарабатывал - не срал бы тут сутками простыни соплей. Просто не было бы времени.

Она никому уже не нужна, все давно на javascript переходят

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

Попахивает «элиткой». Часто встречающееся отклонение у айтишников.

сишечка не нужна

все давно на javascript переходят

бабосы рубят

Дальше не читал

Мне тебя о5 смешать с говнецом.

попробуй. Это забавно.

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

ты мудак. Вероятность коллизий имеет меньший порядок малости, и не влияет на результат.

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

ты мудак. Бесконечность тут не при чём. Число N в O-нотации вполне конечно, тебя обманули. На самом деле, речь идёт о бесконечном пределе функции, когда N→∞, но каждый раз по дороге к этому пределу, число N считается КОНЕЧНЫМ.

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

Т.е. реальный O(1) будет давать тоже время, что на одном елементе, что на бесконечности. Хештаблица априори не может быть O(1), ибо поиск будет бесконечно долгим. Это свойство любого хеша.

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

Причем тут размер таблицы? Я где-то говорил про размер таблицы?

да, говорил. Ибо вероятность коллизии линейно зависит от размера таблицы.

O(1) ни от чего не зависит и не может менять ни от каких величин.

не зависит, потому что это предел. Вот смотри:

Предел суммы ряда 1-⅓+⅕-… зависит от числа членов? Нет, этот предел в точности равен π/4. А сама сумма? Ну возьми и посчитай, сам увидишь, что сумма зависит, она то больше, то меньше π/4.

Где хештаблица из хештаблиц

у тебя find внутри find.

Откуда ты это высрал?

это твой высер, детка.

Время поиска в бревне не логарифм, а в лучшем случае логарифм.

а мужики-то не знали… Что если дерево вырождается в список, сложность вырождается в O(n).

Почемуж конеченные балаболы настолько тупые, что немогут высирать свой высер с условиями, аля балансировка, аля перфектхеш.

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

Как это не на что не влияет - влияет. Алгоритмически с увеличением кол-ва елементов в таблице увеличивается время поиска. Это не O(1), ибо O(1) не зависит от N, а финд с логарифомом по бакету зависит.

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

Задача? Ну вот простейшая задача: web-приложение/сайт для совместной работы сотрудников. Можешь попробовать написать за 3 дня на сишке.

дык это всё очень просто реализуется на самом деле:

1. делаем удобный и годный String, не на шаблонах как в STL, а так, ибо время похрен.

2. делаем Integer внутри String, и чтоб одно в другое конвертилось

3. делаем одну коллекцию, но чтоб можно было с ней делать ВСЁ, т.е. доступ по индексу Integer AND/OR String, push/pop, delete чего угодно

4. на базе п3 делаем GC для п1 и п2

5. делаем тривиальный парсер AST и его «выполнятор». Используем сишную нотацию, но с нашими String, Integer, and Collection.

6 ?????????????????????

7 PROFIT

PS: php уже придумали, OH SHI~~

Смысл людям писать на си и упарываться указателями с памятью?

что-бы обезьяны тоже могли писать свой говнокод. Разве не очевидно?

Да, на пхп или на питоне.

Ну например обезьяна не может понять, что коллекция типа сишного массива позволяет доступ за O(1), но вставка O(n). Список — наоборот. Даём обезьяне дерево, там на всё про всё O(log(n)) с огромной константой пропорциональности. Это плохо, но лучше, нежели O(n). В итоге — профит. Обезьяна в принципе не может ошибиться. Что-бы она не делала, всегда получается O(log(n)).

Другой пример: обезьяна не может убирать своё говно, то, что она срёт в память. Нет проблем! Дадим ей GC! И всё чудесно, говно само убирается. Да, повсюду кучи говна, но это разве проблема, с нынешними ценами на RAM?!

Ну и так далее. Обезьяны радуются и гордятся своим умением. Intel&AMD имеют устойчивый рынок сбыта. Все довольны и счастливы.

Разве это плохо? Нет, это замечательно!

Ты переходишь на личности и срёшь какашками в треде по причине безвыходности сишечки.

он просто дурак. Не слушай его. Just as planned.

ты мудак. Вероятность коллизий имеет меньший порядок малости, и не влияет на результат.

Как это не влияет. У нас есть отсилы 24битный хеш - это <10лямов дипазон. Т.е. если мы вставим туда 100лямов, то будет по 10коллизий.

Ну давай, если ты конечно не балабол, выкати мне хешфункцию, которая не даст мне больше 1-й коллизии на лярд значений. И потом на этом хеше ты мне напишешь хештаблицу без деления массива, чтобы ты о5 не разродился md5.

ты мудак. Бесконечность тут не при чём. Число N в O-нотации вполне конечно, тебя обманули.

Тебе объяснили для дебила, ибо ты не понимаешь основное свойство O(1) - независимость от N. Которое невозможно, если имеется деление таблицы и/либо коллизии.

Любая вероятность коллизий привязывает твой O(1) к N и это уже не O(1). Т.е. будет не просто константа, константа с коэффициентом завясящим от N, т.е. O(что-то(N)).

На самом деле, речь идёт о бесконечном пределе функции, когда N→∞, но каждый раз по дороге к этому пределу, число N считается КОНЕЧНЫМ.

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

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

Пацанёнок уже слился на математику. Меня не интерсует твоя бесполезная математика. А математиков она не волнует лишь тогда, когда ширина хеша infinitybit. Во всех остальных случаях - она волнует.

Хотя конечно тебя, как нулёвого нонейма псевдознания которого есть примитивное обобщённое говнище. Когда при обсёре обезьяна суёт мд5, бесконечность в ширину хеша и прочее.

Оправдывай себя.

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

Обычный - это какой? Эти обсёры, эти обсёры.

Я тебе напомню, чтобы ты так явно не обсирался - контекст stl. И ты кукарекал про кнута на фоне разговоров об стл, и спросил я тебя про дефолтную хештаблицу.

Ни про какое-то мистическое доказанное в каждом учебники O(1) обычная хештаблица. Где доказательства? Где описание обычности?

да, говорил. Ибо вероятность коллизии линейно зависит от размера таблицы.

Т.е. я не говорил - ты это сам вывел.

Дак размер таблицы есть N. А от вероятности коллизий зависит время поиска. Т.е. у нас уже получается не O(1), а O(f(вероятность_коллизий(N))); Это отсилы можно назвать «в районе O(1)».

у тебя find внутри find.

Финд каким-то образом связан с хештаблицей? Ты мне показывай не финды, а хештаблицы. Две штуки. Вложенных. А так - обсёр.

Естественно вероятность коллизий требует их обработки, а обработка требует финда. Поэтому в любой хештаблице будет 2-й финд, если это не перфектхеш.

это твой высер, детка.

Конкретно цитатку и указанием на первую хештаблицу и на вложенную.

а мужики-то не знали…

Естественно не знали, ибо в противном случае ты бы не кукарекал на каждом шагу про логарафм, которого там нет без условия балансировки.

Что если дерево вырождается в список, сложность вырождается в O(n).

Причём тут вырождение в список? Это наверное единственно, что ты нагуглил.

Логарифм существует только для идеально сбалансированного дерева. Во всех остальных случаях его нет и полное вырождение тут непричем.

Ты обычный дефолтный балабол. Повтори ещё раз: логарифм есть только в идеально сбалансированном дереве, а O(1) есть только в перфектхеше.

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

Нет, ты просто балаболишь дефолтными цитатками из талмуда, даже не понимая их.

Идеально сбалансированное дерево невозможно в реализации, собственно как и перфектхеш для рандомных данных за разумное время. Поэтому кукарекать о том, что на самом деле ты подразумевал их, а не дефолтные брёвна/хеши, причем будучи в разделе девелопмент, а не в разделе «примитивный матан для дошкольников».

потому что ты мудак, и не смог сделать реализацию с O(1)

Началось, началось. Я уже это помню. Ну сделай мне реализацию O(1). Сделай. Без перфектхеша.

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

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

У нас есть отсилы 24битный хеш

это у вас. А у нас 32 бита CRC как минимум.

Т.е. если мы вставим туда 100лямов, то будет по 10коллизий.

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

Ну давай, если ты конечно не балабол, выкати мне хешфункцию, которая не даст мне больше 1-й коллизии на лярд значений.

CRC32

И потом на этом хеше ты мне напишешь хештаблицу без деления массива

да легко! Возьму любые 32 бита той же md5.

Пойми, дурачок, хеш таблица и должна быть заполнена на малую часть. Это не баг, а фича. Если тебе нужен миллиард ключей, то делай хеш как минимум на 4 миллиарда. И не ной, O(1) не бесплатен, да.

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

Тебе объяснили для дебила, ибо ты не понимаешь основное свойство O(1) - независимость от N. Которое невозможно, если имеется деление таблицы и/либо коллизии.

не, ну как можно быть таким мудаком? Это и без тебя все давно знали.

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

ох, мудилка…

При росте N (число эл-тов), одновременно растёт и M (размер таблицы). Или(что равносильно), полагается M всегда намного больше N. Тогда и только тогда сложность хеша O(1).

Извини, читать нужно всё, а не первые 10 строк википедии, как делаешь ты.

Пацанёнок уже слился на математику. Меня не интерсует твоя бесполезная математика.

вот как можно быть таким мудаком? O-большое это и есть — математика.

Дак размер таблицы есть N

нет, размер таблицы это M. Например, если у тебя за хеш CRC32, то таблица у тебя вмещает M=4294967296 ключей. В таком хеше можно хранить не более миллиарда ключей, если больше, то это уже не хеш, а хрень ненужная.

Логарифм существует только для идеально сбалансированного дерева. Во всех остальных случаях его нет и полное вырождение тут непричем.

ты дебил. Про 23-дерево(aka красно-чёрное) слышал? Вот его высота в лучшем случае log₃(n), а в худшем случае log₂(n). Учи матчасть, и не позорься.

Идеально сбалансированное дерево невозможно в реализации, собственно как и перфектхеш для рандомных данных за разумное время. Поэтому кукарекать о том, что на самом деле ты подразумевал их, а не дефолтные брёвна/хеши, причем будучи в разделе девелопмент, а не в разделе «примитивный матан для дошкольников».

facepalm

в реализациях стл"а его нет.

Это легко проверить экспериментально, кому интересно. Доступные в инете графики показывают рост времени работы с размером данных. Но они не нормированы, для оценки реализации следовало бы умножить их на измеренную рядом реальную скорость O(1)-а(скажем, память[рандом()] на соответствующих объёмах).

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

это у вас. А у нас 32 бита CRC как минимум.

Реализацию на crc32 без деления массива.

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

Чего считать? Причём тут вставки?

Если ты пытался высрать вопрос «насколько возрастёт время финда имея 10коллизий на елемент таблицы» - алгоритмически в lb(10)раз в лучшем случае, если мы юзаем бревно. Реально же бревно заюзает только идиот и там будет линейный поиск - т.е. даже алгоритмически в 10раз. Реально в зависимости от реализации.

CRC32

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

да легко! Возьму любые 32 бита той же md5.

Реализацию мне, которая вместит 100лямов void*+void* с оверхедом по памяти не более 2-4N и при этом будет O(1). Диапазон ключей 0 - 1ккк.

Ах да, ты же там 32битный питушок. Такое непрокатит на 32битах, ибо требует сотню гигов адресспейса, ну либо минимум 16, если посрать на перфоманс.

Пойми, дурачок, хеш таблица и должна быть заполнена на малую часть. Это не баг, а фича. Если тебе нужен миллиард ключей, то делай хеш как минимум на 4 миллиарда. И не ной, O(1) не бесплатен, да.

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

Равномерное распределение + хеш на 32бита = оверхед по памяти 4к. Нереализуемо - привет модхеш. 4раза мало.

На основной ЦА - это до десятков метров - прощай кеширование. И реально 10коллизий будет быстрее O(1). Для больших случаев не реализуемо, ибо имеет адский оверхед по памяти - привет мму-жопу + жопа на вставке. Для гиганских случаев просто нереализуемо, ибо просто столько памяти ненайдёшь.

Среднего O(1) добиться можно, только как я уже выше объяснял - этого никто не делает, ибо это слишком за гранью разумного.

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

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

stl-хеши не обладают подефолту таким уровнем заполнения, чтобы давать O(1). Собственно как и почти любые другие.

не, ну как можно быть таким мудаком? Это и без тебя все давно знали.

Маловероятно, иначе ты бы такую херню не нёс. Оказывается уже O(1) возможен только с определённым заполнением - молодец. Уже лучше.

При росте N (число эл-тов), одновременно растёт и M (размер таблицы). Или(что равносильно), полагается M всегда намного больше N. Тогда и только тогда сложность хеша O(1).

Твоё полагается не реализуемо. И нигде не реализовано.

Тогда и только тогда сложность хеша в среднем O(1).

И да, это требует динамического M, а это привет ребилдинг и привет жопа на вставках.

нет, размер таблицы это M

Пусть будет M.

Например, если у тебя за хеш CRC32, то таблица у тебя вмещает M=4294967296 ключей.

Зачем ты мне это рассказываешь? Я тебе уже это рассказал неделю назад.

Суть не в этом - суть том, что CRC32 ты юзать никак не можешь, ибо 4к оверхед по памяти. Ты можешь юзать mod_hash(crc32()), т.е. динамический M.

При этом какая с этим связана жопа на вставках + некешируемость + адский оверхед. Юзабельно это только на труЪбигдате в 1метр ключей.

ты дебил. Про 23-дерево(aka красно-чёрное) слышал?

И? К чему ты это высрал?

Вот его высота в лучшем случае log₃(n), а в худшем случае log₂(n).

И? Это сбалансированное бревно, а т.к. оно не идеально сбалансировано у тебя и есть худший/лучший случай.

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

Раз там лог3 - это не двоичное бревно, а значит при идеальной балансировке по 3-м ногам - там будет постоянный log3.

Собственно в твоём бревне и нет логарифма - в нём есть 2логарифма. Плюс больше константа, а собственно профит на дефолтной труЪбигдате крайне сомнителен.

facepalm

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

Это легко проверить экспериментально, кому интересно.

Лоадфакто на stl"е не опускается ниже 0.5.

Доступные в инете графики показывают рост времени работы с размером данных.

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

для оценки реализации следовало бы умножить их на измеренную рядом реальную скорость

Зачем? Они растут - это уже показатель. А то, что железо O(1) - я тебе гарантирую.

Больше ничего интересного ты сказать не смог.

Приведи мне пример интересного, либо в очередной раз обделаешься?

Приводимые аргументы стары и учтены

Не учтены. Они просто выкидываются. Мы возмём хешец пошире, на цену ребилда и вставки забьём, а на оверхед по памяти просто положим. Мы же не думаем о чем-то большем, чем Труъжабабигдата в 100килобайт ключей. Где насрать на то, что на 100кило шехтаблица весит 250метров.

зачем ты их повторяешь.

Затем, что у пацанов O(1) в stl, которого там нет. Потом пацаны свичатся с темы на мистические доказанные хеши. Потом посторяют твои слова, потом кукарекают, что это итак всем ясно.

Если ясно, то какого хрена у стл"а везде стоит O(1) средний, если его там нету - там O(1) минимальный.

Остальные очевидно ложны

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

Это дефолные павадки нулёвой балаболки - прятаться за всех, за очевидно, за кого-то, либо что-то.

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

Ну и да, зачем ты дёргаешь из контекста - в надежде на то, что кто-то не почитает ветку выше? Зачем ты пересказываешь мне мои слова, в надежде на то, что кто-то не перечитает ветку выше?

А на чем там v8 написан, а?

Ну а вот тебе задача: дизельный двигатель выдаёт до 4к оборотов в секунду, 6 цилиндров. Надо анализировать в реальном времени момент воспламенения топливной воздушной смеси в каждом цилиндре и используя алгоритмы machine learning варьировать состав смеси для выжима ния максимума эффективности из двигателя.

Доступное железо - NEC микроконтроллеры и одно тощее ядро ARM. Ничего более тяжёлого нет. Вперёд, насилуй свою ябку.

Это - задача. А твои убогие уеб-странички для Васек Пупкиных - ненужная мразота. Мир без уеба был бы лучше.