На моём ПК 60.91 с. Древнющий комп еще с сокетом 1366, 6 ядер (Xeon W3690). Процессор купил года 4 назад потому что было дёшево, хотя сейчас еще дешевле.
БАЙТ.
1_000_000_000_000 бит
каждые 8 бит хранят информацию о 30 числах.
1_000_000_000_000 / 30 = 33_333_333_334 пачек по 8 бит (посделняя 4 на хвостик). Пачка из 8 бит и есть байт
Вы ошибаетесь 1 триллион это 10^12, для 10^12/30 нужно 33_333_333_334 байт, то есть более 33 миллиардов байт. Это примерно 31,044 ГиБ (если поделить на 1024 три раза). Как раз это я и предложил выше.
А вот по номеру так искать конечно не получится.
Поиск по номеру можно легко оптимизировать, сохраняя промежуточные Pi(N) — количество простых чисел не превосходящих данное. Сохранять например одно число на 256 КиБ, то есть на 256102430=7864320 чисел. Это удобно, потому что потребует хранения всего 127157 чисел, а 256 килобайт — отлично ложится в L2 кэш процессора и посчитать биты тм достаточно просто.
И асимптотически такой метод проиграет кодированию интервалов.
Асимптотический проигрыш этой схемы хранения кодированию интервалов совсем не очевиден. На больших значениях интервалы будут расти, а значит будут требовать всё больших значений. При этом "плотность" заполнения битовой маски падает вместе с упомянутым Pi(N), который близок к n/ln(n). То есть очень медленно.
Ещё замечание (извиняюсь за спам).
Простые числа до 2^32 считаются сейчас вовсе не часы, а секунды или даже доли секунды. Это не отменяет того, что дальше считать всё сложнее и сложнее, но до 2^40 просеять не проблема.
Если эта тема интересует, есть primesieve.org, это опенсорсный проект на гитхабе. Там все разъяснения есть.
Для цикла 210 получается 48 значений остатков, т.е. хранить можно 48 бит из 210, это уже 26,6 ГиБ.
Для цикла 2310 получается 480 допустимых значений, это уже 24,19 ГиБ. И это уже лучше вашего результата :)
За старание и за качественное изложение — несомненный плюс.
Но. Но к чему такая сложность? Для простых чисел, если это небольшие числа, то есть если это не всякие порядка 2^256, а как здесь меньше 2^40 вполне годится тупое хренение битовой маски. Есть правда одна «хитрость», но это хитрость достаточно очевидна.
Давай посчитаем. Пусть у нас есть простые до 10е12. Для хранения прямо вот просто битовой маски достаточно 1,25е11 бит. Это сразу же 116 ГиБ. Заметим также, что если взять произведение нескольких простых чисел, то простые числа могут попадать не на все, а только на некоторые остатки от деления на это произведение (кроме самых первых):
2 — только остаток 1
2*3=6 — только остатки 1 и 5
2*3*5=30 — только 1, 7, 11, 13, 17, 19, 23, 29 (8 чисел)
Для 2*3*5*7=210 можно тоже вручную посчитать, даже для 2*3*5*7*11=2310 можно маску сохранить. Дальше выигрыш совершенно несущественный.
В решете Эратосфена эту оптимизацию часто называют wheel optimization. Мы можем хранить не все биты, а только попадающие в остатки. То есть для «колеса» в 30 не все 30 бит, а только 8. Это даёт нам сразу менее 32 ГиБ
Раскодировать такое хранение на несколько порядков проще. Ну и кодировать прямо скажем — не занудно.
На предыдущем месте работы проекты в 500 таблиц (и гора SP, UDF и т.п., понятно) собирались минут 10-20, "большой" проект на 2000 таблиц (и 6000 кажется всего объектов) собирался больше часа на 16 ГБ. После перехода на SSD "всего" 30 минут. Плюс там регулярно 32-битная VS начинает утыкаться в лимит памяти. Если несколько таких проектов зависят друг от друга, то это адский мрак. Короче, формировать адский файл модели данных в XML (это он при компиляции и разборе проекта делает) было не самой лучшей архитектурной идеей.
Мне правда SSDT понравился, и, правда, я не тот кто "просто не умеет готовить", но на наших решениях перейти не получилось.
Кстати, в апгрейдах есть еще одна засада. В SSDT очень легко при разруливании merge conflict потерять историю рефакторинга и вместо аккуратной трансформации таблицы получить "оопс".
Причем обидно, что уже лет 5 SSDT в развитии практически замер (ну или мне так кажется). Если MS его похоронит, будет печаль.
Где-где, в дикой природе и в кровавом энтерпрайзе :)
Ну, это, знаешь, начинается всё с одной затяжки небольшого скрипта для "подготовки проекта к сборке", потом в этом скрипте оказывается много текста и ты выносишь функции в отдельный, потом осознаёшь, что скриптов уже 15 и надо бы их рассовать по папочкам, оп-оп-оп… И через годик смотришь: "Какой чудила наворотил этого монстра?!" :)
Вон, например, минималистичный установщик Manjaro как раз примерно подобного масштаба. При этом он раз в 5 больше большинства установщиков Arch, а делает то же самое — всего-то чуть чуть вариативности и универсальности.
SSDT — прекраснейшая по задумке штука (отделить разработку кода от живой БД — это супер, иметь нормальные code references и рефакторинг — почти бесценно). И для небольших решений подходит, наверное. Но для сколько-то крупных решений это сплошная мука. Вот кратко только то обо что совсем больно спотыкаться.
Разработка решений из нескольких БД/серверов.
Разработка нескольких БД у которых существенная общая часть кода.
Разработка БД больше 1000 объектов (сколько будет собираться решение?).
Разработка БД для нескольких разных версий СУБД.
Разработка с объектами уровня сервера.
Мелочь, а всё-таки, сборка проектов с enterprise фичами.
Модульные тесты SSDT это просто соседнее решение почти обычных UT, которое можно прикрутить к сборке SSDT. Не то чтобы это совсем плохо, но получается достаточно узкая применимость. Навскидку:
Это C# решение, а значит надо, чтобы разработчик базово умел C#.
Сборка под виндой (что уже ограничение), плюс headless сборка SSDT — это та еще румба с бубном.
Тесты хранятся в интерактивно меняемых resx. Как с этим жить с git? Я сам-то умру такое сравнивать/мержить, а уж убедить всю команду так делать… Только если действовать как Каа на бандерлогов, но у меня дар убеждения так не прокачан.
В отличие, например, от tSQLt, у которого кишки нормально спрятаны, у модульных тестов SSDT все кишки разложены в решении. Это лишняя когнитивная нагрузка на разработчика, задача которого "просто написать юнит-тест" прямо сейчас.
Но, повторюсь, если у вас всего объектов <500 и есть еще логика на C#, если всё лежит в одной БД, у которой нет ни вызовов master/msdb, ни вызовов linked server'ов, ни передачи данных из ХП в ХП через временные таблицы, нет требований по автоматизации сборки, то, конечно, попробовать стоит.
Да, там еще и SC36XX и SC37XX (а это вам не SC35XX) по таким смешным ценам проскакивают. Если SSD стоял в DC как системный, то у него пробег может быть меньше объёма (брал несколько SC3700 на 400 таких). Последний из вкусняшек, который так брал — SC3610 на 1,6 ТБ за 200 баксов (пробег ~100 ТБ).
Но а) SMART надо смотреть, б) понимать, что всё равно кот в мешке, в) скорости не рекордные, хотя бы потому что дискам уже 2-3 года, г) удачные предложения совсем не каждый день.
В публичном доступе я пока знаю только одно "исследование" на эту тему. Да, тут только не серверные, а "гражданские", да, только по 1 штуке, да, методика не раскрывает write amplification. Но других открытых данных я пока не видел.
И судя по тем тестам и темпам записи ваш 850 достанется внукам :) Если контроллер не сдохнет.
У PS шаг вправо-шаг влево и натыкаешься на совершенно нечитаемые сообщения об ошибках и синтаксис очень многословный. Мне сначала PS тоже приглянулся, но за красивой оберткой горы граблей: и место шва между нативными и .net приложениями, и куча "защит", и зависимость от сторонних наборов скриптов.
Впрочем, разгребать скрипты на bash 5000 строк и более -тоже глазоломство неприятное.
А как gui мне таки нравится ZSH, особенно Oh My ZSH! с докрученными свистелками и гуделками.
Спорить можно до бесконечности, в любом случае это "было бы" и Борланд опоздал, а задним умом удобно быть умными :)
Но таки мне кажется .NET был явно уже безальтернативен, VB6 явно MS не собирался развивать (а это был очень популярный язык), а С++ MS пытался не развивать (Managed C++ похож на анекдот), но им самим надо же было на чем-то писать. Хотя может именно на этом фоне и надо было форсировать (совместимостью с тем же свежевышедшим C++03, например).
Я посмотрел по Tiobe, он не до конца адекватен, но, да, пожалуй и в 2003 был у них шанс (Deplhi, C#)
Еще лучше — 20. К 2003 году, кажется, пациент был еще жив, но смертельный диагноз уже был. Там же наложились несколько больших движений:
MS выпустила .NET и агрессивно пропихивала его. В 2003 уже было понятно, что .NET надолго и выпущена VS 2003. В 2003 виндовая разработка очень быстро мигрировала на .NET. И потому что C# неплох, и потому что MS пропихивала на место VB/Delphi и прочего.
Хейлсберга Borland зря упустил. Это 1996.
Borland (и все его ипостаси) в 2000-2003 пыталась усидеть на нескольких стульях, по сути проедая драгоценное время. Заигрывания с Qt, Kylix, JBuilder, попытки влезть в .NET отказавшись от Win32, а потом вернуть Win32. Слияния, поглощения, переименования. А по факту после Delphi 6 застой.
Короче, хороший пример то ли отсутствия стратегии, то ли очень неудачной стратегии. А вот в 1998, наверное, можно было успеть сделаться непотопляемыми, раздав официально Community Edition.
1_000_000_000_000 бит
каждые 8 бит хранят информацию о 30 числах.
1_000_000_000_000 / 30 = 33_333_333_334 пачек по 8 бит (посделняя 4 на хвостик). Пачка из 8 бит и есть байт
Markdown съел звёздочки.
Должно быть:
Вы ошибаетесь 1 триллион это 10^12, для 10^12/30 нужно 33_333_333_334 байт, то есть более 33 миллиардов байт. Это примерно 31,044 ГиБ (если поделить на 1024 три раза). Как раз это я и предложил выше.
Поиск по номеру можно легко оптимизировать, сохраняя промежуточные Pi(N) — количество простых чисел не превосходящих данное. Сохранять например одно число на 256 КиБ, то есть на 256102430=7864320 чисел. Это удобно, потому что потребует хранения всего 127157 чисел, а 256 килобайт — отлично ложится в L2 кэш процессора и посчитать биты тм достаточно просто.
Асимптотический проигрыш этой схемы хранения кодированию интервалов совсем не очевиден. На больших значениях интервалы будут расти, а значит будут требовать всё больших значений. При этом "плотность" заполнения битовой маски падает вместе с упомянутым Pi(N), который близок к n/ln(n). То есть очень медленно.
Ещё замечание (извиняюсь за спам).
Простые числа до 2^32 считаются сейчас вовсе не часы, а секунды или даже доли секунды. Это не отменяет того, что дальше считать всё сложнее и сложнее, но до 2^40 просеять не проблема.
Если эта тема интересует, есть primesieve.org, это опенсорсный проект на гитхабе. Там все разъяснения есть.
Для цикла 210 получается 48 значений остатков, т.е. хранить можно 48 бит из 210, это уже 26,6 ГиБ.
Для цикла 2310 получается 480 допустимых значений, это уже 24,19 ГиБ. И это уже лучше вашего результата :)
Но. Но к чему такая сложность? Для простых чисел, если это небольшие числа, то есть если это не всякие порядка 2^256, а как здесь меньше 2^40 вполне годится тупое хренение битовой маски. Есть правда одна «хитрость», но это хитрость достаточно очевидна.
Давай посчитаем. Пусть у нас есть простые до 10е12. Для хранения прямо вот просто битовой маски достаточно 1,25е11 бит. Это сразу же 116 ГиБ. Заметим также, что если взять произведение нескольких простых чисел, то простые числа могут попадать не на все, а только на некоторые остатки от деления на это произведение (кроме самых первых):
2 — только остаток 1
2*3=6 — только остатки 1 и 5
2*3*5=30 — только 1, 7, 11, 13, 17, 19, 23, 29 (8 чисел)
Для 2*3*5*7=210 можно тоже вручную посчитать, даже для 2*3*5*7*11=2310 можно маску сохранить. Дальше выигрыш совершенно несущественный.
В решете Эратосфена эту оптимизацию часто называют wheel optimization. Мы можем хранить не все биты, а только попадающие в остатки. То есть для «колеса» в 30 не все 30 бит, а только 8. Это даёт нам сразу менее 32 ГиБ
Раскодировать такое хранение на несколько порядков проще. Ну и кодировать прямо скажем — не занудно.
Лично я очень надеюсь, что дозреет DataGrip от JetBrains (правда, moscas ?), но пока они сосредоточены на немного другой модели работы разработчика.
На предыдущем месте работы проекты в 500 таблиц (и гора SP, UDF и т.п., понятно) собирались минут 10-20, "большой" проект на 2000 таблиц (и 6000 кажется всего объектов) собирался больше часа на 16 ГБ. После перехода на SSD "всего" 30 минут. Плюс там регулярно 32-битная VS начинает утыкаться в лимит памяти. Если несколько таких проектов зависят друг от друга, то это адский мрак. Короче, формировать адский файл модели данных в XML (это он при компиляции и разборе проекта делает) было не самой лучшей архитектурной идеей.
Мне правда SSDT понравился, и, правда, я не тот кто "просто не умеет готовить", но на наших решениях перейти не получилось.
Кстати, в апгрейдах есть еще одна засада. В SSDT очень легко при разруливании merge conflict потерять историю рефакторинга и вместо аккуратной трансформации таблицы получить "оопс".
Причем обидно, что уже лет 5 SSDT в развитии практически замер (ну или мне так кажется). Если MS его похоронит, будет печаль.
Где-где, в дикой природе и в кровавом энтерпрайзе :)
Ну, это, знаешь, начинается всё с
одной затяжкинебольшого скрипта для "подготовки проекта к сборке", потом в этом скрипте оказывается много текста и ты выносишь функции в отдельный, потом осознаёшь, что скриптов уже 15 и надо бы их рассовать по папочкам, оп-оп-оп… И через годик смотришь: "Какой чудила наворотил этого монстра?!" :)Вон, например, минималистичный установщик Manjaro как раз примерно подобного масштаба. При этом он раз в 5 больше большинства установщиков Arch, а делает то же самое — всего-то чуть чуть вариативности и универсальности.
SSDT — прекраснейшая по задумке штука (отделить разработку кода от живой БД — это супер, иметь нормальные code references и рефакторинг — почти бесценно). И для небольших решений подходит, наверное. Но для сколько-то крупных решений это сплошная мука. Вот кратко только то обо что совсем больно спотыкаться.
Модульные тесты SSDT это просто соседнее решение почти обычных UT, которое можно прикрутить к сборке SSDT. Не то чтобы это совсем плохо, но получается достаточно узкая применимость. Навскидку:
Но, повторюсь, если у вас всего объектов <500 и есть еще логика на C#, если всё лежит в одной БД, у которой нет ни вызовов master/msdb, ни вызовов linked server'ов, ни передачи данных из ХП в ХП через временные таблицы, нет требований по автоматизации сборки, то, конечно, попробовать стоит.
Да, там еще и SC36XX и SC37XX (а это вам не SC35XX) по таким смешным ценам проскакивают. Если SSD стоял в DC как системный, то у него пробег может быть меньше объёма (брал несколько SC3700 на 400 таких). Последний из вкусняшек, который так брал — SC3610 на 1,6 ТБ за 200 баксов (пробег ~100 ТБ).
Но а) SMART надо смотреть, б) понимать, что всё равно кот в мешке, в) скорости не рекордные, хотя бы потому что дискам уже 2-3 года, г) удачные предложения совсем не каждый день.
Я выше кинул ссылку на статью, которую обновляют уже пару лет. Судя по ней — брать Samsung.
В публичном доступе я пока знаю только одно "исследование" на эту тему. Да, тут только не серверные, а "гражданские", да, только по 1 штуке, да, методика не раскрывает write amplification. Но других открытых данных я пока не видел.
И судя по тем тестам и темпам записи ваш 850 достанется внукам :) Если контроллер не сдохнет.
У PS шаг вправо-шаг влево и натыкаешься на совершенно нечитаемые сообщения об ошибках и синтаксис очень многословный. Мне сначала PS тоже приглянулся, но за красивой оберткой горы граблей: и место шва между нативными и .net приложениями, и куча "защит", и зависимость от сторонних наборов скриптов.
Впрочем, разгребать скрипты на bash 5000 строк и более -тоже глазоломство неприятное.
А как gui мне таки нравится ZSH, особенно Oh My ZSH! с докрученными свистелками и гуделками.
Спорить можно до бесконечности, в любом случае это "было бы" и Борланд опоздал, а задним умом удобно быть умными :)
Но таки мне кажется .NET был явно уже безальтернативен, VB6 явно MS не собирался развивать (а это был очень популярный язык), а С++ MS пытался не развивать (Managed C++ похож на анекдот), но им самим надо же было на чем-то писать. Хотя может именно на этом фоне и надо было форсировать (совместимостью с тем же свежевышедшим C++03, например).
Я посмотрел по Tiobe, он не до конца адекватен, но, да, пожалуй и в 2003 был у них шанс (Deplhi, C#)
Еще лучше — 20. К 2003 году, кажется, пациент был еще жив, но смертельный диагноз уже был. Там же наложились несколько больших движений:
Короче, хороший пример то ли отсутствия стратегии, то ли очень неудачной стратегии. А вот в 1998, наверное, можно было успеть сделаться непотопляемыми, раздав официально Community Edition.