[Wina_Segmentacji]

Mój super algorytm kilka godzin rozkładał na czynniki pierwsze liczbę 600851475143 ale zrobił to dobrze.
Czas go zoptymalizować.

#golang #naukaprogramowania

[S.....t]

@Wina_Segmentacji jak go zoptymalizujesz, jeśli można wiedzieć? Jestem ciekawskim laikiem

[Wina_Segmentacji]

@SmileLikeYouMeanIt:
Mam kilka pomysłów.
1. Utworzenie tablicy liczb pierwszych i wykorzystanie jej do faktoryzacji.
2. Zmianę sposobu wyszukiwania dzielników liczby, ponieważ obecnie to jest coś co zajmuje najwięcej czasu.
Nad oboma metodami muszę się zastanowić i raczej obie zaimplementuję aby zobaczyć jakie będą różnice.

[marahin]

@Wina_Segmentacji: czy wykorzystujesz jakoś wielowątkowość? :)

[Wina_Segmentacji]

@marahin: Nie. Jeszcze nic o niej nie wiem.

[FairyMax]

@Wina_Segmentacji: robisz coś bardzo źle taką liczbę da się rozłożyć w ułamku sekundy
edit: ok nie zauważyłem tagu #naukaprogramowania never mind

[Wina_Segmentacji]

@FairyMax:
Będę miał już punkt odniesienia.

Tym źle jest pewnie wyszukiwanie dzielników ponieważ obecnie działa to mniej więcej tak.
1. Znajdź dzielniki liczby a i zapisz je w "kontenerze"
2. Dla każdego dzielnika w kontenerze zrób 1
3. Jeżeli znaleziono nowe dzielniki wróć do 2

A wyszukiwanie dzielników polega na sprawdzaniu od 2 do połowy danej liczby czy jest jej dzielnikiem więc tu się najwięcej czasu marnuje.

[FairyMax]

@Wina_Segmentacji: Nie rozumiem Twojego algorytmu, możesz wrzucić kod gdzieś?

[Wina_Segmentacji]

@FairyMax: https://pastebin.com/9aKrgWE7

[FairyMax]

@FairyMax: sry zle wklepalem do konsoli ;p

[Wina_Segmentacji]

@FairyMax: Jaki masz wynik?
Tutaj jest taki:
/tmp/go $ go run factor2.go
1000
[2 2 2 5 5 5]

[FairyMax]

@Wina_Segmentacji: tak moja wina w programie dalem 10000 a w konsoli 1000 fałszywy alarm ( ͡° ͜ʖ ͡°)

[FairyMax]

@Wina_Segmentacji: W sumie to nie musisz tworzyć pustych slajsów za pomocą make

[Wina_Segmentacji]

@FairyMax: Dlaczego?

[FairyMax]

@Wina_Segmentacji: możesz napisać po prostu "var result []uint64" wtedy append wykryje że ma do czynienia z pustym slajsem i zaalokuje nowy

[Wina_Segmentacji]

@FairyMax: Jednym prostym trikiem poprawiłem szybkość o 9 sekund dla liczby 1000000000. (⌐ ͡■ ͜ʖ ͡■)
A tak na poważnie to napiszę wersję z wygenerowaną tablicą liczb pierwszych. Będzie raczej najszybsza jak do tej pory.

[FairyMax]

A tak na poważnie to napiszę wersję z wygenerowaną tablicą liczb pierwszych

@Wina_Segmentacji: Protip: wystarczy wygenerować liczby pierwsze do pierwiastka kwadratowego z danej liczby ( ͡° ͜ʖ ͡°)

[Wina_Segmentacji]

@FairyMax:
Gotowe. Faktoryzacja trwa ułamek sekundy. Teraz tworzenie tablicy liczb pierwszych jest najdłuższe. Dla 600851475143 czyli 775146 trwa 82 sekundy. Spore przyspieszenie w porównaniu do kilku godzin wcześniej.

[Wina_Segmentacji]

@FairyMax: Dziękuję za pomoc.

[Wina_Segmentacji]

Teraz pomyślę nad tymi pierwszymi.