У вас на момент рекурсивного вызова выделено и не освобождено О(n) памяти (массивы restFirst и restSecond). Глубина рекурсии О(log n). Соответственно, сложность по памяти О(n * log n).
Все началось с сообщения о том, что в любом алгоритме сортировки (к слову, даже не в реализации, а именно в алгоритме) есть минусы и что для любого из них можно назвать множество примеров, где этот алгоритм не будет оптимальным. Вы в ответ стали возражать, зачем-то приводя в пример sort из стандартной библиотеки исходя из его превосходства по каким-то отдельным критериям, которые далеко не всегда имеют решающее значение и которые, вообще говоря, никак не относятся к алгоритму как таковому.
Теперь вот оказывается, что вы все таки не считаете библиотечный sort той самой серебряной пулей, которая оптимальна всегда и везде. И для него тоже есть множество примеров, где он не оптимален.
Можете тогда пожалуйста конкретнее прояснить, с чем именно вы не согласны и каков ваш посыл? Что зачастую можно написать std::sort и все будет хорошо? Ну да. Только с этим никто и не спорил и речь вообще о другом была.
Да, вы правы. С "у любого" я слегка погорячился.
Но общий посыл от этого не меняется — не существует серебряной пули, которая будет одинаково эффективно сортировать любые данные в любых условиях. Даже если речь о sort-е из стандартной библиотеки (любого языка).
А, у вас какое-то своё толкование задачи оптимизации. В классическом смысле это поиск минимума (или максимума) некоторой функции от этих самых параметров.
Нет, у меня толкование вполне классическое.
Как правило, эта функция: полная стоимость решения с учетом ограничений.
Что конкретно входит в "полную стоимость решения с учетом ограничений"? И с какими весами?
И в очень редких случаях sort не подходит, или не оптимален.
И, как сказал Prototik, можно назвать мильйон таких "редких случаев", в которых библиотечный sort будет неоптимальным.
"Нулевая стоимость поддержки и реализации" не равно "оптимально по всем параметрам". Помимо стоимости поддержки и реализации есть и другие параметры. Часть из них я упомянул в своем комментарии.
С сортировкой не так то, что сортировать можно очень разные данные и в очень разных условиях. Массив из 10 элементов эффективнее будет сортировать вставками. Из 10 миллионов элементов — квиксорт (если массив упорядочен случайно). Для 3 элементов эффективнее будет нахардкодить дерево из ифов. Если подключить сюда еще размер данных для сортировки (просто инты или 10-мегабайтные структуры?), тип структуры контейнера (массив или односвязный список?), характер данных (почти отсортированные? Случайно упорядоченные? Отсортированные в почти-обратном порядке?), то количество оптимальных для каждого отдельного случая алгоритмов растет еще больше.
sort из стандартной библиотеки — это компромисс, который good enough для самых распространенных случаев. Но даже в каждом из них — далек от оптимальности. Не говоря уже об искусственно созданных "плохих" входных данных, которые есть у любого алгоритма сортировки.
Рационализировать при желании можно все что угодно. Про экстрасенсов с гадалками тоже очень часто используется объяснение «прежде всего хороший психолог».
Но в конечном итоге значение имеет только то, работает это «что угодно», или нет. Полиграф (в качестве детектора лжи) — не работает. Нет качественных научных подтверждений его эффективности.
Нормальный научный показатель — это когда есть ссылка на нормальное научное исследование, в котором этот показатель был получен.
В соседнем предложении я вижу только голословное утверждение про 80%. В других предложениях я тоже не вижу ссылок на научные исследования, подтверждающие эти 80%
Половина перечисленных товарищей тоже работает с измеримой реальностью. У гомеопатов — измеримые разбавления действующего вещества с измеримыми потряхиваниями сосудов. У хиромантов — измеримые линии на ладонях. У астрологов — вполне измеримые положения небесных тел.
Всех их (с полиграфистами включительно) объединяет субъективная интерпретация этой объективной реальности. И то, что эта интерпретация в условиях контролируемого эксперимента не находит никаких подтверждений своей достоверности. В том числе и по причине того, что эта измеримая объективная реальность по факту не накладывает для этих товарищей почти никаких ограничений на простор для интерпретаций. Так что все они действительно зачастую могут наинтерпретировать что угодно, вне зависимости от того, что им показывают приборы, звезды и линии на руках.
Если не рассматривать полиграф как 100% гарантирующий выявление лжи прибор, то он вполне себе научен.
Ну да, если рассматривать его как прибор, одновременно измеряющий пульс, давление, электропроводность кожи и т.д. — он вполне научен.
Но чтобы рассматривать его как детектор лжи (неважно, на 100% точный, на 90% или на 80%) — нужны доказательства его эффективности. А их нет. Все свидетельства, показывающие эффективность полиграфа в качестве детектора лжи — это либо очень низкокачественные исследования, проведенные различными ассоциациями полиграфистов, либо вообще "авторитетные" свидетельства отдельных полиграфистов на основе личного опыта.
Ага. Вот только если спуститься в комментарии к статье, то можно заметить, что источник этих цифр — не нормальное научное исследование, а «полиграфолог из личного опыта».
У экстрасенса из личного опыта тоже эффективность близка к 100%. Как и у астролога.
О, долго мучился с такой-же проблемой. Даже систему переустанавливал и начал уже грешить на железо, как тут выше многие советуют. Но смущало все же то, что во-первых в журнале событий все чинно, а во-вторых, ubuntu на той-же машине работала без нареканий (на подвисания во всяком случае).
Собственно, эта статья и вдохновила разобраться таки в причинах этого безобразия с помощью ETW/xperf.
В общем, в моем случае тригерром подвисаний стала комбинация из нескольких вещей:
При смене темы оформления в процессе explorer-а лочится UI поток.
Смена цвета акцента означает смену темы оформления
В настройках персонализации стояла галочка automatically pick an accent color from my background
Там же в качестве фона было выбрано слайд-шоу со сменой картинки каждую минуту.
Собственно, дальше уже наверное понятно, что происходило. Каждую минуту смена фона раб. стола запускала цепочку "смена фона -> смена цвета акцента -> смена темы -> блокировка UI потока эксплорера -> фризы и подвисания всего UI".
Я конечно допускаю, что первоисточник проблемы может быть и не в этом, а где-то глубже. Ибо после перезагрузки подвисало намного меньше, чем после десятков часов работы, и на чистой системе до установки всего софта тоже сильных подвисаний вроде бы замечено не было. Но глубже копать у меня уже мотивации не было, т.к. проблема ушла после снятия одной галочки, а весь установленный софт мне все равно нужен для работы.
В общем, TLDR; Если включена смена фонов рабочего стола и выбор цвета акцента в зависимости от фона — попробуйте что-то из этого отключить.
То C++ решение нарушает другое правило. Оно читает размер файла и выделяет буфер нужного размера сразу. Этого тоже нельзя делать. Но если хочется, то можно. Ведь автор правил писал одно а подразумевал, оказывается, совсем другое.
Так что проблема все таки не в расте и не в решениях на нем, а в самом конкурсе, где нет четких требований, а те требования что есть — каждый понимает как хочет.
И снова нет. "Используя весь арсенал доступных оптимизаций" программы на C++ были бы копипастом программ на C и работали бы со скоростью программ на C. А в случае, если бы какой-то язык обогнал си (неважно, Rust это будет или, скажем, Python) — все решения на языках, поддерживающих asm вставки, превратились бы в одну большую asm вставку с дизассемблированным кодом этого более быстрого решения.
То есть используется как минимум не "весь арсенал". И мы снова приходим к тому, что меряется в этой игре бенчмарков непонятно что. И результаты этих измерений между собой не сравнимы.
Сравнил за вас.
Тимсорт лучше чуть менее, чем везде.
Время выполнения на моей машине:
Исходник (слегка модифицированный авторский): https://pastebin.com/kQVC6Cam
У вас на момент рекурсивного вызова выделено и не освобождено О(n) памяти (массивы restFirst и restSecond). Глубина рекурсии О(log n). Соответственно, сложность по памяти О(n * log n).UPD: пардон, там arr освобождается. Все таки O(n)
O(3n) = O(4n) = O(100500n) = O(n)
Я немного утратил нить вашего тезиса.
Все началось с сообщения о том, что в любом алгоритме сортировки (к слову, даже не в реализации, а именно в алгоритме) есть минусы и что для любого из них можно назвать множество примеров, где этот алгоритм не будет оптимальным. Вы в ответ стали возражать, зачем-то приводя в пример sort из стандартной библиотеки исходя из его превосходства по каким-то отдельным критериям, которые далеко не всегда имеют решающее значение и которые, вообще говоря, никак не относятся к алгоритму как таковому.
Теперь вот оказывается, что вы все таки не считаете библиотечный sort той самой серебряной пулей, которая оптимальна всегда и везде. И для него тоже есть множество примеров, где он не оптимален.
Можете тогда пожалуйста конкретнее прояснить, с чем именно вы не согласны и каков ваш посыл? Что зачастую можно написать std::sort и все будет хорошо? Ну да. Только с этим никто и не спорил и речь вообще о другом была.
Да, вы правы. С "у любого" я слегка погорячился.
Но общий посыл от этого не меняется — не существует серебряной пули, которая будет одинаково эффективно сортировать любые данные в любых условиях. Даже если речь о sort-е из стандартной библиотеки (любого языка).
Труда действительно не составляет. Правда не могу понять, чем вам не угодили библиотеки. Но да ладно.
https://github.com/git/git/blob/master/pack-revindex.c#L27
https://github.com/torvalds/linux/blob/master/lib/sort.c#L199
https://github.com/antirez/redis/blob/unstable/src/pqsort.c#L99
А мой вопрос вы решили проигнорировать? Про количественный и качественный состав "полной стоимости решения с учетом ограничений".
Нет, у меня толкование вполне классическое.
Что конкретно входит в "полную стоимость решения с учетом ограничений"? И с какими весами?
И, как сказал Prototik, можно назвать мильйон таких "редких случаев", в которых библиотечный sort будет неоптимальным.
"Нулевая стоимость поддержки и реализации" не равно "оптимально по всем параметрам". Помимо стоимости поддержки и реализации есть и другие параметры. Часть из них я упомянул в своем комментарии.
С сортировкой не так то, что сортировать можно очень разные данные и в очень разных условиях. Массив из 10 элементов эффективнее будет сортировать вставками. Из 10 миллионов элементов — квиксорт (если массив упорядочен случайно). Для 3 элементов эффективнее будет нахардкодить дерево из ифов. Если подключить сюда еще размер данных для сортировки (просто инты или 10-мегабайтные структуры?), тип структуры контейнера (массив или односвязный список?), характер данных (почти отсортированные? Случайно упорядоченные? Отсортированные в почти-обратном порядке?), то количество оптимальных для каждого отдельного случая алгоритмов растет еще больше.
sort из стандартной библиотеки — это компромисс, который good enough для самых распространенных случаев. Но даже в каждом из них — далек от оптимальности. Не говоря уже об искусственно созданных "плохих" входных данных, которые есть у любого алгоритма сортировки.
Мне нужно сложить 2 целых числа.
Можете назвать оптимальное решение, оптимизированное по всем параметрам сразу?
Рационализировать при желании можно все что угодно. Про экстрасенсов с гадалками тоже очень часто используется объяснение «прежде всего хороший психолог».
Но в конечном итоге значение имеет только то, работает это «что угодно», или нет. Полиграф (в качестве детектора лжи) — не работает. Нет качественных научных подтверждений его эффективности.
Нормальный научный показатель — это когда есть ссылка на нормальное научное исследование, в котором этот показатель был получен.
В соседнем предложении я вижу только голословное утверждение про 80%. В других предложениях я тоже не вижу ссылок на научные исследования, подтверждающие эти 80%
Половина перечисленных товарищей тоже работает с измеримой реальностью. У гомеопатов — измеримые разбавления действующего вещества с измеримыми потряхиваниями сосудов. У хиромантов — измеримые линии на ладонях. У астрологов — вполне измеримые положения небесных тел.
Всех их (с полиграфистами включительно) объединяет субъективная интерпретация этой объективной реальности. И то, что эта интерпретация в условиях контролируемого эксперимента не находит никаких подтверждений своей достоверности. В том числе и по причине того, что эта измеримая объективная реальность по факту не накладывает для этих товарищей почти никаких ограничений на простор для интерпретаций. Так что все они действительно зачастую могут наинтерпретировать что угодно, вне зависимости от того, что им показывают приборы, звезды и линии на руках.
Ну да, если рассматривать его как прибор, одновременно измеряющий пульс, давление, электропроводность кожи и т.д. — он вполне научен.
Но чтобы рассматривать его как детектор лжи (неважно, на 100% точный, на 90% или на 80%) — нужны доказательства его эффективности. А их нет. Все свидетельства, показывающие эффективность полиграфа в качестве детектора лжи — это либо очень низкокачественные исследования, проведенные различными ассоциациями полиграфистов, либо вообще "авторитетные" свидетельства отдельных полиграфистов на основе личного опыта.
Ага. Вот только если спуститься в комментарии к статье, то можно заметить, что источник этих цифр — не нормальное научное исследование, а «полиграфолог из личного опыта».
У экстрасенса из личного опыта тоже эффективность близка к 100%. Как и у астролога.
Совершенно верно. Полиграф — это один из ярких примеров псевдонауки, довольно успешно маскирующейся под науку.
По сложности примерно сравнима с задачей поиска хорошего уфолога, гомеопата, экстрасенса или хироманта.
del
О, долго мучился с такой-же проблемой. Даже систему переустанавливал и начал уже грешить на железо, как тут выше многие советуют. Но смущало все же то, что во-первых в журнале событий все чинно, а во-вторых, ubuntu на той-же машине работала без нареканий (на подвисания во всяком случае).
Собственно, эта статья и вдохновила разобраться таки в причинах этого безобразия с помощью ETW/xperf.
В общем, в моем случае тригерром подвисаний стала комбинация из нескольких вещей:
Собственно, дальше уже наверное понятно, что происходило. Каждую минуту смена фона раб. стола запускала цепочку "смена фона -> смена цвета акцента -> смена темы -> блокировка UI потока эксплорера -> фризы и подвисания всего UI".
Я конечно допускаю, что первоисточник проблемы может быть и не в этом, а где-то глубже. Ибо после перезагрузки подвисало намного меньше, чем после десятков часов работы, и на чистой системе до установки всего софта тоже сильных подвисаний вроде бы замечено не было. Но глубже копать у меня уже мотивации не было, т.к. проблема ушла после снятия одной галочки, а весь установленный софт мне все равно нужен для работы.
В общем,
TLDR; Если включена смена фонов рабочего стола и выбор цвета акцента в зависимости от фона — попробуйте что-то из этого отключить.
То C++ решение нарушает другое правило. Оно читает размер файла и выделяет буфер нужного размера сразу. Этого тоже нельзя делать. Но если хочется, то можно. Ведь автор правил писал одно а подразумевал, оказывается, совсем другое.
Так что проблема все таки не в расте и не в решениях на нем, а в самом конкурсе, где нет четких требований, а те требования что есть — каждый понимает как хочет.
И снова нет. "Используя весь арсенал доступных оптимизаций" программы на C++ были бы копипастом программ на C и работали бы со скоростью программ на C. А в случае, если бы какой-то язык обогнал си (неважно, Rust это будет или, скажем, Python) — все решения на языках, поддерживающих asm вставки, превратились бы в одну большую asm вставку с дизассемблированным кодом этого более быстрого решения.
То есть используется как минимум не "весь арсенал". И мы снова приходим к тому, что меряется в этой игре бенчмарков непонятно что. И результаты этих измерений между собой не сравнимы.