Sito Eratostenesa, wielowątkowość

Odpowiedz Nowy wątek
2015-01-10 17:47
0

Witam,

od kilku dni próbuję dojść do tego jak usprawnić działanie metody Sito Eratostenesa, w celu jak najszybszego wykonania na wielu wątkach aplikacji. Prawidłowy wynik podobny do tego w aplikacji wykorzystującej jeden wątek otrzymuję jedynie po zastosowaniu Thread.Sleep i Lock. Taka forma mimo iż jest bardziej wydajna dla większych liczb wydaje mi się nieelegancka, czy da się jakoś usprawnić synchronizację w tej metodzie? W button1 zawarta jest metoda działająca na jednym wątku a w button2 na wielu.

public partial class Form1 : Form
{
Stopwatch sw = new Stopwatch();
List<thread> lt;

    public Form1()
    {
        InitializeComponent();
    }

    private void button1_Click(object sender, EventArgs e)
    {
        int n = Convert.ToInt32(textBox1.Text);
        bool[] tab = new bool[n + 1];

        sw.Reset();
        sw.Start();

        for (int i = 2; i * i <= n; i++)
        {
            if (tab[i] == true)
            {
                continue;
            }
            for (int j = 2 * i; j <= n; j += i)
            {
                tab[j] = true;
            }
        }

        sw.Stop();

        WypiszWynik(n, tab);
    }

    private void button2_Click(object sender, EventArgs e)
    {
        int n = Convert.ToInt32(textBox1.Text);
        bool[] tab = new bool[n + 1];
        lt = new List<Thread>();

        sw.Reset();
        sw.Start();

        for (int i = 2; i * i <= n; i++)
        {
            if (tab[i] == true)
            {
                continue;
            }

            lt.Add(new Thread(() => Eliminacja(i, n, tab)));
            lt.Last().Start();

           lock (tab)
            {
                Thread.Sleep(1);
            }
        }

        foreach (var t in lt)
        {
            t.Join();
        }

        sw.Stop();
        WypiszWynik(n, tab);
    }

    private void Eliminacja(int i, int n, bool[] tab)
    {
        for (int j = 2 * i; j <= n; j += i)
        {
            tab[j] = true;
        }
    }

    private void WypiszWynik(int n, bool[] tab)
    {
        long suma = 0;

        listBox1.Items.Clear();
        listBox1.Items.Add("Liczby pierwsze z zakresu [0," + n + "]: ");

        for (int i = 2; i <= n; i++)
        {
            if (tab[i] == false)
            {
                if (n < 1000)
                {
                    listBox1.Items.Add(i + " ");
                }

                suma += i;
            }
        }

        listBox1.Items.Add("Suma: " + suma);
        listBox1.Items.Add("Czas operacji: " + sw.ElapsedMilliseconds);
    }
} 

Pozostało 580 znaków

2015-01-11 00:43

zamiast Sleep powinno wystarczyc:

int i2 = i;
lt.Add(new Thread(() => Eliminacja(i2, n, tab)));

wtedy w momencie wywołania do funkcji Eliminacja będzie przekazywana odpowiednia wartość "i", teraz może to już być kolejna, czyli np dla i =2 nigdy się nie wywoła tylko dwa razy dla i=3.

Nie ma też sensu mnożyć wątków, ThreadPool.QueueUserWorkItem i np ManualResetEvent, żeby wiedzieć kiedy funkcja się skończyła:

var lt = new List<ManualResetEvent>();
...
int i1 = i;
var ev = new ManualResetEvent(false);
lt.Add(ev);
ThreadPool.QueueUserWorkItem(obj =>
{
 Eliminacja(i1, n, tab);
 ev.Set();
});
..
foreach (var t in lt)
{
   t.WaitOne();
}

Taka implementacja dla liczb od około 1mln osiąga lepsze wyniki na moim sprzęcie.

Pozostało 580 znaków

2015-01-11 02:15
0

Dziękuję, wszystko działa poprawnie. Niestety u mnie po użyciu ThreadPool.QueueUserWorkItem i ManualResetEvent aplikacja działa wolniej niż w przypadku zdublowanych wątków

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0