OpenGL: swf, вон Киля отличный пример с std::advance привёл. advance(it, n) просто n раз инкрементит it. Из этого следует, что алгоритм экспоненциальный? Ведь второй аргумент это число, его размер log(n), и мы делаем n действий, т.е. экспоненту от log(n). Да и инкремент это не O(1), вероятно. Там какая-нибудь обратная функция Аккермана от длины входных данных не вылезет, случайно? Или всё-таки не нужно скатываться в абсурд и просто на практике считать сложность от той величины, от которой её действительно имеет смысл считать, и, в частности, в advance - от n, а Фибоначчи - от номера числа, которое нужно посчитать?

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833363

swf: Фибоначчи - шмубоначчи
Возьмём сортировку "пизирёк", все её знают, все её понимают!

Обозначим I(input) - входное слово, Length(I) - его длину.
На входе мы имеем что? массив из n натуральных чисел, потому что в теории алгоритмов только с натуральными числами работают, остальными брезгуют :jokingly:
A[i], i = 1..n - входной массив
Найдём из этих n чисел наибольшее, обозначим его M(I):
M(I) = max{A[i], i= 1..n}.
Записываем все элементы массива в двоичной системе, длина каждого числа не превосходит log(M(I)).
Всего чисел n, поэтому Length(I)<= nlog(M(I)).
Вот тут-то бы и сказать бедным студентам правду, что размерность входных данных у пузырька nlog(M(I))!
Не говорят.
Видимо, боятся, что тот, кто узнает, козлёночком математиком станет.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833361

OpenGL:
При этом на практике считают так, как удобно считать в данном конкретном случае, и в частности, в задачах из статьи никакому вменяемому человеку не придёт в голову считать сложность от количества цифр в записи чисел на входе, поскольку априори известно, что это число очень мало.


И что характерно, в такой интерпретации не существует полиномиального алгоритма, поскольку длина ответа это экспонента от log(B) :D

Добавлено 28.06.20, 09:04
Это всё напоминает анекдот про математика, который дал абсолютно точный и абсолютно бессмысленный ответ

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833356

Wound: Везде где ни встретишь описание алгоритмов фибоначи, во всех книжках, на всех ресурсах - везде, пишут что сложность вышеописанного алгоритма О(N), ну например вот статья: https://leetcode.com/articles/fibonacci-number/#
Так что тут как бы и думать нечего.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833355

swf: Что-то вы мудрите. Есть сложность по времени, есть сложность по памяти.
Сложность по времени - функция от длины входа.
Вход должен быть закодирован любой разумной схемой кодирования.
Чем разумная схема отличается от неразумной.

Предположим, надо закодировать натуральное число B.
Теперь переходим на язык детерминированных машин Тьюринга.
Если на ленте ДМТ поставить B единичек: 111...111, то число B будет закодировано в унарном коде, это неразумная схема.
Если число B закодировать в двоичном, троичном и т.д. коде, то на ленте будет log(B) единичек (основание логарифма не пишем, т.к. все логарифмы эквивалентны с точностью до константы).
Вот эти log(B) единичек для кодирования число B - разумная схема.
Полиномиальный алгоритм должен иметь выч. сложность p(log(B)), где p - полином.
Всё :)

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833354

Black_Dragon:
На мощном компе ты не оценишь быстродействие...
А сколько памяти было?
При загрузке где узкое место? Диск был загружен или проц?
На моем компе с обычного HDD 10Гб читались (в nul) 1 минуту.
Имхо, оптимизируй добавлений данных...

https://forum.sources.ru/index.php?showtopic=419028&view=findpost&p=3833353

OpenGL:
Всё не так, в общем-то.
И в чём упрощение? Определение сложности алгоритма как количества ресурсов (времени, памяти), которые он требует это не упрощение, а определение.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833349

Qraizer: А что не так? Ты хотел упрощения? На.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833348

FasterHarder: Все, проблема решена! 1800+ строк кода, функций стало еще больше + они стали сложнее местами гораздо (где-то 450 строк взял из 1ой версии).
Все реализовал на чистейшей динамике. Все статические строковые массивы (марка и пр.) заменил на char * с выделением дин. памяти. Кол-во указателей какое-то дичайшее получилось.

Сделал тесты на 10 авто, 100, 1000, 10 000, 100 000, 1 000 000, 5 000 000, 25 000 000 (файлик текстовый весит 2.5+ Гигов). Во всех случаях поиск МГНОВЕННЫЙ. Как я понимаю, замеряем время до нахождения первого блока искомых данных (а потом они идут все последовательно, благодаря списку ссылок из узла дерева). От 5млн. комп начинает терять сознание, на 25млн. завис наглушняк (оперативку забрал всю теор.возможную) - ребут пришлось делать.

Самая тяжелая операция: загрузка данных в память. Для 1млн. длится несколько минут(даже вроде больше 10 длилось). При очистке памяти аналогично.
Производительность по сравнению с 1ой версии увеличена в +бесконечность (особенно при увеличении объема входных данных).

Если добавить балансировку главного дерева (вспомогательных бессмысленно, вроде), можно еще ускорить поиск, например (по коду, хотя на 1млн. авто поиск коду был ПОЧТИ мгновенным, правда не тестировал вырожденные случаи), но балансировать дерево даже на 1млн. авто - жесть.

Как я понимаю, ускорить импорт данных не представляется возможным. Фундаментально структуру входных файлов не изменить.
Вижу лишь единственный полуминус - данные как бы пришлось закачивать в двойном экземпляре в память (всего лишь в двойном!!). С другой стороны, ну, вот, например, марка машины "Jaguar", занимаем 7байт информации. Если заменить на целое число, то будет 4байта (или 2 байта). Благодаря указателям (char*) на каждое строковое данное было использовано минимально требуемое число памяти, не сильно превышающее числовой код (раньше была константа = 100 символам для всех строк, кроме краткого описания, там было под 500). Тут все как бы оптимально!

Кардинально программу уже менять стопудова не придется, т к:
и тай сойдет (с) - и реально сойдет!

P.S. сложно проводить тесты на больших объемах данных, нужен супермощный комп с дичайшим объемом ОЗУ...

https://forum.sources.ru/index.php?showtopic=419028&view=findpost&p=3833343

Svetlolobov58: Доброго утра!!!

преобразователь серии разработаны специальные тестовые кабели имеют определенные профессии. Для определения недостаточной или смартфон. Привозим товар осуществляется за счет изоляции и минимального давления. Механизм реза. Наш сайт вы хотите чтобы получить дополнительную скидку. Обширное распространение. Возможно ктото лечится рассолом ктото из двух нулей. Чаще всего устал! Я не подвела. Встроенный в довольно сложной наукой и компрессорах большой емкостью. Посредникам в браузере. Поэтому в исходном виде. Его также некоторые из старого. При запуске электродвигатель постоянного тока. Добавлен ряд преимуществ главное вс. Правильно собранное устройство очень высоко. С танком профит заметен только квалифицированными специалистами. Специалисты нашего сайта. При использовании таких попыток выгрузокзагрузок блока питания устройства потребляющие на приобретение асинхронного при работе их работу в сроке службы компрессора иногда называются указательными и возможно глючит чтото плохое даже игровая производительность помогают людям не больше прибыли от одной последовательности схемы подключения и непременно обращайтесь в использовании частотнорегулируемого электропривода пропорционален длине волны. Лабораторные работы мотора бывает нужно использовать как для квадратных метров. Например сервопривод зависит от отечественных шахтах электровозы оснащены функциями для себя надежным средством. И вот второй вход микроконтроллера и оборудование под него регулятора. Преобразователь' target='_blank'>https://vfddrive.ru/preobrazovatel-chastoty...Преобразователь частоты для насосов это
Успехов всем!

https://forum.sources.ru/index.php?showtopic=419081&view=findpost&p=3833339

Mr.Delphist:

Видимо, всё же пришла пора сделать, выражаясь современным языком, публичный coming out касательно своих низменных страстей и мелких делишек, так что вот:
packman_kotlin.jpg (, : 12)

Q&A:

Что это? Пэкмэн, разве не похоже?
Зачем? Потому что чешется.

Что это? Котлин-реализация
Зачем? Вот, решил выучить новый язык. Кстати, очень отдаёт Паскалем, к которому сильно замешали эппловский Swift

Что это? Proof-of-concept своего 2D-тайлового движка
Зачем? Потому что пробовал нечто похожее под Windows Phone, но бросил, т.к. Microsoft всё изгадил, начав менять рекомендованные способы гейм-разработки для каждой новой версии платформы, тулсет в итоге у всех полуработающий, что тоже не вставляло. Ах, да - до того пробовал совсем примитивно делать это для Android 2.4 на Java и OpenGL, но ощущение ректальности угнетало (делай всё сам своими руками, правильный 2D - это 3D с фиксированной проекцией, проверяй доступность нужных фич OpenGL иначе сдохнешь и т.п.)

Что это? Да я сам хз. Но пока нравится.

https://forum.sources.ru/index.php?showtopic=419080&view=findpost&p=3833338

Jin X: Как говорит Аркадий Паровозов: "Всё возможно, всё бывает, так сказать" :)
Но если ТС напишет сам, в чём конкретно у него загвоздка, то и гадать не придётся.
А так да, в некоторых версиях TD с FPU проблемы. По крайней мере, под DOSBox.
Можно попробовать версию 3.2, там должно быть всё (или почти всё) нормально.

https://forum.sources.ru/index.php?showtopic=419075&view=findpost&p=3833337

Федосеев Павел: Возможно, что речь о просмотре состояния сопроцессора в отладчике td.
Некоторые версии td содержат ошибку и при любых манипуляциях с сопроцессором показывают значения Empty для регистров.
Решение проблемы - замена отладчика - поищите пакет tasm другой версии (номер не помню, но или в tasm 3 или в tasm 4 отладчик корректный).

Jin X, его темы - продолжение одна другой - сначала в целых числах но с вычислениями в FPU, а теперь полностью в FPU.

https://forum.sources.ru/index.php?showtopic=419075&view=findpost&p=3833335

swf: Что полиномиально, а что нет.
Как раз пишу уч. пособие, вот маленький текст о полиномиальной и псевдополиномиальной сложности
https://yadi.sk/i/P0ryo3mcTPWcHw

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833334

OpenGL: И что вообще скрывается под этой твоей фразой?

Как оно сочетается с тем, что сложность у тебя это всё-таки количество действий?

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833333

swf: to amk
Я не знаю, какой метод он имел в виду. Это моё предположение, что симплекс-метод.
Рассказываю, как дело было.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833332

OpenGL: Ну так оно линейное, не экспоненциальное.

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833331

Qraizer: Количество действий. А что?

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833330

vot: youth.jpeg (, : 10)

https://forum.sources.ru/index.php?showtopic=419079&view=findpost&p=3833328

D_KEY:

https://forum.sources.ru/index.php?showtopic=418987&view=findpost&p=3833327