Propozycje uproszczenia kodu

Hej,
chciałbym abyście podpowiedzieli mi co mogę zmienić aby mój kod wykonywał się szybciej. Jest to zadanie na SPOJ, osiągam wyniki na poziomie 0.33 (najlepsze są ~0.2).

            byte przypadki = byte.Parse(Console.ReadLine());
            int[] n = new int[przypadki];

            for (int i = 0; i < przypadki; i++)
            {
                var liczby = Console.ReadLine().Split(null);
                int a = int.Parse(ab[0]);
                int b = int.Parse(ab[1]);
                n[i] = Nwd(a, b);
            }
            for (int i = 0; i < przypadki; i++)
            {
                Console.WriteLine(n[i]);
            }

I jeszcze jedno. Co to jest dokładnie NZEC? W co drugim zadaniu takie coś otrzymuję.
Dziękuję za pomoc i pozdrawiam.

Zacząłbym od pozbycia się tej tablicy; poza tym wrzuć cały kod + link do zadania.

Co to jest dokładnie NZEC

Afair przekroczenie czasu CPU (zbyt wolny program).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {

        static int Nwd(int a, int b)
        {
            while (b != 0)
            {
                int c = a % b;
                a = b;
                b = c;
            }
            return a;
        }
        static void Main(string[] args)
        {            
            byte przypadki = byte.Parse(Console.ReadLine());
            int[] n = new int[przypadki];

            for (int i = 0; i < przypadki; i++)
            {
                Console.WriteLine("Podaj liczby: ");
                var ab = Console.ReadLine().Split(null);
                int a = int.Parse(ab[0]);
                int b = int.Parse(ab[1]);
                n[i] = Nwd(a, b);
            }
            for (int i = 0; i < przypadki; i++)
            {
                Console.WriteLine(n[i]);
            }
        }
    }
}

http://pl.spoj.com/problems/PP0501A/

Pozdrawiam

1.Zbędna tablica.
2.Niezbyt wydajny algorytm liczenia NWD; u siebie korzystam z takiego:

function<int> gcd(int u, int v)
{
 if ((u < 0) || (v < 0))
  return 0;

 var<int> shift;
 
 if (u == 0)
  return v;
  
 if (v == 0)
  return u;
 
 for (shift = 0; ((u | v) & 1) == 0; shift++)
 {
  u >>= 1;
  v >>= 1;
 }
 
 while ((u & 1) == 0)
  u >>= 1;
 
 do
 { 
  while ((v & 1) == 0)
   v >>= 1;

  if (u > v)
  {
   var<int> t = v;
   v = u;
   u = t;
  } 
       
  v-= u;
 } while (v != 0);

 return u << shift;
}

Średnio 60% wydajniejszy, niż ten Euklidesowy: http://en.wikipedia.org/wiki/Binary_GCD_algorithm#Iterative_version_in_C

1. Nie wypisuj durnot na stdout.
2. Nie uzywaj taliby, tylko Od razu wywalaj wynik.
3. Nie ma jakiejs metody do czytania liczb ze stdin?

Zbędna tablica? Mogę prosić o jakieś nakierowanie czym to zastąpić? Głowię się od kilku ładnych godzin i nie mam pomysłu. Funkcja na pobieranie liczb ze stdin? Co konkretnie masz na myśli?
Moje pytania mogą wydać się wam dość banalne, ale jestem na etapie nauki C# i zadania ze SPOJ są swego rodzaju uzupełnieniem tego... :)

Tez jestem na etapie nauki tego jezyka :P
Co do tablicy, to po prostu wczytaj te 2 liczby, oblicz co masz obliczyc i wypisz.
Co do metody wczytujacej liczby to znalazlem BinaryReader.ReadInt32(), ale jeszcze nie testowalem tego :P

Zapoznałeś się ze specyfikacją tego zadania?
Najpierw użytkownik podaje wszystkie liczby a następnie dopiero wyświetla się wynik. Jakbym nie użył tablicy do wyniku tylko zastosował np. Console.WriteLine(Nwd(a, b)); w miejscu obecnego n[i] = Nwd(a, b); to program pobierał by liczby wyświetlał wynik i znów pobierał liczby.
Chyba, że masz na myśli inny sposób... :)

@Sopelek
fakt, takie coś też zaakceptowało. Jednak mimo wszystko ani "waga" programu ani czas wykonania się nie zmniejszyły, a wręcz przeciwnie- z ~0.33s wzrosło do ~0.45s :)

SiSz napisał(a)

Najpierw użytkownik podaje wszystkie liczby a następnie dopiero wyświetla się wynik.

Standardowe wejście oraz wyjście to są dwie różne i niepowiązane ze sobą rzeczy; to, że np.w windowsowej konsoli są one łączone nie oznacza, że SPOJ (bądź cokolwiek innego) też tak postępuje.

a wręcz przeciwnie- z ~0.33s wzrosło do ~0.45s

Zmieniłeś algorytm na ten podany przeze mnie?

@Patryk27 zmieniłem. Zmienne zadeklarowałem przed pętlą i wynik jest ~0.36s. Wieczorem pogrzebię z BinaryReader.
Jeszcze załączę kompletny kod:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace NWD
{
    class Program
    {
        static int Nwd(int a, int b)
        {
            int i, d;
            if ((a < 0) || (b < 0))
                return 0;
            if (a == 0)
                return b;
            if (b == 0)
                return a;
            for (i = 0; ((a | b) & 1) == 0; i++)
            {
                a >>= 1;
                b >>= 1;
            }
            while ((a & 1) == 0)
                a >>= 1;
            do
            {
                while ((b & 1) == 0)
                    b >>= 1;
                if (a > b)
                {
                    d = b;
                    b = a;
                    a = d;
                }
                b -= a;
            } while (b != 0);
            return a << i;
        }
        static void Main(string[] args)
        {
            int przypadki = int.Parse(Console.ReadLine());
            int a, b;
            for (int i = 0; i < przypadki; i++)
            {
                var ab = Console.ReadLine().Split(null);
                a = int.Parse(ab[0]);
                b = int.Parse(ab[1]);
                Console.WriteLine(Nwd(a, b));
            }
        }
    }
}

Skorzystaj z liczb unsigned int (w C# to chyba uint), wtedy ten warunek możesz usunąć:

            if ((a < 0) || (b < 0))
                return 0;

BTW. Z racji tego, że dopiero co zaczynam swoją przygodę z programowaniem ciekawi mnie jedna sprawa. Jeżeli do programu potrzebny jest algorytm (pierwsze lepsze ze SPOJ'a: silnia, liczby pierwsze itd.) to szukacie najlepszego w internecie czy sami tworzycie? Ja osobiście na tym etapie nie potrafię bez "pomocy internetu" poradzić sobie z zadaniem na chociażby liczby pierwsze :)

Wielkim matematykom dojście do jakiejś 'optymalnej' wersji algorytmu zajmuje czasami nawet całe lata - jeżeli jest to zadanie typu silnia/liczby pierwsze, to przeważnie szukam jakiegoś opisu gotowego algorytmu i na własną rękę staram się możliwie jak najlepiej zaimplementować.
Co innego oczywiście, gdy chodzi o mniej trywialne zadania, w których trzeba już myśleć na własną rękę ofc. :P

Patryk27
Z Twoim NWD daje 0.34 ms.
Po zmianie int na uint -> 0.36 ms.

A taki kod daje 0.36 ms:

using System;

namespace ConsoleApplication1
{
    class Program
    {
        static int nwd(int a, int b)
        {
            int c;

            do
            {
                c = a % b;
                a = b;
                b = c;
            } while (0 != (b = c));

            return a;
        }

        static void Main(string[] args)
        {
            int count, separator;
            string numbers;
            
            Int32.TryParse(Console.ReadLine(), out count);

            for (int i = 0; i < count; i++)
            {
                separator = (numbers = Console.ReadLine()).IndexOf(' ');
                
                Console.WriteLine(nwd(
                    Int32.Parse(numbers.Substring(0, separator)),
                    Int32.Parse(numbers.Substring(++separator, numbers.Length - separator))));
            }
        }
    }
}

Zmiana Int32.Parse na Convert.ToInt32 - > 0.34 ms

Zmiana Int32.TryParse na int.TryParse i Int32.Parse na Convert.ToInt32 -> 0.33 ms

Dodatkowa zmiana Convert.ToInt32 na int.Parse -> 0.33 ms

Zastosowanie .Split(' ') i tablicy -> 0.35 ms

Zamiana .IndexOf(' ') na pętle -> 0.33 ms

for (separator = 0; separator < numbers.Length; separator++)
    if (' ' == numbers[separator])
        break;

Kod końcowy, czas wykonania 0.31 ms:

class Program
{
    static int nwd(int a, int b)
    {
        int c;

        do
        {
            c = a % b;
            a = b;
            b = c;
        } while (0 != b);

        return a;
    }

    static void Main()
    {
        int count, separator, i;
        string numbers;

        int.TryParse(System.Console.ReadLine(), out count);

        for (i = 0; i < count; i++)
        {
            numbers = System.Console.ReadLine();

            for (separator = 0; separator < numbers.Length; separator++)
                if (' ' == numbers[separator])
                    break;

            System.Console.WriteLine(nwd(
                int.Parse(numbers.Substring(0, separator)),
                int.Parse(numbers.Substring(++separator, numbers.Length - separator))));
        }
    }
}