baden_badenДля определённых случаев сортировка за линейное время осуществима, но хочется узнать, что бы дало в принципе такое уменьшение времени, ведь даже log(1 000 000 000 000) не так велик. Даже для тех задач, которые я решал, было значительное отличие при замене сортировки пузырьком на быструю сортировку, но там мы заменяли N * Т на N * log(N), а произойдёт ли что-то революционное(решатся какие-то нерешаемые ранее из-за времени задачи, появятся новые алгоритмы, благодаря которым в нашей повседневности или хотя бы в некоторых профессиях появятся сильно упрощающие жизнь системы), если мы уберём log(N) и научимся волшебным образом сортировать числа за N действий?

Таких постановок практически нету. Если вы сортируете вектор
целых чисел то:

1 000 000 000 000 / 2^32 = / 4 294 967 295 = 232

Какова кардинальность? Каждое число диапазона целых
при равномерной гистограме встречается в выборке 232 раза!
Учитывая специфику предметной области я утверждаю
что линейных гистограмм практически не бывает. Поэтому
проще подсчитывать подсчётом (1 проход!)
и выводить результат. Это для чисел.

Если вы сортируете набор строк в БД то их никто не сортирует
а строят индекс и по нему извлекают.

Сортировка - это очень тяжёлый алгоритм с очень малым КПД
и малым полезным эффектом в принципе!

Данные выгоднее поддерживать с сортированных структурах
а не сортировать на каждый чих! Из-за этого мы имеем
непонимание студентами принципов оптимизации. Студент
оптимизирует "не то" и "не там" и не смотрит в корень
постановки.

И еще раз. Таких постановок не бывает.

Из контекста понятно что я говорю о 1 000 000 000 000 словах?

miksoft, придумай постановку где тебе "вне DBMS" нужно
сортировать 10^12 слов.

miksoft, для сортировки этой сотни гигабайт ему нужен был как минимум
еще пара таких дисков. +Merge sort. Дальше не скажу нужна статистика
по данным. Что. Чего. Сколько. Какая средняя длина элемента e.t.c.

ЧотакактаI/O-сопроцессоры, математические сопроцессоры, графические сопроцессоры... ждем аппаратного БДшного сопроцессора (около-мгновенная сортировка/поиск/фильтрация непосредственно в памяти, а дальше и на носителях), ну и чуть позже приход алгоритмического сопроцессора.

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

В подобной технике нельзя что-то одно ускорить с стотыщпитсот раз и оставить при этом без
изменения всё остальное. Если даже предположить что существует процессор иммитирующий
работу DBMS-Oracle то его узким местом мгновенно станет память. Надо будет ее ускорять
во столько-же раз. Вобщем придём к тому что закон Мура уже не действует (старик Гордон
ухмыляется) и надо форсировать параллелизм. А его уже давно форсируют строя кластеры.
А кластеры само по себе решение дешевле чем строительство новых процессоров. Ведь перезалить
софт стоит в тыщи раз дешевле чем изготовить новый процессор.

Нужно форсировать неисследованные идеи. К примеру вообще отказаться от принципа трех-уровневой
памяти и ввести еще парочку уровней. Создав тем самым много слоёв кеширования и отказавшись
от дорогостоящей DDR3 как от основной и от магнитного диска. Новые процессоры на аналоговых имплементациях нейросетей.
Новые типы устройств хранения (без энергопотребления вообще). Вспомогательные процессоры
для логических машин типа Lisp, для быстрой символьной логики и ФП. Игровые процессоры графики
больше не развивать. И так бесполезная трата энергии. А вот физику - форсировать. Дело
полезное и не только в играх но и в науке.

Исследовать био-технологии процессоры не на основе кремния а на основе живых структур и т.п.

KhodКак устройства хранения без энергопотребления могут ускорить вычисления?
Есть разные пути ускорения расчётов. Часть из них основаны
на том что ты повышаешь скорость АЛУ и наращиваешь количество ядер.
Но иногда есть предел. (Элементарно денег не хватит).
Есть и другой подход. В общем случае это мемоизация. Почитай
на тему.

KhodПочему вспомогателные процессоры для языков типа Лиспа, а не Дракона например.Или машину Тьюринга имели ввиду?
Не обязательно Лиспа. Любую машину символьной логики
которая активно использует не классическую (плоскую)
модель памяти с ячейками а модель на ассоциаций и деревьев.

KhodИгровые процессоры не развивать. Но ведь их используют для вычислений (та же Суба).
Их слабо используют. И их API и фреймворки запилены только под рендеринг графики.
И они узко-специализированные. Набор команд - неуниверсальный.
То что из запилили под некоторые расчётные алгоритмы это просто забавный технический
казус. Но если-бы цель стояла просто поднять перформанс основного CPU
для расчётов математики то никто-бы не ставил себе на борт игровые видяшки
а вкладывались бы в большее количество обычных штатных CPU на одной motherboard.
И то что красноглазики и технофрики считают Raibow tables на видяшках
это тоже забавных техничекий казус. Это не системый подход. Это воля случая.

KhodУ биотехнологий процент адекватного решения стремится к 100% но не раывен 100%.
Ты очень сильно удивишся но системы распознающие лицевые образы,
отпечатки пальцев штрих и QR-коды всегда выдают вероятностный
ответ или выдают множество эталонных образов попадающих в допустимую
группу совпадений. (То что не видишь на экране этих критериев
просто говорит о том что разработчих их от тебя стыдливо скрыл
и не показывает).

Другого метода брадт, еще не создали ни на кремниях ни на биотехнологиях.

P.S. А биотехнологии просто могли-бы быть дешевле.