Optymalizacja funkcji.

0

Cześć mam taką funkcje która zlicza mi sumę z wartości podanej do funkcji w taki sposób że jak n = 11 to suma to 1 + 2 + 3 + 4 + 5 + 6 +7 +8 + 9 + (1 + 0) + (1 + 1). Funkcja działa poprawnie tylko za wolno. Na 100% można to zoptymalizować ale bardziej zastanawiam się dlaczego tyle czasu się wykonuje. Poniżej ta funkcja.

static public long DigitalSum(long n)
        {
            char[] number;
            long count = 0;
            for (int i = 0; i <= n; i++)
            {
                number = i.ToString().ToArray();
                count += number.Sum(x => int.Parse(x.ToString()));
            }
            return count;
        }
0

A dlaczego wybrałeś akurat operację na charach ? Spróbuj na int[], wtedy w każdym przebiegu pętli unikniesz zamiany na stringa i parsowania w LINQ

1
public static long SumDigitsInNumber(long n)
{
    long result = 0;
    while (n != 0)
    {
        result += n % 10;
        n /= 10;
    }
    return result;
}

public static long DigitalSum(long n)
{
    long result = 0;
    for (long i = 1; i <= n; ++i)
    {
        result += SumDigitsInNumber(i);
    }
    return result;
}

Przy dostatecznie dużym n nastąpi overflow zmiennej, ale korzystanie z dużych liczb spowolniłoby działanie.

0

ToArray jest zbędne. Niepotrzebnie też wołasz ToString na charze i korzystasz z int.Parse. Wystarczy przecież wartość char zmniejszyć o '0', aby uzyskać jego wartość liczbową. Sum też ma swój narzut wydajnościowy, jak wszystko w LINQ. Pozbycie się tego wszystkiego powoduje sześciokrotny wzrost wydajności.

Druga sprawa - nie musisz konwertować i do stringa, żeby sumować cyfry. Operowanie na samych liczbach pozwoli przyspieszyć Twoją bazową wersję 25 razy.

0

Póki co nie mam rozwiązania dla tego zagadnienia. Szczególnie dla liczb powyżej 10 cyfrowych.

0

Niestety, dla dużych liczb, będzie dużo iteracji i dużo liczenia. Tu potrzeba lepszego algorytmu.

0

jeżeli suma 0..9 to a
suma 10, 11, ..., 19 = (1 + 0) + (1 + 1) ... + (1 + 9) = 10 1 + (0 + 1 + ... + 9) = 10 + a
analogicznie suma 20..29 to 20 + a
czyli suma 10..99 to (10 + a) + (20 + a) + ... + (90 + a) = 450 + 10
a
suma 1..99 to b
suma 100, 101, ..., 199 = 100 1 + b
suma 200, 201, ..., 299 = 100
2 + b
...
obliczasz sumę 1..999 = c
...
suma 1000, 1001, ..., 1999 = 1000 1 + c
suma 2000, 2001, ..., 2999 = 1000
2 + c
...
itd

z początkowej złożoności twojego algo O(n) robi się O(log10 n)

3

Zamiast pracowicie sumować cyfry w każdej liczbie wystarczy policzyć ile razy niezerowa cyfra występuje w liczbach od 1 do n
(dla każdej cyfry wynik jest taki sam).
Wśród liczb jednocyfrowych każda cyfra różna od zera występuje raz.
Wśród liczb dwucyfrowych (jest ich 90) każda cyfra różna od zera występuje 19 razy (180 cyfr - 9 zer)/9.
Wśród liczb trzycyfrowych (jest ich 900) każda cyfra różna od zera występuje 280 razy
(2700 cyfr - 18 zer w pełnych setkach - 81 zer w liczbach postaci 307 - 81 zer w liczbach postaci 370)/9
Wśród liczb czterocyfrowych (jest ich 9000) każda cyfra różna od zera występuje 3700 razy
(36000 cyfr - 27 zer w pełnych tysiącach - 812C(3,2) w liczbach z dwoma zerami - 243C(3,1) w liczbach z jednym zerem)/9 =
(36000 - 2700)/9 = 3700
....
1+2+3+4+5+6+7+8+9 = 45
f(99) = 45
(1+19) = 900
f(999) = 45(1+19+280) = 13 500
f(9999) = 45
(1+19+280+3700) = 180 000
Napisałem programik, który liczy f(99..99). http://ideone.com/ffZvOS
Jego złożoność, to O(k) gdzie k to ilość cyfr liczby 99..99. Dla dowolnych liczb złożoność byłaby chyba rzędu O(k2).
f(999 999 999 999) = 54 000 000 000 000

0

Zaimplementowałem swój algorytm. W ciągu 7 sekund wylicza sumy cyfr dla miliona liczb 17-cyfrowych.
Dla przykładu f(98 765 432 123 456 789) = 7 466 927 298 458 161 955

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