• Комментарий из публикации, перенесённой в черновики.
  • Комментарий из публикации, перенесённой в черновики.
  • Комментарий из публикации, перенесённой в черновики.
  • Комментарий из публикации, перенесённой в черновики.
  • Комментарий из публикации, перенесённой в черновики.
  • Комментарий из публикации, перенесённой в черновики.
  • Комментарий из публикации, перенесённой в черновики.
  • Комментарий из публикации, перенесённой в черновики.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    +2
    Если число делится на что-то большее, чем корень из него,

    Как может число делиться нацело на что-то большее корня этого числа? sqrt(N) * sqrt(N)= N

    то, очевидно, оно делится на что-то меньшее.

    С чего вдруг?
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    +1
    Да, это все хорошо. Проблема в другом :) Меня — заглючило. Решето Эратосфена — про массивы, а не про деревья. Сам алгоритм предполагает, что есть массив. И процесс поиска — это вычеркивание пометок. Эратосфен, думаю, не предполагал, что людям придется вычислять триллион первых простых чисел :), поэтому алгоритм занимает O(n) памяти.

    Другое дело, что конструкция array [2..1000000000] of boolean — далеко не самый удачный вариант. А решить можно по разному:
    1) разбить лярд на диапазоны сильно скромнее
    2) Использовать более сложные структуры данных, например std::vector (TArray)
    3) использовать битовые маски.
    4) не использовать решето Эратосфена для больших размерностей.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    Интересный тест. Кстати, а вектор гарантирует наличие непрерывного куска памяти? Или все же выделяет ее кусочками? Вообще, в теории, у операционки блок какого максимального размера можно запросить?
  • Комментарий из публикации, перенесённой в черновики.
  • Чётные числа Фибоначчи
    0
    Значит можно сказать — потенциальный работодатель не умеет давать чёткие ТЗ

    … Добро пожаловать в реальный мир :) Не знаю, на счет работодателей, но подавляющее большинство Заказчиков не умеет давать четкие ТЗ и предпочитают играться с формой квадрата.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    Спасибо, уже разобрался. Странно, факт — элегантный и простейший, но, почему-то в вики про это ни слова.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    +1
    Любые простые числа за исключением 2 и 3 подчиняются простой формуле 6*N ± 1.

    Сомнительное утверждение. Можете это доказать? Особенно про «ВСЕ».
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    я завтра если время будет добавлю свопа

    Так не честно :)

    пройтись по нему. консольная прога, с.с++ win10. результат отпишу

    А винт, случаем, не SSD?
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    Буду, нпр., искать грант на покупку/аренду нужного железа ;)

    Первое, с чего вы начнете, это попытаться оптимизировать алгоритм и выжать максимум из железа, как я понимаю :)
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    Нет. sizeof bool = 1 в сях и плюсах. 1 байт.

    Не байт, а char. :) sizeof возвращает размер не в байтах, а в char'ах. А размер char'а не обязан быть 1 байт. Т.е. bool в плюсах у вас может спокойно занимать 4 байта.

    1 байт. можно ужать в бит, но пострадает скорость доступа к этому счастью.

    Если постараться, то скорость пострадает у вас не сильно.

    опять же — нет. типичный комп сейчас имеет 8GB рамы. у программеров 16-32 и более.

    Если у вас на компе 8Gb, и вы отдаете тут же половину непонятно куда, то отзывчивость вашей системы пострадает ой как сильно. Если у вас x32 (что, слава богу, уже редкость), то вы получите прямой выкидыш по памяти. И это еще вопрос, в x64 вы компилируетесь или в x32. Т.е. даже на 64битной системе можете получить выкидыш.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    Разве речь в статье только о домашних ПК? Можно и о супер-компах заботу проявить ;)))

    У вас на суперкомпах память быстрее кончится, чем вычислительные возможности. Ну, например, 256Гб памяти — это уже где-то ближе к верхней планке. При этом, этим алгоритмом ее сожрать можно очень быстро.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    В win x64 VA для процесса 8TB. И максимальный лимит на swap файл 16TB. т.е. выделить можно

    Но то, что оно именно ВЫДЕЛИТСЯ — далеко не факт :) Т.е. вероятность заработать out of memory exception — очень и очень повышается.

    не нужно, это да, но можно.

    Именно с этого я и начал, пока в маразм не ушел :) Часто вижу, как свежедипломированные специалисты подобными вещами в реальных проектах начинают чудить. А все почему? Потому что 4-6 лет в ВУЗе, если не пьянку пьянствовали, то решали только учебные задачи.
    Меня, например, порадовало, как один краснодипломник на тестовом задании в цикле коннекшн к базе устанавливал. Ну там, цикл по количеству элементов в коллекции. На каждой итерации: а) создаем ADO DB com-объект, устанавливаем коннекшн, выполняем запрос.
    Вопрос был только один: почему диплом — красный. :)
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    И это м.б. целью тестирования: как выделяет, насколько быстро и т.д.

    В таком случае, это будет тест ядра операционной системы, а не железа/приложения. возможно и реальная задача, но явно не распространенная. Насколько я разбираюсь в колбасных обрезках, обычно нужно протестировать производительность своего разработанного софта. И тут уже не решето Эратосфена применяют, а имитируют нагрузку пользователей. При чем, стараются угадать реальные кейсы.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    Не понял: 1 гиг — это много для среднего современного ПК?

    А у вас в программе одна единственная структура данных? :) Программа работает в изолированной среде? Ну и потом, а что если ваши аппетиты вырастут и будет не миллиард, а триллион. Аккуратнее надо с числами. Понятно, что пример — учебный. Но в этом и есть проблема. Студенты учатся на учебных примерах и о таких вопросах начинают задумываться не в ВУЗе, а на реальной работе, после десятка-другого неудачных экспериментов. В вашем случае, какие-никакие проверки на память просятся.

    1гиг — это еще сильно зависит от реализации. Если бы вы тоже самое писали на c++, то это было бы 4гига. А это уже фатально :)
    Битовые маски — это как раз то решение, которое вам имеет смысл использовать. Для дельфи в 8 раз память с экономите. Для плюсов — в 32 раза.

    В достаточно крупной задаче есть чего мерять

    Это вы уже применение к задаче находите. Но задача формулируется не как «нагрузочное тестирование, на примере решета эратосфена», а именно как поиск простых чисел.
  • UML&Enterprise Architect: проектируем целевой процесс при создании автоматизированной системы
    +1
    А что значит «простой» проект?

    Некая выбранная мера сложности. Например, количество сущностей (или классов, юз-кейсов, акторов и т.д.).

    А если у нас для автоматизации всего один небольшой процесс, но о котором на входе в проект мало информации, и нет четких требований и понимания, что в итоге должно получится, то почему бы и не разработать модель?

    Ну вот это и есть критерий, как я понимаю. Если нет четких требований и понимания, то моделирование — оправдано. Да, это лучше, чем формальные критерии по количеству элементов системы.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    Вряд ли бенчмарк будет одним здоровым куском выделять память. Скорее, это будут порции памяти разумного размера.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    Смотрю делимость на 3 нечетных чисел. В дерево попадает 25.

    Про дерево я сморозил глупость. Это тоже напоминание о том, что сперва нужно подумать, а потом — писать :)
    Проблема в том, что у любого алгоритма есть свои ограничения.
    И если в исходных текстах массив на миллиард элементов — выглядит вполне безобидно, то в скомпилированной программе — это будет сильно. Если вы приводите примеры с такими размерностями, то не мешает задуматься о структурах данных. Например, делить целиковый диапазон на поддиапазоны. Или поискать более экономный по памяти алгоритм.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    «Решето Эратосфена» — это, если я правильно помню, алгоритм, который выщитывает простые числа в диапазоне от 2 до N путём вычёркивания в этом диапазоне всех чисел, больше текущего простого числа, которые делятся на это число. Мы начинаем с 2. Следующим простым числом будет первое невычеркнутое число.

    Да, прошу прощения — меня заглючило.
    Но как бы там ни было, выделение гигабайта памяти — это сильно. А если терабайт потребуется? Тоже так написать? Просто нужно смотреть на применимость алгоритмов. Для больших N — не использовать решето Эратосфена, или бить диапазоны на куски.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    если памяти мало — общий диапазон разбивается на под-диапазоны и решето применяется последовательно.

    Тьфу-ты, бес попутал :) Прошу пардону. :) Действительно, вся соль решета Эратосфена в потреблении кучи памяти. И хоть какой-то разумный выход — действительно бить большой диапазон на более мелкие.
    Но это как раз и говорит о том, что нужно думать, что пишешь: выделить массив на гигабайт просто в качестве примера — это сильно. Если речь идет о таких числах, значит изначально нужно продумывать либо менее требовательный к памяти алгоритм, либо бить задачу на куски.
    Тоже самое и про терабайт памяти. Хрен вы его выделите одним куском.
  • UML&Enterprise Architect: проектируем целевой процесс при создании автоматизированной системы
    0
    Что мешает собрать модель и после сгенерирвать код, сэкономив время

    Что такое генерация кода по модели? Каркасы классов накидать и заглушек методов повставлять?
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    часто сознательно загружая ОЗУ.

    Вам тут очень легко перестараться: размер ОЗУ вы можете узнать у операционки, а вот фрагментацию ОЗУ вы уже не узнаете просто так. Да и еще непонятно, что операционка будет делать с вашими страницами памяти. Возьмет и отправит в своп. И весь ваш бенчмарк слился. Кстати, не могу сказать, что задача оценки производительности стоит «часто».
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    Первая пришедшая в голову идея. Записываем, нпр., в дерево числа до 1 млн. начинаем удалять

    Да у вас вообще не должно быть в дереве лишних элементов!
    Изначально — дерево пустое. И функция проверки на простоту для любого числа будет возвращать false.
    Затем запускаете алгоритм Эратосфена. Нашли число — добавили его в дерево. Четные числа вообще не надо проверять. Просто в цикле шаг меняете и все.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    Перестройка тоже разная бывает. Если задействовано 3 элемента — то ерунда. Ну вставка записей даже в огромную БД не скажу, что прям лагает. Т.е. решаемо.
  • UML&Enterprise Architect: проектируем целевой процесс при создании автоматизированной системы
    0
    А есть ли минимальный размер проекта, с которого целесообразно заниматься моделированием? Просто моделирование для простых проектов выглядит моделью ради модели.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    +2
    Вы не могли бы накидать алгоритм, как можно решето эратосфена на двоичном дереве сделать?

    Точно также, как и на массиве, но вместо
    sieve[i]
    будете писать
    getSieve(i)
    . Функция getSieve(idx) будет вам возвращать true, если число — простое, и false — В противном случае.

    если задача будет стоять найти их с помощью алгоритма эратосфена — то да, буду выделять.

    Сильно. Т.е. вас не будет смущать, что, программа у вас тупо вылетит по out of memory exception? И при этом, я вам привел простой путь, как можно разменять память на скорость.

    если задача будет стоять найти их с помощью алгоритма эратосфена

    Студент? :) На практике у вас не будет стоять задача найти ИМЕННО с помощью такого-то алгоритма. На практике у вас будет задача — РЕШИТЬ задачу корректно и с учетом разумных ограничений по памяти/скорости + доп. ограничения предметной области.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    0
    ну а как вы обходить то это дерево будете?

    Бинарным поиском.

    и изначально в нём должны быть все числа. весь миллиард.

    Зачем? Вы в дерево можете добавлять элементы динамически. Да, балансировка дерева — это затраты времени. Вопрос в том, что чем больше числа, тем реже будут попадаться простые, соответственно перестройка дерева — относительно редкая операция.

    вы алгоритм эратосфена-то видели?

    Видел. И что? Ну а если вы захотите триллион простых чисел найти, сразу же терабайт памяти выделять будете? И гарантированно уроните домашнюю систему, и среднестатистический сервер? Или все же будете думать о тех проблемах, которые у вас возникнут? массив и дерево — эквивалентные представления одной и той же структуры данных. А вот свойства их сильно разные. Дерево — занимает ровно столько памяти, сколько необходимо. При этом сложность поиска — логарифмическая. Что не страшно даже для размерностей в триллион.

    бинарное дерево может быть хорошо для записи результата работы

    Напротив, дерево занимает минимум памяти. И результат работы алгоритма — это еще вопрос, какой должен быть. В консоль весь перечень чисел вы будете выплескивать только на лабораторках в ВУЗе/школе. В реальной работе будут какие-либо вменяемые структуры данных. Список? Дерево? Хэш-таблица? Зависит от потребностей.
  • UML&Enterprise Architect: проектируем целевой процесс при создании автоматизированной системы
    0
    Спасибо за статью! Реальные примеры всегда интереснее вымышленных.
    Не пробовали оценить, насколько моделирование UML вообще необходимо?
    Что проще в данном случае? Написать классическое ТЗ и броситься в бой? Или модели дают реальный выхлоп? Является ли модель заменой ТЗ или по модели затем сочиняется ТЗ?
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    –1
    Как обычно: что нужно — на то и кидаем: нужно ускорить — не постоим за памятью,

    А тут еще вопрос, насколько поиск по бинарному дереву тормознее. Да, это лишний log n. Но для миллиарда — это плюс-минус 30 сравнений. А по памяти экономия колоссальная.

    В вики, нпр., ссылки, где простоту каждого числа 1 битом кодируют…

    Хотя бы. Вы тут от 8 до 32 раз потребление памяти уменьшите. Но скорость несколько уменьшится.
  • Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии
    +2
     N = 1000000000; // number of primes
    var
     sieve : array [2..N] of boolean; // false if prime

    Волшебно! :) Выкинуть гигабайт памяти непонятно на что :)

    Что-то мне подсказывает, что бинарное дерево простых чисел будет занимать радикально меньше памяти.

    Как обычно, нужно принимать во внимание не только вычислительную сложность алгоритма, но еще и сложность по памяти. И если миллиард итераций для современных камней — это нормально, то гигабайт памяти на вспомогательную структуру данных — явный перебор.
  • Авария Boeing 737 Max глазами разработчика ПО
    0
    Т.е. понятие криптостойкости формально применимо даже там, где никакого шифрования нет.

    Что-то вы тоже не то говорите. В слове «криптостойкость», есть корень «крипто-», который намекает на устойчивость алгоритмов шифрования к взлому.

    Вот с вики:
    Криптографическая стойкость (или криптостойкость) — способность криптографического алгоритма противостоять криптоанализу.

    Т.е. криптографию — только к шифрованию.
    а грязные хаки — это уже не криптография.

    Но речь шла о другом. Есть такое направление математики — доказательство корректности программ. Теоретически, подход был придуман как раз для критических отраслей. Вроде авиации, оборонки, космоса и т.д.

    Т.е. на любой разработанный алгоритм можно провести его формальное доказательство корректности и убедиться, что он работает именно так, как вы того ожидаете. Подход интересный, но, насколько я знаю, не взлетел. С ростом сложности программ — экспоненциально растет сложность доказательства. Т.е. не применяется.
  • Хабро-самоубийство. Боль планирования в 1С
    0
    Лучше удалить эту консоль от греха хотя бы из интерфейса, а то клиент будет лазить, и ненароком наткнется на нее.

    Так невозможно конструктор запросов из интерфейса удалить. Правая кнопка — и на те. Это раз. Самое-то интересное, что семерошники в массе своей вообще не умели 8ку. Потому ее просто сторонились, а клиентам объясняли, что еще рано. Вам красоту или ехать? Ну так как-то. Да и даже сейчас, во многих решениях прям в интерфейсе есть универсальный отчет и консоль запросов. Вот прям с трудом представляю, чтобы гендир взял и на коленках сваял что-нибудь интересное. Да, они даже представления не имеют как у них в программе данные хранятся, не то, что SQL знать!
  • Авария Boeing 737 Max глазами разработчика ПО
    0
    п 2.5 §2

    И если почитать, то там написано про обязанность оказать первую помощь, но не написано, как именно эта помощь оказывается. Что не отменяет того, что водитель должен это знать и уметь.

    Да. После ледяного дождя: человек не успел пробежать — упал, сосед не успел затормозить.

    Таки ABS отказала в этой ситуации? Или ABS — работала, а машина продолжала ехать?

    Вы вообще в какой вселенной живёте? Пока ключ вставлен руль не блокируется

    В вашей живу, в вашей. Прекрасно блокируется. Чтобы не блокировался — нужно ключ в положение 2 провернуть. А там уже кое-что да запитано.

    Особенно хорошо работает на ж/д переезде…

    О чем мы спорим? У вас в авто есть аварийный чек-лист на видном месте? А пилоты 2 раза в год тренажер проходят + у них есть QRH всегда с собой + memory items в памяти нужно держать.