Да, это все хорошо. Проблема в другом :) Меня — заглючило. Решето Эратосфена — про массивы, а не про деревья. Сам алгоритм предполагает, что есть массив. И процесс поиска — это вычеркивание пометок. Эратосфен, думаю, не предполагал, что людям придется вычислять триллион первых простых чисел :), поэтому алгоритм занимает O(n) памяти.
Другое дело, что конструкция array [2..1000000000] of boolean — далеко не самый удачный вариант. А решить можно по разному:
1) разбить лярд на диапазоны сильно скромнее
2) Использовать более сложные структуры данных, например std::vector (TArray)
3) использовать битовые маски.
4) не использовать решето Эратосфена для больших размерностей.
Интересный тест. Кстати, а вектор гарантирует наличие непрерывного куска памяти? Или все же выделяет ее кусочками? Вообще, в теории, у операционки блок какого максимального размера можно запросить?
Комментарий из публикации, перенесённой в черновики.
Значит можно сказать — потенциальный работодатель не умеет давать чёткие ТЗ
… Добро пожаловать в реальный мир :) Не знаю, на счет работодателей, но подавляющее большинство Заказчиков не умеет давать четкие ТЗ и предпочитают играться с формой квадрата.
Не байт, а char. :) sizeof возвращает размер не в байтах, а в char'ах. А размер char'а не обязан быть 1 байт. Т.е. bool в плюсах у вас может спокойно занимать 4 байта.
1 байт. можно ужать в бит, но пострадает скорость доступа к этому счастью.
Если постараться, то скорость пострадает у вас не сильно.
опять же — нет. типичный комп сейчас имеет 8GB рамы. у программеров 16-32 и более.
Если у вас на компе 8Gb, и вы отдаете тут же половину непонятно куда, то отзывчивость вашей системы пострадает ой как сильно. Если у вас x32 (что, слава богу, уже редкость), то вы получите прямой выкидыш по памяти. И это еще вопрос, в x64 вы компилируетесь или в x32. Т.е. даже на 64битной системе можете получить выкидыш.
Разве речь в статье только о домашних ПК? Можно и о супер-компах заботу проявить ;)))
У вас на суперкомпах память быстрее кончится, чем вычислительные возможности. Ну, например, 256Гб памяти — это уже где-то ближе к верхней планке. При этом, этим алгоритмом ее сожрать можно очень быстро.
В win x64 VA для процесса 8TB. И максимальный лимит на swap файл 16TB. т.е. выделить можно
Но то, что оно именно ВЫДЕЛИТСЯ — далеко не факт :) Т.е. вероятность заработать out of memory exception — очень и очень повышается.
не нужно, это да, но можно.
Именно с этого я и начал, пока в маразм не ушел :) Часто вижу, как свежедипломированные специалисты подобными вещами в реальных проектах начинают чудить. А все почему? Потому что 4-6 лет в ВУЗе, если не пьянку пьянствовали, то решали только учебные задачи.
Меня, например, порадовало, как один краснодипломник на тестовом задании в цикле коннекшн к базе устанавливал. Ну там, цикл по количеству элементов в коллекции. На каждой итерации: а) создаем ADO DB com-объект, устанавливаем коннекшн, выполняем запрос.
Вопрос был только один: почему диплом — красный. :)
И это м.б. целью тестирования: как выделяет, насколько быстро и т.д.
В таком случае, это будет тест ядра операционной системы, а не железа/приложения. возможно и реальная задача, но явно не распространенная. Насколько я разбираюсь в колбасных обрезках, обычно нужно протестировать производительность своего разработанного софта. И тут уже не решето Эратосфена применяют, а имитируют нагрузку пользователей. При чем, стараются угадать реальные кейсы.
Не понял: 1 гиг — это много для среднего современного ПК?
А у вас в программе одна единственная структура данных? :) Программа работает в изолированной среде? Ну и потом, а что если ваши аппетиты вырастут и будет не миллиард, а триллион. Аккуратнее надо с числами. Понятно, что пример — учебный. Но в этом и есть проблема. Студенты учатся на учебных примерах и о таких вопросах начинают задумываться не в ВУЗе, а на реальной работе, после десятка-другого неудачных экспериментов. В вашем случае, какие-никакие проверки на память просятся.
1гиг — это еще сильно зависит от реализации. Если бы вы тоже самое писали на c++, то это было бы 4гига. А это уже фатально :)
Битовые маски — это как раз то решение, которое вам имеет смысл использовать. Для дельфи в 8 раз память с экономите. Для плюсов — в 32 раза.
В достаточно крупной задаче есть чего мерять
Это вы уже применение к задаче находите. Но задача формулируется не как «нагрузочное тестирование, на примере решета эратосфена», а именно как поиск простых чисел.
Некая выбранная мера сложности. Например, количество сущностей (или классов, юз-кейсов, акторов и т.д.).
А если у нас для автоматизации всего один небольшой процесс, но о котором на входе в проект мало информации, и нет четких требований и понимания, что в итоге должно получится, то почему бы и не разработать модель?
Ну вот это и есть критерий, как я понимаю. Если нет четких требований и понимания, то моделирование — оправдано. Да, это лучше, чем формальные критерии по количеству элементов системы.
Смотрю делимость на 3 нечетных чисел. В дерево попадает 25.
Про дерево я сморозил глупость. Это тоже напоминание о том, что сперва нужно подумать, а потом — писать :)
Проблема в том, что у любого алгоритма есть свои ограничения.
И если в исходных текстах массив на миллиард элементов — выглядит вполне безобидно, то в скомпилированной программе — это будет сильно. Если вы приводите примеры с такими размерностями, то не мешает задуматься о структурах данных. Например, делить целиковый диапазон на поддиапазоны. Или поискать более экономный по памяти алгоритм.
«Решето Эратосфена» — это, если я правильно помню, алгоритм, который выщитывает простые числа в диапазоне от 2 до N путём вычёркивания в этом диапазоне всех чисел, больше текущего простого числа, которые делятся на это число. Мы начинаем с 2. Следующим простым числом будет первое невычеркнутое число.
Да, прошу прощения — меня заглючило.
Но как бы там ни было, выделение гигабайта памяти — это сильно. А если терабайт потребуется? Тоже так написать? Просто нужно смотреть на применимость алгоритмов. Для больших N — не использовать решето Эратосфена, или бить диапазоны на куски.
если памяти мало — общий диапазон разбивается на под-диапазоны и решето применяется последовательно.
Тьфу-ты, бес попутал :) Прошу пардону. :) Действительно, вся соль решета Эратосфена в потреблении кучи памяти. И хоть какой-то разумный выход — действительно бить большой диапазон на более мелкие.
Но это как раз и говорит о том, что нужно думать, что пишешь: выделить массив на гигабайт просто в качестве примера — это сильно. Если речь идет о таких числах, значит изначально нужно продумывать либо менее требовательный к памяти алгоритм, либо бить задачу на куски.
Тоже самое и про терабайт памяти. Хрен вы его выделите одним куском.
Вам тут очень легко перестараться: размер ОЗУ вы можете узнать у операционки, а вот фрагментацию ОЗУ вы уже не узнаете просто так. Да и еще непонятно, что операционка будет делать с вашими страницами памяти. Возьмет и отправит в своп. И весь ваш бенчмарк слился. Кстати, не могу сказать, что задача оценки производительности стоит «часто».
Первая пришедшая в голову идея. Записываем, нпр., в дерево числа до 1 млн. начинаем удалять
Да у вас вообще не должно быть в дереве лишних элементов!
Изначально — дерево пустое. И функция проверки на простоту для любого числа будет возвращать false.
Затем запускаете алгоритм Эратосфена. Нашли число — добавили его в дерево. Четные числа вообще не надо проверять. Просто в цикле шаг меняете и все.
Перестройка тоже разная бывает. Если задействовано 3 элемента — то ерунда. Ну вставка записей даже в огромную БД не скажу, что прям лагает. Т.е. решаемо.
А есть ли минимальный размер проекта, с которого целесообразно заниматься моделированием? Просто моделирование для простых проектов выглядит моделью ради модели.
Вы не могли бы накидать алгоритм, как можно решето эратосфена на двоичном дереве сделать?
Точно также, как и на массиве, но вместо
sieve[i]
будете писать
getSieve(i)
. Функция getSieve(idx) будет вам возвращать true, если число — простое, и false — В противном случае.
если задача будет стоять найти их с помощью алгоритма эратосфена — то да, буду выделять.
Сильно. Т.е. вас не будет смущать, что, программа у вас тупо вылетит по out of memory exception? И при этом, я вам привел простой путь, как можно разменять память на скорость.
если задача будет стоять найти их с помощью алгоритма эратосфена
Студент? :) На практике у вас не будет стоять задача найти ИМЕННО с помощью такого-то алгоритма. На практике у вас будет задача — РЕШИТЬ задачу корректно и с учетом разумных ограничений по памяти/скорости + доп. ограничения предметной области.
и изначально в нём должны быть все числа. весь миллиард.
Зачем? Вы в дерево можете добавлять элементы динамически. Да, балансировка дерева — это затраты времени. Вопрос в том, что чем больше числа, тем реже будут попадаться простые, соответственно перестройка дерева — относительно редкая операция.
вы алгоритм эратосфена-то видели?
Видел. И что? Ну а если вы захотите триллион простых чисел найти, сразу же терабайт памяти выделять будете? И гарантированно уроните домашнюю систему, и среднестатистический сервер? Или все же будете думать о тех проблемах, которые у вас возникнут? массив и дерево — эквивалентные представления одной и той же структуры данных. А вот свойства их сильно разные. Дерево — занимает ровно столько памяти, сколько необходимо. При этом сложность поиска — логарифмическая. Что не страшно даже для размерностей в триллион.
бинарное дерево может быть хорошо для записи результата работы
Напротив, дерево занимает минимум памяти. И результат работы алгоритма — это еще вопрос, какой должен быть. В консоль весь перечень чисел вы будете выплескивать только на лабораторках в ВУЗе/школе. В реальной работе будут какие-либо вменяемые структуры данных. Список? Дерево? Хэш-таблица? Зависит от потребностей.
Спасибо за статью! Реальные примеры всегда интереснее вымышленных.
Не пробовали оценить, насколько моделирование UML вообще необходимо?
Что проще в данном случае? Написать классическое ТЗ и броситься в бой? Или модели дают реальный выхлоп? Является ли модель заменой ТЗ или по модели затем сочиняется ТЗ?
Как обычно: что нужно — на то и кидаем: нужно ускорить — не постоим за памятью,
А тут еще вопрос, насколько поиск по бинарному дереву тормознее. Да, это лишний log n. Но для миллиарда — это плюс-минус 30 сравнений. А по памяти экономия колоссальная.
В вики, нпр., ссылки, где простоту каждого числа 1 битом кодируют…
Хотя бы. Вы тут от 8 до 32 раз потребление памяти уменьшите. Но скорость несколько уменьшится.
N = 1000000000; // number of primes
var
sieve : array [2..N] of boolean; // false if prime
Волшебно! :) Выкинуть гигабайт памяти непонятно на что :)
Что-то мне подсказывает, что бинарное дерево простых чисел будет занимать радикально меньше памяти.
Как обычно, нужно принимать во внимание не только вычислительную сложность алгоритма, но еще и сложность по памяти. И если миллиард итераций для современных камней — это нормально, то гигабайт памяти на вспомогательную структуру данных — явный перебор.
Т.е. понятие криптостойкости формально применимо даже там, где никакого шифрования нет.
Что-то вы тоже не то говорите. В слове «криптостойкость», есть корень «крипто-», который намекает на устойчивость алгоритмов шифрования к взлому.
Вот с вики:
Криптографическая стойкость (или криптостойкость) — способность криптографического алгоритма противостоять криптоанализу.
Т.е. криптографию — только к шифрованию.
а грязные хаки — это уже не криптография.
Но речь шла о другом. Есть такое направление математики — доказательство корректности программ. Теоретически, подход был придуман как раз для критических отраслей. Вроде авиации, оборонки, космоса и т.д.
Т.е. на любой разработанный алгоритм можно провести его формальное доказательство корректности и убедиться, что он работает именно так, как вы того ожидаете. Подход интересный, но, насколько я знаю, не взлетел. С ростом сложности программ — экспоненциально растет сложность доказательства. Т.е. не применяется.
Лучше удалить эту консоль от греха хотя бы из интерфейса, а то клиент будет лазить, и ненароком наткнется на нее.
Так невозможно конструктор запросов из интерфейса удалить. Правая кнопка — и на те. Это раз. Самое-то интересное, что семерошники в массе своей вообще не умели 8ку. Потому ее просто сторонились, а клиентам объясняли, что еще рано. Вам красоту или ехать? Ну так как-то. Да и даже сейчас, во многих решениях прям в интерфейсе есть универсальный отчет и консоль запросов. Вот прям с трудом представляю, чтобы гендир взял и на коленках сваял что-нибудь интересное. Да, они даже представления не имеют как у них в программе данные хранятся, не то, что SQL знать!
И если почитать, то там написано про обязанность оказать первую помощь, но не написано, как именно эта помощь оказывается. Что не отменяет того, что водитель должен это знать и уметь.
Да. После ледяного дождя: человек не успел пробежать — упал, сосед не успел затормозить.
Таки ABS отказала в этой ситуации? Или ABS — работала, а машина продолжала ехать?
Вы вообще в какой вселенной живёте? Пока ключ вставлен руль не блокируется
В вашей живу, в вашей. Прекрасно блокируется. Чтобы не блокировался — нужно ключ в положение 2 провернуть. А там уже кое-что да запитано.
Особенно хорошо работает на ж/д переезде…
О чем мы спорим? У вас в авто есть аварийный чек-лист на видном месте? А пилоты 2 раза в год тренажер проходят + у них есть QRH всегда с собой + memory items в памяти нужно держать.