Нашли или выдавили из себя код, который нельзя назвать нормальным,
на который без улыбки не взглянешь?
Не торопитесь его удалять или рефакторить, — запостите его на
говнокод.ру, посмеёмся вместе!
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;
}
}
https://habr.com/ru/post/508876/ Вероятно, хватит рекомендовать «Чистый код»
> Я остановлюсь на ещё одном вопиющем примере кода. Это генератор простых чисел из главы 8:
Не называл бы функции так, чтобы их имена приходилось выписывать на отдельной строке.
Но вообще, я не настоящий ма-те-ма-ти-к и с алгоритмами кобенаций генераций простых чисел знаком слабо. А понимать смысл этой ёбанной портянки я решительно отказываюсь, потому что без подсветки тупо не вижу, какие функции вызываются.
Обычно в этой предметной области переменные называются n, f, i, j и k2. ОП - еретик.
З.Ы. Причём подразумевается, что ты знаешь что означают p, q и n в конкретной задаче т.к. они взяты из общеизвестных формул. Никаких комментариев об этом не будет.
Дык понятий много, а букв всего 52 (иногда плюс немного греческих). А учитывая, что большую часть истории ма-те-ма-ти-ки ма-те-ма-ти-ки писали руками на бумаге/пергаменте/etc, традиции называть переменные длинно и понятно как-то не появилось.
Ну вообще конечно код не обязан быть понятным для того, кто не умеет в предметную область.
Если я не знаю, что такое "ip", то нехуя мне лазить в код для работы с сетью.
Если я не знаю, что вероятность это "p", то нехуя мне лазить в код про вероятность.
Так что может быть толика логики тут есть.
Я как-то ковырялся в коде, где не было четкой политики владения.
То-есть каждый раз надо было думать "а кто создал этот объект, а когда мне его удалить, а вдруг не мне, а вдруг он уже удален?".
И это самый пиздецкий пиздец и ад
Делать что-то вручную не смертельно только тогда, когда если ты забудешь что-то сделать — тебя в обязательном порядке отругает конпелятор. Ну, например, когда ты в ЙАЖУ приходишь и целый день пишешь «public void setYetAnotherField(Huj huj); public Huj getYetAnotherField();». Забудешь какой-нибудь очередной «public» — похуй, конпелятор или IDE скажут.
Но совсем другое дело — это когда ошибка в тупой и утомительной рутине приводит к утечкам ресурсов, дедлокам и прочим гейзенбагам. Проблема в том, что человек чисто физически не может все 100% времени быть в абсолютно полной концентрации, он в любом случае её теряет и ошибается. Ну а самое неприятное то, что тупая и утомительная рутина катастрофически снижает концентрацию. Поэтому когда тупая и утомительная рутина является крайне важной частью программирования, ошибки в которой приводят к крайне неприятным и трудноотлавливаемым багам… Ну, это хуёво.
Ручное управление ресурсами а-ля си лучше «RAII» тогда и только тогда, когда над проектом работают исключительно никогда не ошибающиеся сверхлюди. Ну или когда проект — это маленькая программка на 1000 строк (500 из которых занимают ручные выделения/освобождения ресурсов :-), да.
Блин, я помнится писал код про что-то COM'овское. Сишный пример занимал сотни строк и выглядел весьма серьёзно. Большую часть кода там создавали и освобождали комовские строки и массивы и обрабатывали ошибки от всей этой поебени.
В крестах с готовыми RAII обёртками это уместилось в десяток строк.
Ну кстати со вложенными ифами оно не так уж и ужасно будет смотреться. По крайней мере квадратичного роста очисток не будет. Да и нулл в указателе вместо флажка вполне канает.
Да блин) Я не спорю с тем, что у raii есть плюсы, я в том тредике лишь отметил, что они усложняют систему, и за эти плюсы приходится платить. Бесплатных абстракций не бывает.
А тут я сказал, что жить с ручным RC можно, если есть строгие правила когда и что увеличивать.
Если правил нет, то все, пиздец, жить нельзя вообще.
И разумеется я согласен, что бойлерплецт это плохо. Жаве следует сгореть в аду, например
В странах, принявших Венскую конвенцию о дорожном движении, можно увидеть круглый знак с чёрным числом на белом фоне с красной обводкой. Все знают, что это предельно разрешённая скорость в км/ч.
В США же можно увидеть охрененно длинную прямоугольную табличку (такую, что шею сломаешь, пока её всю разглядишь), на которой написано: «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 можно было бы чуть подробнее расписать. А остальное норм, имхо.
Столько страниц — это на случай перехода между сегментами, работающими в разных режимах (разные кольца защиты, разная дефолтная разрядность адреса и данных и т. п.)?
Ну, значит, все багры только от RETF, которая прыгает между сегментами. В случае RETN всё проще (там только исключение может вылететь, если адрес разврата нехороший).
Да, отсутствует одна ветка: у IRET нет версии с «ближним развратом», потому что предугадать, какой сегмент будет текущим, когда сработает прерывание, невозможно.
А помните нашу любимую библиотеку «ncurses» с такими же названиями функций? Там буква «w», в зависимости от расположения, может означать либо уникодный символ («wide char»), либо вывод в окошко («window»).
Реальный пример:
• getstr — ввод «узкого» символа из неограниченной области;
• wgetstr — ввод «узкого» сивола из окошка;
• get_wstr — ввод «широкого» символа из неограниченной области;
• wget_wstr — ввод «широкого» символа из окошка.
Попрошу не путать, а то могут и напутать. Скажут, никакой он не «window», а «wide».
Поддерживаю nemyxa. В попытке понять, какую функцию вызывает «if (isLeastRelevantMultipleOfNextLargerPrim eFactor(candidate))», мне пришлось несколько раз (!) прыгать глазами туда-сюда, сравнивая отдельные части этого шедевра ЙАЖАименования.
Удивительно, что массив простых чисел у автора назван «primes», а не «arrayOfFirstNaturalNumbersThatIsNotAPro ductOfSmallerNaturalNumbers».
private static boolean isPrime(int candidate) {
int nextLargerPrimeFactor = primes[multiplesOfPrimeFactors.size()];
int leastRelevantMultiple = nextLargerPrimeFactor * nextLargerPrimeFactor;
// is Least Relevant Multiple Of Next Larger PrimeFactor
if (candidate == leastRelevantMultiple) {
multiplesOfPrimeFactors.add(candidate);
return false;
}
// is Not Multiple Of Any Previous Prime Factor
for (int n = 1; n < multiplesOfPrimeFactors.size(); n++) {
if (isMultipleOfNthPrimeFactor(candidate, n))
return false;
}
return true;
}
Автор как бы намекает нам, что благодаря его охуительному стилю наименования код становится самодокоментируемым™, но это нихуя не так. Понять его можно только убрав эту лапшу из методов и добавив вменяемых комментариев.
А х.з., имхо его чувствовать надо. В этом и заключается скилл программиста.
Если ты начинаешь мельчить - полезный код тонет в бойлерплейте от описаний функций и их вызовов. Плюс есть риск разбить простой и понятный фрагмент на куски, которые по-отдельности не понять.
Если ты пишешь портянку - она не входит в экран и её очень сложно осознать и удержать в памяти. Особенно если там куча переменных и происходит что-то нетривиальное.
Надо какой-то середины держаться, чтобы и связанные вещи на куски не порвать (high cohesion) и независимую хуйню в кучу не свалить (low coupling).
> правильно назвать метод
Ну я так-то не спорю, что методы нужно называть понятно. Я против возведения принципа «DRY» в ранг религиозной догмы, как это в ТС-коде сделано. Разбивать методы на огрызки по две строки просто потому, что их можно разбить — это, ИМХО, идиотизм. А уж разбивать методы на огрызки по две строки, которые имеют хуеву тучу побочных эффектов — это вообще пиздец какой-то.
Вот, например, «boolean isPrime(int candidate)»: любой вменяемый человек просто по названию и сигнатуре скажет, что это чистая функция. И она даже используется как чистая функция:
int primeIndex = 1;
for (int candidate = 3;
primeIndex < primes.length;
candidate += 2) {
if (isPrime(candidate))
primes[primeIndex++] = candidate;
}
Но нет, нихуя, функция с префиксом is у нас мало того, что имеет запутанные побочные эффекты, так ещё и не реентерабельна. Охуеть.
Более того, её вообще нельзя звать джважды для одного и того же числа. И вне цикла generate она вообще неюзабельна т.к. она полагается на эффекты от этого цикла.
Т.е. это какой-нибудь checkCandidate если уж хочется вынести, но никак не isPrime.
А сколько там в Штатах вообще видов знаков, например?
Если ты привык видеть SPEED LIMIT, то считываться он будет ничуть не хуже, чем круглый знак с чёрным числом на белом фоне с красной обводкой. Просто потому что опыт и привычка.
Пиктограммы и хитровыделанные обозначения это хорошо, только вот, если говорить про знаки, я никак не могу увидеть логику в 7.1.1 и 7.2.1. Было бы написано словами, сразу стало бы понятнее.
С другой стороны, иконки это хорошо в нашем ёбаном европейском Вавилоне - куда не приедешь, а там круглый знак с чёрным числом на белом фоне с красной обводкой.
Самый багор — это знаки 3.1 «Въезд запрещён» и 3.2 «Движение запрещено». Между ними есть разница, и заключается она в списке исключений, кому под этот знак проезжать можно. Эту разницу и пиктограммой сложно выразить, и текстовым списком тоже сложно, ибо он будет очень длинным. Хотя если подумать, для чего их ставят, всё становится логичным. 3.1 («Кирпич») обычно ставят там, где одностороннее движение, направленное в лоб смотрящему на этот знак, а 3.2 (обкусанную редиску) — там, где регулярное движение не организовано и на каждом шагу могут поджидать неприятности.
P.S. 3.1 и 3.2 — это по российским ПДД, конечно. В оригинальной Венской конвенции они обозначались как C1a и C2 соответственно. Почему у номера первого знака суффикс «a»? Потому что допускался вариант «C1b», на котором вместо кирпича была перечёркнутая чёрная стрелка (типа как на знаке «Поворот запрещён», но только прямая).
>> А сколько там в Штатах вообще видов знаков, например?
Самый непонятный знак — это «даймонд сайн» — оранжевый квадрат, повёрнутый на угол, внутри которого что-то нарисовано. Жопа в том, что они вообще никак не стандартизированы. Некоторые подобные знаки существуют в единственном экземпляре.
>Или там какая-то хитрая магия, что обычно 1-2 итерации?
Оно идёт по нечётным.
3, 9, 15, 21
5, 15, 25, 35
7, 21, 35
А явные составные (чётные) 6, 12, 18 скипает.
Эм, они лезут в неинициализированную часть массива primes (ну ок, занулённую раз джава)?
Для candidate == 3 у нас в обоих массивах лежит только джвойка. И в строке primes[multiplesOfPrimeFactors.size()] мы лезем к элементу за этой двойкой. Странная логика.
Да похуй пока на потоки. Что-то мне намекает, что это код вообще не рабочий. Мы же isPrime(3) зовём прямо в generate. И в массивах лежит только двойка.
1. Лалка использует массивы, там где их использовать не надо.
>primes[primeIndex++] = candidate;
Ручное петушение с primeIndex, когда есть new ArrayList<Integer>(n);
2. Код принципиально однопоточный
>private static ArrayList<Integer> multiplesOfPrimeFactors;
Мало того что стасики говно, так можно аргументом в isPrime передавать.
>Ручное петушение с primeIndex, когда есть new ArrayList<Integer>(n);
Если бы речь шла не про праймы, то я обратил бы твое внимание на количество занимаемой памяти.
Я ещё в универе игрался, многократно писал такую хуйню.
Самое лучшее решето получается при использовании битовых масок (флаг простое или нет).
Как в класическом алгоритме Эратосфена, идём и зачёркиваем составные.
>количество занимаемой памяти
Оно и здесь довольно хуёвое.
А, понял. Оно для тройки вылетает за границу и сравнивает с нулевой хуетой. Но потом для следующих чисел там в массиве уже есть тройка и всё норм сравнивается. Пора мне спать.
Сначала он забит нулями. 0 - простое, 1 - составное.
Проходим с шагом первого простого элемента (3), записываем во все третьи элементы (9, 15 ,21 ...) признак составного. Потом ищем следующее простое, опять проходим с новым шагом.
Идти нужно до корня из размера bitseta
После чего функция isPrime(n) сводится к 0==bitset[n/2-1]
А я блоками обрабатывал. Типа делаем битсет метров на сто, выкалываем в нём все составные числа и выписываем из него простые. Потом чистим его и начинаем следующую итерацию.
Малость специальных алгоритмов для их обнаружения. Например, дядя Пи предложил хранить половинки диффов. Двойка выпадает из его системы, её нужно отдельно добавлять вручную.
Как известно, казино невозможно обыграть из-за наличия «zero». Но есть способы наебать онлайн-казино путём создания фейковых акков, собирая бонусы за вход.
Этим когда-то марили адепты многоядерности.
В реальности перепитушня на синхронизацию программистов съест весь буст пирфоманса.
В итоге 8 человек устроят байкшеддинг на целый день.
> Этим когда-то марили адепты многоядерности.
А потом оказалось, что 95% алгоритмов искаропки не многопоточны, и 95% реальных примеров программ жрут одно-два ядра, пока все остальные 265 ядер простаивают.
Так это можно видеть на примере человеческого труда.
Если команда достаточно большая, а таска тривиальная куча времени уйдёт на обсуждение.
Хорошо паралелятся полтора землекопа, а полтора десятка быдлокодеров асспараллелятся плохо.
Это отлично описано у Брукса:
Мифический человеко-месяц.
Время выполнения проекта не обратно пропорционально числу программистов, по крайней мере по 2 причинам.
В программировании, в отличие от, например, сбора хлопка, работа не может быть произвольно разделена на несколько независимых частей. Части проекта зависят друг от друга, и некоторые задачи можно начинать выполнять только после того, как будут закончены другие. Программисты должны тратить часть времени на взаимодействие друг с другом.
Если есть N программистов, то количество пар программистов равно N(N—1)/2, то есть с ростом числа программистов затраты времени на взаимодействие растут квадратично. Поэтому начиная с какого-то N, рост числа программистов замедляет выполнение проекта.
Если сроки сорваны, наём новых программистов замедляет выполнение проекта и по другой причине: новичкам требуется время на обучение. В книге сформулирован «закон Брукса»: «Если проект не укладывается в сроки, то добавление рабочей силы задержит его ещё больше».
Кстати вот читаю и вижу что Брукс изобрёл конь-цеп-цию big.LITTLE задолго до Арма и Штеуда.
Ну это когда в ЦПУ ядра негетерогенны. Есть одно большое, быстрое ядро с кучей транзисторов, и рядом несколько маленьких с малым энергопотреблением.
Арм давно такое делает. Но Штеуд тоже решил взять на вооружение, и выпустить пятиядерники (intel pentacore).
Разумно, если в группе разработчиков есть один «хороший» программист, реализующий самые критические части системы, и несколько других, помогающих ему или реализующих менее критические части. Так делаются хирургические операции. роме того, по мнению Брукса, лучшие программисты работают в 5-10 раз быстрее остальных.
Отключение ядер тоже часто увеличивает пирформанс.
Особенно в многопроцессорных и NUMA системах, где тратится уйма времени на синхронизацию кешей в разных чипах.
Все потоки попадают на один процессор, улучшается cache locality.
>Брукс же имел ввиду, что работа не всегда параллелится.
По-научному этот нехитрый факт называется «Закон Амдала»
>удаление НЕНУЖНОЙ многопотчоности иногда увеличивает скорость, бо не тратится время на синхронизацию
А я не рассказывал стори, как пару лет назад оптимизировал плюсовый код?
Нашёл значит я место, hot spot это были вложенные один в другой циклы в которых программа проводила 40% времени.
Программа была однопоточной.
А результаты внутреннего циклы никак друг от друга не зависели, и могли вычисляться в произвольном порядке.
Вот их я и решил раскидать по потокам.
В общем взял я std::launch::async и довольно быстро расспараллелил.
Хотя я сам много стебал шарперов с их LINQ AssParallel(), но мне казалось что буст должен быть, ибо вложенные циклы довольно тяжелые.
Каков же был багор, когда программа стала работать примерно так же как и однопоточная версия (может даже чуть медленее).
Но при этом она жрала примерно 50% на всех 4х ядрах. Ну то есть в джва раза больше ЦПУ, при чуть меньшей скорости!
>ну это очевидно: если два питуха на разных ядрах тормозят, значит они воюют за общий ресурс
Не всегда.
Иногда может быть ещё более банальная ситуация, когда объём работы для потока настолько мал, что не превышает накладных расходов на создание future и переключение контекстов.
>Зачем вообще LINQ питухи делают ЖопаПараллель не сняв сначала профиль?
Ответ, по-моему, очевиден.
Лалки накупили четырёхядерников.
Но как же их использовать?
А! Так тут же Микрософт сделал специальный метод ЖопаПараллель, который ускоряет все программы в четыре раза!
Как тебе такое, Царь?
Просто когда процесс ждет IO, это легко видно в vmstat даже.
А когда процессор ждет память, то получается, что ОС это вообще не видит: это чисто "железные" заморочки.
Нужно или как-то считывать инфу со счетчиков процессора, или гонять в эмуляторе, не?
круто
а как оно работает? Использует процессороспецифичную пишутню, чтобы считывать cache miss?
Зы: Брендон все объяснил
5.2. Hardware Events (PMCs)
perf_events began life as a tool for instrumenting the processor's performance monitoring unit (PMU) hardware counters, also called performance monitoring counters (PMCs), or performance instrumentation counters (PICs). These instrument low-level processor activity, for example, CPU cycles, instructions retired, memory stall cycles, level 2 cache misses, etc. Some will be listed as Hardware Cache Events.
Правда есть конечно соблазн оптмизировать всё так, что на твоей рабочей машине это будет летать, а на других сосать.
Но в целом полезный инструмент наверное, особенно для хйлоада.
Проблема в том, что реализации ма-те-ма-ти-чес-ких алгоритмов зачастую невозможно понять без знания этоих самых алгоритмов. Хоть ты зарефакторись и обмажь всё говорящими именами. Тут надо или большой подробный коммент перед методом или отсылку к первоисточнику.
А тут ещё и очень тонкий трюк с чтением незаполненного слота для тройки, из-за которого я подумал, что код вообще не рабочий. Возможно стоило бы тройку сразу засунуть в результат чтобы лишних вопросов не возникало.
> Хоть ты зарефакторись и обмажь всё говорящими именами. Тут надо или большой подробный коммент перед методом или отсылку к первоисточнику.
Подтверждаю. Без краткого описания алгоритма в комментарии все вот эти вот «isLeastRelevantMultipleOfNextLargerPrim eFactor()» ни на гран не понятнее сишного кода с «p q m2 k».
Ну да, я их названия понял только когда разобрался в алгоритме.
Least relevant multiple для простого числа - это его квадрат. Т.е. например первое число, которое имеет смысл тестить на тройку это девять. А на пятёрку - 25. Ибо у меньших чисел будут меньшие делители, которые будут пойманы раньше.
решето вообще говоря на пистоне пишется примтивно, зачем тут так много буов?
MAX = 100
non_primes = set()
def next_candidate_after(prev_candidate):
try:
return next(i for i in range(2, MAX) if i not in non_primes and i > prev_candidate)
except StopIteration:
return None
n = 0
while 1:
n = next_candidate_after(n)
if not n:
break
for non_prime in range(n * 2, MAX, n):
non_primes.add(non_prime)
print([i for i in range(MAX) if i not in non_primes])
Зачем? Зачем? Ты же можешь перед главным циклом положить в n единичку а не ноль и тогда можно тупо начать range с prev_candidate + 1, а не пролистывать каждый раз все числа с самого начала.
from bitarray import bitarray
MAX = 4096
non_primes = bitarray('0' * MAX) # 128 bytes
def next_candidate_after(prev_candidate):
try:
return next(i for i in range(prev_candidate + 1, MAX) if not non_primes[i] and i > prev_candidate)
except StopIteration:
return None
n = 1
while 1:
n = next_candidate_after(n)
if not n:
break
for non_prime in range(n * 2, MAX, n):
non_primes[non_prime] = True
print([i for i in range(MAX) if not non_primes[i]])
Ну потому что как была наивная реализация, так и осталась. Твой код и на сишке и на джаве будет почти одинаково читаться. Ну разве что на сишке чуть-чуть битоёбства вокруг массива будет.
А в коде из топика другой алгоритм решета, более сложный.
По идее — книга по читаемому коду оптимизированной версии решета. Подразумевается, что следование правилам из книги поможет сделать даже сложный, ненаивный алгоритм понятным и читаемым (как оказалось — нет, не поможет).
Интересно, что в питухоне из коробки нету битсета, но в pypi нашелся bitarray, которого можно инициализировать нужным количеством бит, и он посчитает сколько нужно байт, и выделит массив. bitarray писан на сях, и потому шустер.
Было бы забавно иметь в питоне аналог паскалевого множества.
Например
foo = {'a', 2, 'x'}
С этого момента в foo можно добавлять только 'a', 2 или 'x'.
В результате у нас и получается битсет размером в лог, ну и добавление в него чего либо это просто задирание нужного бита
А вот в хороших языках бисет из коробки.
Причем ``vec`` можен быть одновременно и lvalue и r.
Perl -- для элиты.
Факт
#!/usr/bin/perl -w
use strict;
use warnings FATAL => 'all';
use v5.30;
use Devel::Size qw(size);
my $scalar;
say size $scalar; # 24
vec($scalar, 200, 1) = 1;
say size $scalar; # 64
say vec $scalar, 200, 1; # 1
say vec $scalar, 201, 1; # 0
>>Самое лучшее решето получается при использовании битовых масок (флаг простое или нет).
>>Как в класическом алгоритме Эратосфена, идём и зачёркиваем составные.
З.Ы. Блядь лол, наивная реализация настолько наивная, что я там поюзал int вместо байта... Т.е. она 16 гигов жрала вместо не 4. С байтом вообще за минуту все числа вываливает, как и битуйня.
Я понял.
Но с джавой он обосрался бы ещё сильнее.
А код получился ещё менее читабельный чем аналогичный Сишный (из-за синтаксического мусора protected static, class,)
Пикантности обсёру придаёт тот факт что именно в Жабе отсутствуют const array.
То есть он публикует мутабельное говно. И учит так делать посонов.
Решил перевести на коко свой супернаивный вариант с питухона.
Но BitSet в жопе получает размером int, так что юзать лонги будет неудобно.
Так как джава -- язык для заедушных анскилябров, и unsigned там нет, пришлось считать числа до Int.MAX_VALUE, тоесть до 2147483648.
Получилось
const val MAX: Int = Int.MAX_VALUE
val nonPrimes = BitSet(MAX)
fun nextCandidateAfter(prevCandidate: Int): Int = (prevCandidate + 1..MAX).firstOrNull { !nonPrimes[it] } ?: -1
fun main() {
val before = System.currentTimeMillis()
var n = 1
while (true) {
n = nextCandidateAfter(n)
if (n == -1) break
val from = n * 2
if (from < 0) break
for (i in from..MAX step n) {
nonPrimes[i] = true
}
}
val primes = ((2..MAX).filterNot { nonPrimes[it] }.toList()).toList()
val time = (System.currentTimeMillis() - before) / 1000
print("First 10: ${primes.subList(0, 10)}, total: ${primes.size}, took $time sec")
}
First 10: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29], total: 105097565, took 61 sec
Если бы у меня была 32-х битная ОС, то вопросов бы не было: на винде ты не можешь выделить более 2 гигов (более 3, при каком-то там ключе), на прыщах видимо тоже, потому что в адресное пространство мапица всякое говно из ос (vdso или как оно там).
А если у меня ОС 64 бита, и 64 гига рэм, то почему я должен страдать?
Наименьший общий знаменатель же. Код ограничен возможностями самой хуёвой из платформ. Иначе где-то он не сможет запуститься или будет пиздец неэффективным. Хотели конпелять один раз - вот и жрите говно.
В крестах и сишке ты ведь не от хорошей жизни под каждую платформу заново конпеляешь свой код.
Ага, и пройти по всем граблям, на которые наступали сишники.
Всё-таки текущее решение - наименьшее зло. Массивы на 2 гига мало кому нужны. А если нужны - всегда можно разбить их на блоки. Общий объём памяти то не ограничен. Зато в остальных местах всё консистентно и реально не зависит от платформы.
Шарп же не системный язык, это больше для всякой опердени где не хочется задумываться о низкоуровневых деталях.
Если ты его в аллокатор добавишь, то он собой всю стандартную либу зашкварит. И всем потом придётся в циклах, обращениях к массивам и т.п. его юзать потому что вдруг там больше 2 гигов. А там где не поюзали начнутся баги и краши когда ты захочешь поюзать больше 2 гигов.
Нахуй и впизду. Это реально нинужно в платформе для опердени.
всмысле ты про питуза, который вместо size_t использовал int?
ну так на момент запиливания С# было очевидно же, что это зло.
Просто представь: пройдет пять лет, у всех будет по 64 гига оперативки, а жаба и .net буду любезно предлагать 32х битные битсеты, причем джава даже 31-нобитный
Да, это пердолинг. Касты снижают читаемость кода. Прикладному программисту надо прикладную задачу решать, а не с кастами пердолиться. Сейчас у него везде знаковые инты и он сыт и доволен.
Правильно ли я понимаю, что с твоей точки зрения unsigned 32, 16 и 64 в .net не нужны? Типа целое, и целое. Да?
Мне вот думается, что касты сами по себе не так страшны, просто в няшной в рантайме ничего не проверяется, и можно так удачно кастануться, что получить 42 (как в твоем примере с инициализацией).
А в C# все проверяется, и там можно кинуть exception, и все будет понятно.
ну вот я хотел сделать решето, и соснул. Это был маргинальный кейс?
Я не понимаю правда масштаб проблемы, потому и спрашиваю.
Я предлагаю иметь отдельный тип size_t и кидать исключение при его коверции неудачной. Так в .net произойдет при попытке скаститься к инту из лонга как мне кажется
Да в общем-то между джвумя гигами и четырьмя нет особой разницы. Оба из них - какая-то рандомно выбранная граница. Если хватило 4 но не хватило 2 - ну это уже какое-то везение, а не дизайн. Завтра уже не хватит.
Датасайнтисты обрабатывают десятки гигабайт, покупают на амазоне специальные машины, и вынуждены потом руками разбивать данные на куски, пердолица, как деды пердолились с сегментированной памятью, когда кусок нельзя было больше сегмента сделать без ебли, говно
int size()
Returns the number of elements in this collection.
If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.
Ага. Ждём когда big data станет реально большой и они запилят в Жабу long size64() или что-то в этом духе.
Но самые отборные лулзы начнутся при вызове:
<T> T[] toArray(T[] a)
Returns an array containing all of the elements in this collection; the runtime type of the returned array is that of the specified array. If the collection fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this collection.
If this collection fits in the specified array with room to spare (i.e., the array has more elements than this collection), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of this collection only if the caller knows that this collection does not contain any null elements.)
If this collection makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.
Не помню что там с реализациями этого метоад, но по-моему они используют size() для аллокации массива нужного размера.
> the element in the array immediately following the end of the collection is set to null.
Штоблядь?..
…Пиздец, тупо взяли и напрямую спиздили из сишки null-terminated массив. Действительно, нахуя напрягаться и придумывать нормальные, вписывающиеся в архитектуру разрабатываемого языка, интерфейсы, когда можно отключить мозг, спиздить что-то из сишки и потечь?
Да охуеть вообще. Что это вообще за тупая хуйня — одновременно и возврат значения, и выходной параметр? Почему бы, блядь, не сделать «T[] toArray()» и «int toArrayInplace(T[] a)»!?
Он есть, но им лучше не пользоваться. Ибо он очень хуёвый из-за type erasure.
Точнее есть Object[] toArray(), а чтобы было T нужно передать что-то параметром: Class<T>, T или T[], чтобы оно в рантайме могло взять тип.
Но прикол даже не в этом. А в том что если даже возвращённый Object[] содержит в себе одни лишь только T (что логично, ибо в коллекции других нету) его невозможно превратить в T[] без ПОЛНОГО копирования и malloca ещё одного массива.
И привести этот Object[] обратно в Т[] невозможно никак.
Нет никаких кастов способных это осуществить, как в Сишке или Крестах.
>> If this collection contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.
Напоминает жёсткие диски стандарта LBA48, которые при запросе размера по протоколу LBA28 возвращают (2^28-1) секторов (≈ 120 гигабайт) вместо реального размера. Правда, у них есть альтернативная команда, возвращающая полный размер софту, поддерживающему LBA48, а вот в «Йаже», похоже, такого альтернативного метода нет.
тогда зачем приводить его в пример?)
Это же значит, что куча бабла будет кинута сейчас на изобретение чего-то принципиально нового для преодаления лимита.
Закон Мура помирает потому, что мы упёрлись в физические ограничения. Продолжать Муровский рост можно только уменьшая размер транзистора — а это бесконечно делать нельзя. На единицах нанометров (именно там, где мы сейчас и находимся) в дело вступает, ехидно потирая лапки, квантушня, и радостно начинает туннелировать электроны — вплоть до того, что вместо сигнала получается белый шум.
А из принципиально нового у нас есть только та же самая квантушня, но, как я писал выше, программировать на ЙАЖЕ под неё не будут.
ну, сейчас нет, а завтра придумают. Когда-то и чипсет казался фантастикой.
Но может быть вы и правы, макака не обязана уметь в физику. Мой консерн был в том, что int в джаве это плевок в вечность, и теперь там везде говно. Теперь на 64битной ОС я ограничен signed int массивом, фу
> int в джаве это плевок в вечность
Гы-гы, настоящий плевок в вечность — это «IPv4». ЙАЖУ хоть можно на помойку выкинуть и писать на нормальных языках, а вот взять и отказаться от «IPv4» не получится.
Неважно. 2^64 байт в обозримом будущем не будет — просто потому, что у классической памяти есть фундаментальные ограничения на плотность записи, а неклассическая — это квантушня, под которую на ЙАЖЕ ничего написать не получится.
Какие бы они ни были, они всё равно обязаны подчиняться законам физики. А законы физики, увы, не позволяют даже на атомарном уровне упаковывать битики.
Очевидно, что чип там занимает весь корпус — иначе бы его в 2.5 уместили.
А материнку ты можешь хоть утопить в этих чипах — всё равно к 2^63 не приблизишься.
Нахуй size_t? Что такое size_t? Зачем он для коллекций?
Это же блять ЙАЖА, зачем мне знать какого размера size_t на конкретной платформе?
Если уж обмазываться абасракциями и жООП лучше интерфейс Number c возможностью вернуть любое число (Int, Long, BigInteger).
>чуть дальше
2**63 — это очень дохуя между прочим.
Да жаба с 4х гиговой коллекцией в куче будет тупить не по-детски. Куча будет гига 32 (Объект минимум 8 байт*4 миллиарда), а задержки гц от stop-the-world секунд по 20.
>зачем мне знать какого размера size_t на конкретной платформе?
Не за чем тебе знать совершенно. Если нужно -- можно бы спросить в рантайме через System. Просто не понятно зачем физически лимитировать размер коллекции.
>секунд по 20
Так я не про сейчас же, я про то, что будет через 15-20 лет
>640K хватит всем.
Количество атомов на планете Земля сколько? 10**50?
Даже если из каждого атома сделать по битику, 10**50 бит всё равно это верхний предел выше которого придётся перерабатывать целые планеты на планки памяти для лалок с йажами, хромами, виртуалками и прочей безумной перепитушнёй.
ну вот в QLC в SSD они уже хранят 4 бита на ячейку же, так что вероятно одно и тоже количество атомов может быть использовано для разного количества бит
Не напоминай. Нарвался я как-то в начале нулевых на динозавра из прошлого века, у которого в BIOS не было «автодетекта» хардов. Если батарейка сядет, «C-H-S» приходилось вбивать вручную (открыв корпус и прочитав на этикетке винчестера либо подобрав), иначе система не загрузится.
у меня в первых прыщах лило не умел LBA, и не мог грузить ядро дальше 1024 цилиндра чтоли (он мулировался разумеется), в итоге прыщи из жопы диска было не загрузить
Да, был такой багор. Разделы, которые ближе к началу нумерации блоков, приходилось беречь под загрузку, а дальние можно было использовать только для данных.
BITSET
Released under the PHP License 3.01
The BitSet library assists by providing a mechanism to manage sets of bits. This
provides a similar API (object-based) to java.util.BitSet with some PHP-specific
flavoring.
Мощность множества ограничена типом long для данной платформы. В 32-битном пыхе это будет 2 гига (потому что в сишке по умолчанию целые питухи знаковые), в 64-битном пыхе это будет дохрена (9223372036854775807).
Помните, мы ржали над константой PHP_INT_MAX, которая в «высокоуровневом» языке зависит от платформы?
use strict;
use v5.22;
my $bitset;
vec($bitset, (2**35), 1) = 1;
vec($bitset, (2**3), 1) = 1;
sleep 10;
$ ps -C "perl" -o vsize
VSZ
4220896
виртуальная память в килобайтах. Правда, больше все равно не взять: пишет аут оф мемори. Толи ограничение перла, толи ядра на один кусок памяти, не разбирался.
Тем не менее, на перле я могу, а на жобе с шарпом -- нет
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 за вычетом библиотек и замапанных файлов, которые можно просто выбросить и потом перечитать когда понадобятся.
ps: вот опять, ну почему такие пидорские маны у прыщей? Нухя не понятно же из man ps что это блядь такое.
Сравним с лучшей в мире OS:
dsiz Data size, in Kilobytes.
maxrss Maximum resident set size (in 1024 byte units).
rss The real memory (resident set) size of the process (in 1024 byte units).
rsz
Alias: rssize. Resident set size + (text size / text use count).
ssiz
Stack size, in Kilobytes.
tsiz
Text size, in Kilobytes.
vsz
Alias: vsize. Virtual size, in Kilobytes.
сука, даже я понял я первого раза.
Почему все самое хорошее и удобное в мире никому не нужно?
RSS - это сколько сейчас реально на оперативку замапано
VSIZE - это вся виртуальная память
SIZE - а это только та, которая поддерживается свопом, просто данные по сути
Т.е. например я сейчас файл на 16 гиг на рид-онли замапал. VSIZE стало 16 гигов, а в SIZE и RSS копейки. Затем я его прочитал и RSS вырос до 16 гигов т.к. странички подмапались но SIZE не изменился т.к. они не будут своповаться.
Затем я сделал malloc на 16 гигов. VSIZE и SIZE стали по 16, RSS копейки даже если всё прочитать (ибо zero page). И если я потом в этот массив сру, то RSS тоже догоняется до 16.
Но вообще, я не настоящий ма-те-ма-ти-к и с алгоритмами кобенаций генераций простых чисел знаком слабо. А понимать смысл этой ёбанной портянки я решительно отказываюсь, потому что без подсветки тупо не вижу, какие функции вызываются.
З.Ы. Причём подразумевается, что ты знаешь что означают p, q и n в конкретной задаче т.к. они взяты из общеизвестных формул. Никаких комментариев об этом не будет.
Они могут иногда по разному писаться, иногда вообще одинаково.
Если я не знаю, что такое "ip", то нехуя мне лазить в код для работы с сетью.
Если я не знаю, что вероятность это "p", то нехуя мне лазить в код про вероятность.
Так что может быть толика логики тут есть.
Смотри не перепутай.
А вот «set0» — это да, жопа какая-то непонятная.
З.Ы. Кто-то там говорил, что RAII не нужен и программист сам справится?
'get0' returns a pointer to some data structure without incrementing reference counters.
ну вот опять же: всё просто и понятно, хотя 0 и 1 не самые приятные названия.
У ябла была раньше тоже такая конвенция, когда ты по названию должен был понять увеличился ли счетчик, чи ни
Ну вроде как ручное кручение счетчика ссылок по явной, простой и хорошо задокументированной это не самая большая проблема.
Делать что-то вручную неприятно, но не смертельно. Если конечно ты точно понимаешь, что делать.
То-есть каждый раз надо было думать "а кто создал этот объект, а когда мне его удалить, а вдруг не мне, а вдруг он уже удален?".
И это самый пиздецкий пиздец и ад
Не... Есть ещё сишная асинхронщина. Тот самый момент, когда ручное управление ресурсами встречается с тредами и коллбеками.
И никто ведь не опишет, что коллбек тебе могут позвать во время 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, то бишь переменных аргументов?..
Какой анскилл )))
Наебал ты меня, нет такой функции, только
А вы еще смеялись над всякими lpcwstr
Угадал. Какой багор )))
Я сначала вообще подумал, что борманд прикололся.
Удивительно, что массив простых чисел у автора назван «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.
Так что и здесь аналогия полная.
Гнидо именно так и объяснял свой GIL.
Брукс же имел ввиду, что работа не всегда параллелится. Да и время на коммуникацию уходит доуха
По-научному этот нехитрый факт называется «Закон Амдала»
>удаление НЕНУЖНОЙ многопотчоности иногда увеличивает скорость, бо не тратится время на синхронизацию
А я не рассказывал стори, как пару лет назад оптимизировал плюсовый код?
Нашёл значит я место, hot spot это были вложенные один в другой циклы в которых программа проводила 40% времени.
Программа была однопоточной.
А результаты внутреннего циклы никак друг от друга не зависели, и могли вычисляться в произвольном порядке.
Вот их я и решил раскидать по потокам.
В общем взял я std::launch::async и довольно быстро расспараллелил.
Хотя я сам много стебал шарперов с их LINQ AssParallel(), но мне казалось что буст должен быть, ибо вложенные циклы довольно тяжелые.
Каков же был багор, когда программа стала работать примерно так же как и однопоточная версия (может даже чуть медленее).
Но при этом она жрала примерно 50% на всех 4х ядрах. Ну то есть в джва раза больше ЦПУ, при чуть меньшей скорости!
а почему так? Они трогали разные места в памяти и засирали общий кеш или не давали контроллеру dram работать?
Ты знал!
Я как раз ниже дописал.
https://govnokod.ru/26791#comment557404
Там и в однопоточной версии, обращения к памяти были довольно хаотичны (хитрая хеш-мапа).
Оказалось что если префетчить следующую итерацию, то количество промахов немного падает.
Врядли это общий IO (ты бы это сразу увидел), значит они воюют за доступ к памяти
Не всегда.
Иногда может быть ещё более банальная ситуация, когда объём работы для потока настолько мал, что не превышает накладных расходов на создание future и переключение контекстов.
На что я неоднократно указывал LINQ-питухам. Так и родился мем AssParallel.
https://gcode.space/#!/search?q=assparallel
Даже если у нас пул потоков (про создание отдельных мы, конечно, не говорим) то и переключение их, и синхронизация это переголова.
Ядерные чуваки вроде иной раз даже синхронизируются бизивейтом, чтобы не тратить ресурсы на создание структур для синхронизации.
Зачем вообще LINQ питухи делают ЖопаПараллель не сняв сначала профиль?
Ответ, по-моему, очевиден.
Лалки накупили четырёхядерников.
Но как же их использовать?
А! Так тут же Микрософт сделал специальный метод ЖопаПараллель, который ускоряет все программы в четыре раза!
Как тебе такое, Царь?
Исходный тред:
https://govnokod.ru/9194#comment127669
По итогу треда выяснилось что LINQ замедляет вычисления раз в 20 (!), а ЖопаПараллел возвращает 1.5х пирформанса.
Я переодически вижу, как чуваки пишут на диск в двадцать потоков. Ну типа чем больше потоков -- тем быстрее должно же быть
Там случалось очень много кеш-промахов.
Так вот пару префетчей помогли гораздо больше чем хвалёная многопоточность.
Просто когда процесс ждет IO, это легко видно в vmstat даже.
А когда процессор ждет память, то получается, что ОС это вообще не видит: это чисто "железные" заморочки.
Нужно или как-то считывать инфу со счетчиков процессора, или гонять в эмуляторе, не?
Но в Линуксе есть 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 (рисует красивое дерево вызовов).
а как оно работает? Использует процессороспецифичную пишутню, чтобы считывать cache miss?
Зы: Брендон все объяснил
5.2. Hardware Events (PMCs)
perf_events began life as a tool for instrumenting the processor's performance monitoring unit (PMU) hardware counters, also called performance monitoring counters (PMCs), or performance instrumentation counters (PICs). These instrument low-level processor activity, for example, CPU cycles, instructions retired, memory stall cycles, level 2 cache misses, etc. Some will be listed as Hardware Cache Events.
даже винда умеет, лол
https://randomascii.wordpress.com/2016/11/27/cpu-performance-counters-on-windows/
Да. У каждого процессора есть специальные счётчики. Оно читает оттуда.
Оверхед почти нулевой.
Полный список можно получить через perf list
У амд раньше было совсем мало.
Типа stalled-cycles-backend, stalled-cycles-frontend
У Штеуда там пара сотень событий со времён Sandy Bridge.
Есть ещё software events, которые считает ОС.
В принципе вот эти базовые события есть почти на любом x64 железе 10-летней давности.
Правда есть конечно соблазн оптмизировать всё так, что на твоей рабочей машине это будет летать, а на других сосать.
Но в целом полезный инструмент наверное, особенно для хйлоада.
зы: вот как у ябла dtrace+instruments
https://www.robertpieta.com/content/images/2019/04/Counters3Formulas.png
Я когда оптимизировал тот код. То проверял на амд и штеуде.
Были такие случаи, когда простая перестановка операций в цикле или ручной unrolling давал пирфоманс +1-2% на штеуде, и -1% на амд. Или наоборот.
Ещё у них префетчи как-то по-разному работают. Но я вычислил общий знаменатель, выбрал инструкцию которая помогал и там и там.
Штеуд всегда более агрессивно префетчил. Ему емнип не нравилось когда я в L1 ложил.
А как питузы жили до того, как появились эти PMC?
Читали мануал к конерктному железу, и пытались всё заранее посчитать?>
А тут ещё и очень тонкий трюк с чтением незаполненного слота для тройки, из-за которого я подумал, что код вообще не рабочий. Возможно стоило бы тройку сразу засунуть в результат чтобы лишних вопросов не возникало.
Подтверждаю. Без краткого описания алгоритма в комментарии все вот эти вот «isLeastRelevantMultipleOfNextLargerPrim eFactor()» ни на гран не понятнее сишного кода с «p q m2 k».
Least relevant multiple для простого числа - это его квадрат. Т.е. например первое число, которое имеет смысл тестить на тройку это девять. А на пятёрку - 25. Ибо у меньших чисел будут меньшие делители, которые будут пойманы раньше.
З.Ы. Вот всяко в каком-нибудь numpy есть готовая функция.
> and i > prev_candidate
Зачем? Зачем? Ты же можешь перед главным циклом положить в n единичку а не ноль и тогда можно тупо начать range с prev_candidate + 1, а не пролистывать каждый раз все числа с самого начала.
Код супернеоптимальный, но кажется что он в тыщу раз понятнее, чем код на джаве
Всё еще читаемее джавы
А в коде из топика другой алгоритм решета, более сложный.
Было бы забавно иметь в питоне аналог паскалевого множества.
Например
С этого момента в foo можно добавлять только 'a', 2 или 'x'.
В результате у нас и получается битсет размером в лог, ну и добавление в него чего либо это просто задирание нужного бита
Причем ``vec`` можен быть одновременно и lvalue и r.
Perl -- для элиты.
Факт
В левом углу ринга Чистый Кот: 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.
То есть он публикует мутабельное говно. И учит так делать посонов.
Но BitSet в жопе получает размером int, так что юзать лонги будет неудобно.
Так как джава -- язык для заедушных анскилябров, и unsigned там нет, пришлось считать числа до Int.MAX_VALUE, тоесть до 2147483648.
Получилось
i7 3770K
У меня на сишной наивности и i7 8700k получилось 30 секунд. Неплохой пирфоманс у коко.
З.Ы. Правда там 5 секунд из них уходит на высирание всех чисел в файл, если его закомментить - то 25.
еще раз обращаю внимание, что я считал не ВСЕ 32хбитные числа
зы: хотел переписать на шарп: там есть unsigned 32bit int, но увы: BitVector там тоже получает размер в signed int.
Какая-то хуйня, если честно.
Или я туплю, или все соснули.
Ну блоками считай. Я так когда-то делал когда у меня памяти было мало. Хотя это будет уже не так наивно и кратко, конечно.
Если бы у меня была 32-х битная ОС, то вопросов бы не было: на винде ты не можешь выделить более 2 гигов (более 3, при каком-то там ключе), на прыщах видимо тоже, потому что в адресное пространство мапица всякое говно из ос (vdso или как оно там).
А если у меня ОС 64 бита, и 64 гига рэм, то почему я должен страдать?
Реально, проще на няшной написать
Добро пожаловать в Царский клуб.
К вашим услугам простой и понятный язык, беспрецедентный пирформанс, минимум синтаксического мусора.
https://docs.unity3d.com/Packages/com.unity.render-pipelines.core@8.0/api/UnityEngine.Rendering.BitArray64.html
CLR такое всё из себя кросссукаплатформенное, но прибито гвоздями к 32м битам. Говно
Наименьший общий знаменатель же. Код ограничен возможностями самой хуёвой из платформ. Иначе где-то он не сможет запуститься или будет пиздец неэффективным. Хотели конпелять один раз - вот и жрите говно.
В крестах и сишке ты ведь не от хорошей жизни под каждую платформу заново конпеляешь свой код.
Или пусть тогда он тупо падает на 32хбитной платформе.
Я срал-ебал 32 бита, мой код никогда не будет работать на такой платфоме, почему у меня int 32 бита?
Половина API принимает int
Ага, и пройти по всем граблям, на которые наступали сишники.
Всё-таки текущее решение - наименьшее зло. Массивы на 2 гига мало кому нужны. А если нужны - всегда можно разбить их на блоки. Общий объём памяти то не ограничен. Зато в остальных местах всё консистентно и реально не зависит от платформы.
Шарп же не системный язык, это больше для всякой опердени где не хочется задумываться о низкоуровневых деталях.
В том месте, где был uint8_t, граблей не было же?
В CLR нет int, там есть UInt32 и Uint64.
int это алиас уровня C# который зачем-то питухи придумали.
Причем не понятно зачем.
Если ты его в аллокатор добавишь, то он собой всю стандартную либу зашкварит. И всем потом придётся в циклах, обращениях к массивам и т.п. его юзать потому что вдруг там больше 2 гигов. А там где не поюзали начнутся баги и краши когда ты захочешь поюзать больше 2 гигов.
Нахуй и впизду. Это реально нинужно в платформе для опердени.
ну так на момент запиливания С# было очевидно же, что это зло.
Просто представь: пройдет пять лет, у всех будет по 64 гига оперативки, а жаба и .net буду любезно предлагать 32х битные битсеты, причем джава даже 31-нобитный
Ты либо обмазываешь все, сука вообще все, в size_t либо даже сравнить его толком не можешь с интом.
И в шарпе тоже не сможешь. Потому что 64-битные числа разного знака он не сравнивает.
Для конвертирования его в int можно сделать спец функцию.
Что плохого в том, что размер массива будет машинозависимый?
Ну типа у меня есть типы с явным указанием размера, и есть size_t.
Если я хочу превратить одно в другое, то я вызываю фунцию, и получаю исключение в случае, если там оверфлоу
Сравни сайзт и инт. Или прибавь инт к сайзт.
Приведи пример бизнес задачи
Ну не хочет кто-то идти по "обмазываешь все, вообще все".
и что я делаю?
я делаю cast.
Точно так же и тут.
Я могу еще более стращный вариант предложить: я иду обычным сишным forом от 0 до size, и хочу индекс куда-то выводить. И опять таки: кастчу.
Ты это называешь обмазыванием?
ну, тогда да, конечно.
Но зачем тогда вообще какие либо числовые типы кроме int? это же тоже пирдолинг.
Надо тогда иметь только Number, и все. Не?
З.ы. Ну и decimal'ы иногда.
Мне вот думается, что касты сами по себе не так страшны, просто в няшной в рантайме ничего не проверяется, и можно так удачно кастануться, что получить 42 (как в твоем примере с инициализацией).
А в C# все проверяется, и там можно кинуть exception, и все будет понятно.
Они по большей части для криптографии и прочего битоёбства, которое на знаковых интах неприятно выглядит.
Ради экономии одного бита в прикладном языке их юзать смысла нет, имхо.
А ксты страшны тем, что читаемость портят. У тебя вместо i < n будет i < (size_t)n. И ты постоянно будешь спотыкаться и забывать их.
Тогда 99% питухов это не аффектнет, а упадет только у тех, кто попытается там сравнить размер десятигигабайтного массива с числом 100
но нахуя оно int получает вместо uint?
почему я не могу иметь массив или битсет даже от 32?
А ты предлагаешь ради какого-то мифического случая с 2 гиговым массивом всем другим разрабам поднасрать.
Это очень простое разделение понятий кмк, любой программист может в него понять.
Можно сделать сахар, чтобы литерал превращался в size_t.
>мифического
ну да, откуда в 2020 году двухгиговый массив..
Ради которого ты хочешь заставить бедных шарпеев пердолиться по-сишному. При этом даже не представляешь масштаб проблемы.
Я не понимаю правда масштаб проблемы, потому и спрашиваю.
Я предлагаю иметь отдельный тип size_t и кидать исключение при его коверции неудачной. Так в .net произойдет при попытке скаститься к инту из лонга как мне кажется
Даже если ты движок баз данных пишешь, у тебя будет все небольшими страничками своповаться.
А почему 32-то? Потому что в 2000-м году (или когда там .net пилили) у x86 была такая адресация?
Распарсеный csv это уже явно не один массив а что-то вложенное. А сам парсер будет чанками читать.
А 2 миллиарда строк в ксв - это уже совсем пиздец какой-то.
Пиздец, не хочу больше быть прикладным программистом
то-есть в этом месте C# программист достаточно умен, чтобы справиться с двумя разными типами, а если это будет не файл, а строка в памяти, то уже нет?
пожалуйста мне минус седьмой элемент массива, и вооон тот объект по адресу -42.
Кажется, что бедный программист запутается еще больше, не?
Это норм на самом деле, чтобы потом всякие ssize_t с горя не городить.
https://docs.microsoft.com/en-us/dotnet/framework/configure-apps/file-schema/runtime/gcallowverylargeobjects-element?redirectedfrom=MSDN
The maximum number of elements in an array is UInt32.MaxValue.
The maximum index in any single dimension is 2,147,483,591
пиздец, еще хуже стало.
Короче, я не могу массив на UInt32.MaxValue. Зато могу массив на -32.
Джава в этом вопросе чеснее даже.
Я считаю, что в какой-то момент .NET и JVM упрутся в это ограничение, и испытают боль.
Так что я думаю не упрутся.
Спиздили с Жабы, у которой не было unsigned.
Впрочем есть альтернативная версия, что это разработчик Пасцаля сделал.
На самом деле на ГК это не так давно обсуждали, и пришли к выводу, что таки да, лучше знаковые числа. Ибо потом их передавать в функции и вообще.
Страшно подумать что было бы, если бы .net начали писать под win16
А то что в платформе для опердени все абстракции типа Queue, List сделали прибитыми к int32_t это нормально?
Вот я питух анскильный, в ваших лоулевелах не силен, знаю только, что у меня на сервере 64 гига, и хочу строчку на три гига в C#, а мне хуй
Да нормально наверное. Это уже элементы а не байты.
Да и при таком количестве в опердени обычно субд юзают и не ебут мозг.
Они не прогаммисты так-то.
Они умеют взять библиотеку готовую, и вызвать три метода
>Общий объём памяти то не ограничен.
На самом деле это даже хорошо, что язык заставляет программиста использовать странички.
Другое дело что размеры коллекций прибиты гвоздями к 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()
то-есть отложить граблю чуть дальше вместо завоза size_t
Ты знаешь сколько RAM будет через 15 лет?
Выйдут планки по 2**64 байт?
Ты в 2005-м году предвидел вот такую планку?
https://www.allhdd.com/memory/pc4-17000/512gb/dell-370-abuu-nrfs/
У меня в 2005 была планка 512 Мб.
К 2025 году, было вполне вероятно увеличение размера обычной планки до 512Гб. 1024 раза за 20 лет.
Методика расчёта здесь:
https://govnokod.ru/26791#comment557605
в 1999 не было еще у всех планок 64
https://en.wikipedia.org/wiki/Moore%27s_law
https://www.cnet.com/news/moores-law-is-dead-nvidias-ceo-jensen-huang-says-at-ces-2019/
Да, dead, потому что мы упёрлись в физические ограничения и поддерживать x2 рост уже не можем.
Ещё лет 10 обещают протянуть, но с меньшими темпами (удвоение плотности в 3-4 года).
Но сам факт что производителей транзисторов из нескольких десятков в 90х, осталось только 2 (TSMC, Samsung) говорит что там всё очень туго.
IBM с AMD отошли в сторону. Да и Штеуд же не от хорошей жизни шестой год стагнирует на 14нм.
Но я же сразу сказал что беру самый оптимистичный из возможных сценарией роста:
>Даже при такой оптимистичной экспоненте
Это же значит, что куча бабла будет кинута сейчас на изобретение чего-то принципиально нового для преодаления лимита.
Потому что остальные сценарии роста в перспективе ещё хуже.
Вероятнее всего что в лимит 2**63 байт мы не упрёмся даже через 60 лет.
Как сделать битсет на 4 гига в джаве-то?
Как получить 2**32 элемент массива?
C-way
Закон Мура помирает потому, что мы упёрлись в физические ограничения. Продолжать Муровский рост можно только уменьшая размер транзистора — а это бесконечно делать нельзя. На единицах нанометров (именно там, где мы сейчас и находимся) в дело вступает, ехидно потирая лапки, квантушня, и радостно начинает туннелировать электроны — вплоть до того, что вместо сигнала получается белый шум.
А из принципиально нового у нас есть только та же самая квантушня, но, как я писал выше, программировать на ЙАЖЕ под неё не будут.
Но может быть вы и правы, макака не обязана уметь в физику. Мой консерн был в том, что int в джаве это плевок в вечность, и теперь там везде говно. Теперь на 64битной ОС я ограничен signed int массивом, фу
Гы-гы, настоящий плевок в вечность — это «IPv4». ЙАЖУ хоть можно на помойку выкинуть и писать на нормальных языках, а вот взять и отказаться от «IPv4» не получится.
IPv6 по-тихоньку внедряют, авось внедрят на нашем веку
Тогда был кошмар и ужас с зоопарком техники несопоставимых классов.
Вполне было реально в НИИ в 1999-м использовать софт под дос 1989-го, а он и на 286-м себе работал.
>никаких подвижек нет
Потому что все идет не равномерно. Пять лет ничего не происходит, потом хуяк
А материнку ты можешь хоть утопить в этих чипах — всё равно к 2^63 не приблизишься.
Этими чипами конено нет (сколько там получается? 8 петабайт?), но прогресс не стоит на месте
Нахуй size_t? Что такое size_t? Зачем он для коллекций?
Это же блять ЙАЖА, зачем мне знать какого размера size_t на конкретной платформе?
Если уж обмазываться абасракциями и жООП лучше интерфейс Number c возможностью вернуть любое число (Int, Long, BigInteger).
>чуть дальше
2**63 — это очень дохуя между прочим.
Да жаба с 4х гиговой коллекцией в куче будет тупить не по-детски. Куча будет гига 32 (Объект минимум 8 байт*4 миллиарда), а задержки гц от stop-the-world секунд по 20.
Не за чем тебе знать совершенно. Если нужно -- можно бы спросить в рантайме через System. Просто не понятно зачем физически лимитировать размер коллекции.
>секунд по 20
Так я не про сейчас же, я про то, что будет через 15-20 лет
Сейчас планка 16 ГБ.
Даже при такой оптимистичной экспоненте через 20 лет, среднестатистическая планка будет в 2**10 (1024) раз больше.
То есть всего 16ТБ. Это где-то 2**44. До 2**63 закону Мура нужно ещё лет 60 .
Короче, я понял.
640K хватит всем.
int size() 32х битного хватит всем
Это очевидно
Количество атомов на планете Земля сколько? 10**50?
Даже если из каждого атома сделать по битику, 10**50 бит всё равно это верхний предел выше которого придётся перерабатывать целые планеты на планки памяти для лалок с йажами, хромами, виртуалками и прочей безумной перепитушнёй.
Меня пока и long бы устроил, а вот int это пиздец
))))))))
Напитон, пидар!
Программируешь на сишке - будь добр помнить что какого размера на какой платформе.
Виртуальная память-то как угодно нарезается (кроме занятых областей).
Сказал джавашок
http://pecl.php.net/package/Bitset
Именно поэтому я за «PHP».
Кстати, в перле битсет из коробки (vec)
Помните, мы ржали над константой PHP_INT_MAX, которая в «высокоуровневом» языке зависит от платформы?
для данного компилятора:)
Зачем long? Зачем? Зачем?
Почему не size_t? Почему? Почему?
Увидит long — даст по яйцам.
от винта
ла-ла-лалалалалала
виртуальная память в килобайтах. Правда, больше все равно не взять: пишет аут оф мемори. Толи ограничение перла, толи ядра на один кусок памяти, не разбирался.
Тем не менее, на перле я могу, а на жобе с шарпом -- нет
И они будут в нём.
Только int size будет отдавать хуйню.
Тогда еще лучше.
А ты неужели реально проверил?
Ты может еще знаешь, чем size и vsize в ps отличается?
Я правда на ноуте, а тут 8 гиг
> size и vsize
А хер знает что такое size, везде только про vsize и rss пишут.
Если спать -- то с королевой
Если скриптовать --то на перле.
RSS это resident set size, то-есть то, что в SDRAM (комитет в террминологии сам знаешь кого).
vsize это размер всей виртуальной памяти (всех таблиц, таблица которых загружена в сам знаешь какой регистр)
На таком уровне и я понимаю.
А что такое size -- хз
size -- это кол-во реально занятой виртуальной памяти. Если vsize кратен рразмеру страницы, то size может быть чуть меньше.
Так вижу. но могу и ошбаться.
Такое вообще реально посчитать?
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 за вычетом библиотек и замапанных файлов, которые можно просто выбросить и потом перечитать когда понадобятся.
пнятно
А по виндовски это как?
Сравним с лучшей в мире OS:
сука, даже я понял я первого раза.
Почему все самое хорошее и удобное в мире никому не нужно?
RSS - это сколько сейчас реально на оперативку замапано
VSIZE - это вся виртуальная память
SIZE - а это только та, которая поддерживается свопом, просто данные по сути
Т.е. например я сейчас файл на 16 гиг на рид-онли замапал. VSIZE стало 16 гигов, а в SIZE и RSS копейки. Затем я его прочитал и RSS вырос до 16 гигов т.к. странички подмапались но SIZE не изменился т.к. они не будут своповаться.
Затем я сделал malloc на 16 гигов. VSIZE и SIZE стали по 16, RSS копейки даже если всё прочитать (ибо zero page). И если я потом в этот массив сру, то RSS тоже догоняется до 16.
Можно сказать, что в случае с файлом это будут грязные страницы мая собственая r/w память?
> моя собственная r/w память
Похоже что да.
Надо поэксперементировать с malloc/mmap, кажется это очень просто, и я сам всё пойму.
Или про ядро дочитать наконец)
седня попробую.
Вот почему, блин, так было не написать в man ps?
комитет следует читать как воркингсет
API с запашком говна?