Мат. ожидание от qsort [re: 9 задачек на прогр]
Ну и что, как выбор случайного элемента поможет сделать сортировку упорядоченного массива быстрее?
в таком случае матожидание времени работы O(nlogn)
Умные люди пишут, что если знать rand seed, то можно построить и плохую последовательность.
Умные люди пишут, что если знать rand seed, то можно построить и плохую последовательность.
в таком случае матожидание времени работы O(nlogn)матожидание в любом случае n log n, лол.
ты на каком пространстве событий матожидание считаешь?
На перестановках наверное, других корректных ввести не получится.
Как это не получится? А если по выдаче генератора случайных чисел построить?
Мне казалось, что верное утверждение следующее: для данного массива (перестановки?) в случае рандомизированного выбора разбивающего элемента матожидание времени работы будет O(n log n).
Так вот, в случае нерандомизированного выбора (последний элемент - разбивающий) и упорядоченного массива это матожидание будет O(n^2)
Так вот, в случае нерандомизированного выбора (последний элемент - разбивающий) и упорядоченного массива это матожидание будет O(n^2)
Так вот, в случае нерандомизированного выбора (последний элемент - разбивающий) и упорядоченного массива это матожидание будет O(n^2)Нет. Если массив упорядоченный, то причем тут матожидание?
Сорри, думал, что отвечаю
Какой еще генератор? Перечитай вопрос, там о вер. пространстве спрашивали.
Нет, ну вот ты же должен понимать следующую вещь: если колоду карт размешать случайным образом, то вероятность достать туза не изменится от того, буду я доставать всегда первую карту или буду доставать случайную.
Верное утверждение следующее: есть перестановка чисел 1..n. Обозначим ее P. Пусть T(P) — число сравнений, если qsort запустить на этой перестановке. Пусть все перестановки равновероятны, тогда![[math]$$\mathbb{E}_P T(P) = n \log_2 n$$[/math]](mathimg.php?math=%24%24%5Cmathbb%7BE%7D_P%20T%28P%29%20%3D%20n%20%5Clog_2%20n%24%24)
, без O.
Верное утверждение следующее: есть перестановка чисел 1..n. Обозначим ее P. Пусть T(P) — число сравнений, если qsort запустить на этой перестановке. Пусть все перестановки равновероятны, тогда
Хотя я наврал, O там все-таки нужен. Но где-то читал, что константа там небольшая. Т.е. не 3
Пусть есть упорядоченный массив длины n и идеальный генератор случайных чисел, выдающий числа, например, от 1 до n.
Пусть qsort выбирает на i-ом вызове j%len-ый элемент массива для сравнений, где j - i-ое число, выданное ГСЧ. Назовём множеством исходов M - множество всех таких подпоследовательностей, выдаваемых ГСЧ, на которых такой qsort завершается.
Выше утверждалось, что матожидание T(M) = n log n
Пусть qsort выбирает на i-ом вызове j%len-ый элемент массива для сравнений, где j - i-ое число, выданное ГСЧ. Назовём множеством исходов M - множество всех таких подпоследовательностей, выдаваемых ГСЧ, на которых такой qsort завершается.
Выше утверждалось, что матожидание T(M) = n log n
> есть модификации, когда в качестве разграничивающегося
> элемента берётся элемент из середины, или случайный элемент,
> или даже медианный (который в свою очередь находится
> хитрожопым способом где-нибудь за O(n
Ну и как они изменяют асимтотику? Ты в любом случае можешь
словить массив, когда будет n^2.
>>> Предложите наиболее быстрый алгоритм сортировки массива,
>>> элементами которого являются числа от одного до ста.
>> В таких случаях сортируют подсчётом.
> Зависит от размера массива.
> Для коротких
"Коротких" это сколько? У тебя длина массива ограничена снизу числом "100."
> выгоднее запросто может оказаться отлаженная и оптимизированная
> библиотечная функция, или там написанная от руки наспех
> сортировка вставками.
Да, сортировка вставками будет быстрее подсчёта в один проход.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
> элемента берётся элемент из середины, или случайный элемент,
> или даже медианный (который в свою очередь находится
> хитрожопым способом где-нибудь за O(n
Ну и как они изменяют асимтотику? Ты в любом случае можешь
словить массив, когда будет n^2.
>>> Предложите наиболее быстрый алгоритм сортировки массива,
>>> элементами которого являются числа от одного до ста.
>> В таких случаях сортируют подсчётом.
> Зависит от размера массива.
> Для коротких
"Коротких" это сколько? У тебя длина массива ограничена снизу числом "100."
> выгоднее запросто может оказаться отлаженная и оптимизированная
> библиотечная функция, или там написанная от руки наспех
> сортировка вставками.
Да, сортировка вставками будет быстрее подсчёта в один проход.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
Блин, лост, тебе в самую пору основать собственную науку, которая изучает методы сортировки уже упорядоченных массивов.
Блин, лост, тебе в самую пору основать собственную науку, которая изучает методы сортировки уже упорядоченных массивов.Блин, , перечитай тред и заметь, что я никаких заявлений не делал, а только постарался тебе формально объяснить о чём говорят влад и .
Upd. перечитал твой пост внимательнее, заметил что ты говорил о перестановках.
Речь просто шла о упорядоченном массиве (ему соответствует ровно одна перестановка) и о том, что если используется рандомизированный qsort, то эта перестановка не является решением задачи "найти вход, на котором библиотечный qsort работает дольше всего", т.к. матожидание сравнений в qsort с идеальным ГСЧ на любой перестановке O(n log n).
Ок, я действительно понял о чем они говорят, спасибо тебе.
Теперь их очередь, им надо понять что говорим им мы с КОНТР'ой.
Займись, плз.
Теперь их очередь, им надо понять что говорим им мы с КОНТР'ой.
Займись, плз.
да, похоже ты прав.
А хотя я че-то реально туплю.
КОНТРА, ты реальне гонишь, короче не факт, что стандартный qsort на упорядоченных работает медленней всех. Вот.
КОНТРА, ты реальне гонишь, короче не факт, что стандартный qsort на упорядоченных работает медленней всех. Вот.
Нет, это ты прав! Читай вот этот ^^^ пост
Ну в смысле, может быть ты и ошибся, но я понял о чем тут говорят
Ну в смысле, может быть ты и ошибся, но я понял о чем тут говорят
Ты прав вот в посте и неправ вот в
я был неправ в том, как делается анализ qsorta - теперь благодаря тебе освежил память )
я был неправ в том, как делается анализ qsorta - теперь благодаря тебе освежил память )
> не факт, что стандартный qsort на упорядоченных работает медленней всех.
Факт. Ты исходники читай, это, говорят, просветляет.
На одном только пузырьке кучу сравнений и перестановок словишь.
---
"Narrowness of experience leads to narrowness of imagination."
Факт. Ты исходники читай, это, говорят, просветляет.
На одном только пузырьке кучу сравнений и перестановок словишь.
---
"Narrowness of experience leads to narrowness of imagination."
ну да, так и есть, затупил.
Факт. Ты исходники читай, это, говорят, просветляет.Какие исходники? Библиотеку C можно по-разному реализовывать.
На одном только пузырьке кучу сравнений и перестановок словишь.
У Microsoft сделано так:
короткие куски (8 и меньше элементов) отрезаются и сортируются
> Какие исходники? Библиотеку C можно по-разному реализовывать.
> У Microsoft сделано так: короткие куски отрезаются и
> сортируются пузырьком, в качестве разделяющего элемента
> выбирается средний.
И что? Расскажи про пузырьки и про то, как они влияют на qsort.
---
"Narrowness of experience leads to narrowness of imagination."
SEE ALSO
sort(1 radixsort(3)
Hoare, C.A.R., "Quicksort", The Computer Journal, 5:1, pp. 10-15, 1962.
Williams, J.W.J, "Heapsort", Communications of the ACM, 7:1, pp. 347-348,
1964.
Knuth, D.E., "Sorting and Searching", The Art of Computer Programming,
Vol. 3, pp. 114-123, 145-149, 1968.
McIlroy, P.M., "Optimistic Sorting and Information Theoretic Complexity",
Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1992.
Bentley, J.L. and McIlroy, M.D., "Engineering a Sort Function",
Software--Practice and Experience, Vol. 23(11 pp. 1249-1265,
November 1993.
STANDARDS
The qsort function conforms to ISO/IEC 9899:1990 (``ISO C90'').
> У Microsoft сделано так: короткие куски отрезаются и
> сортируются пузырьком, в качестве разделяющего элемента
> выбирается средний.
И что? Расскажи про пузырьки и про то, как они влияют на qsort.
---
"Narrowness of experience leads to narrowness of imagination."
Да, рандомизованный qsort не имеет постоянного наихудшего случая.
И что? Расскажи про пузырьки и про то, как они влияют на qsort.Про пузырьки рассказал. На коротких массивах они быстрее qsort, еще что-то хочешь? Так ты спрашивай, отвечу.
К чему ссылки на эти книги? Ты хочешь сказать, что в любой реализации библиотеки C qsort реализован именно так?
> На коротких массивах они быстрее qsort
Ты не сказал, за счёт чего они быстрее?
> К чему ссылки на эти книги?
К стандарту. Стандарта у меня нет, но есть подозрение, что
алгоритм там оговорен. Иначе бы и функция по-другому звалась.
---
"Это глупость вообще, но мне это знакомая песня."
Ты не сказал, за счёт чего они быстрее?
> К чему ссылки на эти книги?
К стандарту. Стандарта у меня нет, но есть подозрение, что
алгоритм там оговорен. Иначе бы и функция по-другому звалась.
---
"Это глупость вообще, но мне это знакомая песня."
Ты не сказал, за счёт чего они быстрее?qsort юзает дополнительную помять (стек ему необходим соответственно, действия с ней тоже учитываются. Если думать о теоретическом преимуществе (количество сравнений то вроде ничего особенного. Возрастает вероятность схватить n^2, но несущественно.
Стандарта у меня нет, но есть подозрение, чтоНу вот у меня нету таких подозрений, поэтому я их и не постулировал. Если у тебя есть — то ссылки на пункты стандарта, пожалуйста, а не на секцию See Also мана
алгоритм там оговорен.
> Возрастает вероятность схватить n^2, но несущественно.
"Возрастает." Вопрос ведь в том, где этот квадрат достигается.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
"Возрастает." Вопрос ведь в том, где этот квадрат достигается.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
Ну я же и говорю, несущественно. Что существенно — я написал.
Ладно, дальше мне лень, мне ещё надо придумать, как научить
студентку BSD устанавливать и мир создавать. Поэтому вкратце.
Я хочу понять, из каких соображений на обратно упорядоченном
массиве алгоритм Хоара, который n^2, у которого куски короче
семи (хоть ста) элементов упорядочиваются иначе, не суть важно,
пузырьком ли, вставками ли (да хоть bogosort, оно всё равно в
тех условиях O(1 равно как и сам АХ перестанет быть
наихудшим случаем.
Тебя может спасти только то, что алгоритм qsort окажется другим,
не хоаровским, но вот тут-то и вопрос: где не так (если брать
распространённые системы общего назначения, хакнуть libc мы оба
можем)? У меня нет доступа к glibc и соляре, про винду ты сам
говоришь, что там Хоар (или нет? и мне откровенно лень их
доставать, чтобы узнать несущественную деталь.
---
"Лень --- движитель прогресса."
студентку BSD устанавливать и мир создавать. Поэтому вкратце.
Я хочу понять, из каких соображений на обратно упорядоченном
массиве алгоритм Хоара, который n^2, у которого куски короче
семи (хоть ста) элементов упорядочиваются иначе, не суть важно,
пузырьком ли, вставками ли (да хоть bogosort, оно всё равно в
тех условиях O(1 равно как и сам АХ перестанет быть
наихудшим случаем.
Тебя может спасти только то, что алгоритм qsort окажется другим,
не хоаровским, но вот тут-то и вопрос: где не так (если брать
распространённые системы общего назначения, хакнуть libc мы оба
можем)? У меня нет доступа к glibc и соляре, про винду ты сам
говоришь, что там Хоар (или нет? и мне откровенно лень их
доставать, чтобы узнать несущественную деталь.
---
"Лень --- движитель прогресса."
Я же тебе написал, что если говорить о нерандомизованном qsort'е, то ты прав, а так же то, что тебе лишь предложили "расширить сознание".
Если брать модификацию со случайными числами, то всё зависит от
модификации, но как это отменяет похожий наихудший случай?
Или ты своей лёгкой рукой плавно превращаешь алгоритм Хоара в
какой-нибудь кучевой или помесь с кучевым?
В общем, про модификации сказано неубедительно.
Про то, как это в стандарте, я узнаю, но это не сейчас.
Допускаю, что может быть так, что в qsort разрешено использовать
кучевой метод, когда с наихудшим случаем ничего не ясно (я не
встречал построения, статья с анализом передо мной). Но тогда
исходный вопрос теряет смысл.
---
"Лень --- движитель прогресса."
модификации, но как это отменяет похожий наихудший случай?
Или ты своей лёгкой рукой плавно превращаешь алгоритм Хоара в
какой-нибудь кучевой или помесь с кучевым?
В общем, про модификации сказано неубедительно.
Про то, как это в стандарте, я узнаю, но это не сейчас.
Допускаю, что может быть так, что в qsort разрешено использовать
кучевой метод, когда с наихудшим случаем ничего не ясно (я не
встречал построения, статья с анализом передо мной). Но тогда
исходный вопрос теряет смысл.
---
"Лень --- движитель прогресса."
Изначальный вопрос — какой массив будет давать наихудший результат. Ты сказал, что упорядоченный, это и обсуждается. Меня временно понесло не в ту сторону.
Короче, вот ехал я сейчас с работы и понял. Для qsort из библиотеки C by Microsoft упорядоченный массив — не есть наихудший случай.
Никто и не утверждает, что худший случай — n log n сравнений. Утверждается лишь, что ты, сказав, что наихудший — упорядоченный, был неправ.
Короче, вот ехал я сейчас с работы и понял. Для qsort из библиотеки C by Microsoft упорядоченный массив — не есть наихудший случай.
Никто и не утверждает, что худший случай — n log n сравнений. Утверждается лишь, что ты, сказав, что наихудший — упорядоченный, был неправ.
Ну и как они изменяют асимтотику? Ты в любом случае можешьсловить массив, когда будет n^2.Квиксорт с вычислением медиан имеет nlogn worst case. Хотя О там несколько больше.
Для массива длины сто вероятность словить что-нибудь существенно хуже n*log(n) (не помню точно константу, что-то вроде 1/log(4/3 меньше вероятности аппаратного сбоя.
Все виденные мной реализации qsort берут в качестве пивота медиану первого, среднего и последнего элемента. Можешь попытаться построить руками худший случай, кстати. Даже если просто брать средний элемент, построение худшего случая нетривиально (нет, это не реверснутый массив).
Более того, рискну предположить, что вообще все реализации в конце концов используют средний элемент в качестве пивота (меняя его местами с первым/последним если нужно) просто в силу особенностей алгоритма. Не следует забывать, что однострочная реализация кусорта, которую любят приводить в пример хаскелисты, кусортом строго говоря не является, так как настоящий кусорт содержит ещё одну крайне важную алгоритмическую фишку, а именно линейный проход по массиву с двух сторон и своп нужных элементов, именно за счёт которой он оказывается дружелюбен к кэшу и дико быстр на практике. Чтобы это работало, пивот должен быть в центре.
> Утверждается лишь, что ты, сказав, что наихудший — упорядоченный, был неправ.
http://google.com/search?q=quick+sort+worst+case
http://mathworld.wolfram.com/Quicksort.html
Мои тараканы круче твоих, и они --- не ошибаются.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
http://google.com/search?q=quick+sort+worst+case
http://mathworld.wolfram.com/Quicksort.html
Мои тараканы круче твоих, и они --- не ошибаются.
---
"Vyroba umelych lidi, slecno, je tovarni tajemstvi."
Мои тараканы круче твоих, и они --- не ошибаются.Они ошиблись в этот раз. В реализации qsort by Microsoft, где в качестве разделяющего берется средний, что я выше и писал, (еще читай, что написал Fj) упорядоченный — не худший.
> Квиксорт с вычислением медиан имеет nlogn worst case.
Ладно, убедил.
> Даже если просто брать средний элемент, построение худшего
> случая нетривиально
Хм. То есть преподаватели даже тут обманывают наивных студентов.
---
"Будь особенно бдителен, когда всё хорошо и нет поводов для тревоги."
Ладно, убедил.
> Даже если просто брать средний элемент, построение худшего
> случая нетривиально
Хм. То есть преподаватели даже тут обманывают наивных студентов.
---
"Будь особенно бдителен, когда всё хорошо и нет поводов для тревоги."
Хм. То есть преподаватели даже тут обманывают наивных студентов.В Хоаре выбирается последний элемент, там наихудший как ты сказал. В этом случае наихудший случай построить чуть сложнее.
Да, преподаватели могли соврать.
Кстати вдруг вспомнил, что и про это хотел написать.
И что? Расскажи про пузырьки и про то, как они влияют на qsort.Чуваки, пишущие реальный код, который потом исполняется на реальных процессорах, относятся к асимптотическим оценкам особым образом. Особый образ состоит в том, чтобы понимать, где именно следует отказаться от этой оценки и посмотреть на код с понтом сколько циклов процессора он приблизительно жрёт. И вот тут как бы где-то в районе 8 элементов (ака 32 сравнений/свопов в тайт лупе) баббл сорт оказывается лучше, чем квиксорт, с его выбором среднего элемента и прочими накладными расходами, ну, посмотрите на его внутренний цикл же.
Там было не про это. Там было про то, что, поскольку
переключение происходит на каком-то однажды определённом
размере, этот вклад ограничен постоянной. Но он точно так же
ограничен постоянной, если ты эти обрезки сортируешь не
пузырьком, а qsort-ом.
---
"...Мелочи меня не интересуют."
переключение происходит на каком-то однажды определённом
размере, этот вклад ограничен постоянной. Но он точно так же
ограничен постоянной, если ты эти обрезки сортируешь не
пузырьком, а qsort-ом.
---
"...Мелочи меня не интересуют."
на код с понтом сколько циклов процессора он приблизительно жрёт.щас не циклы считают, а промахи мимо кэша
Оставить комментарий
Dmitriy82
>> Рассмотрим библиотечную функцию qsort> Это не зависит от того, использовал ты её или нет, знать должен.
> На упорядоченных.
А ты проверить не пробовал взять и запустить? И не должен ли ты знать, что есть модификации, когда в качестве разграничивающегося элемента берётся элемент из середины, или случайный элемент, или даже медианный (который в свою очередь находится хитрожопым способом где-нибудь за O(n?
>> Предложите наиболее быстрый алгоритм сортировки массива,
>> элементами которого являются числа от одного до ста.
> В таких случаях сортируют подсчётом.
Зависит от размера массива. Для коротких выгоднее запросто может оказаться отлаженная и оптимизированная библиотечная функция, или там написанная от руки наспех сортировака вставками.