Optymalizacja funkcji.

Optymalizacja funkcji.
Mikios
MI
Mikios
MI
  • Rejestracja:około 11 lat
  • Ostatnio:9 miesięcy
  • Postów:22
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.

Kopiuj
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;
        }
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
lukashid
lukashid
lukashid
lukashid
  • Rejestracja:ponad 11 lat
  • Ostatnio:3 dni
  • Postów:93
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

Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
Marcin S.
MS
Marcin S.
MS
  • Rejestracja:ponad 9 lat
  • Ostatnio:około 6 lat
  • Postów:3
1
Kopiuj
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.

edytowany 1x, ostatnio: Marcin S.
Zobacz pozostały 1 komentarz
MI
Dzięki, chciałem to zrobić w linq żeby było wszystko w jednej linii, jednak widzę że jest to mało optymalny pomysł.
MI
Jednak dalej dla dużych liczb funkcja za długo się wykonuje.
somekind
Co to znaczy "za długo"? I dla jak dużych liczb?
MS
No to musisz zmienić podejście do problemu. Zamiast brute-forca spróbować znaleźć jakiś ogólny wzorek (nie wiem czy taki istnieje, nie sprawdzałem), albo zastosować programowanie dynamiczne. Np. niech funkcja suma(n) zwraca sumę do n. Całkiem łatwo wyznaczyć wartość funkcji suma dla dużych n, mając jej wartości dla mniejszych (które można zapisywać w pamięci, by nie liczyć wiele razy). Zwróć uwagę na to co się dzieje gdy pojawiają się dziesiątki, setki itd.
somekind
A tak w ogóle, to sugeruję z komentarzy wrócić do postów, skoro dyskusja jest na temat wątku.
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
somekind
somekind
somekind
somekind
Moderator
  • Rejestracja:około 17 lat
  • Ostatnio:2 dni
  • Lokalizacja:Wrocław
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.

Zobacz pozostałe 5 komentarzy
somekind
W C# generalnie nie ma czegoś takiego jak inlinowanie funkcji, nie robi też tego na pewno kompilator C#. Teoretycznie JIT może coś takiego robić, i pewno czasami robi, ale nie wiadomo jakie są przesłanki do tego. Według moich testów, wersja korzystająca z pomocniczej metody jest dwa razy wolniejsza.
MI
Mi też wersja funkcji z pomocniczą metodą spowalniała program. Może nie 2x ale spokojnie 10-15% wolniej się wykonywało.
Patryk27
Hm, w takim razie chylę czoła, mea culpa. Wydawało mi się, że akurat inlinowanie to jedna z takich standardowych optymalizacji w kompilatorach :P
MS
https://msdn.microsoft.com/en-us/library/system.runtime.compilerservices.methodimploptions%28v=VS.110%29.aspx -> AggressiveInlining: Można zasugerować kompilatorowi, by inlinował metody (ale nie musi się posłuchać). No i zazwyczaj, gdy szukamy takich optymalizacji, to znak, że pora poszukać lepszego algorytmu (tak jak w przypadku autora tematu).
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
Mikios
MI
Mikios
MI
  • Rejestracja:około 11 lat
  • Ostatnio:9 miesięcy
  • Postów:22
0

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

Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
somekind
somekind
somekind
somekind
Moderator
  • Rejestracja:około 17 lat
  • Ostatnio:2 dni
  • Lokalizacja:Wrocław
0

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

bogdans
Mam taki algorytm
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
reptile333
R3
reptile333
R3
  • Rejestracja:ponad 11 lat
  • Ostatnio:2 dni
  • Postów:419
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)

Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
bogdans
bogdans
bogdans
bogdans
Moderator
  • Rejestracja:prawie 17 lat
  • Ostatnio:prawie 5 lat
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

To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
edytowany 4x, ostatnio: bogdans
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
bogdans
bogdans
bogdans
bogdans
Moderator
  • Rejestracja:prawie 17 lat
  • Ostatnio:prawie 5 lat
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

To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
edytowany 1x, ostatnio: bogdans
Udostępnij
Kopiuj link do postu Kopiuj link do postu jako Markdown
Komentuj
Treść
Podgląd
Kliknij, aby dodać treść...
Kliknij, aby dodać załącznik lub wklej ze schowka.
Instrukcja obsługi Markdown
Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)