Здравствуйте, netch80, Вы писали:
N>Здравствуйте, smeeld, Вы писали:
N>Не так.
N>Во-первых, их три: quick, heap и insertion. Как раз insertion используется для мелких кусков, но вызывается не на каждый мелкий кусок, а в финальном проходе сразу по всему массиву. То есть они тут экономят на кэше кода за счёт возможного второго некэшированного прохода по всем данным (зато последовательного). За счёт предварительного разделения через quicksort расстояние перемещения в этом проходе ограничено тем самым пределом размера.
Что за insertion тут у Вас? Тут introsort_loop- который воплощает quick sort, и partial_sort, который есть heap sort
Здравствуйте, smeeld, Вы писали:
N>>Во-первых, их три: quick, heap и insertion. Как раз insertion используется для мелких кусков, но вызывается не на каждый мелкий кусок, а в финальном проходе сразу по всему массиву. То есть они тут экономят на кэше кода за счёт возможного второго некэшированного прохода по всем данным (зато последовательного). За счёт предварительного разделения через quicksort расстояние перемещения в этом проходе ограничено тем самым пределом размера.
S>Что за insertion тут у Вас? Тут introsort_loop- который воплощает quick sort, и partial_sort, который есть heap sort
Я привёл код ко второму утверждению, а не к первому. К первому вот этот кусок имеет отношение — реализация всей std::sort() (если непонятно, я вслед за контекстом говорю именно о ней, а не о std::partial_sort, которая вообще никак раньше не вспоминалась):
Здравствуйте, netch80, Вы писали:
N>Здравствуйте, smeeld, Вы писали:
N>>>Во-первых, их три: quick, heap и insertion. Как раз insertion используется для мелких кусков, но вызывается не на каждый мелкий кусок, а в финальном проходе сразу по всему массиву. То есть они тут экономят на кэше кода за счёт возможного второго некэшированного прохода по всем данным (зато последовательного). За счёт предварительного разделения через quicksort расстояние перемещения в этом проходе ограничено тем самым пределом размера.
S>>Что за insertion тут у Вас? Тут introsort_loop- который воплощает quick sort, и partial_sort, который есть heap sort
N>Я привёл код ко второму утверждению, а не к первому. К первому вот этот кусок имеет отношение — реализация всей std::sort() (если непонятно, я вслед за контекстом говорю именно о ней, а не о std::partial_sort, которая вообще никак раньше не вспоминалась):
N>
sort -> introsort_loop -> partial_sort -> heap_sort. Так это устроено. heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения. То есть, тут типичный quick sort, реализованный в цикле introsort_loop, и heap sort, которому передаётся управление тогда, когда размер разбиваемого куска станет достаточно малым. То есть, алгоритм quick sort дробит на куски, а куски сортируются heap sort-ом. Где тут какое-то insertion, не понятно.
Здравствуйте, smeeld, Вы писали:
S> heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения.
Неверно. Нет такого.
Выше уже была приведена ссылка с кодом: http://rsdn.org/forum/flame.comp/7349517.1
Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
W>Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
Это всегда происходит, когда исходный массив "большой".
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, smeeld, Вы писали:
S>> heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения. W>Неверно. Нет такого. W>Выше уже была приведена ссылка с кодом: http://rsdn.org/forum/flame.comp/7349517.1
W>Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
В смысле, тот самый счётчик глубины отражает размер куска.
Здравствуйте, watchmaker, Вы писали:
W>Здравствуйте, smeeld, Вы писали:
S>> heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения. W>Неверно. Нет такого. W>Выше уже была приведена ссылка с кодом: http://rsdn.org/forum/flame.comp/7349517.1
W>Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
В смысле 2: если бы не было счётчика глубины, то мы в дроблении доходили бы до размера кусков в один-два элемента, которые бы свопились. С счётчиком мы доходим до размера куска, определяемого величиной счётчика (чем больше счётчик тем меньше возможен размер куска) после чего на куске запускается heap sort.
Здравствуйте, smeeld, Вы писали:
S>Дык, и я о том же:
НЕТ
S>sort -> introsort_loop -> partial_sort -> heap_sort. Так это устроено. heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения. То есть, тут типичный quick sort, реализованный в цикле introsort_loop, и heap sort, которому передаётся управление тогда, когда размер разбиваемого куска станет достаточно малым.
*Откуда* утверждение про размер??? Читаем C++ по фоновому:
__depth_limit это не размер, это параметр, который уменьшается на 1 с каждым рекурсивным вызовом функции самой себя. И если рекурсия зашла слишком глубоко (а размер при этом, наоборот, больше, чем ожидался!) — то тут и включается __partial_sort.
S> То есть, алгоритм quick sort дробит на куски, а куски сортируются heap sort-ом. Где тут какое-то insertion, не понятно.
В __introsort_loop первая строка тела:
while (__last - __first > int(_S_threshold))
то есть если мы попали на начало итерации цикла, а разница позиций уже меньше _S_threshold, никакая сортировка на этом этапе выполняться не будет. И вот это то, что insertion sort дорабатывает в самом конце.
W>>Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
S>В смысле, тот самый счётчик глубины отражает размер куска.
Он отражает его _наоборот_.
Достижение случая __depth_limit == 0 возможно, если падение длины куска сильно меньше, чем хотелось.
В идеале (каждое деление строго пополам) это невозможно, потому что начальное значение __depth_limit равно log2(size)*2, а при идеальном делении глубина рекурсии не превысит log2(size).
Достижение __depth_limit == 0 возможно только если все деления "по дороге" оказались в среднем (геометрическом) хуже, чем 2.41:1 (2.41 = sqrt(2)/(1-sqrt(2))).
Здравствуйте, smeeld, Вы писали:
W>>Видно, что heap_sort как раз не вызывается при нормальном сценарии (а вызывается только если лимит глубины исчерпан, но это редкая ситуация, и ожидается, что при сортировке она вероятно не произойдёт).
S>Это всегда происходит, когда исходный массив "большой".
Нет. Это происходит только при цепочке достаточно неоптимальных разбиений. Если все разбиения достаточно неплохи, то оно никогда в heapsort не скатывается.
Здравствуйте, smeeld, Вы писали:
N>>*Откуда* утверждение про размер??? Читаем C++ по фоновому:
S>Выше про отражение счётчиком минимального размера куска, на которые можем разбиваться в рекурсии intrsort_loop
Вы писали:
>> heap_sort вызывается в partial_sort, которая вызывается в introsort_loop когда размер массива, куска на которые разбиваемся в introsort_loop становится меньше некоторого значения.
Так вот — нет никакого правила "partial_sort вызывается, когда размер куска становится меньше некоторого значения".
При этом вообще ничего не вызывается в цикле до финального прохода insertion.
Здравствуйте, smeeld, Вы писали:
N>>Он отражает его _наоборот_.
S>Да, и в треде об этом написал, хотя, это уже и не важно как именно он отражает.
Важно, если мы говорим о том, при каких условиях и с какими размерами зовётся heapsort.
Она никогда не будет вызвана при размерах не более _S_threshold. Только при бо́льших, а в типичном случае — заметно бо́льших.
Иначе и смысла нет.
В>>Это жалоба или хвасталка? В>>В чём, собственно, проблема?
В>>Запоминать порядок вставки нужно, пусть и редко. Кому это мешает?
N>Вот это вам кажется, что оно "редко" нужно. А ширнармассы кодеров хотят этого всегда, и разработчики под них прогибаются. N>В этом и проблема.
OrderedDict встречается очень редко и в сторонних библиотеках и в тех местах, где я работал.
Есть ещё SortedDict, но это вообще экзотика.
N>Зато штатного аналога <map> нет ни в JS, ни в Python. И это вторая проблема.
Ни разу не видел, где бы он (аналог) понадобился бы. Можно пример?
Зато пока в C++ не ввели unordered_map было скучно на огромных объёмах данных.
N>Можно подключить внешнюю библиотеку, но хипстеры берут сразу sqlite.
Может лучше сразу redis?
One surprising part is that the new design, besides being more memory efficient, is ordered by design: it preserves the insertion order. This is not forbidden by the Python language, which allows any order. It makes the collections.OrderedDict subclass much faster than before: it is now a thin subclass of dict.
Эта цитата из pypy.
А в CPython пишут, что мол это "implementation details", которые вполне могут и поменяться в будущем.
Здравствуйте, Ватакуси, Вы писали:
N>>А вот читаем по ссылке отсюда:
N>>
One surprising part is that the new design, besides being more memory efficient, is ordered by design: it preserves the insertion order. This is not forbidden by the Python language, which allows any order. It makes the collections.OrderedDict subclass much faster than before: it is now a thin subclass of dict.
В>Эта цитата из pypy.
С каких это пор официальная документация CPython стала "цитата из pypy"??
В>А в CPython пишут, что мол это "implementation details", которые вполне могут и поменяться в будущем.
Если речь именно про порядок перебора, то в 3.7 его стандартизовали:
the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec.
Ну и вряд ли будут в будущем менять реализацию на менее эффективную, ящетаю (tm)
В>>Эта цитата из pypy.
N>С каких это пор официальная документация CPython стала "цитата из pypy"?? https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html
В>>А в CPython пишут, что мол это "implementation details", которые вполне могут и поменяться в будущем.
N>Если речь именно про порядок перебора, то в 3.7 его стандартизовали:
Твоя ссылка вела на 3.6, а там написано именно то, что я и сказал.
N>
the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec.
Здравствуйте, Ватакуси, Вы писали:
В>>>А в CPython пишут, что мол это "implementation details", которые вполне могут и поменяться в будущем. N>>Если речь именно про порядок перебора, то в 3.7 его стандартизовали: В>Твоя ссылка вела на 3.6, а там написано именно то, что я и сказал.
Что в 3.7 его закрепили формально, я написал в первом письме темы.
N>>
the insertion-order preservation nature of dict objects has been declared to be an official part of the Python language spec.
N>>Ну и вряд ли будут в будущем менять реализацию на менее эффективную, ящетаю (tm) В>Меняли и не раз уже.
Рандомизировали не от веселья, а вероятно потому, что можно устроить DoS с помощью Hash Collision Complexity Attack, упорядоченный словарь выдаёт атакующему информацию о хэширующей функции.
