Многопоточный генератор Мандельброта Ver 2

Обновить : Версия 3 здесь .

Моя первая версия была ответом, который я предоставил EBrown для своего оригинального сообщения под названием «Многопоточный мандельброт Генератор ". В моем ответе было много хороших вещей, но я чувствовал, что некоторые части кода были слабыми, особенно вокруг моих усилий по применению некоторого гибкого масштабирования, а не использования константы 2. Эта версия устраняет эти недостатки, подтягивает некоторый код и упростило многопоточность.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

// Original CodeReview Question:
// https://codereview.stackexchange.com/questions/104171/multithreaded-mandelbrot-generator

// Interesting link about coloring:
// http://www.fractalforums.com/programming/newbie-how-to-map-colors-in-the-mandelbrot-set/

// Trusty Wikipedia:
// https://en.wikipedia.org/wiki/Mandelbrot_set

namespace Mandelbrot_Generator
{
    public class MandelbrotGeneratorV2
    {
        // Readonly properties to be set in constructor
        public int Width { get; }
        public int Height { get; }
        public short MaxIterations { get; }
        public float ScaleFactor { get; }

        private short[] _iterationsPerPixel = null;
        private Point _center;
        private SizeF _scaleSize;
        private float _scaleSquared;

        public MandelbrotGeneratorV2(int height, short maxIterations, float scaleFactor = 2.0F)
        {
            // Use some very basic level limit checking using some arbitrary (but practical) limits.
            const int heightLow = 512;
            const int heightHigh = 4096 * 2;
            const short iterationLow = 100;
            const short iterationHigh = 32000;
            const float scaleLow = 1.0F;
            const float scaleHigh = 8.0F;

            CheckLimits(nameof(height), height, heightLow, heightHigh);
            CheckLimits(nameof(maxIterations), maxIterations, iterationLow, iterationHigh);
            CheckLimits(nameof(scaleFactor), scaleFactor, scaleLow, scaleHigh);

            ScaleFactor = scaleFactor;
            Width = (int)(scaleFactor * height);
            Height = height;
            MaxIterations = maxIterations;

            _center = new Point(Width / 2, Height / 2);

            // And we'll scale the size so the brot sits within region [-ScaleFactor,ScaleFactor], 
            _scaleSquared = ScaleFactor * ScaleFactor;
            _scaleSize = new SizeF(_center.X / ScaleFactor, _center.Y);
        }

        private void CheckLimits(string name, double value, double inclusiveLow, double inclusiveHigh)
        {
            if (value < inclusiveLow || value > inclusiveHigh)
            {
                throw new ArgumentOutOfRangeException(name, $"Argument must be between {inclusiveLow} and {inclusiveHigh} inclusively.");
            }
        }

        public void Generate()
        {
            _iterationsPerPixel = new short[Width * Height];

            var sections = GetHoriztonalSections();

            Parallel.ForEach(sections, section =>
            {
                var data = GenerateSection(section);

                for (var y = section.Start.Y; y < section.End.Y; y++)
                {
                    var brotOffset = y * Width;
                    var dataOffset = (y - section.Start.Y) * Width;

                    for (var x = 0; x < Width; x++)
                    {
                        _iterationsPerPixel[brotOffset + x] = data[dataOffset + x];
                    }
                }
            });
        }

        public void SaveImage(string filename) => SaveImage(filename, ImageFormat.Png);

        public void SaveImage(string filename, ImageFormat imageFormat)
        {
            if (_iterationsPerPixel == null || _iterationsPerPixel.Length == 0)
            {
                throw new Exception("You must create the Mandelbrot data set before you can save the image to file.");
            }

            // Create our image.
            using (Bitmap image = new Bitmap(Width, Height))
            {
                for (var y = 0; y < Height; y++)
                {
                    var brotOffset = y * Width;

                    for (var x = 0; x < Width; x++)
                    {
                        image.SetPixel(x, y, LookupColor(_iterationsPerPixel[brotOffset + x]));
                    }
                }

                image.Save(filename, imageFormat);
            }
        }

        // Coloring is probably has the greatest potential for further improvements.
        // This is just one attempt that suffices for now.
        private Color LookupColor(short iterations)
        {
            if (iterations >= MaxIterations)
            {
                return Color.Black;
            }
            if (iterations < 64)
            {
                return Color.FromArgb(255, iterations * 2, 0, 0);
            }
            if (iterations < 128)
            {
                return Color.FromArgb(255, (((iterations - 64) * 128) / 126) + 128, 0, 0);
            }
            if (iterations < 256)
            {
                return Color.FromArgb(255, (((iterations - 128) * 62) / 127) + 193, 0, 0);
            }
            if (iterations < 512)
            {
                return Color.FromArgb(255, 255, (((iterations - 256) * 62) / 255) + 1, 0);
            }
            if (iterations < 1024)
            {
                return Color.FromArgb(255, 255, (((iterations - 512) * 63) / 511) + 64, 0);
            }
            if (iterations < 2048)
            {
                return Color.FromArgb(255, 255, (((iterations - 1024) * 63) / 1023) + 128, 0);
            }
            if (iterations < 4096)
            {
                return Color.FromArgb(255, 255, (((iterations - 2048) * 63) / 2047) + 192, 0);
            }
            return Color.FromArgb(255, 255, 255, 0);
        }

        private struct Section
        {
            public Point Start { get; }
            public Point End { get; }

            // The way I create sections, End.Y will always be greater than Start.Y
            // but the math nerd in me insists on using Math.Abs() anyway.
            public int Height => Math.Abs(End.Y - Start.Y);
            public int Width => Math.Abs(End.X - Start.X);

            public Section(Point start, Point end)
            {
                Start = start;
                End = end;
            }
        }

        private Section[] GetHoriztonalSections()
        {
            var sections = new Section[2 * Environment.ProcessorCount];

            var heightPerSection = Height / sections.Length;

            if (Height % sections.Length > 0) { heightPerSection++; }

            for (var i = 0; i < sections.Length - 1; i++)
            {
                var startY = heightPerSection * i;
                sections[i] = new Section(new Point(0, startY), new Point(Width, startY + heightPerSection));
            }

            // SPECIAL TREATMENT FOR LAST SECTION:
            // The width is the same per section, namely the image's Width,
            // but the very last section's height could be different since 
            // it's upper rightmost point really should be clamped to the image's boundaries.
            {
                var lastIndex = sections.Length - 1;
                var startY = heightPerSection * lastIndex ;
                sections[lastIndex] = new Section(new Point(0, startY), new Point(Width, Height));
            }

            return sections;
        }

        private short[] GenerateSection(Section section)
        {
            // The sectionWidth is the same value as Width but for some odd reason
            // using Width is noticeably faster on my 8-core PC.  This is true even
            // if I create a local copy such as:
            //      var sectionWidth = section.Width;
            var data = new short[section.Height * Width];

            for (var y = section.Start.Y; y < section.End.Y; y++)
            {
                var indexOffset = (y - section.Start.Y) * Width;
                var anchorY = (y - _center.Y) / _scaleSize.Height;

                for (var x = section.Start.X; x < section.End.X; x++)
                {
                    // The formula for a mandelbrot is z = z^2 + c, basically. We must relate that in code.
                    var anchorX = (x - _center.X) / _scaleSize.Width;

                    short iteration;
                    float xTemp = 0;
                    float yTemp = 0;
                    float xSquared = 0;
                    float ySquared = 0;

                    for (iteration = 0; iteration < MaxIterations; iteration++)
                    {
                        if (xSquared + ySquared >= _scaleSquared) { break; }
                        // Important for yTemp to be calculated BEFORE xTemp
                        // since yTemp depends on older value of xTemp.
                        yTemp = 2 * xTemp * yTemp + anchorY;
                        xTemp = xSquared - ySquared + anchorX;
                        xSquared = xTemp * xTemp;
                        ySquared = yTemp * yTemp;
                    }

                    data[indexOffset + x] = iteration;
                }
            }

            return data;
        }
    }
}

Различия в версиях

Конструктор больше не требует отдельного Width и Height. Вместо этого используется Height вместе с ScaleFactor, который по умолчанию равен 2.0F. Затем в конструкторе вычисляется Width.

После просмотра некоторых форумов других фанатов Mandelbrot, которые ссылаются на книгу, я изменил некоторые имена, чтобы их совместить с их использованием, например. _iterationsPerPixel или MaxIterations.

Только минимальные минимальные свойства теперь public. Другие были переключены на поля и сделали private; такие частные поля изменили свои имена, чтобы начать с подчеркивания.

GenerateSection был слегка изменен. Старая точка anchor была разделена на новые поплавки с именем anchorX и anchorY. Небольшое улучшение, потому что anchorY вычисляется один раз перед входом в цикл X, а не повторяется внутри цикла X.

В старой версии использовался оригинальный NumberOfSections и NumberOfCores. Ни одно из них не влияет на качество вычисляемых значений пикселей. Скорее они использовались как разделение работы на несколько потоков. Хотя я упростил несколько потоков в своем первом ответе (спасибо TPL), я понял, что могу упростить его еще больше. Эта версия не раскрывает NumberOfSections или NumberOfCores как public, поскольку я считаю, что они действительно являются деталями реализации, которые не должны касаться кого-то, использующего класс.

Я добавил разные цвета. Не обязательно лучше. Просто другой. По иронии судьбы, мой интерес к подбору этого предмета заключался в том, чтобы в конечном итоге попробовать некоторые классные эффекты окраски. Но прежде чем я смогу добраться до этого этапа, я хочу убедиться, что остальная часть класса прочная.

Избегание магических чисел:

Я обратил внимание на то, чтобы избежать магических чисел. Некоторые методы имеют константы, объявленные, чтобы избежать использования магических чисел. Однако в GetHoriztonalSections можно сказать, что я использую магическое число с:

var sections = new Section[2 * Environment.ProcessorCount];

Я не могу использовать 2 * Environment.ProcessorCount как константу (так как это не так). Я не могу объявить выражение как readonly внутри метода «один-единственный», который его использует. Я мог бы объявить его как readonly для всего класса, но это увеличивает его область действия далеко за пределами одного метода, который его использует.

И я нашел, что это менее читаемо и больше кода, чем было необходимо:

const int factor = 2;
var numberOfSections = factor * Environment.ProcessorCount;
var sections = new Section[numberOfSections];

И я не думаю, что это разъясняло мое намерение больше, чем одна строка, на которой я остановился.

Пример использования:

private static void RickVersion2()
{
    Console.WriteLine("\nRICK's 2ND VERSION:\n");

    var brot = new MandelbrotGeneratorV2(height: 2048, maxIterations: 1000);

    Console.WriteLine($"Creating Mandelbrot image of size ({brot.Width},{brot.Height}), max iteration of {brot.MaxIterations}, and Width:Height scale of {brot.ScaleFactor}.");

    Console.WriteLine("\n\tGenerating Mandelbrot set ...");
    var sw = Stopwatch.StartNew();
    brot.Generate();
    sw.Stop();
    Console.WriteLine($"\tMandelbrot generation took {sw.ElapsedMilliseconds}ms.");

    Console.WriteLine("\n\tSaving image to file ...");
    sw.Restart();
    brot.SaveImage("test3.png");
    sw.Stop();
    Console.WriteLine($"\tImage save took {sw.ElapsedMilliseconds}ms.");
}

Вот результат вывода консоли:

 введите описание изображения здесь>> </a> </p>

<p> И вот отрезанный фрагмент графика: </p>

<p> <a href= введите описание изображения здесь>> </a> </p>

<p> В то время как окраска - это будущий интерес для меня, я не интересуюсь обзором кода, который я использую для раскраски. Тем не менее, меня очень интересуют дискуссии о возможных методах окраски. </p>

<p> Я не заинтересован в том, чтобы метод <code>---- +: = 28 =: + ----</code> был отменен (пока). Да, я мог каким-то образом передать токен отмены. Я не исключаю этого для будущей версии. Я даже подумал о наличии свойства <code>---- +: = 29 =: + ----</code> на основе <code>---- +: = 30 =: + --- -</code>, например <code>---- +: = 31 =: + ----</code>. Но это на другой день. </p></body></html>

11 голосов | спросил Rick Davin 11 FriEurope/Moscow2015-12-11T17:04:54+03:00Europe/Moscow12bEurope/MoscowFri, 11 Dec 2015 17:04:54 +0300 2015, 17:04:54

3 ответа


11

Только что заметил это

private Section[] GetHoriztonalSections()  

, который является IMO правильным, но это

private short[] GenerateSection(Section section)  

следует назвать как-то иначе, потому что он не генерирует Section.


public void SaveImage(string filename, ImageFormat imageFormat)

это должно быть улучшено с помощью не , используя SetPixel(), потому что он слишком медленный.

Вы должны создать изображение как массив, а затем скопировать весь массив в растровое изображение.

ответил Heslacher 11 FriEurope/Moscow2015-12-11T17:42:20+03:00Europe/Moscow12bEurope/MoscowFri, 11 Dec 2015 17:42:20 +0300 2015, 17:42:20
11

Я думаю, что ваш лимит проверки немного неясен.

Почему константы определены в конструкторе? Они связаны с вашим классом, а не с вашим конструктором. Если бы я мог изменить Width или Height, когда-нибудь, мне нужны эти константы, чтобы подтвердить, что мои новые значения по-прежнему «законны».

Возможно, вы захотите посмотреть контракт класс в .Net Framework. Он предлагает функциональные возможности, которые были бы полезны для вас. В противном случае, если вы не хотите использовать это, вы должны хотя бы переименовать метод CheckLimits на что-то вроде AssertValueInRange или что-то близкое к этому. Прямо сейчас CheckLimits не очень понятно.

Комментарии вроде этого:

// Coloring is probably has the greatest potential for further improvements.
// This is just one attempt that suffices for now.

Бесполезны в коде. Они должны быть в отставании продукта или что-то в этом роде (проблема с вашим Github, записка на салфетке на стороне вашего стола). По мере необходимости оставляйте небольшие комментарии. Но сейчас я понимаю, что это означает, что этот код, возможно, не нужно будет пересматривать, поскольку он изменится.

Не используйте скобки, когда это не нужно, как здесь:

{
    var lastIndex = sections.Length - 1;
    var startY = heightPerSection * lastIndex ;
    sections[lastIndex] = new Section(new Point(0, startY), new Point(Width, Height));
}

Во-первых, это сбивает с толку. Может, вы забыли написать условие, возможно, для? Я не знаю, и это меня смущает. Удалите эти скобки.

// The sectionWidth is the same value as Width but for some odd reason
// using Width is noticeably faster on my 8-core PC.  This is true even
// if I create a local copy such as:
//      var sectionWidth = section.Width;

Найдите эту причину, lol. Это кажется странным. И вторая часть вашего комментария бесполезна, я не против, если это правда, даже если bla bla bla. Я знаю, почему вы использовали Width, это был хороший комментарий, но не нужно слишком много объяснять. Помните, минимальные комментарии.

В целом, ваш код хорош! Некоторые из ваших замечаний превосходны, поскольку они объясняют почему что-то делать вместо того, что вы делаете. Но другие комментарии должны быть удалены.

ответил IEatBagels 11 FriEurope/Moscow2015-12-11T17:24:24+03:00Europe/Moscow12bEurope/MoscowFri, 11 Dec 2015 17:24:24 +0300 2015, 17:24:24
5

В ответе Хеслахера было заключительное замечание об использовании SetPixel в моем SaveImage. Я получил базовую реализацию, а производительность - от 5 секунд до 0,7 . Отличное предложение.

Затем я попытался добавить новый код к ответу Хеслахера, но неназванный редактор (хорошо, я назову редактор: Heslacher) сказал, что должен опубликовать его как свой собственный ответ.

Основная реализация:

Требуется: using System.Runtime.InteropServices;

public void SaveImage(string filename, ImageFormat imageFormat)
{
    if (_iterationsPerPixel == null || _iterationsPerPixel.Length == 0)
    {
        throw new Exception("You must create the Mandelbrot data set before you can save the image to file.");
    }

    using (Bitmap image = new Bitmap(Width, Height))
    {
        var data = image.LockBits(new Rectangle(Point.Empty, image.Size), ImageLockMode.WriteOnly, PixelFormat.Format24bppRgb);

        // Each pixel has 3 bytes for RGB
        var bytes = Math.Abs(data.Stride) * image.Height;
        var rgbValues = new byte[bytes];

        for (int pixel = 0, rgbOffset = 0; pixel < _iterationsPerPixel.Length; pixel++)
        {
            var color = LookupColor(_iterationsPerPixel[pixel]);
            // Oddly enough RGB should be ordered BGR below!
            rgbValues[rgbOffset++] = color.B;
            rgbValues[rgbOffset++] = color.G;
            rgbValues[rgbOffset++] = color.R;
        }

        Marshal.Copy(rgbValues, 0, data.Scan0, rgbValues.Length);
        image.UnlockBits(data);
        image.Save(filename, imageFormat);
    }
}

Но так как Хеслачер хотел, чтобы я сделал свой ответ, , тогда с помощью молота Грабтара , я сделаю это своим. Я изменил его еще больше, сделав его многопоточным при создании массива byte[]. Это сократило время до 0,4 ​​секунды .

Многопоточная реализация:

public void SaveImage(string filename, ImageFormat imageFormat)
{
    if (_iterationsPerPixel == null || _iterationsPerPixel.Length == 0)
    {
        throw new Exception("You must create the Mandelbrot data set before you can save the image to file.");
    }

    using (Bitmap image = new Bitmap(Width, Height))
    {
        var data = image.LockBits(new Rectangle(Point.Empty, image.Size), ImageLockMode.WriteOnly, PixelFormat.Format24bppRgb);
        var rgbValues = GetRgbValues(data.Stride, image.Height);
        Marshal.Copy(rgbValues, 0, data.Scan0, rgbValues.Length);
        image.UnlockBits(data);
        image.Save(filename, imageFormat);
    }
}

private byte[] GetRgbValues(int stride, int height)
{
    var rgbValues = new byte[Math.Abs(stride) * height];

    var ranges = 2 * Environment.ProcessorCount;
    var rangeSize = Math.Max(_iterationsPerPixel.Length / ranges, 1);
    if (_iterationsPerPixel.Length % ranges > 0) { rangeSize++; }

    Parallel.For(0, ranges, range =>
    {
        var startingPixel = range * rangeSize;
        var endingPixel = Math.Min(startingPixel + rangeSize, _iterationsPerPixel.Length);

        // Since a color has 3 bytes to make up the RGB, we multiply by 3 to get the rgbIndex.
        for (int pixel = startingPixel, rgbIndex = startingPixel * 3; pixel < endingPixel; pixel++)
        {
            var color = LookupColor(_iterationsPerPixel[pixel]);
            rgbValues[rgbIndex++] = color.B;
            rgbValues[rgbIndex++] = color.G;
            rgbValues[rgbIndex++] = color.R;
        }
    });

    return rgbValues;
}
ответил Rick Davin 11 FriEurope/Moscow2015-12-11T22:22:03+03:00Europe/Moscow12bEurope/MoscowFri, 11 Dec 2015 22:22:03 +0300 2015, 22:22:03

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132