Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Как изменится мир если сортировка будет проходить за константу?  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2653
Здравствуйте C:
Естественно я не говорю сортировках типа сортировки подсчетом(хотя это все равно не константа) или каких-либо других вырожденных случаях. Пусть появится алгоритм который будет сортировать любой набор данных с любым компаратором за константу. И пусть данный абстрактный алгоритм будет во всех основных библиотеках и доступен каждому.
Так что по вашему изменится?
16 май 19, 21:56    [21886657]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
SashaMercury
Здравствуйте C:
Естественно я не говорю сортировках типа сортировки подсчетом(хотя это все равно не константа) или каких-либо других вырожденных случаях. Пусть появится алгоритм который будет сортировать любой набор данных с любым компаратором за константу. И пусть данный абстрактный алгоритм будет во всех основных библиотеках и доступен каждому.
Так что по вашему изменится?

это из разряда квантовых процессоров?
16 май 19, 22:10    [21886666]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2653
Roman Mejtes,

Не обязательно. Допустим квантовые процессоры никогда не появятся. А сортировка за константу появится
16 май 19, 22:12    [21886670]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
SashaMercury,

то есть вы предполагаете, что алгоритм сортировки выполнится за константное время O(c), а не за O(n)?
16 май 19, 22:14    [21886672]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2653
Roman Mejtes
SashaMercury,

то есть вы предполагаете, что алгоритм сортировки выполнится за константное время O(c), а не за O(n)?

Cейчас мы как правило ожидаем O(nlog(n)), в некоторых случаях мы можем получить линию O(n)(например сортировка подсчетом), а я лишь прошу вас предположить, что будет, если сортировка будет выполняться за константное время O(c).

В общем вы поняли правильно, меня только смутила последняя часть вашего вопроса:
Roman Mejtes
а не за O(n)?

поскольку, повторюсь, сейчас мы как правило ожидаем O(nlog(n))
16 май 19, 22:35    [21886686]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
booby
Member

Откуда:
Сообщений: 1662
SashaMercury,

не ясно, какого сорта ответ ты хочешь услышать.

Сортировка за константу означает, что она не зависит от объема сортируемого набора данных.

Сама сортировка описывается в терминах перестановок элементов.
Пусть у тебя есть некий "массив массивов", то есть массив, каждый элемент которого сам является массивом.
Пусть такой массив содержит все перестановки для фиксированного мультимножества, из
которого составлен сортируемый набор.
Тогда в этом массиве будут две, для конкретного мультимножества заранее известные
известные позиции i_max и i_min, представляющие сортировку по возрастанию и сортировку
по убыванию для данного конкретного мультимножества.

Сортировка за константу сведётся к указанию заранее известных позиций i_max или i_min для конкретного мультимножества.

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

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

Логически это значит, что все сортировки подсчетом, идентифицирующие мультимножество,
выполнены заранее и, дополнительно, процедура выполнения идентификации мультимножества не требует времени выполнения (константа на классификацию равна нулю). То есть добавление элемента сводится к указанию на соответствующий, заранее построенный массив перестановок (сведённый до двух элементов), представляющий
изменённое мультимножества после добавления нового элемента.

Что это означает?
В не квантовых терминах, вероятно, прежде всего то, что реализована память с
произвольным доступом неограниченного размера, доступ к любому элементу которой гарантируется за константу, и все алгоритмы поиска/сортировки заранее реализованы в ней в табличном виде.
То есть все состояния всех вычислительных процессов сортировки зафиксированы,
и динамика сводится к переходу по указателю на ту область памяти за константное время, которая хранит соответствующий сортированный набор.

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

Как-то так думаю.
17 май 19, 01:10    [21886729]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
x1ca4064
Member

Откуда:
Сообщений: 1003
SashaMercury
И пусть данный абстрактный алгоритм будет во всех основных библиотеках и доступен каждому.
Так что по вашему изменится?


Скорее всего ничего: по закону подлости, этот алгоритм будет требовать немеренно памяти и константа будет очень большой, т.е. выгода его использования будет только при очень-очень больших недостижимых n (2^256, например).
17 май 19, 03:32    [21886753]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
x1ca4064
Member

Откуда:
Сообщений: 1003
SashaMercury
Так что по вашему изменится?


Возможно, построение этого алгоитма может иметь большие теоретические последствия.
17 май 19, 03:39    [21886756]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
Dima T
Member

Откуда:
Сообщений: 13915
SashaMercury
сортировать любой набор данных с любым компаратором за константу.

Чтение набора данных это уже O(n). O(c) значит сортировать не читая. Это как?
Хотя даже если вместо O(n*log(n)) получим O(n*c), т.е. сортировка за постоянное количество проходов, то это уже замечательно.
SashaMercury
Так что по вашему изменится?

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

Есть небольшой круг задач массовой обработки наборов данных, возможно там заметно повлияет.
17 май 19, 08:49    [21886819]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
kolobok0
Member

Откуда:
Сообщений: 1951
SashaMercury
..Так что по вашему изменится?


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

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

имхо - как то так...посему как это один из моих пока замороженных проектов :)

(круглый)
17 май 19, 10:30    [21886950]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Память дешевеет. И если мы купим кластер памяти размером с вселенную. То можно будет создать такую
мапу.

Map<byte[],byte[]> map = ...


То рано или поздно мы наполним эту табличку актуальными несортированными и сортированными
массивчиками и сортировка будет проходить за константу.
17 май 19, 10:45    [21886982]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
x1ca4064
Member

Откуда:
Сообщений: 1003
Roman Mejtes
SashaMercury,

то есть вы предполагаете, что алгоритм сортировки выполнится за константное время O(c), а не за O(n)?


O(c), в данном контексте, как-то писать не правильно, O(1) должно быть.
17 май 19, 12:02    [21887094]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
SashaMercury,

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

возможно порушит что-то в NP-полных задачах
17 май 19, 13:09    [21887180]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
alex55555
Member

Откуда:
Сообщений: 2129
SashaMercury
Так что по вашему изменится?

А что побудило задать такой вопрос?
17 май 19, 13:26    [21887195]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48132
SashaMercury
Пусть появится алгоритм который будет сортировать любой набор данных с любым компаратором за константу.

Это невозможно. О(1) требует отсутствия обращения непосредственно к данным. Как только появляется такое обращение, оно сразу подскакивает до O(N) и упасть обратно уже не может.
17 май 19, 13:41    [21887216]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Чьорт побьери.

Кстати те кто быстро сортируют массивы целых чисел обычно затрудняются ответить на другие
вопросы. Например - откуда данный массив вообще появился и сколько времени будет занимать
его публикация в виде результата.

Вобщем софизмы и парадоксы изначально сопровождают саму постановку сортировки.
17 май 19, 13:56    [21887241]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5107
mayton,

Это более сложные вопросы, так как зависят от кучи неизвестных факторов
17 май 19, 14:13    [21887264]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
mayton
Member

Откуда: loopback
Сообщений: 41808
Наверное поэтому сама постановка сортировки за константу парадоксальна.
Развивая идею - мы имеем память с нулевой латеностью (тахионная память).
И имееп процессор с бесконечной частотой тактового генератора. Или с настолько
высокой что какую задачу мы ему-бы не поставили он (процессор) ее решит
всегда за примлемое время. Тоесть вы не успеете моргнуть глазом.

В свете вышесказанного. Если такое чудо техники будет создано то
и NP-сложные задачи нам по боку.
17 май 19, 14:18    [21887271]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
ЕвгенийВ
Member

Откуда: Москва
Сообщений: 4779
mayton

В свете вышесказанного. Если такое чудо техники будет создано то
и NP-сложные задачи нам по боку.

Бесконечно большие величины бывают разных порядков.
Примерно так, что бесконечно большая величина первого порядка, оказывается бесконечно маленькой для бесконечно большой второго порядка.
17 май 19, 16:10    [21887457]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
alex55555
Member

Откуда:
Сообщений: 2129
ЕвгенийВ
Бесконечно большие величины бывают разных порядков.
Примерно так, что бесконечно большая величина первого порядка, оказывается бесконечно маленькой для бесконечно большой второго порядка.

Вообще это спорное заявление. То есть в математике такую фигню просто приняли за аксиому (и то в другой формулировке, не позволяющей буквально заявлять то, что заявлено в цитате), но такой подход некорректно работает, если попробовать принять немного другие аксиомы, или тем более, попробовать доказать что-то про "разницу порядков" без аксиом типа "у порядков обязательно есть разница".
18 май 19, 11:18    [21887811]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
exp98
Member

Откуда:
Сообщений: 1674
Опередили, ИМХО самый адекватный ответ с моей поправкой:
x1ca4064
Скорее всего ничего: по закону подлости, этот алгоритм будет требовать немеренно памяти и константа будет очень большой, т.е. выгода его использования будет только при очень-очень больших недостижимых n (2^256, например).
... и сос всеми вытекающими из этого (к прмеру полноценный доступ по значению вместо адресного).
Досужие рассуждения в стиле: наличия отсутствия обращения непосредственно к данным, напомнили случай доказать, что для сортировки просто необходимо сравнить каждого с каждым.
20 май 19, 16:35    [21889020]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
Roman Mejtes
Member

Откуда: г. Пермь
Сообщений: 3429
exp98
Опередили, ИМХО самый адекватный ответ с моей поправкой:
x1ca4064
Скорее всего ничего: по закону подлости, этот алгоритм будет требовать немерено памяти и константа будет очень большой, т.е. выгода его использования будет только при очень-очень больших недостижимых n (2^256, например).
... и сос всеми вытекающими из этого (к примеру полноценный доступ по значению вместо адресного).
Досужие рассуждения в стиле: наличия отсутствия обращения непосредственно к данным, напомнили случай доказать, что для сортировки просто необходимо сравнить каждого с каждым.
каждый с каждым это O(n^2) худший из вариантов.
автор фантастики наверное начитался :)
20 май 19, 20:35    [21889208]     Ответить | Цитировать Сообщить модератору
 Re: Как изменится мир если сортировка будет проходить за константу?  [new]
Partisan M
Member

Откуда:
Сообщений: 1359
SashaMercury
Так что по вашему изменится?


Кому будет казаться, что мир изменился таким образом, доктор будет прописывать таблетки, клизму и холодный душ, пока не перестанет казаться.
20 май 19, 20:45    [21889215]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить