Ха. В пределах одного бинарника может быть МНОГО повторяющегося кода — все методы std::vector<int>, std::vector<unsigned> и std::vector<что_угодно*> в 32-битном коде бинарно идентичны, но различны с точки зрения компилятора. По бинарнику не всегда можно судить о «bicyclity» исходников.
Хуже того, любую процедуру компилятор может попытаться встроить (inline) в вызывающий код. Если мест вызова много — получаем разбухание на ровном месте. Этот пример заодно демонстрирует,
почему бы не сделать на основе этого некое подобие словаря часто используемых кусокв, и на его основе сделать соответствующие системные вызовы ОС:
часто есть выбор скорость/размер кода, и компиляторы уже давно стремятся к скорости любой ценой. Системные вызовы ОС дают некоторые накладные расходы. А размер… что размер? Тормозит программа, из-за оптимизаций не влезающая в кэш процессора — возьмите новый процессор с большим кэшем и поставьте новое, более быстрое поколение памяти. Долго грузится система, читающая с диска десятки (если не сотни) мегабайт ядра, драйверов, системных данных, разнообразных программ с библиотеками — возьмите SSD. А оптимизация по размеру никого не интересует, совсем не интересует.
В ProjectEuler есть задача на более общие тождества такого же вида (сумма m+1 последовательных квадратов слева равна сумме m последовательных квадратов справа), когда нет ограничения, что последовательность справа продолжает последовательность слева, под номером 261 (русский перевод).
Например: 1082 + 1092 + 1102 = 1332 + 1342.
Что это? Здесь чего-то не хватает? Что хотели сделать с ячейкой массива?
Очевидно, эту ячейку хотели создать, что успешно и сделали. operator[] у std::set/std::map вставляет ключ, если его ещё не было (в случае std::map — с вызовом конструктора по умолчанию для значения). Код выше подтверждает, что цель в этом: если ключ уже есть в таблице, ситуация считается ошибкой. Здесь PVS-Studio проявляет излишнюю паранойю.
Боюсь, что не понял, о чём вы. Попробуйте поискать на mathworld.wolfram.com/, там у вещей, реализованных в Mathematica, указан их Mathematica-синтаксис, который понимает WolframAlpha.
Прошу прощения, перепутал знак в сравнении. Если все Ai различны, вы правы.
Впрочем, если все Ai одинаковы, будет всё-таки Θ(log n), алгоритм остановится после однократного рекурсивного спуска, в какую бы сторону ни пойти.
Число сравнений в этом алгоритме [ленивого поиска research] не зависит ни от X, ни от Ai и задаётся следующей рекурсивной формулой:
Почему? В лучшем случае research(X,i,j) заканчивается после 1 сравнения и одного рекурсивного вызова research(X,i,m), то есть получается 1+T([n/2]), что сводится к Θ(log n). В худшем случае — Θ(n), но в худшем случае и наивный алгоритм справляется.
Тестовым заданием было получить текстовый файл с такой табличкой на вход, загрузить в придуманную кандидатом структуру данных, отсортировать строки по значению одного из столбцов и вывести в другой текстовый файл аналогичного формата.
Это делает честь NTFS, т.к. например, структура ext2/ext3 требует для файла минимум 4-байтного числа на каждый 4-Kb блок данных:
То есть, надо дополнительно тратить по байту на каждый килобайт данных, на терабайт выходит гигабайт, а закэшировать гигабайт не так то просто. Впрочем, в ext4 такой проблемы, по-видимому, нет, или она замаскирована с помощью экстентов.
Для справки: в NTFS расположение файла на диске кодируется пофрагментно (каждый непрерывный кусок файла на диске описывается одной структурой). Если файл нефрагментирован, будет одна структура на весь файл, если файл разбит на два куска «первые N кластеров файла расположены в кластерах [A,A+N-1] диска, последние M кластеров — в кластерах [B,B+M-1] диска», то будут две структуры, кодирующие пары (N,A) и (M,B-A) соответственно, и так далее. Кодирование использует переменную длину, отбрасывая ведущие нули или FFки.
В частности, мы планируем ввести более длинные имена файлов, номера версий файлов, устойчивую к сбоям файловую систему, поддержку терминально-независимых дисплеев, возможно, завершение имён файлов, а со временем — оконную систему на базе Лисп, в которой несколько программ на Лисп и обычных программ Unix могут разделять один экран. В качестве системных языков программирования будут доступны как Си, так и Лисп. У нас будут сетевые программы на основе chaosnet — протокола Массачусетского технологического института, значительно превосходящего протокол UUCP.
tl;dr: Мы напишем свою операционную систему, с Лиспом и сетью на chaosnet!
std::vector<int>,std::vector<unsigned>иstd::vector<что_угодно*>в 32-битном коде бинарно идентичны, но различны с точки зрения компилятора. По бинарнику не всегда можно судить о «bicyclity» исходников.Хуже того, любую процедуру компилятор может попытаться встроить (inline) в вызывающий код. Если мест вызова много — получаем разбухание на ровном месте. Этот пример заодно демонстрирует, часто есть выбор скорость/размер кода, и компиляторы уже давно стремятся к скорости любой ценой. Системные вызовы ОС дают некоторые накладные расходы. А размер… что размер? Тормозит программа, из-за оптимизаций не влезающая в кэш процессора — возьмите новый процессор с большим кэшем и поставьте новое, более быстрое поколение памяти. Долго грузится система, читающая с диска десятки (если не сотни) мегабайт ядра, драйверов, системных данных, разнообразных программ с библиотеками — возьмите SSD. А оптимизация по размеру никого не интересует, совсем не интересует.
Например: 1082 + 1092 + 1102 = 1332 + 1342.
6 = 3!
5 = [6!2-2]
10 = [5!2-1]
43 = [10!2-2]
44 = [43!2-5]
7 = [44!2-6]
8 = [7!2-2]
14 = [8!2-2]
4 = [14!2-4]
24 = 4!
30 = [24!2-4]
106 = [30!2-4]
21 = [106!2-7]
290 = [21!2-3]
201 = [290!2-8]
884 = [201!2-7]
148 = [884!2-10]
10904 = [148!2-6]
250 = [10904!2-14]
7042 = [250!2-7]
860 = [7042!2-13]
126 = [860!2-10]
2007 = [126!2-6], 2008 = -[-126!2-6]
Полагаю, что можно добраться и до 2008 = [x!2-y] без верхней целой части (замаскированной под целую часть от -x), только числа в цепочке будут больше.
\left\lceil \frac{!(!4)\cdot2}{\lceil !(3!) / 2\rceil} \right\rceil
(!(3!-1)+1)^2\oplus((3!)!!+1)
Очевидно, эту ячейку хотели создать, что успешно и сделали. operator[] у std::set/std::map вставляет ключ, если его ещё не было (в случае std::map — с вызовом конструктора по умолчанию для значения). Код выше подтверждает, что цель в этом: если ключ уже есть в таблице, ситуация считается ошибкой. Здесь PVS-Studio проявляет излишнюю паранойю.
reference.wolfram.com/mathematica/ref/InterpolatingPolynomial.html
Впрочем, если все Ai одинаковы, будет всё-таки Θ(log n), алгоритм остановится после однократного рекурсивного спуска, в какую бы сторону ни пойти.
Почему? В лучшем случае
research(X,i,j)заканчивается после 1 сравнения и одного рекурсивного вызоваresearch(X,i,m), то есть получается 1+T([n/2]), что сводится к Θ(log n). В худшем случае — Θ(n), но в худшем случае и наивный алгоритм справляется.Вы для этого пишете отдельную программу?
(Для числовой сортировки — добавить ключ -n к sort, если поля разделяются конкретным символом, а не пробелом+табуляцией, то добавить ключ -t туда же.)
Для справки: в NTFS расположение файла на диске кодируется пофрагментно (каждый непрерывный кусок файла на диске описывается одной структурой). Если файл нефрагментирован, будет одна структура на весь файл, если файл разбит на два куска «первые N кластеров файла расположены в кластерах [A,A+N-1] диска, последние M кластеров — в кластерах [B,B+M-1] диска», то будут две структуры, кодирующие пары (N,A) и (M,B-A) соответственно, и так далее. Кодирование использует переменную длину, отбрасывая ведущие нули или FFки.
2. bash.im/quote/408012:
tl;dr: Мы напишем свою операционную систему, с Лиспом и сетью на chaosnet!