- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
package literatePrimes;
import java.util.ArrayList;
public class PrimeGenerator {
private static int[] primes;
private static ArrayList<Integer> multiplesOfPrimeFactors;
protected static int[] generate(int n) {
primes = new int[n];
multiplesOfPrimeFactors = new ArrayList<Integer>();
set2AsFirstPrime();
checkOddNumbersForSubsequentPrimes();
return primes;
}
private static void set2AsFirstPrime() {
primes[0] = 2;
multiplesOfPrimeFactors.add(2);
}
private static void checkOddNumbersForSubsequentPrimes() {
int primeIndex = 1;
for (int candidate = 3;
primeIndex < primes.length;
candidate += 2) {
if (isPrime(candidate))
primes[primeIndex++] = candidate;
}
}
private static boolean isPrime(int candidate) {
if (isLeastRelevantMultipleOfNextLargerPrimeFactor(candidate)) {
multiplesOfPrimeFactors.add(candidate);
return false;
}
return isNotMultipleOfAnyPreviousPrimeFactor(candidate);
}
private static boolean
isLeastRelevantMultipleOfNextLargerPrimeFactor(int candidate) {
int nextLargerPrimeFactor = primes[multiplesOfPrimeFactors.size()];
int leastRelevantMultiple = nextLargerPrimeFactor * nextLargerPrimeFactor;
return candidate == leastRelevantMultiple;
}
private static boolean
isNotMultipleOfAnyPreviousPrimeFactor(int candidate) {
for (int n = 1; n < multiplesOfPrimeFactors.size(); n++) {
if (isMultipleOfNthPrimeFactor(candidate, n))
return false;
}
return true;
}
private static boolean
isMultipleOfNthPrimeFactor(int candidate, int n) {
return
candidate == smallestOddNthMultipleNotLessThanCandidate(candidate, n);
}
private static int
smallestOddNthMultipleNotLessThanCandidate(int candidate, int n) {
int multiple = multiplesOfPrimeFactors.get(n);
while (multiple < candidate)
multiple += 2 * primes[n];
multiplesOfPrimeFactors.set(n, multiple);
return multiple;
}
}
Follow us!
Но вообще, я не настоящий ма-те-ма-ти-к и с алгоритмами кобенаций генераций простых чисел знаком слабо. А понимать смысл этой ёбанной портянки я решительно отказываюсь, потому что без подсветки тупо не вижу, какие функции вызываются.
З.Ы. Причём подразумевается, что ты знаешь что означают p, q и n в конкретной задаче т.к. они взяты из общеизвестных формул. Никаких комментариев об этом не будет.
Они могут иногда по разному писаться, иногда вообще одинаково.
Если я не знаю, что такое "ip", то нехуя мне лазить в код для работы с сетью.
Если я не знаю, что вероятность это "p", то нехуя мне лазить в код про вероятность.
Так что может быть толика логики тут есть.
Смотри не перепутай.
А вот «set0» — это да, жопа какая-то непонятная.
З.Ы. Кто-то там говорил, что RAII не нужен и программист сам справится?
Ну вроде как ручное кручение счетчика ссылок по явной, простой и хорошо задокументированной это не самая большая проблема.
Делать что-то вручную неприятно, но не смертельно. Если конечно ты точно понимаешь, что делать.
То-есть каждый раз надо было думать "а кто создал этот объект, а когда мне его удалить, а вдруг не мне, а вдруг он уже удален?".
И это самый пиздецкий пиздец и ад
Не... Есть ещё сишная асинхронщина. Тот самый момент, когда ручное управление ресурсами встречается с тредами и коллбеками.
И никто ведь не опишет, что коллбек тебе могут позвать во время close или даже после него.
Но совсем другое дело — это когда ошибка в тупой и утомительной рутине приводит к утечкам ресурсов, дедлокам и прочим гейзенбагам. Проблема в том, что человек чисто физически не может все 100% времени быть в абсолютно полной концентрации, он в любом случае её теряет и ошибается. Ну а самое неприятное то, что тупая и утомительная рутина катастрофически снижает концентрацию. Поэтому когда тупая и утомительная рутина является крайне важной частью программирования, ошибки в которой приводят к крайне неприятным и трудноотлавливаемым багам… Ну, это хуёво.
Ручное управление ресурсами а-ля си лучше «RAII» тогда и только тогда, когда над проектом работают исключительно никогда не ошибающиеся сверхлюди. Ну или когда проект — это маленькая программка на 1000 строк (500 из которых занимают ручные выделения/освобождения ресурсов :-), да.
В крестах с готовыми RAII обёртками это уместилось в десяток строк.
В питоньей консольке в одну.
Ух, бля. Сочувствую.
[/color]
Яблы когда вводили свой ARC, они посчитали, что огромная часть типовой программы это retain/release.
Да это хуйня. Ты вот попробуй заполнить безопасный массив из вариантов, в которых лежат строки. Вот где самый ад начинается.
Дейкстра же основал секту одноразвратников.
Потому нееет, ретурнами тут не обойтись.
Нужно ебошить флажок состояния или делать вложенные ифы.
А тут я сказал, что жить с ручным RC можно, если есть строгие правила когда и что увеличивать.
Если правил нет, то все, пиздец, жить нельзя вообще.
И разумеется я согласен, что бойлерплецт это плохо. Жаве следует сгореть в аду, например
Цари
ftfy
>или когда проект — это маленькая программка на 1000 строк
Царская демо программа-выебон на 100 строк чтобы слить лалок в хламину.
В странах, принявших Венскую конвенцию о дорожном движении, можно увидеть круглый знак с чёрным числом на белом фоне с красной обводкой. Все знают, что это предельно разрешённая скорость в км/ч.
В США же можно увидеть охрененно длинную прямоугольную табличку (такую, что шею сломаешь, пока её всю разглядишь), на которой написано: «SPEED LIMIT 60 MPH».
Если бы эти знаки встречались редко, было бы удобно писать, как в США, чтобы всё было разжёвано и чтобы не напрягать память, вспоминая, знак какой формы и какого цвета что означает. Но когда эти знаки через каждые несколько метров, читать длинные надписи тупо некогда. Именно поэтому я за Венскую конвенцию.
К чему это я? Если у нас большущая функция, её можно назвать длинно. Например, PrimeGenerator. Простительно даже назвать ещё длиннее, чтобы не вспоминать, что она генерирует. Например, PrimeNumbersGenerator. А вот внутри функции имя каждого счётчика делать длинным ни к чему. Хватит и комментария при объявлении переменной.
А сейчас на ассемблере пишут разве что с интринсиками (которые как раз подробно развёрнутыми).
А у тех, кто занимается реверсом, всегда есть под рукой мануал. В «x64dbg», например, можно через «Ctrl+F1» для любой инструкции вызвать подробную справку, а если нажать «Ctrl+Shift+F1» — напротив инструкций будет их краткое описание: https://i.imgur.com/ZF320si.png. И, честно говоря, правая панель не выглядит особо удобной в чтении.
Лол, да популярных инструкций очень мало, на самом деле. Конпеляторы ещё более консервативны чем люди. Я по-моему за пару дней их все встретил и запомнил.
А остальные либо поштучно в лютой системщине, либо кучками в лютом матане, либо вообще устарели и не используются.
З.Ы. Даже если конпелятор юзает SSE для "векторизации", то по большей части это xor для зануления да mov.
> А остальные либо поштучно в лютой системщине, либо кучками в лютом матане, либо вообще устарели и не используются.
Ну вот, как раз для них и есть «Ctrl+F1». Ну и для SSE/AVX/MMX/3DNow! и прочего дерьма.
Разве что всякие SSE можно было бы чуть подробнее расписать. А остальное норм, имхо.
> внятный хелп
Ха-ха. Почитай-ка описание инструкции ret на досуге. Там 10 страниц из которых 8 - псевдокод с алгоритмом его работы.
З.Ы. Причём, блин, мне однажды реально пришлось этот псевдокод читать.
https://c9x.me/x86/html/file_module_x86_id_280.html
https://c9x.me/x86/html/file_module_x86_id_145.html
Да, отсутствует одна ветка: у IRET нет версии с «ближним развратом», потому что предугадать, какой сегмент будет текущим, когда сработает прерывание, невозможно.
Когда мне надо вывести широкий чар, мне приходится подглядывать в доку.
Реальный пример:
• getstr — ввод «узкого» символа из неограниченной области;
• wgetstr — ввод «узкого» сивола из окошка;
• get_wstr — ввод «широкого» символа из неограниченной области;
• wget_wstr — ввод «широкого» символа из окошка.
Попрошу не путать, а то могут и напутать. Скажут, никакой он не «window», а «wide».
Какое-то форматирование строки со стандартными процентными мудификаторами.
> snprintf
Форматирование с записью в строку.
> snprintf
Запись в строку максимум n символов.
> wsnprintf
Запись wchar_t, широких символов.
> v
А вот это забыл. Кажется, запись из va_list, то бишь переменных аргументов?..
Какой анскилл )))
Наебал ты меня, нет такой функции, только
Угадал. Какой багор )))
Я сначала вообще подумал, что борманд прикололся.
Удивительно, что массив простых чисел у автора назван «primes», а не «arrayOfFirstNaturalNumbersThatIsNotAPro ductOfSmallerNaturalNumbers».
Автор как бы намекает нам, что благодаря его охуительному стилю наименования код становится самодокоментируемым™, но это нихуя не так. Понять его можно только убрав эту лапшу из методов и добавив вменяемых комментариев.
У меня нет strong opinion, и твой код кажется мне примерно таким же по читаемости
Ну не до маразма же с методами на 3 строчки, которые по-отдельности один хер понять невозможно.
Где-то читал, что метод не должен быть длине трех слов (предлоги не считаются)
Ну это уже форт какой-то.
А х.з., имхо его чувствовать надо. В этом и заключается скилл программиста.
Если ты начинаешь мельчить - полезный код тонет в бойлерплейте от описаний функций и их вызовов. Плюс есть риск разбить простой и понятный фрагмент на куски, которые по-отдельности не понять.
Если ты пишешь портянку - она не входит в экран и её очень сложно осознать и удержать в памяти. Особенно если там куча переменных и происходит что-то нетривиальное.
Надо какой-то середины держаться, чтобы и связанные вещи на куски не порвать (high cohesion) и независимую хуйню в кучу не свалить (low coupling).
Ну я так-то не спорю, что методы нужно называть понятно. Я против возведения принципа «DRY» в ранг религиозной догмы, как это в ТС-коде сделано. Разбивать методы на огрызки по две строки просто потому, что их можно разбить — это, ИМХО, идиотизм. А уж разбивать методы на огрызки по две строки, которые имеют хуеву тучу побочных эффектов — это вообще пиздец какой-то.
Вот, например, «boolean isPrime(int candidate)»: любой вменяемый человек просто по названию и сигнатуре скажет, что это чистая функция. И она даже используется как чистая функция:
Но нет, нихуя, функция с префиксом is у нас мало того, что имеет запутанные побочные эффекты, так ещё и не реентерабельна. Охуеть.
Более того, её вообще нельзя звать джважды для одного и того же числа. И вне цикла generate она вообще неюзабельна т.к. она полагается на эффекты от этого цикла.
Т.е. это какой-нибудь checkCandidate если уж хочется вынести, но никак не isPrime.
Если ты привык видеть SPEED LIMIT, то считываться он будет ничуть не хуже, чем круглый знак с чёрным числом на белом фоне с красной обводкой. Просто потому что опыт и привычка.
Пиктограммы и хитровыделанные обозначения это хорошо, только вот, если говорить про знаки, я никак не могу увидеть логику в 7.1.1 и 7.2.1. Было бы написано словами, сразу стало бы понятнее.
С другой стороны, иконки это хорошо в нашем ёбаном европейском Вавилоне - куда не приедешь, а там круглый знак с чёрным числом на белом фоне с красной обводкой.
Какой артефакт )))
Самый непонятный знак — это «даймонд сайн» — оранжевый квадрат, повёрнутый на угол, внутри которого что-то нарисовано. Жопа в том, что они вообще никак не стандартизированы. Некоторые подобные знаки существуют в единственном экземпляре.
Дональд Кнут во время своего путешествия по США и по Канаде собрал коллекцию «бриллиантовой питушни»:
https://www-cs-faculty.stanford.edu/~knuth/diamondsigns/diam.html
Полный список «diamond signs»:
https://www-cs-faculty.stanford.edu/~knuth/diamondsigns/list.html
Чуть-чуть Канады:
https://www-cs-faculty.stanford.edu/~knuth/diamondsigns/canadian.html
Чуть-чуть Австралии и Новой Зеландии:
https://www-cs-faculty.stanford.edu/~knuth/diamondsigns/australian.html
https://www-cs-faculty.stanford.edu/~knuth/diamondsigns/newzealand.html
З.Ы. Или там какая-то хитрая магия, что обычно 1-2 итерации?
Даже понимая предметную область этот ебаный джавизм очень трудно читать.
УПД: Сейчас в ИДЕ киду, поинлайню методы, посмотрим как он станет НАМНОГО проще.
Оно идёт по нечётным.
3, 9, 15, 21
5, 15, 25, 35
7, 21, 35
А явные составные (чётные) 6, 12, 18 скипает.
Я охуел насколько быдляцкие листинги с кодом там приведены.
Такое ощущение что их студентота насрала.
А ведь многие по этим книгам учатся погромировать, ёпт.
Для candidate == 3 у нас в обоих массивах лежит только джвойка. И в строке primes[multiplesOfPrimeFactors.size()] мы лезем к элементу за этой двойкой. Странная логика.
Точка входа: generate. Но тем не менее это говно и однопоточная питушня.
Второй поток с другим n всё распидорасит.
primes = {2, 0...}
multiplesOfPrimeFactors = {2}
candidate = 3
nextLargerPrimeFactor = primes[1] = 0 <--- читаем хуйню
leastRelevantMultiple = 0
В итоге multiplesOfPrimeFactors.add(candidate) будет вызван только когда кандидат станет равен квадрату нуля. Т.е. никогда.
Код тупо не рабочий.
Какой образец )))
Читал это всё ещё лет 10 назад, некоторые места и даже главы мне совсем не зашли.
Ещё тогда такое чувство было, что там местами хуита написана.
1. Лалка использует массивы, там где их использовать не надо.
>primes[primeIndex++] = candidate;
Ручное петушение с primeIndex, когда есть new ArrayList<Integer>(n);
2. Код принципиально однопоточный
>private static ArrayList<Integer> multiplesOfPrimeFactors;
Мало того что стасики говно, так можно аргументом в isPrime передавать.
Итд.
Если бы речь шла не про праймы, то я обратил бы твое внимание на количество занимаемой памяти.
Самое лучшее решето получается при использовании битовых масок (флаг простое или нет).
Как в класическом алгоритме Эратосфена, идём и зачёркиваем составные.
>количество занимаемой памяти
Оно и здесь довольно хуёвое.
>multiples.add(2);
Но т.к. идём по нечётным то потом начинаем счёт с 1.
>for (int n = 1; n < multiples.size(); n++) {
Зачем? Зачем?
>пофикси код чтобы он работал.
UPD: https://ideone.com/EpdmTi
https://ideone.com/EpdmTi
Какой «Чистый код» )))
А чойта в multiples только двойка валяется после того как алгоритм завершён? Четвёрка там тоже никогда не выпадет.
https://ideone.com/ODWN2t
Но всё равно какой чистый и понятный код )))
И первая отрефакторенная версия тоже.
Я проверил.
Если System.out.println(generate(10));
даёт нормальный результат
[2, 3, 5, 7, 9, 11, 13, 15, 17, 19]
То System.out.println(generate(50)) высирает степени тройки
[2, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]
9
Да оно просто все нечётные вываливает потому что в multiples никогда ничего не суётся и тестить числа нечем.
https://ideone.com/z3WAXz
Потому я за «Си».
А вообще я когда-то реализовывал решето без умножений вообще.
Выделяем bitset интерпретируем его как нечётные.
0 — 3
1 — 5
2 — 7
3 — 9
4 — 11
5 — 13
6 — 15
...
Сначала он забит нулями. 0 - простое, 1 - составное.
Проходим с шагом первого простого элемента (3), записываем во все третьи элементы (9, 15 ,21 ...) признак составного. Потом ищем следующее простое, опять проходим с новым шагом.
Идти нужно до корня из размера bitseta
После чего функция isPrime(n) сводится к 0==bitset[n/2-1]
Тогда нужно было итерироваться только по 2м делителями из 6ти.
1 mod 6
5 mod 6
Превращалось в
MAKAKA говорила про занимаемую память.
Так вот самый компактный способ хранить простые числа нет List<Integer> и не int[].
Самый компактный способ хранить 1/2х байтный дифф. А т.к. дифф всегда чётный, то его ещё можно на 2 поделить.
Т.к. мы в решете обходим их последовательно, то просто суммируем дифф к счётчику.
2 и 3 — простые, но дифф равен 1.
А так да, начиная с пары (3; 5), дифф уже будет чётным.
Ну вот кстати, я смотрю на этот сишный код и он выглядит понятнее, чем исходная джавахуйня с "говорящими" именами.
Оцените энциклопедию целочисленных последовательностей:
https://oeis.org/A000040
https://oeis.org/A065091
Спасибо! Теперь я знаю как выигрывать в казино.
Этим когда-то марили адепты многоядерности.
В реальности перепитушня на синхронизацию программистов съест весь буст пирфоманса.
В итоге 8 человек устроят байкшеддинг на целый день.
А потом оказалось, что 95% алгоритмов искаропки не многопоточны, и 95% реальных примеров программ жрут одно-два ядра, пока все остальные 265 ядер простаивают.
Если команда достаточно большая, а таска тривиальная куча времени уйдёт на обсуждение.
Хорошо паралелятся полтора землекопа, а полтора десятка быдлокодеров асспараллелятся плохо.
Это отлично описано у Брукса:
Мифический человеко-месяц.
Время выполнения проекта не обратно пропорционально числу программистов, по крайней мере по 2 причинам.
В программировании, в отличие от, например, сбора хлопка, работа не может быть произвольно разделена на несколько независимых частей. Части проекта зависят друг от друга, и некоторые задачи можно начинать выполнять только после того, как будут закончены другие. Программисты должны тратить часть времени на взаимодействие друг с другом.
Если есть N программистов, то количество пар программистов равно N(N—1)/2, то есть с ростом числа программистов затраты времени на взаимодействие растут квадратично. Поэтому начиная с какого-то N, рост числа программистов замедляет выполнение проекта.
Если сроки сорваны, наём новых программистов замедляет выполнение проекта и по другой причине: новичкам требуется время на обучение. В книге сформулирован «закон Брукса»: «Если проект не укладывается в сроки, то добавление рабочей силы задержит его ещё больше».
Фактически закон Амдала ИРЛ.
А вот увольнение должно помочь. Оставшиеся получат временный бонус к скиллам и концентрации. Ненадолго правда. И второй раз это уже не работает.
Ну это когда в ЦПУ ядра негетерогенны. Есть одно большое, быстрое ядро с кучей транзисторов, и рядом несколько маленьких с малым энергопотреблением.
Арм давно такое делает. Но Штеуд тоже решил взять на вооружение, и выпустить пятиядерники (intel pentacore).
Разумно, если в группе разработчиков есть один «хороший» программист, реализующий самые критические части системы, и несколько других, помогающих ему или реализующих менее критические части. Так делаются хирургические операции. роме того, по мнению Брукса, лучшие программисты работают в 5-10 раз быстрее остальных.
Отключение ядер тоже часто увеличивает пирформанс.
Особенно в многопроцессорных и NUMA системах, где тратится уйма времени на синхронизацию кешей в разных чипах.
Все потоки попадают на один процессор, улучшается cache locality.
Так что и здесь аналогия полная.
По-научному этот нехитрый факт называется «Закон Амдала»
>удаление НЕНУЖНОЙ многопотчоности иногда увеличивает скорость, бо не тратится время на синхронизацию
А я не рассказывал стори, как пару лет назад оптимизировал плюсовый код?
Нашёл значит я место, hot spot это были вложенные один в другой циклы в которых программа проводила 40% времени.
Программа была однопоточной.
А результаты внутреннего циклы никак друг от друга не зависели, и могли вычисляться в произвольном порядке.
Вот их я и решил раскидать по потокам.
В общем взял я std::launch::async и довольно быстро расспараллелил.
Хотя я сам много стебал шарперов с их LINQ AssParallel(), но мне казалось что буст должен быть, ибо вложенные циклы довольно тяжелые.
Каков же был багор, когда программа стала работать примерно так же как и однопоточная версия (может даже чуть медленее).
Но при этом она жрала примерно 50% на всех 4х ядрах. Ну то есть в джва раза больше ЦПУ, при чуть меньшей скорости!
Ты знал!
Я как раз ниже дописал.
https://govnokod.ru/26791#comment557404
Там и в однопоточной версии, обращения к памяти были довольно хаотичны (хитрая хеш-мапа).
Оказалось что если префетчить следующую итерацию, то количество промахов немного падает.
Не всегда.
Иногда может быть ещё более банальная ситуация, когда объём работы для потока настолько мал, что не превышает накладных расходов на создание future и переключение контекстов.
На что я неоднократно указывал LINQ-питухам. Так и родился мем AssParallel.
https://gcode.space/#!/search?q=assparallel
Ответ, по-моему, очевиден.
Лалки накупили четырёхядерников.
Но как же их использовать?
А! Так тут же Микрософт сделал специальный метод ЖопаПараллель, который ускоряет все программы в четыре раза!
Как тебе такое, Царь?
Исходный тред:
https://govnokod.ru/9194#comment127669
По итогу треда выяснилось что LINQ замедляет вычисления раз в 20 (!), а ЖопаПараллел возвращает 1.5х пирформанса.
Там случалось очень много кеш-промахов.
Так вот пару префетчей помогли гораздо больше чем хвалёная многопоточность.
Но в Линуксе есть perf. Из коробки.
EVENTS=cpu-clock,branches,branch-misses,cache-misses,cache-references,cpu-cycles,instructions,stalled-cycles-backend,stalled-cycles-frontend,ref-cycles,alignment-faults,page-faults,uops_issued.stall_cycles,resource _stalls.any,L1-dcache-load-misses,L1-dcache-loads,LLC-load-misses,LLC-loads,LLC-store-misses,LLC-stores,cycle_activity.stalls_l1d_pending ,cycle_activity.cycles_l2_pending,cycle_ activity.cycles_ldm_pending,cycle_activi ty.cycles_no_execute
Выведет тебе такую статистику:
Ещё есть perf record (записывает в файл такую же статистику, но по каждой функции).
И perf report (рисует красивое дерево вызовов).
Да. У каждого процессора есть специальные счётчики. Оно читает оттуда.
Оверхед почти нулевой.
Полный список можно получить через perf list
У амд раньше было совсем мало.
Типа stalled-cycles-backend, stalled-cycles-frontend
У Штеуда там пара сотень событий со времён Sandy Bridge.
Есть ещё software events, которые считает ОС.
В принципе вот эти базовые события есть почти на любом x64 железе 10-летней давности.
Я когда оптимизировал тот код. То проверял на амд и штеуде.
Были такие случаи, когда простая перестановка операций в цикле или ручной unrolling давал пирфоманс +1-2% на штеуде, и -1% на амд. Или наоборот.
Ещё у них префетчи как-то по-разному работают. Но я вычислил общий знаменатель, выбрал инструкцию которая помогал и там и там.
Штеуд всегда более агрессивно префетчил. Ему емнип не нравилось когда я в L1 ложил.
А тут ещё и очень тонкий трюк с чтением незаполненного слота для тройки, из-за которого я подумал, что код вообще не рабочий. Возможно стоило бы тройку сразу засунуть в результат чтобы лишних вопросов не возникало.
Подтверждаю. Без краткого описания алгоритма в комментарии все вот эти вот «isLeastRelevantMultipleOfNextLargerPrim eFactor()» ни на гран не понятнее сишного кода с «p q m2 k».
Least relevant multiple для простого числа - это его квадрат. Т.е. например первое число, которое имеет смысл тестить на тройку это девять. А на пятёрку - 25. Ибо у меньших чисел будут меньшие делители, которые будут пойманы раньше.
З.Ы. Вот всяко в каком-нибудь numpy есть готовая функция.
> and i > prev_candidate
Зачем? Зачем? Ты же можешь перед главным циклом положить в n единичку а не ноль и тогда можно тупо начать range с prev_candidate + 1, а не пролистывать каждый раз все числа с самого начала.
А в коде из топика другой алгоритм решета, более сложный.
В левом углу ринга Чистый Кот: 10.7 секунд
В правом углу ринга Наивная Хуйня: 2.9 секунды
Ждём пи с цитатой от царя.
UPD: чтобы найти десять миллионов простых чисел решетом, надо сделать решето размером 179'424'673 числа.
> решето размером 179'424'673 числа
Ну собственно отсюда и 180 метров.
I told ya.
https://govnokod.ru/26791#comment557212
>>Самое лучшее решето получается при использовании битовых масок (флаг простое или нет).
>>Как в класическом алгоритме Эратосфена, идём и зачёркиваем составные.
Ищем все 32-битные простые числа. Наивная Хуйня утверждает, что их там 203280221 штук.
Выпьем чаю, послушаем музыку, прогуляемся на балкон, почитаем комменты на гк, поиграем в osu и подождём ответ Чистого Кота...
Наивная Хуйня: 1m40s (4 гига)
Наивная Битуйня: 1m00s (полгига)
Чистый Кот: 17m45s (1.6 гига)
Какое фиаско )))
З.Ы. Блядь лол, наивная реализация настолько наивная, что я там поюзал int вместо байта... Т.е. она 16 гигов жрала вместо не 4. С байтом вообще за минуту все числа вываливает, как и битуйня.
UPD: И это именно тот случай, когда предварительная оптимизация привела к написанию хуйни.
Царь таких лошков раньше пачками сливал.
Ошибка №1: анскильная лалка выбрала джаву.
Ошибка №2: глупый отброс не осилил битовые маски и классический алгоритм тысячелетней давности.
Ошибка №3: отребье написало книгу и начало учить пацанов.
> слиться Наивной Хуйне в 5 строчек одновременно по памяти, пирфомансу, асимптотике и читабельности - это надо постараться
В оригинале к тому же код небезопасен и немногопоточен из-за статических переменных и публикации мутабельного массива из кишок класса.
Я с сишным портом сравнивал. Так что там всё честно.
Но с джавой он обосрался бы ещё сильнее.
А код получился ещё менее читабельный чем аналогичный Сишный (из-за синтаксического мусора protected static, class,)
Пикантности обсёру придаёт тот факт что именно в Жабе отсутствуют const array.
То есть он публикует мутабельное говно. И учит так делать посонов.
У меня на сишной наивности и i7 8700k получилось 30 секунд. Неплохой пирфоманс у коко.
З.Ы. Правда там 5 секунд из них уходит на высирание всех чисел в файл, если его закомментить - то 25.
Ну блоками считай. Я так когда-то делал когда у меня памяти было мало. Хотя это будет уже не так наивно и кратко, конечно.
Добро пожаловать в Царский клуб.
К вашим услугам простой и понятный язык, беспрецедентный пирформанс, минимум синтаксического мусора.
Наименьший общий знаменатель же. Код ограничен возможностями самой хуёвой из платформ. Иначе где-то он не сможет запуститься или будет пиздец неэффективным. Хотели конпелять один раз - вот и жрите говно.
В крестах и сишке ты ведь не от хорошей жизни под каждую платформу заново конпеляешь свой код.
Ага, и пройти по всем граблям, на которые наступали сишники.
Всё-таки текущее решение - наименьшее зло. Массивы на 2 гига мало кому нужны. А если нужны - всегда можно разбить их на блоки. Общий объём памяти то не ограничен. Зато в остальных местах всё консистентно и реально не зависит от платформы.
Шарп же не системный язык, это больше для всякой опердени где не хочется задумываться о низкоуровневых деталях.
Если ты его в аллокатор добавишь, то он собой всю стандартную либу зашкварит. И всем потом придётся в циклах, обращениях к массивам и т.п. его юзать потому что вдруг там больше 2 гигов. А там где не поюзали начнутся баги и краши когда ты захочешь поюзать больше 2 гигов.
Нахуй и впизду. Это реально нинужно в платформе для опердени.
Ты либо обмазываешь все, сука вообще все, в size_t либо даже сравнить его толком не можешь с интом.
И в шарпе тоже не сможешь. Потому что 64-битные числа разного знака он не сравнивает.
Сравни сайзт и инт. Или прибавь инт к сайзт.
Ну не хочет кто-то идти по "обмазываешь все, вообще все".
З.ы. Ну и decimal'ы иногда.
Они по большей части для криптографии и прочего битоёбства, которое на знаковых интах неприятно выглядит.
Ради экономии одного бита в прикладном языке их юзать смысла нет, имхо.
А ксты страшны тем, что читаемость портят. У тебя вместо i < n будет i < (size_t)n. И ты постоянно будешь спотыкаться и забывать их.
А ты предлагаешь ради какого-то мифического случая с 2 гиговым массивом всем другим разрабам поднасрать.
Ради которого ты хочешь заставить бедных шарпеев пердолиться по-сишному. При этом даже не представляешь масштаб проблемы.
Даже если ты движок баз данных пишешь, у тебя будет все небольшими страничками своповаться.
Распарсеный csv это уже явно не один массив а что-то вложенное. А сам парсер будет чанками читать.
А 2 миллиарда строк в ксв - это уже совсем пиздец какой-то.
Это норм на самом деле, чтобы потом всякие ssize_t с горя не городить.
Так что я думаю не упрутся.
Спиздили с Жабы, у которой не было unsigned.
Впрочем есть альтернативная версия, что это разработчик Пасцаля сделал.
На самом деле на ГК это не так давно обсуждали, и пришли к выводу, что таки да, лучше знаковые числа. Ибо потом их передавать в функции и вообще.
А то что в платформе для опердени все абстракции типа Queue, List сделали прибитыми к int32_t это нормально?
Да нормально наверное. Это уже элементы а не байты.
Да и при таком количестве в опердени обычно субд юзают и не ебут мозг.
>Общий объём памяти то не ограничен.
На самом деле это даже хорошо, что язык заставляет программиста использовать странички.
Другое дело что размеры коллекций прибиты гвоздями к 32-битам.
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.count?view=netcore-3.1
А в жабе к int size(), дописали унизительный коммент, в стиле (вы конечно можете засунуть и больше элементов, но size вернёт вам хуйню).
>Есть мнение, что страничнки должен использовать менеджер виртуальной памяти, на худой конец фреймворк
Массив это сполшной кусок памяти.
С этим большие проблемы.
А вот List это абстракция. Но жавашки и шарпушки превратили её в абасракцию.
Какой UB )))
Там не UB, а скорее Math.min(my_real_collection_size, Integer.MAX_VALUE)
https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html#size()
Но самые отборные лулзы начнутся при вызове:
Не помню что там с реализациями этого метоад, но по-моему они используют size() для аллокации массива нужного размера.
Штоблядь?..
…Пиздец, тупо взяли и напрямую спиздили из сишки null-terminated массив. Действительно, нахуя напрягаться и придумывать нормальные, вписывающиеся в архитектуру разрабатываемого языка, интерфейсы, когда можно отключить мозг, спиздить что-то из сишки и потечь?
Да, очень ржачное применение.
Он есть, но им лучше не пользоваться. Ибо он очень хуёвый из-за type erasure.
Точнее есть Object[] toArray(), а чтобы было T нужно передать что-то параметром: Class<T>, T или T[], чтобы оно в рантайме могло взять тип.
Но прикол даже не в этом. А в том что если даже возвращённый Object[] содержит в себе одни лишь только T (что логично, ибо в коллекции других нету) его невозможно превратить в T[] без ПОЛНОГО копирования и malloca ещё одного массива.
И привести этот Object[] обратно в Т[] невозможно никак.
Нет никаких кастов способных это осуществить, как в Сишке или Крестах.
Напоминает жёсткие диски стандарта LBA48, которые при запросе размера по протоколу LBA28 возвращают (2^28-1) секторов (≈ 120 гигабайт) вместо реального размера. Правда, у них есть альтернативная команда, возвращающая полный размер софту, поддерживающему LBA48, а вот в «Йаже», похоже, такого альтернативного метода нет.
int size()
long mysqlreal_collection_size()
Выйдут планки по 2**64 байт?
У меня в 2005 была планка 512 Мб.
К 2025 году, было вполне вероятно увеличение размера обычной планки до 512Гб. 1024 раза за 20 лет.
Методика расчёта здесь:
https://govnokod.ru/26791#comment557605
https://en.wikipedia.org/wiki/Moore%27s_law
Да, dead, потому что мы упёрлись в физические ограничения и поддерживать x2 рост уже не можем.
Ещё лет 10 обещают протянуть, но с меньшими темпами (удвоение плотности в 3-4 года).
Но сам факт что производителей транзисторов из нескольких десятков в 90х, осталось только 2 (TSMC, Samsung) говорит что там всё очень туго.
IBM с AMD отошли в сторону. Да и Штеуд же не от хорошей жизни шестой год стагнирует на 14нм.
Но я же сразу сказал что беру самый оптимистичный из возможных сценарией роста:
>Даже при такой оптимистичной экспоненте
Потому что остальные сценарии роста в перспективе ещё хуже.
Вероятнее всего что в лимит 2**63 байт мы не упрёмся даже через 60 лет.
C-way
Закон Мура помирает потому, что мы упёрлись в физические ограничения. Продолжать Муровский рост можно только уменьшая размер транзистора — а это бесконечно делать нельзя. На единицах нанометров (именно там, где мы сейчас и находимся) в дело вступает, ехидно потирая лапки, квантушня, и радостно начинает туннелировать электроны — вплоть до того, что вместо сигнала получается белый шум.
А из принципиально нового у нас есть только та же самая квантушня, но, как я писал выше, программировать на ЙАЖЕ под неё не будут.
Гы-гы, настоящий плевок в вечность — это «IPv4». ЙАЖУ хоть можно на помойку выкинуть и писать на нормальных языках, а вот взять и отказаться от «IPv4» не получится.
Тогда был кошмар и ужас с зоопарком техники несопоставимых классов.
А материнку ты можешь хоть утопить в этих чипах — всё равно к 2^63 не приблизишься.
Нахуй size_t? Что такое size_t? Зачем он для коллекций?
Это же блять ЙАЖА, зачем мне знать какого размера size_t на конкретной платформе?
Если уж обмазываться абасракциями и жООП лучше интерфейс Number c возможностью вернуть любое число (Int, Long, BigInteger).
>чуть дальше
2**63 — это очень дохуя между прочим.
Да жаба с 4х гиговой коллекцией в куче будет тупить не по-детски. Куча будет гига 32 (Объект минимум 8 байт*4 миллиарда), а задержки гц от stop-the-world секунд по 20.
Сейчас планка 16 ГБ.
Даже при такой оптимистичной экспоненте через 20 лет, среднестатистическая планка будет в 2**10 (1024) раз больше.
То есть всего 16ТБ. Это где-то 2**44. До 2**63 закону Мура нужно ещё лет 60 .
Количество атомов на планете Земля сколько? 10**50?
Даже если из каждого атома сделать по битику, 10**50 бит всё равно это верхний предел выше которого придётся перерабатывать целые планеты на планки памяти для лалок с йажами, хромами, виртуалками и прочей безумной перепитушнёй.
))))))))
Напитон, пидар!
Программируешь на сишке - будь добр помнить что какого размера на какой платформе.
http://pecl.php.net/package/Bitset
Именно поэтому я за «PHP».
Помните, мы ржали над константой PHP_INT_MAX, которая в «высокоуровневом» языке зависит от платформы?
Зачем long? Зачем? Зачем?
Почему не size_t? Почему? Почему?
Увидит long — даст по яйцам.
И они будут в нём.
Только int size будет отдавать хуйню.
> size и vsize
А хер знает что такое size, везде только про vsize и rss пишут.
Approximate amount of swap space that would be required if the process were to dirty all writable pages and then be swapped out. This number is very rough!
Т.е. это vsize за вычетом библиотек и замапанных файлов, которые можно просто выбросить и потом перечитать когда понадобятся.
RSS - это сколько сейчас реально на оперативку замапано
VSIZE - это вся виртуальная память
SIZE - а это только та, которая поддерживается свопом, просто данные по сути
Т.е. например я сейчас файл на 16 гиг на рид-онли замапал. VSIZE стало 16 гигов, а в SIZE и RSS копейки. Затем я его прочитал и RSS вырос до 16 гигов т.к. странички подмапались но SIZE не изменился т.к. они не будут своповаться.
Затем я сделал malloc на 16 гигов. VSIZE и SIZE стали по 16, RSS копейки даже если всё прочитать (ибо zero page). И если я потом в этот массив сру, то RSS тоже догоняется до 16.
> моя собственная r/w память
Похоже что да.
API с запашком говна?