Строки произвольной длины, про которые вы сказали, подразумевают что их длинна не фиксированная, а произвольная, не так ли? Иными словами К зависит от набора строк. Вы же не говорите что фиксируете N в быстрой сортировке и она выполняется за О(1).
Тем более что касается чисел Фибоначчи, то там длину можно зафиксировать только если зафиксировать само N.
К тому же стоило бы рассказать каким образом Вы собираетесь перемножать длинные числа за О(n), потому что обычное перемножение делается за O(N^2), и в таком случае ваш алгоритм скатывается до O(N^2*log(N)), что даже хуже чем реализация влоб.
Конечно нет! Кто вам такое сказал? Асимптотическая оценка предполагает учет всего, что не является константой и влияет на скорость работы алгоритма. Скорость работы алгоритма быстрой сортировки на строках произвольной длины O(k*N*log(N)), где N — кол-во строк, k- максимальная длина строки.
Аналогично и с фибоначчи, если заметить что длина n — го числа фибоначчи будет O(n), что так же было у помянуть в комментариях к предыдущей статье.
По поводу точности я тоже думал, но тут все не так плохо :) Если Вы посмотрите ссылку которую я давал чуть выше, то там можно будет найти часть — Дискретное преобразование Фурье в модульной арифметике. Так вот, при использовании этой модификации данного метода Вы избавитесь от погрешностей и сохраните асимптотику, но ухудшите константу.
И еще один момент. На самом деле при использовании БПФ на каждом шаге, вы все равно получите асимптотику O(n*log(n)), потому что последний шаг по сложности будет покрывать все предыдущие, а асимптотика последнего шага как раз таки O(n*log(n)).
Что касается перевода числа из двоичной записи в десятичную я как то не задумывался. А как вы предлагаете действовать в это случае?
Вы решили повторить тоже не упоминать тот факт, что в итоге кол-во умножение (или сложений) у вас будет N * log(N), потому что для n-го числа придется использовать некоторые ухищрения по типу длинной арифметики?
Да, пожалуй с китайской теоремой об остатках я погорячился :) Тогда посмотрим что нам дает БПФ. Оно позволяет нам выполнять перевод чисел за O(n*log(n)), их перемножение за O(n), и обратный перевод тоже за O(n*log(n)). Причем обратно мы можем переводить только после выполнения всех операций.
Тогда получается O(n*log(n)) — перево числа + O(n*log(n)) — возведение в степень + O(n*log(n)) — обратное преобразование. Итого в сумме O(n*log(n)).
Там число востанавливается за O(n^2 * log(k)) n — число простых модулей — т.е. по сути длинна числа / константу и k — максимальный из модулей (либо на нахождение гсд расширенным алгоритмом евклида). Однако такая операция производится только 1 раз, так что это не ухудшит ассимптотики. Как можно восстановить число за n*log(n) не слышал :)
Длинные числа можно перемножать за O(n), где n — длинна числа, если использовать Китайскую теорему об остатках. И того задача поставленная в статье задача решается за O(N*log(N)) против O(N^2) — общеизвестного решения. Думаю профит очевиден.
Да, кстати, если вы будете использовать БПФ для этих целей, то вы получите O(N*log^2(N)). Но можно поступить еще проще поступить — можно использовать Китайскую теорему об остатках, и тогда вы получите O(N*log(N)) против O(N^2). Тут прирост скорости очевиден.
Собственно я говорил не про абстрактный поток, а про реализацию файловых потоков в дотнете, т.к. именно их использовали в статье, и мне показалось (видимо ошибочно) что вы спросили про возможность ошибочного поведения в представленном примере.
В общем случае это момент который нужно учитывать, но как я уже сказал, в данном примере с этим проблемы возникать не будут.
Думаю теперь мы друг друга понял :)
Вы написали:
>А разве при использовании потока не нужно явно задавать размер?
>Странно. А в SDK для Java написано:…
>А гигабайтный файл нормально получается загрузить таким образом?
Ответ был на это.
Не знаю как в яве, но в дотнет (в статье речь о нем идет) с этим проблем не будет, и определять размер файла не обязательно. Это скорее нужно что бы человеку показать сколько качается и сколько осталось, если файл большой, но это уже другая история.
Не должен он отжирать 1 гб памяти. Файловые потоки в дотнете устроены таким образом, что создается буфер (по умолчанию 4 кб кажется), который считывается. Когда буфер заполнен, его содержимое сбрасывается в файл (flush). Именно размер этого буфера вы и устанавливаете, когда задаете размер потока.
Так что кушаться память должна только под буфер.
Я думаю основная проблема не в толщине, а в весе :) Насколько я понимаю отсоединить экран у слайдера не получится, и потому пользоваться всей этой тяжеленной хреновиной как планшетом будет не очень комфортно…
Да неужели) Вот только сегодня защитил диплом — Москва, НИТУ МИСиС. Сказали принести электронную версию диплома в формате Word. В библиотеку сдавать в формате pdf. Мне все же кажется что это не в Беларусии свои законы, это в каждом вузе свои.
Да и каждый сам для себя решает что ему важнее — время или деньги. Если бы все использовали OO, то и разговора не было бы, но это не так.
Тут скорее дело в виртуалке. Тоже сперва поставил так — все тормазило, раздражало и вообще было очень неудобно (теже углы просто неюзабельны). Потом поставил на vhd — совершенно другие ощущения. В опрос мне кажется нужно разделить пункты пользовался на пользовался на виртуалке и ставил нативно.
Ну и привыкли же. Тут особо деваться некуда — либо привыкнешь, либо поставишь другую ОС. Тот же риббон, когда он появился в офисе вызвал кучу негодований (у меня по крайней мере), но постепенно стал привычным. Так и тут — все будет, но со временем. Если конечно MS не придумает еще чего то нового что заменит WP7, в чем я сомневаюсь.
В скором времени выйдет Windows 8, в котором метро интерфейс. Хочешь не хочешь, а люди постепенно будут перетекать на новую операционку и привыкать к ней. Через некоторое время люди привыкнут к такому интерфейсу и начнут по-другому глядеть на WP7. Мне кажется на то и расчет, не?
Тем более что касается чисел Фибоначчи, то там длину можно зафиксировать только если зафиксировать само N.
К тому же стоило бы рассказать каким образом Вы собираетесь перемножать длинные числа за О(n), потому что обычное перемножение делается за O(N^2), и в таком случае ваш алгоритм скатывается до O(N^2*log(N)), что даже хуже чем реализация влоб.
Аналогично и с фибоначчи, если заметить что длина n — го числа фибоначчи будет O(n), что так же было у помянуть в комментариях к предыдущей статье.
И еще один момент. На самом деле при использовании БПФ на каждом шаге, вы все равно получите асимптотику O(n*log(n)), потому что последний шаг по сложности будет покрывать все предыдущие, а асимптотика последнего шага как раз таки O(n*log(n)).
Что касается перевода числа из двоичной записи в десятичную я как то не задумывался. А как вы предлагаете действовать в это случае?
Тогда получается O(n*log(n)) — перево числа + O(n*log(n)) — возведение в степень + O(n*log(n)) — обратное преобразование. Итого в сумме O(n*log(n)).
В общем случае это момент который нужно учитывать, но как я уже сказал, в данном примере с этим проблемы возникать не будут.
Думаю теперь мы друг друга понял :)
>А разве при использовании потока не нужно явно задавать размер?
>Странно. А в SDK для Java написано:…
>А гигабайтный файл нормально получается загрузить таким образом?
Ответ был на это.
Не знаю как в яве, но в дотнет (в статье речь о нем идет) с этим проблем не будет, и определять размер файла не обязательно. Это скорее нужно что бы человеку показать сколько качается и сколько осталось, если файл большой, но это уже другая история.
Так что кушаться память должна только под буфер.
Да и каждый сам для себя решает что ему важнее — время или деньги. Если бы все использовали OO, то и разговора не было бы, но это не так.