- 1
- 2
http://habrahabr.ru/blogs/algorithm/103513/
Советую всем посмотреть, очень воодушевляет.-
Куча / Говнокод #4169
+121
А теперь по теме, вторая часть видео ( http://video.yandex.ru/users/ya-events/view/128/?cauthor=ya-events&cid=10 ) 44:44 .
Александр Александрович: "У указателей не нужно определять операцию сравнения [....] равенство есть, а неравенства нет.
[..] Вы не можете теперь создать множество. Точнее можете, но оно будет очень медленным."
Какое-то чудило: " ээ, ну если вести хэшировние, и операцию equals, как в Java сделано"..
Интересно, как он хеширование сделает, если две сущности можно сравнивать только на равенство?
Да, и ещё, сразу виден развращённый( хешированием ) неокрепший детский мозг - видимо никогда не слышал про двоичные деревья поиска, что уже говорить по красно-чёрные деревья.
P.S. Где тут куча? это же PascalЗапостил:
J0hnny,
04 Сентября 2010
Follow us!
>«о истории алгоритма нахождения наибольшего общего делителя»
на подходе следующая архиважнейшая и непостижимо сложная задача: алгоритм нахождения решения уравнения 2*2 = X
...долбаный наркоман
http://govnokod.ru/4169#comment46217
[45.30] "у Вирта была неправильная идея что нужно машину прятать, например он считал, что у указателей не нужно определять операцию сравнения, и в паскале это так. ... равенство есть, а неравенства нет."
"хеширование ... функция из типа в числа, которая вводит упорядоченность." так и сделает хеширование. и сравнивать будет хеши. и деревья из них строить.
где тут говнокод?
Ещё раз: "как он хеширование сделает, если две сущности можно сравнивать только на равенство?"
Поясняю, то что хеширование можно сделать я не спорю, как сделать такое хеширование поиск в множестве которого будет быстро работать, без создания огромной таблицы(в случае указателей в x32 размера 2^32 )?
"Summary: Every Java object has a hashCode() and an equals() method. Many classes override the default implementations of these methods to provide a higher degree of semantic comparability between object instances. "
и
"The Object class has two methods for making inferences about an object's identity: equals() and hashCode(). In general, if you override one of these methods, you must override both, as there are important relationships between them that must be maintained. In particular, if two objects are equal according to the equals() method, they must have the same hashCode() value (although the reverse is not generally true). "
Есть вопросы?
у нас есть тип, для элементов которого мы можем определить только эквивалентность, и есть возможность взятия хеша. нам надо построить из них бинарное дерево.
я правильно сформулировал задачу, которую ты не можешь решить?
Я думаю что её никто не сможет решить.
"у нас есть тип, для элементов которого мы можем определить только эквивалентность"
Да, больше ничего.
"и есть возможность взятия хеша"
Возможность взятия хэша, вытекает из эквивалентности, вот только взятие такого хэша требует много времени.
Я чувствую что ты сейчас начнёшь говорить, типа если только эквивалентность, то как взять хэш, и сядешь в лужу.. ничё ничё, давай садись, всё готово, зловонная куча уже бурлит..
f(A) = 265
f(B) = 42
теперь мы можем сравнивать, да?
чего тебе еще надо, вано?
Да, я не отрицаю что можно сделать такую хэш функцию, т.е. для сущностий с введённой эквивалентностью.
Но, как это сделать?
Можно создать большой массив из пар. В каждой паре первый элемент это исходный указатель, а второй элемент хэш значение, пусть int - их можно сравнивать.
Но, как быстро взять такой хэш? Не перебирая кучу элементов? Хэш у которого сложность будет "меньше" O(N)?
Если нельзя, то поиск с помощью такого хэша будет очень долгим.
Смысл не просто взять хэш, смысл быстро взять хэш.
Ты, сидя в своей луже, можешь показать как взять быстро такой хэш? Ты вообще слышал про ассоциативные массивы с быстрым поиском, аля std::map?
теперь ты что-то лепишь про лужи, быстрые хеши и стд:мап. у тебя вообще все в порядке?
Суть сделать множество указателей(у которых есть только сравнение на равенство), с быстрым поиском, именно об этом и говорит Степанов(см. видео).
Ещё раз, ты можешь сделать такое множество, с БЫСТРЫМ поиском?
Сделать множество указателей с поиском O(N), это не трудно, такое кэпство даже не считаю нужным обсуждать.
быстрый поиск - под двоичному дереву, в узлах которого - замечательные числовые хеши от несравненных элементов.
так чего я не понял?
Но, (сейчас будут брызги, так как скорей всего до тебя наконец допрёт, что всё таки упал в жижу), как ты хэш будешь вычислять для таких указателей?
Если не дошло - вот есть у тебя уже сформированное дерево с хэшами в узлах,
1. на вход функции find поступает значение указателя, нужно найти соответствующий элемент.
2. ??( hash(указатель) )??
3. Делаем поиск по дереву используя хеш.
какая сложность этапа 2, O(?) ?
Может быть O( N )?
>> сделать такое множество, с БЫСТРЫМ поиском
вот я и спросил "чего тебе надо?"
но, если ты посмотришь на наш тред еще раз, ты увидишь, что:
1. мы договорились о том, что и в ролике, и в концепции все правильно. задача решаема.
2. быстрый поиск тоже осилили.
3. накладные расходы на вычисление хеша указателя окупаются за счет ускорения поиска
4. это одна из тех "неправильных идей" о которых говорил Александр Александрович
так о чем мы?
2. Нет, не осилили. Поиск хеша быстрый, генерация хеша - нет, соответственно поиск по исходному указателю тоже не быстрый.
3. ну да: у нас есть запорожец без двигателя, надо быстро добраться из Москвы в Париж.. толкаем его почти до Парижа, ну 1 км остаётся. Там уже ждёт ракета которую построили по предварительному заказу, и пролетаем этот 1км на ней.. да очень круто.. а главное без накладных расходов..
4. Хм, это о чём ТЫ?
сравниваем строки фиксированной длинны (L). функция хеширования - сложение с переполнением.
линейный поиск: среднее число сравнений символов в строках = М
среднее количество сравнений строк между собой = К
время вычисления хеша от такой строки по выбранному алгоритму - примерно равно количеству сравнений (М*К) производимому за (L) итераций. в идеальных условиях: как только количество строк привышает длинну строки - оптимизация уже точно возможна. но условия обычно чертовски далеки от идеальных.
вышел из дома - сел на маршрутку. (запарожец? ракета? париж? москва? хватит придумывать)
а теперь скажи-ка мне уважаемый, как же ты так хитро собрался генерить хеш, что весь профит от дерева теряется?
http://govnokod.ru/4169#comment46034
>>"Интересно, как он хеширование сделает, если две сущности можно сравнивать только на равенство?"
>> "то что хеширование можно сделать я не спорю, как сделать такое хеширование поиск в множестве которого будет быстро работать"
>> "Хэш у которого сложность будет "меньше" O(N)? Если нельзя, то поиск с помощью такого хэша будет очень долгим"
>> "Да, всё замечательно, дерево с хешами в узлах ... всё отлично, и поиск O(log N)"
и на закуску:
>> "Возможность взятия хэша, вытекает из эквивалентности"
итак
"Интересно , как он хеширование сделает, если две сущности можно сравнивать только на равенство?"
"то что хеширование можно сделать я не спорю, как сделать такое хеширование поиск в множестве которого будет быстро работать"
Я не говорил что это не возможно. Мне было интересно, какая сложность будет у этого хеширования. Хеширование со сложностью O(N), не вижу смысла применять - оно не даёт преимуществ в скорости.
Возвращающемся к ролику
"Вы не можете создать множество... нет ну можете но оно будет очень медленным, потому что поиск будет линейным"
Тип явно не понимал о чём речь(тот который про Java и equals трындел), к тому же по всей видимости он не знает о чём говорил, как соотносятся хеши в Java и equals, и видимо вообще не знал о hashCode.
Кстати, а это не ты случайно?
"Хэш у которого сложность будет "меньше" O(N)? Если нельзя, то поиск с помощью такого хэша будет очень долгим"
"Да, всё замечательно, дерево с хешами в узлах ... всё отлично, и поиск O(log N)"
Ты опять не врубился, либо не доконца.. То что поиск в дереве O(log N), вовсе не означает что хэширование данного указателя является быстрым, что соответственно не означает что по исходному указателю можно быстро найти элемент.
"Да, всё замечательно, дерево с хешами в узлах, если не брать в расчёт алгоритм генерации хеша всё отлично, и поиск O(log N)"
Чуешь Тайд?
ты на это ответь, умник
http://govnokod.ru/4169#comment46053
И я правда так и не понял, чего в Паскале нет "... у указателей не нужно определять операцию сравнения, и в паскале это так. ... равенство есть, а неравенства нет."
То есть для указателей определен оператор ==, но не определён != ? В таком случае кто мешает сделать !(p == q) ?
Или же не определены операторы < и > ? А кто их использует и зачем?
И какую таблицу размера 2^32 вы собрались делать?
Разнообразные деревья поиска можно строить вообще без указателей, используя лишь структуры типа std::vector.
Приведите пример функции хеширования, которая возвращает хэш к сущностям которые нельзя сравнить.
"Или же не определены операторы < и > "
имеется ввиду это (http://ru.wikipedia.org/wiki/Неравенство).
" В таком случае кто мешает сделать !(p == q) ?"
и не надо кэпствовать.
"И какую таблицу размера 2^32 вы собрались делать?"
Ну в построении таблицы такого размера, не вижу ничего сложного.. вот только я уже сказал здесь http://govnokod.ru/4169#comment45919 , что для сущностей которые нельзя сравнивать, нельзя построить такую хэш таблицу.
"Разнообразные деревья поиска можно строить вообще без указателей, используя лишь структуры типа std::vector."
Да, можно, дались вам эти указатели. Суть в том, что дерево строится на основе неравенства (обычно less)
Все объекты в конечном итоге состоят из примитивов - строк, символов, чисел и т.п. Их сравнивать можно думаю даже в Паскале. А это значит, что любые более сложные классы могут вычислять свой хэшкод (с помощью хэшкодов полей класса) и срваниваться друг с другом (сравнивая поля класса).
Вот функция хэширования строки. На Паскале такое нельзя написать?
"дерево строится на основе неравенства (обычно less)"
Да, но сравниваются не указатели на объекты, а их хэши. Хэши числа, их сравнивать на >, < в любом языке можно.
И эти указатели вообще никак нельзя сравнивать, ну язык вообще не позволяет.
Суть не в том поддерживает ли это паскаль напрямую, или с помощью какого-либо трюка.
Суть в том, как построить хэш или дерево поиска для сущностей, которые нельзя сравнивать, никаким образом.
Вы привели пример со строками и в вашем примере видно(не вдаваясь в подробности диалекта на котором написан код), что строки можно сравнивать, пусть если не напрямую, то через их символы - каждый символ в строке имеет свою позицию и может преобразовываться к сущности типа int, которую можно сравнивать
"Приведите пример функции хеширования, которая возвращает хэш к сущностям которые НЕЛЬЗЯ СРАВНИВАТЬ"
Понятно, что если сами указатели сравнивать нельзя, то такое дерево построить не получится.
Но ведь в большинстве случаев нужно строить дерево не для каких-то сферических сущностей, а для вполне конкретных, а в таком случае можно будет в качестве неравенства для дерева поиска писать не p < q, а p->getHashCode() < q->getHashCode(). Мы же можем имея два указателя вызвать методы объектов, на которые они сссылаются.
Как вычислить хэш не сравнивая указатели? Я выше написал пример вычисления хэша для строки. Там вообще ничего ни с чем не сравнивается, а только проводятся вычисления над примитивами из которых состоит строка.
"Мы же можем имея два указателя вызвать методы объектов, на которые они сссылаются."
Вы начинаете нарушать исходные условия задачи, смысл именно построить множество указателей с быстрым поиском. Может это кажется слишком сферическим, но представьте менеджер памяти, который не имеет понятия о том, на что ссылаются указатели.
"Как вычислить хэш не сравнивая указатели? Я выше написал пример вычисления хэша для строки. Там вообще ничего ни с чем не сравнивается, а только проводятся вычисления над примитивами из которых состоит строка."
По-моему я разжевал где и как в вашем случае используется возможность сравнивать сущности, то есть такая возможность присутствует, перечитайте http://www.govnokod.ru/4169#comment45934
Просто мне казалось что нужно строить множество не для просто указателей (о которых мы ничего не знаем), а конкретных объектов. И множеству извне дана информация как сравнивать объекты. Ну как бы std::set использует operator < либо компаратор, переданный в конструктор. HashSet использует для сравнения методы equals(), и hashCode() которые есть в таблице виртуальных функций каждого объекта. Поэтому и не мог понять в чём проблема.
Как работает менеджер памяти представляю весьма смутно, но непонятно зачем его писать, если сам язык может управлять памятью?
"По-моему я разжевал где и как в вашем случае используется возможность сравнивать сущности, то есть он присутствует, перечитайте http://www.govnokod.ru/4169#comment45934"
Да, тут я действительно как-то упустил из виду вторую половину комментария
По поводу менеджера памяти.
http://en.wikipedia.org/wiki/Memory_pool
У каждого типа менеджера памяти свои преимущества, не факт что тот который предоставляет компилятор/библиотека/система подходит для нужд конкретного приложения.
Я думаю менеджер памяти это не единственный пример где может понадобится множество указателей с эффектным поиском.
Ещё раз по поводу явы и equals, видимо то тип видел что в классах есть equals, и думал что только с её помощью строится хэш таблица. Сразу видно что он и понятия не имеет как именно работают такие таблицы, но тем не менее он вступает в яростную полемику с лектором, мешая слушать остальным.
"
Свинья под Дубом вековым
Наелась жёлудей до-сыта, до-отвала;
Наевшись, выспалась под ним;
Потом, глаза продравши, встала
И рылом подрывать у Дуба корни стала.
«Ведь это дереву вредит»,
Ей с Дубу Ворон говорит:
«Коль корни обнажишь, оно засохнуть может».—
«Пусть сохнет», говорит Свинья:
«Ничуть меня то не тревожит;
В нем проку мало вижу я;
Хоть век его не будь, ничуть не пожалею;
Лишь были б жолуди: ведь я от них жирею».—
«Неблагодарная!» примолвил Дуб ей тут:
«Когда бы вверх могла поднять ты рыло,
Тебе бы видно было,
Что эти жолуди на мне растут».
Невежда также в ослепленье
Бранит науки и ученье,
И все ученые труды,
Не чувствуя, что он вкушает их плоды.
"
Какие проблемы будут с хэшированием и построением деревьев поиска по хэшу?
При совпадении хэша сравнивать через equals (поэлементно сравнивать поля класса)
Я правда на паскале хэши и деревья не писал, но вот на джаве смотрю на код hashCode() и equals(), и там не используется сравнение указателей (разве что проверка на равенство, но во-первых в паскале она вроде есть, а во вторых можно и обойтись без неё)
А лекцию да, надо скачать.
Пиздос, и никто не против. Супер.
За чистоту латыни не поручусь — не помню, так ли склоняться будет, но идея понятна:)
2. оратор опиндосился настолько, что сталина называет джозефом (а x и i на руглише вообще замечательно звучат)
Не знаю, как это смотреть.
http://www.stepanovpapers.com/gcd.pdf
http://www.stepanovpapers.com/gcd_ru.pdf
2. Да, это очень серьёзно, не смотри
2. При том что звук, мягко говоря, херовый, знаменитый русско-американский ученый мог бы и не выпячивать свой акцент. Я отказываюсь верить, что у Степанова нет лекторского опыта.
3. re: [b][color=red]Всем читать
Киса, не говори нам, что делать и мы не скажем, куда тебе пойти, не назовем ***-хомячком и фэнбоем г-на ****
2. Как он сказал, это его первая лекция за тридцать лет. имхо ничего ужасного, режущего слух нету.
3. Кто вы? мания величия?
2. Если заигрывать с аудиторией - лекция превратится в семинар. Этого нельзя забыть.
3. Мы - Легион.
Судя по здешней реакции, многие даже понятия не имели о чём идёт речь, в чём проблема, и вроде для многих этот тред стал достаточно поучительным.
А о том что ты не учуял там говна, да кричи на каждом углу, и в бложке напиши, и сюда ещё раз.
2. Кстате, Яндекс это именно семинаром и называет. http://clubs.ya.ru/company/replies.xml?item_no=24619
Но всё же, имхо это лекция.
Например если взять определение с википедии(ясное дело, что не авторитет)
http://ru.wikipedia.org/wiki/Семинар
Согласно этому, не то что было на видео, не то что ты назвал "заигрыванием" это не семинар.
3. Бред
2. На видео - обычный фэйл начинающих лекторов, практически все через это проходят. Зачем Степанову понадобилось спорить с репликами - пусть останется тайной, у меня нет ни времени, ни желания смотреть столь же объемную предыдущую серию :-Р
PS: Я нашел сайт http://sf.net там говнокода - жопой ешь, lul.
2. К 44 минутам, лекция закончилась, это уже часть вопросов и ответов. Именно в этой части можно отвечать и на реплики. Но после пары фраз Степанов осознал, что потребуется потратить много времени, чтобы чудила осознал что он говногенератор, и он просто перешёл на другую тему. Те кому надо и так поймут, а этот фруктик ещё не спелый.
а дискуссия уже уныла
Троллинг у тебя слишком толстый получается, мне уже надоело тебя в дерьмо тыкать.
"добавим конкретики? сравниваем строки фиксированной длинны"
Причём тут строки?
"а теперь скажи-ка мне уважаемый, как же ты так хитро собрался генерить хеш, что весь профит от дерева теряется?"
От дерева профит никуда не девается, дерево это и есть ракета.
Например вот так: http://govnokod.ru/4169#comment46005
А теперь ты покажи свой вариант генерирования хэша, для сущностей которые можно только сравнивать на равенство?
Пока не покажешь свой вариант такой хэш функции, продолжения разговора не будет
если ты не понял - объясню. строка "а теперь скажи-ка мне уважаемый, как же ты так хитро собрался генерить хеш, что весь профит от дерева теряется?" была реквестом на твою реализацию хеша для сущностей без неравинства. если ты считаешь, что у тебя получится очень плохо - сразу пости ее кнопкой "наговнокодить". если влом писать - опиши алгоритм. он то и покажет, при каком количестве элементов бинарный поиск начнет рулить, а при каком - как тузик тряпку порвет твой замечательный линейный поиск.
кончай передергивать и напиши уже что-нибудь по теме.
реализация за О(n) очевидна. твоя позиция построена на том, что она единственная?
сравниваем сущности попарно (новую и те, что в дереве), и если нет совпадений - отдаем новый хеш из пула свободных. а потом - гоняем хеш по дереву.
если использовать твою аналогию - мы едем не до парижу, а до сан-франциско. через париж. и да, потом - по дну. а от туда - на ракете обратно в париж, но за 5 минут.
так ты бы так и написал, что сложность вычисления хеша для такой сущности зависит от количества сущностей в дереве, а не от сложности самой сущности.
про "сущности" начал писать ты. в записи ребята говорили про указатели. а указатель, он ведь обязательно на что-то указывает, да? вот от этого чего-то мы можем невозбранно взять хеш, и сложность взятия будет зависеть от сложности адресуемой сущности.
1. придумать проблему
2. сделать n веток в край
...
profit!
трололо?
"Ну вот теперь всё стало более ясно. Если вам нужно строить дерево поиска именно для указателей, не зная ничего об объектах на которые они ссылаются, то я согласен, без сравнения указателей не обойтись."
Ты как-то выборочно читаешь
в записи про такое ограничение нет ни слова.
по поводу #comment45928
"Приведите пример функции хеширования, которая возвращает хэш к сущностям которые нельзя сравнить."
Что не ясно?
Да и вообще, не надо быть супер кэпом, чтобы понять, что если разговор идёт о том что нельзя сравнивать указатели, то речь идёт о том, как можно оперировать именно с их множеством(делать поиск, удаление), не вдаваясь в детали объектов на которые они ссылаются.
другое дело, что это глупое ограничение ввел ты. повторю, в записи на это нет указания.
что не ясно?
но да, именно там ты ввел ограничение на использование указуемых объектов и ушел от "указателей" к "сущностям"
ты это зачем сделал?
http://govnokod.ru/4169#comment46151 здесь?
Мусье вы любите быть в дерьме?
я про http://govnokod.ru/4169#comment45928
http://govnokod.ru/4169#comment46151
В видео оно тоже есть это ограничение
а если не лень - так еще и текстом дублируем. только без синхронов.
Это подразумевалось, может там нет явной фразы "нельзя сравнивать объекты на которые указывает указатель", но именно это и имелось ввиду..
Например
" ээ, ну если вести хэшировние, и операцию equals, как в Java сделано"
Как ты думаешь, это чудило хотел equals применять к объектам на которые ссылаются указатели? или на указатели? по-моему не надо быть кэпом чтобы понять.
И вообще, я вижу к тебе приходит сознание того что ты тонешь в болоте дерьма, но всё же часть разума не верит в это, пытается ухватится за всякую фигню.. Чем быстрее ты осознаешь что в дерьме, тем быстрее из него выйдешь
из вас в эти выходные вылилось достаточно много дерьма, но ничего, продолжим.
чудило говорил про иквалс И хеши. я так и не понял, почему ты решил, что хеши он собрался строить на иквале.
или может скорее обшланг пидросяна с туповицкой... Ибо вряд ли ученые мужы генерировали бы с пеной у рта такие смешные диалоги о двоичном дереве поиска без сравнения со сложностью О(n), притягивая в спор и Java и запорожцы ))
Либо ты не в теме, либо также туп как и da4ever.
Если ты можешь сделать реализацию поиска сущностей которые можно сравнивать только на равенство меньше чем O(N), милости просим.
Сначала один был не в теме - burdakovd , потом он понял о чём речь,
http://govnokod.ru/4169#comment45942 , и оказался вменяемым человеком.
Потом был некультурный da4ever, он либо слишком туп, либо слишком тролль. Но вот тут http://govnokod.ru/4169#comment46051 он чуть чуть начал въезжать в тему.
Но всё же продолжает говорить ерись типа:
"так ты бы так и написал, что сложность вычисления хеша для такой сущности зависит от количества сущностей в дереве, а не от сложности самой сущности."
Потом пришёл Lure Of Chaos и просто спустился до оскорблений.. очень похоже на школоту - ну не серьёзно
про сущности и сложность. что такое хороший хеш ты знаешь. логично предположить, что для строки его лоично вычислять проходя по символам. для объекта, инкапсулирующего строку и число - ид+итрер(строка)+итер(число).
тоесть чем больше данных тем больше вычислений нет?
"сравниваем сущности попарно (новую и те, что в дереве), и если нет совпадений - отдаем новый хеш из пула свободных. а потом - гоняем хеш по дереву. "
Итак, ты вроде бы понял как можно вычислить хеш сущности, у которой есть только проверка на равенство. Будем плясать от печки.
a. Какова сложность взятия такого хеша? O(N), пока всё понятно?
b. Рассмотрим следующую ситуацию:
1. Дерево хешей уже построено
2. Вызывается некоторая функция например удалить данный указатель(из дерева и освободить память на которую он указывал), которая получает аргументом указатель(НЕ ХЕШ).
3. Функция, зная указатель, для того чтобы сделать поиск по дереву хешей, должна взять хеш от этого указателя. Какова сложность этой операции? O(N). Возражения/вопросы?
4. Дальше зная хеш, делается поиск в дереве со сложностью O(log N)
5. Какова итоговая сложность работы этой функции?
ты прочитал мой комментарий! и ура, ты его даже понял.
сделай еще один шаг - прочитай следующий. http://govnokod.ru/4169#comment46053
"сущности" ввел в дискуссию ты. с самого начала речь шла о указаьтелях. тоесть мы можем взять хеш от адресуемого объекта. и никакого попарного сравнения. но из-за твоих сущностей 4169 распух от бесполезных комментариев.
осилил?
http://govnokod.ru/4169#comment46117
Теперь смотрим твою хронологию:
"2. быстрый поиск тоже осилили.
3. накладные расходы на вычисление хеша указателя окупаются за счет ускорения поиска"
говнецом попахивает
"ага. реализация за О(n) очевидна. твоя позиция построена на том, что она единственная?"
Ты тут про что говорил? Про указатели? или про то на что они указывают? Явно про указатели, про сущности у которых есть только сравнение.
дальше, видим процесс медленного "осиленния"
[i]"и, судя по всему - она действительно единственная (в заданных условиях)"[i]
Ну блин вот это действительно, наконец-то осилил.
А исходное говнецо, это
" ээ, ну если вести хэшировние, и операцию equals, как в Java сделано"..
Это чудило, думает что хеш строится только на equals.
Так что в итоге, ветку раздул ты. Ты не прочитал/недопёр обсуждение с burdakovd.
Мне пришлось по несколько раз тебе объяснять суть.
Но сударь, я не устал мазать вас говном, ведь это же govnokod.ru
про накладные расходы лур написал ниже.
прочитай еше раз:
"ээ, ну если вести хэшировние, и операцию equals, как в Java сделано"
отсюда можно предположить, что "чудило" думает, что иквалс строится только на хеше.
или предположить, что иквал и хеш вообще не связаны.
будь с честен перед собой. признай, что ты думаешь, что чудило думает, что хеши строятся только на иквале.
вот поэтому то тред и пошел.
Это не я его ввёл, это А.Степанов его ввёл.
Оно не ставит с ног наголову идею бинарного поиска - она запрещает его использование в этой ситуации. Требование бинарного поиска - упорядоченность, у нас её нет, почти такие же слова говорятся в ролике А.Степановым.. Так что я ввёл?
"что "чудило" думает, что иквалс строится только на хеше."
Мусье, у вас белая горячка.
"будь с честен перед собой. признай, что ты думаешь, что чудило думает, что хеши строятся только на иквале.."
спасибо кэп! сообщением ранние я это сказал явно
"Это чудило, думает что хеш строится только на equals."
У кого-то есть возражения/аргументы по этому поводу?
"вот поэтому то тред и пошел."
тред пошёл потому что
1. "согласен. действительно протупил. "
2. ты не прочитал предыдущие сообщения
прув про то, что чудило действительно так считает и хватит додумывать.
есть у нас упорядоченность. точнее мы можем ее легко ввести, хешируя адресуемые объекты. ты абстрагировался от указателей в сущности, поэтому все и завертелось.
указание места в видео, подтверждающего твою правоту, я так понимаю, тоже не будет.
толстый и зеленый уходит из этого поста?
Видимо, именно в этом смысл требования при переопредении одного из этих методов так же корректно переопределять другой
http://govnokod.ru/4169#comment45913
А что делает equals по умолчанию- лень искать, может и опирается на hashCode - это уже детали.
И не факт что сравнить сначала хэши, а потом побайтово будет быстрее, смотря что за хэши.
Вот например если сравниваем массивы, а хэш это размер массива, то да, быстрее..
надеюсь, это резюме уменьшит накал спора
Вычисление хешей, тоже должно входить в оценку сложности алгоритма поиска (я не говорю что в сообщение есть обратное утверждение, просто у некоторых может создаться впечатление..). Возражения есть?
Как искать по исходной сущности? кто хешь будет брать?
Конечно можно извратиться, например в менеджере памяти:
делать allocate, который возвращает и указатель, и хэш(типа handle получается), но это пахнет говном.
ассоциируем "хешь" КАЖДОЙ (в том числе исходной) сущности с ней самой и оперируем с такими парами: для всех операций оперируем хешем, при окончании возвращаем ассоциированную сущность.
> делать allocate, который возвращает и указатель, и хэш
неможко не понял, какой allocate: это к управлению памятью, что ли?
> но это пахнет говном.
ничуть. просто мы будем манипулировать не сущностями X = {x1,x2,x3,...,xN}, а X' = {(x1,h(x1)),(x2,h(x2)),(x3,h(x3)),...,(x N,h(xN))}, где h(x) - хэш сущности x
так, у нас есть библиотека которая реализует malloc, malloc возвращает указатель.
Допустим библиотека позволяет узнать размер выделенной памяти, по заданному указателю.
Внешняя программа, использующая библиотеку делает
p=malloc(10)
...
print get_size(p)
Как поиск в этом случае будет осуществляется?
Вот я и говорю, что если malloc ещё будет и хэш возвращать, то поиск будет быстрым, если нет то нет. Или как?
Возвращение хэша вместе с указателем, имхо редкостное говно
1. разберемся с malloc:
смысл выделения памяти в том, что в некоторую таблицу мы помещает следующую информацию:
а. адрес начала этого участка памяти (тот самый ваш указатель)
б. длина участка памяти (для простоты предположим, что это целый неделимый кусок)
в. идентификатор владельца (для предотвращения "потери навсегда" памяти, при умирании владельца)
при этом возвращается ВСЯ эта запись, а не только указатель, упомянутый в пункте а - именно только поэтому возможно позже спрашивать размер памяти.
З.Ы. и конечно же, здесь должна быть гарантия, что участки памяти в этой таблице не пересекаются, а записи из нее удаляются или явно, или при смерти владельца участка
2. поиск к выделению памяти имеет лишь косвенное отношение, а именно посредством конкретного алгоритма.
Поэтому последующее
> если malloc ещё будет и хэш возвращать, то поиск будет быстрым, если нет то нет
для меня не имеет смысла, пока не постараетесь очень понятно обьяснить
1. помимо malloc есть get_size
которая делает поиск таблице по заданному указателию, и возвращает значение длины участка памяти (1.б в вашем сообщении)
2. malloc возвращает только указатель
3. пользователь (внешняя программа) получает только указатель.
4. в какой-то момент времени пользователь захотел узнать, а какая длина участка памяти, связанной с этим указателем - p. и вызывает get_size(p)
Дальше что, какие действия делает get_size?
4. либо get_size обращается в таблицу, ища запись с этим указателем - поскольку из требования о непересечении участков мы имеем уникальные указатели, то находим лишь одну запись - из которой и берется размер этого участка
4. "ища запись с этим указателем" - поиск какой? O(N) ?
а теперь к исходному
http://govnokod.ru/4169#comment46133
:
"Вычисление хешей, тоже должно входить в оценку сложности алгоритма поиска (я не говорю что в сообщение есть обратное утверждение, просто у некоторых может создаться впечатление..). Возражения есть?"
в остальных случаях просто преобразуем сущности в сущности с хэшем и будем искать среди них
4. зависит от структуры таблицы.
это не то "вычисление" хеша. Не сам его подсчет(который выполняется при добавлении), а поиск хеша. А найти нужный хеш НАМНОГО быстрее, чем найти нужный элемент (что следует из операции сравнения), поэтому может быть не учтен
давай подробней, опиши действия get_size, которая получает указатель.
как она делает поиск, откуда берёт хэш?
"Не сам его подсчет(который выполняется при добавлении), а поиск хеша"
Какая сложность будет у этого поиска - поиск хэша по указателю? O(N)?
"А найти нужный хеш НАМНОГО быстрее, чем найти нужный элемент"
Дан указатель, давай, найди хэш. O(N) ?
сложность поиска зависит от структуры таблицы. Допустим, это бинарное дерево. тогда сложность будет O(log N)
если же мы добавляем записи последовательно, тогда O(N)
> найди хэш
вот же он! ))))) (на самом деле уже ответил)
1.мы внутри get_size
2. у наc есть указатель - p
3. у нас есть некая таблица, бинарное дерево.
Построить это бинарное дерево по указателям, напрямую не можем, так - нету less?
4. Оно построено по хэшу
5. Хэш от указателя берётся долго
6. malloc возвращает только указатель
как делать поиск по этому дереву имея p?
a. Взять опять долгий хэш O(N), и искать по хэшу
б. искать по всему дереву, от начала до конца по указателю
Ты знаешь третий, быстрый вариант?
2. malloc пишет указатель,длину и владельца в таблицу, все записи фикс. длины (8 байт на указатель, 8 на длину, 8 на хэндлер владельца) и поддерживает при этом таблицу в виде упорядоченного бинарного дерева, где значения в ветках являются указателями, (плюс другая полезная инфа, но по ней не сортируем)
3. malloc возвращает только указатель, у наc есть указатель
4. мы внутри get_size
как делать поиск по этому дереву имея указатель?
делаем обычный бинарный поиск со сложностью O(log N) - у нас же дерево указателей (плюс полезная инфа, упакованная в значения ветвей - длина и владелец, но формирование дерева таблицы только по указателям)
как нашли - радуемся, нашли запись - берем из нее длину
Чтобы сделать дерево для поиска со сложностью O(log N) поиска по заданному указателю, у указателей должно быть некоторое упорядочивание, типа less, у нас его нет,
как ты собрался строить это дерево?
указатели - это тоже числа (пусть и довольно большие, скажем 64бит), значит, по ним уже есть упорядочивание и построить по ним бинарное дерево - основная задача алгоритма: мы при каждом malloc строим дерево (СРАЗУ) заново, добавляя куда надо в дерево. Нам не надо валить в кучу, а потом строить дерево
всё что можно сделать с обьектами указатель, только сравнить на равенство.
Смысл в том, что указатель нельзя привести к int, но это пол беды, их вообще нельзя сравнивать, такая операция не определена (только равенство)
Если бы их можно было бы привести к int, то вообще бы не было проблем.. можно даже назвать это взятием хэша от указателя. но НЕЛЬЗЯ
Если бы можно было просто привести к int, то тут бы не показывали как брать O(N) хэш
идите-ка вы спать. я тоже, кстати, хочу.
Идея не самая плохая, можно даже постараться плюсы найти..
не долгий - зависит от сложности самого обьекта, но не от числа обьектов. вычисление N хешей пропорционально N
но для одного обьекта нам надо взять его хэш только один раз, не более того
2. про объекты на которые указывают указатели ничего не известно. - их нельзя использовать, нельзя брать их хеш и т.п.
"для одного обьекта нам надо взять его хэш только один раз"
это в случае если malloc возращает и хэш тоже.
Давай уже врубайся, по таким указателям всегда долгий поиск
2. как это неизвестно? если нам нельзя брать их хеш, то точно мы ничего не найдем
> malloc возращает и хэш тоже
malloc не вернет хэш никогда - он вернет указатель
вы путаетесь в своей же терминологии.
а если у вас система с такими свойствами, как у вас 1 и 2, то тогда точно, вы будете искать долго
"трудно искать черную кошку в темной комнате, особенно если ее там нет"
Всё что разрешает компилятор, это только сравнивать на равенство, всё, никаких int, и т.п.
На самом деле идея, не так плоха, но есть свои + и -
Time complexity
in big O notation
________Average__Worst case
Space___O(n)_____O(n)
Search__O(log n)__O(log n)
Insert___O(log n)__O(log n)
Delete__O(log n)__O(log n)
Я что-то пропустил?
Но если лесть в бутылку:
" у которых время (сложность тоже) поиска короче времени линейного поиска, время вставки длинее."
тут не ясно чего длиннее время вставки, тут можно прочитать как "время вставки длинее времени линейного поиска"
"In the C++ Standard Template Library, the containers std::set<Value> and std::map<Key,Value> are often based on red-black trees"
http://govnokod.ru/4169#comment45942 , То что он не воспитан и не выдержан, это тоже его проблемы.
В итоге, он измазал себя говном.
То что ты без основательно оскорбил меня
"или может скорее обшланг пидросяна с туповицкой..."
Это невоспитанность с твоей стороны - поведение школоты.
"Ибо вряд ли ученые мужы генерировали бы с пеной у рта такие смешные диалоги о двоичном дереве поиска без сравнения со сложностью О(n), притягивая в спор и Java и запорожцы ))"
Что конкретно тебя развеселило/не понравилось в действиях с моей стороны?
молчал бы уж.
Я стараюсь общаться нормально, но когда человек пытается вымазать грязью:
"засрали такую ветку! аж комент написать некуда, а все без толку."
"я правильно сформулировал задачу, которую ты не можешь решить?"
Я имею полное моральное право разговаривать с ним, как мне вздумается.
burdakovd например пытался именно разобраться, ты же пришёл сюда с другим настроем
смотрю, и продолжают засирать = )
"без толку" - очевидно что так.
"не можешь решить" - ну не можешь и не можешь. что расстраиваться то?
вот для того, чтобы разобраться, я в этот пост и написал. поэтому давай отложим говнометания и попробуем, как взрослые люди, прийти к консенсусу.
мне кажется, что ты сделал неправильный вывод из реплики одного из слушателей. и это единственная проблема тут. http://govnokod.ru/4169#comment46160
В видео тоже есть это ограничение, если ты его не уловил, это твои проблемы
тогда показывай где оно.
Не могу. Если разрешена только операция сравнения, то это означает неупорядоченное множество сущностей или их "отпечатков"(хеши и т.п.) и невозможность их упорядочить (построение двоичных, красно-черных деревьев и др. означает упорядочивание их еще ДО поиска - за счет чего получаем сложность меньше, чем O(N)) - следовательно, в процессе поиска мы не будем получать информацию о более точном положении искомой сущности - что означает сложность O(N) и не менее (может повезти найти сразу же или же в последнюю очередь)
"что означает сложность O(N) и не менее (может повезти найти сразу же или же в последнюю очередь)"
Дополнение: когда используется асимптотическая сложность можно не писать то что в скобках. Важна именно оценка роста времени выполнения, с ростом объёма данных.
Можно ещё с другой стороны к этому подойти(те же яйца): функция сравнения даёт нам возможность разделения множества на две части - разделяй и властвуй.
Сравнение на равенство, не даёт нам возможности разделения - каков бы не был порядок элементов во множестве, сравнение заданного элемента с любым элементом множества не даёт нам никакой информации для дискриминации текущего элемента относительно любой части множества
или даже три: "меньше", "больше" или равно (не "меньше" и не "больше")
> Сравнение на равенство, не даёт нам возможности разделения
если быть занудным, то все же информация есть: о том, что испытанные элементы уже не являются искомыми. То есть, множество можно разделить на две части: проверенные и еще нет.
Ну "меньше"/"больше" достаточно для быстро поиска.
Можно сделать хоть 100 состояний сравнения, это просто увеличит основание логарифма, что в свою очередь увеличит скорость поиска и т.п. но суть ведь не в этом.
"если быть занудным, то все же информация есть: о том, что испытанные элементы уже не являются искомыми. То есть, множество можно разделить на две части: проверенные и еще нет."
Есть множество элементов, есть заданный, делаем одно сравнение. И что? да конечно, искомое множество делается на два, только не "проверенные"/"не проверенные", а "не равные" и "не проверенные" (это если элементы не повторяются в множестве)
нет, недостаточно, иначе, если операция сравнения запрещена вообще, мы вообще никогда не закончим поиск, а будем метаться среди "похожих" элементов. Впрочем, этот недостаток можно восполнить, если вспомним, что "равно" - это не "меньше" и не "больше"
> только не "проверенные"/"не проверенные", а "не равные" и "не проверенные"
да, хорошее уточнение
Да, согласен, без такого уточнения либо без "равно", поиска нельзя сделать.
Но имхо, это уточнение вводится автоматом когда вводятся операция, например "меньше", разве не так?
а. для "несравниваемого" множества достаточно определить операцию "равно" - при этом, мы можем о двух элементах сказать, они равны или не равны, но ничего не можем сказать, "меньше" один другого или "больше". При этом критерии могут быть различны, но обязательно обьект должен быть равен самому себе. При этом некоторые операции для несравниваемого множества мы можем определить - хотя бы тот же линейный поиск.
б. введя всего лишь операцию, например, "меньше", мы сможем лишь проверить, один элемент меньше другого, или же он больше или равен - что явно недостаточно для проведения операций - не удастся даже описать алгоритм линейного поиска. необходимо еще ввести и операцию "больше", только тогда мы получаем определение \"равно" - это не "меньше" и не "больше"\
Конечно не самый веский аргумент, но в std::set достаточно операции типа "меньше"
http://www.cplusplus.com/reference/stl/set/
"Compare: Comparison class: A class that takes two arguments of the same type as the container elements and returns a bool. The expression comp(a,b), where comp is an object of this comparison class and a and b are elements of the container, shall return true if a is to be placed at an earlier position than b in a strict weak ordering operation."
кусок из реализации stl
а для ОПРЕДЕЛЕНИЯ, математического определения, упорядоченного множества одной лишь операции "меньше" недостаточно: поскольку тогда "не меньше" мы получаем "нестрогое больше" - "больше либо равно".
согласитесь, из этих двух операций не получим операцию "равно":
"равно" не значит не "меньше" и не "нестрого больше"
"одной лишь операции "меньше" недостаточно: поскольку тогда "не меньше" мы получаем "нестрогое больше" - "больше либо равно"."
то что этим мы введя только "меньше", можем использовать её как "не больше", это не значит что необходимо отдельно определять "не больше" отдельным независимым образом, мы можем вообще её никак не называть. Также, если введя "меньше", мы получаем сразу "равно" - это не значит что его надо определять, мы можем использовать его как определённую функцию которая использует "меньше".
Представьте какое-нибудь дискретное множество, пусть из десяти элементов. на котором есть операция "меньше". Можно ли найти определённый элемент только используя меньше? конечно это только интуитивно.
Опять же, надо найти чёткие определение, иначе бессмысленно.
а где здесь "равно"?
if not a<b and
not b<a
?
"Условимся с самого начала, что равные числа мы будем рассматривать, как одно и тоже число в разных формах.
Иными словами, для нас понятие «равно» (=) означает «тождественно». Поэтому мы не перечисляем свойств равных чисел.
Упорядочение рациональных чисел достигается с помощью понятия больше (>) с которым связана первая группа свойств:
1. для каждой пары чисел а и Ь имеет место одно, и только
одно, из соотношений
а=Ь, а>Ь, Ь>а;"
дошло... поздно, но дошло
так же не надо путать подобие и эквивалентность.
например, для одного типа карт операция equals реализована, как Object.equals, а для другого (забыл, какой там конкретный класс есть) она определена как ==
По поводу оскорблений, если ты не увидел оскорблений, то наверное для тебя является нормой, когда тебя называют "пидросяном" либо "туповицкой"
но вообще яндексу респект за такие сейшены. Все таки они очень хорошая компания
Я не знаю был ли свободный вход на эту лекцию, и работает ли Java+Equals чудило в этой кампании.
Но если работает, как вы думаете, должна ли поисковая кампания брать на работу программистов, которые не знают как работает хеширование, деревья поиска, в общем то что должен знать каждый нормальный программист, а программист работающий в поисковой кампании в особенности?
А "программист" слишком широкое понятие. Кто-то должен. Кто-то -- нет. 1Cнику не обязательно. PHPшнику -- тоже.
А в Яндексе очень много работы, и не вся она связана с поисковыми системами. Но обычно там достойный уровень технарей на всех уровнях.
Да! Я не работаю в Яндексе, если что)
Но опять же моё имхо - даже если программист это не использует, ему нужно это знать, просто для общего развития.. на любую работу лучше брать сразу нормальных программистов, а то потом будет тратится время хороших программистов, на исправление багов дешёвых программистов.
особенно, когда у нас есть новая компания "доктор Зло": Гугел
И нахера хеши, красно-чёрные деревья...
Ограничения на невозможность сравнения я не пойму и не приму, ибо всё есть цепочки байтов.
уж лучше брать хэш и структурировать при создании обьекта, чем делать это каждый раз при поиске, а потом хоть заищись.
впрочем, выбор вида структуры (неупорядоченный список, дерево, куча...) зависит от того, что чаще нужно делать: добавлять\удалять элементы или их искать
уважаемый TarasB, перестаньте пытаться показать, что вы один умнее орды ученых-математиков - тогда вы перестанете оставаться в дураках и минусовать вас не будут )
- сдавайтесь, нас орда!
- а нас рать!!!
И нахера хеши, красно-чёрные деревья...
Если у тебя ключом выступает User, то что ты будешь делать? сравнивать его со всеми элементами в коллекции прямым перебором?
а хеши можно в дерево положить.
Это не говоря уже о том, что метод equals может занимать год. Равно как и получение хеша.
Но если ты один раз заполнил коллекцию объектами, то потом ты просто ищещь в ней по хешам, а сравнивать их куда быстрее, чем объекты.
Любой объект = любая цепочка байтов.
> Если у тебя ключом выступает User, то что ты будешь делать? сравнивать его со всеми элементами в коллекции прямым перебором?
Ты читать не умеешь? Пройду по префиксному дереву от вершины.
> Но если ты один раз заполнил коллекцию объектами, то потом ты просто ищещь в ней по хешам, а сравнивать их куда быстрее, чем объекты.
Вот есть в коллекции поле 'дохренабукв-a', а ты берёшь ключ 'дохренабукв-b' (а его в коллекции нет), и хеш тебя вывел на 'дохренабукв-a', давай, посимвольно проверяй, что это тот ключ, который тебе нужен.
Кто тебе даст гарантию, что если хеш совпал, то и ключ совпал? Если коллекция имеет заранее заготовленный тип с заранее заготовленным набором полей, то используй просто структуры.
И как ты ее получишь? Ты пойдешь по указателю в память, считаешь что там лежит, найдешь в этом другие указатели, пойдешь по ним, и так будешь гулять?)
Хеш это и есть некая цепочка байтов (определенной длины).
>>Ты читать не умеешь? Пройду по префиксному дереву от вершины.
В свете предыдщего абзаца твой ответ теряет смысл.
>>и хеш тебя вывел на 'дохренабукв-a', давай, посимвольно проверяй, что это тот ключ, который тебе нужен.
Именно. Только проверить тебе надо будет не 100500 объхектов, а всего 2-3.
При хорошем хеше конечно. Если у тебя хеш -- константа -- то ты сам себе виноват.
>>Кто тебе даст гарантию, что если хеш совпал, то и ключ совпал
Никто. Но если хеш не совпал -- ключ ТОЧНО не совпадет.
Почитай как хеш работает в java и .net например.
http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx
у произвольных указателей можно оценить равенство адресов и более ничего.
Если не переопределить хеш и иквэлс, то a = b только если это указатели на один и тот же объект.
Мне вот интересно как ТарасБ собрался это делать без этих функций
Короче, лестницу сделать можно, но копать очень много придется.
1. указатели нельзя сравнивать.
мля, если можно посмотреть число(номер ячейки), значит их можно сравнивать.. ИХ НЕЛЬЗЯ СРАВНИВАТЬ (ВЕДЬ НЕ БЫЛО НИ ЕДИНОГО РАЗРЫВА!!!!)
2. про объекты на которые указывают указатели ничего не известно. - их нельзя использовать, нельзя брать их хеш и т.п.
Не было ни единого разрыва, с ноября прошлого года, до 26 апреля сего года!
все поняли, млять? )))))))))))))
http://govnokod.ru/4169#comment46209
http://govnokod.ru/4169#comment46211
Что за разрыв?
Название статьи скажите
только тут это не "ИХ НЕЛЬЗЯ СРАВНИВАТЬ", а "Я ВОЗЬМУ ХЕШ, ПРИВЕДУ К INT", хотя в договоре сказано - разрыв раз в сутки(на видео - нельзя сравнивать)
почему ваня решил, что адресуемые объекты сравнивать нельзя - не понятно. ссылки на себя дает, а пруфов из видео доставить не может.
http://govnokod.ru/4169#comment46191
http://govnokod.ru/4169#comment46187