Facebook

[Sergunka]

Кстати, даже в джавовской реализации O(n) - это worst case. Вот кому-то не лень было объяснять, почему:

Hash tables are O(1) average and amortized case complexity, however is suffers from O(n) worst case time complexity. [And I think this is where your confusion is]

Hash tables suffer from O(n) worst time complexity due to two reasons:

If too many elements were hashed into the same key: looking inside this key may take O(n) time.

Это обычно происходит если в mutable классе не переписать хешкод и использвать один и тот же элемент этого класса для ключа. На каждое добавление в хеш будет возникать колизия которая в жабе разрешается связанным списком для бакета содержащим елементы ключ, значение. Т.е практически хеш выродится до одного связанного списка тогда правда и get будет давать O(n)

Once a hash table has passed its load balance - it has to rehash [create a new bigger table, and re-insert each element to the table].
However, it is said to be O(1) average and amortized case because:

It is very rare that many items will be hashed to the same key [if you chose a good hash function and you don't have too big load balance.
The rehash operation, which is O(n), can at most happen after n/2 ops, which are all assumed O(1): Thus when you sum the average time per op, you get : (n*O(1) + O(n)) / n) = O(1)

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

[АццкоМото]

Это обычно происходит если в mutable классе не переписать хешкод и использвать один и тот же элемент этого класса для ключа. На каждое добавление в хеш будет возникать колизия которая в жабе разрешается связанным списком для бакета содержащим елементы ключ, значение. Т.е практически хеш выродится до одного связанного списка тогда правда и get будет давать O(n)

Ну, строго говоря, если хэшей фиксированное количество, то все равно будет O(n) - не могу не согласиться с wassup: совсем не требуется вырожденного случая
Другой вопрос, кто нас заставляет ограничивать пространство хэшей

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

Да, но пересечение множеств ключей нам таки надо найти, оно не заготовлено заранее (иначе задача вообще вырождается). Если в нашей реализации стоимость лукапа или инсерта О(н) (или просто хкже константы), то мы таки имеем проблему
Но и избежать ее у нас есть все возможности. Удивляюсь, почему это не всем очевидно

[Интеррапт]

Это обычно происходит если в mutable классе не переписать хешкод и использвать один и тот же элемент этого класса для ключа.

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

[crypto5]

Вы вроде несколько раз ссылались на HashMap здесь

Ну, строго говоря - да. Но тут все как-то так нестрого обсуждается, что переночевать негде. Map и Set используются практически взаимозаменяемо, N - то одна величина, то другая, и так далее.
(А главное, я вообще не понимаю, что тут обсуждать. Вариантов не так много, они все тривиальны, со своими очевидными плюсами и минусами)

С таким предположением да:

which are all assumed O(1)

но оно высосано из пальца

Да нет, вполне нормальное утверждение. Если по мере роста таблицы делается resize/rehash, то как раз так и должно быть, как сказано. Т.е. я допускаю, что в джавовской реализации могут быть существенные нюансы, но в общем случае, если мы хотим добиться O(1) on average, то нам не нужен rocket science. Вот если бы нам возжелалось константного worst case, то, пожалуй, был бы облом

Там проблема что они делают вывод о амортизированном О(кототое подразумевает worst case) на основе average оценки, что как бы неправильно.

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

[АццкоМото]

Там проблема что они делают вывод о амортизированном О(кототое подразумевает worst case) на основе average оценки, что как бы неправильно.

Да вроде речь идет об average
Вообще, понятие "амортизированного О" мне представляется довольно туманным. Понятно, о чем, но не понятно, как в точности.

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

Не, это оспаривается легко. Для N=10 можно тупо перечислить все возможные варианты и посчитать среднее. Потом - для чуть меньших и чуть больших размеров. Основываясь на этом не так сложно экстраполировать на общий случай. А человек с хорошим математическим складом ума сразу докажет в общем случае.
Ну и для протокола. Я понял, что вы имели в виду. Но классически сложность сортировки считается по количеству сравнений, а не перестановок. Т.е. O(n*n) будет даже для изначально отсортированного массива, что даже доказывать не надо.

[crypto5]

Там проблема что они делают вывод о амортизированном О(кототое подразумевает worst case) на основе average оценки, что как бы неправильно.

Да вроде речь идет об average

Да нет, в вашей цитате утверждается константность обоих.

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

Не, это оспаривается легко. Для N=10 можно тупо перечислить все возможные варианты и посчитать среднее. Потом - для чуть меньших и чуть больших размеров. Основываясь на этом не так сложно экстраполировать на общий случай. А человек с хорошим математическим складом ума сразу докажет в общем случае.

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

Ну и для протокола. Я понял, что вы имели в виду. Но классически сложность сортировки считается по количеству сравнений, а не перестановок. Т.е. O(n*n) будет даже для изначально отсортированного массива, что даже доказывать не надо.

Да нет, википедия дает линейную сложность в лучшем случае(на счет константной я действительно ошибся): http://en.wikipedia.org/wiki/Bubble_sort

[АццкоМото]

Да нет, в вашей цитате утверждается константность обоих.

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

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

Да ну! Это считается абсолютно формально, без всяких спекуляций. с учетом того, что ниже.
Насчет примера, были то ли MIT-шные, то ли Стэнфордские онлайн курсы по алгоритмике, они давали очень простые примеры строгого математического доказательства лучшего, среднего и худшего случая. В деталях не помню, но это было очень просто

Да нет, википедия дает линейную сложность в лучшем случае(на счет константной я действительно ошибся): http://en.wikipedia.org/wiki/Bubble_sort

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

[Sergunka]

Это обычно происходит если в mutable классе не переписать хешкод и использвать один и тот же элемент этого класса для ключа.

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

Не будем придираться к фразам, просто это случай когда хеш вырождается в Java до LinkedList. Я просто другой вариант придумать пока не смог

[Boriskin]

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

[АццкоМото]

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

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

[wassup]

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

Bingo! И это правильный ответ на поставленную задачу.

[Boriskin]

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

Однако слава ММФ НГУ советского разлива!

[Boriskin]

Тем более, что при некоторых допущениях можно сделать быстрее

Например?

[Boriskin]

Раз уж решили задачками делиться, то вот вам с гугля задача:
Имеется колода 52 карты (от двойки до туза, 4 масти), случайно выбирается 5 карт, они выкладываются на столе. Заходит человек, смотрит на все 5 карт, забирает одну, выкладывает 4 оставшиеся в ряд определенным образом, уходит. Заходит второй человек, смотрит на выложенные 4 карты и называет ту карту, которую унес первый. Возможно ли такое и если да, то как?

[Flash-04]

конечно, если второй перед тем как зайти спросил у первого какую карту тот вынес

[Boriskin]

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

[crypto5]

Тем более, что при некоторых допущениях можно сделать быстрее

Например?

Ну написали же уже все, если хештаблицы предпосчитаны, то все отрабатывает за O(min(N,M)) вместо O(N+M)

[АццкоМото]

Тем более, что при некоторых допущениях можно сделать быстрее

Например?

Например, если мы заранее знаем порядок N
или если 2 вектора существенно различаются по количеству ненулевых элементов

UPD. Сорри, crypto5 уже ответил и более внятно

[АццкоМото]

Раз уж решили задачками делиться, то вот вам с гугля задача:
Имеется колода 52 карты (от двойки до туза, 4 масти), случайно выбирается 5 карт, они выкладываются на столе. Заходит человек, смотрит на все 5 карт, забирает одну, выкладывает 4 оставшиеся в ряд определенным образом, уходит. Заходит второй человек, смотрит на выложенные 4 карты и называет ту карту, которую унес первый. Возможно ли такое и если да, то как?

А второй, как я понимаю, знает, по какому принципу первый перетасовывал 4 оставшихся карты, так? И по какому принципу он выбирал, какую унести - тоже?
Без второго предположения получается только до 24 карт в колоде, а как оно может помочь - пока не понял

[АццкоМото]

Bingo! И это правильный ответ на поставленную задачу.

А вы знаете, что это "правильный ответ", да? Т.е. вот правильный и все тут, а остальные все туфта, так?

[Flash-04]

Без второго предположения получается только до 24 карт в колоде, а как оно может помочь - пока не понял

ага, наверняка из тех идиотских задач "на смекалку".

[Boriskin]

Ясн, мерси.

[АццкоМото]

Без второго предположения получается только до 24 карт в колоде, а как оно может помочь - пока не понял

ага, наверняка из тех идиотских задач "на смекалку".

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

[Boriskin]

А второй, как я понимаю, знает, по какому принципу первый перетасовывал 4 оставшихся карты, так? И по какому принципу он выбирал, какую унести - тоже?

Да. Грубо говоря, надо попытаться придумать способ, как из 5ти произвольных карт выбрать одну так, чтобы оставшимися 4мя ее можно было однозначно закодировать.

[АццкоМото]

UPD. До 28, конечно, решается легко, а не до 24
Но как дальше - ХЗ пока