Konkurs na najszybszy kod [etap 0]

Odpowiedz Nowy wątek
2011-08-06 16:06
0

Witam
W pewnym wątku pojawił się pomysł na stworzenie konkursu na najszybszy kod. Ale ponieważ ani mi ani Demonicalowi nie przychodzi do głowy żaden sensowny pomysł, mam pytanie do was.
Macie pomysł na zadanie, które będzie miało dużo miejsc na optymalizację?

Pozostało 580 znaków

2011-08-06 16:22
0

FFT, BigNum, BLAS, itp numeryczne zabawy.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
Też myślałem o BigNum, ale rzeczywiście jest tam dużo możliwości optymalizacji? - lukasz1235 2011-08-06 16:29
A to wszystkie BigNumy są tak samo szybkie? Można dać jakieś warunki, np zrobienie BigDecimala czyli liczby rzeczywiste zapisane dziesiętnie, a nie binarnie. Przydałoby się też stworzenie szkieletu, tzn interfejsu. - Wibowit 2011-08-06 16:38
Jednak czekam na coś ciekawszego - lukasz1235 2011-08-06 16:40
3 poziom BLAS może być ciekawy - lukasz1235 2011-08-06 16:45

Pozostało 580 znaków

2011-08-06 16:33
Rev
0

To może RPN :D?


buhahaha :] - msm 2011-08-06 17:22

Pozostało 580 znaków

2011-08-06 17:20
0

Kto napisze najszybszy kompilator C++ :]


Widać, że nie masz pojęcia jak to się robi. - Wibowit 2011-08-06 17:21
@Wibowit - czemu? Może chodziło o szybką kompilację :>? Inna sprawa że nikomu by się nie chciało. - msm 2011-08-06 17:23
A to chyba, że o taką prędkość chodzi. A inna sprawa to chyba taka, że mało kto w 100 % ogarnia chociażby standard C++03. Ja np nie ogarniam :P i nawet jakoś specjalnie nie chce mi się w to zagłębiać. - Wibowit 2011-08-06 17:27
C++ ma tyle idiotycznych ficzerów że poznanie i obsłużenie tego wszystkiego jest niezbyt sensowne... - msm 2011-08-06 17:39

Pozostało 580 znaków

2011-08-06 17:25
msm
0

Alokowanie 10000000 obiektów :D

edit: A poważnie to możliwych zadań są tysiące, równie dobrze mogłoby być np. renderowanie sporego systemu cząsteczkowego albo symulowanie wody za pomocą SPH.

edit 2: Przydałoby się napisać coś faktycznie przydatnego, wtedy ktoś by być może na tym skorzystał zamiast pisać dla sztuki...

edytowany 4x, ostatnio: msm, 2011-08-06 17:28

Pozostało 580 znaków

2011-08-06 19:05
0
MSM napisał(a)

edit 2: Przydałoby się napisać coś faktycznie przydatnego, wtedy ktoś by być może na tym skorzystał zamiast pisać dla sztuki...

Ja głosuję na wykonanie tego projektu: http://4programmers.net/Forum/Algorytmy/152955-Model_ro%C5%9Bliny


"HUMAN BEINGS MAKE LIFE SO INTERESTING. DO YOU KNOW, THAT IN A UNIVERSE SO FULL OF WONDERS, THEY HAVE MANAGED TO INVENT BOREDOM."

Pozostało 580 znaków

2011-08-06 19:10
0
MSM napisał(a)

renderowanie sporego systemu cząsteczkowego albo symulowanie wody za pomocą SPH.
Tylko ciekawe komu chciałoby się coś takiego zrobić. Pamiętaj, że mówimy o prostym, konkursowym zadaniu.

edit 2: Przydałoby się napisać coś faktycznie przydatnego, wtedy ktoś by być może na tym skorzystał zamiast pisać dla sztuki...
Jeżeli chcesz zrobić coś przydatnego to pomyśl nad dołączeniem się do jakiegoś projektu open source.

@somekind: Mówimy o czymś wykonalnym ;)

PS. A ja głupi liczyłem na poważne propozycje.

Nie demotywuj mi MSMa, liczyłem że to zrobi. ;) - somekind 2011-08-06 22:23

Pozostało 580 znaków

2011-08-06 19:22
0

Wydajność zależy od wielu czynników, kod na jednym kompie może działać szybko, na drugim wolniej. Jak zamierzasz zorganizować taki konkurs?
Chyba jedynym sensownym sposobem było by postawić serwer ala konkursy algorytmiczne, na którym można by automatycznie wykonywać kod.
Poza tym co jest celem takiego konkursu? Wymyślenie najszybszego algorytmu? Zrównoleglenie go? Czy może dać jakieś proste zadanie i sprawdzić kto potrafi zrobić najlepsze optymalizacje na niskim poziomie?
Ja bym proponował wybrać jakiś mało popularny, NP-trudny problem do rozwiązania. Takie zadania jak liczenie iloczynów macierzy czy FFT zbyt łatwo podpatrzeć na necie.
Ewentualnie dać proste zadanie jak np. wyliczanie histogramu, tyle że dla 50GB pliku.

edytowany 2x, ostatnio: 0x200x20, 2011-08-06 19:25
Serwer już jest, silnik też - lukasz1235 2011-08-06 19:28

Pozostało 580 znaków

2011-08-06 19:23
0

To ja może dam coś bardziej przyziemnego.
1.) Typowe problemy algorytmiczne
2.) Przetwarzanie obrazów
3.) Stworzenie kompresji (stratnej lub nie) pliku. Im lepsza kompresja tym więcej punktów plus im szybciej tym dodatkowe punkty
4.) Najszybsza i najlepsza metoda "liczenia" liczb (pseudo)losowych. Mam tu na myśli własny generator, a słowo "najlepsza" oznacza w miarę równomierny rozrzut.
5.) Najszybsze wyszukiwanie wzorca (w sumie dość typowe)
6.) Najszybsze wylosowanie logicznych zdań z przykładowego tekstu
7.) Najszybsze czytanie captchy :P
8.) Najszybsze wczytanie wielkiego pliku i wydrukowanie go na ekranie monitora.

nie wiem, zadań jest pełno :)

Pozostało 580 znaków

2011-08-06 19:26
neo
0

Konkurs imienia Piotra Olszewskiego - najszybszy skaner antywirusowy w Delphi.

Pozostało 580 znaków

2011-08-06 19:34
msm
0

renderowanie sporego systemu cząsteczkowego albo symulowanie wody za pomocą SPH.

Tylko ciekawe komu chciałoby się coś takiego zrobić. Pamiętaj, że mówimy o prostym, konkursowym zadaniu.

Systemy cząsteczkowe same w sobie są akurat banalne, SPH jest trudniejsze ale za to więcej rzeczy da się zoptymalizować.

Jeżeli chcesz zrobić coś przydatnego to pomyśl nad dołączeniem się do jakiegoś projektu open source.

Nie chodzi mi o cały sensowny projekt, tylko o jakąś funkcję która faktycznie może się przydać przy pisaniu normalnego kodu.

Poza tym co jest celem takiego konkursu? Wymyślenie najszybszego algorytmu? Zrównoleglenie go? Czy może dać jakieś proste zadanie i sprawdzić kto potrafi zrobić najlepsze optymalizacje na niskim poziomie?

Dobre pytanie... Optymalizować można w różny sposób

  • wymyślić najszybszy algorytm rozwiązujący dane zadanie. Wtedy drobne poprawki nie mają znaczenia, liczy się optymalizacja przez duże O.
  • można wygrać przez napisanie wszystkiego w C/Asemblerze wydzierając każdy bit pamięci i cykl procesora.
  • i można wygrać przez uruchomienie powyższego algorytmu na wielu rdzeniach ;)

O ile trzeci sposób to wariacja drugiego to sposób rozwiązania zależy od podanego zadania - mamy __wymyśl algorytm__ i zaimplementuj oraz __zaimplementuj__ jedyny słuszny algorytm. Więc jakiego zadania właściwie chcesz?

Można wygrać pisząc na CUDA. ;) - somekind 2011-08-06 22:25
można nie można... jak sobie ktoś nie zainstalował specjalnych sterowników nVidia, to chyba cały algorytm wykorzystuje zwykły CPU :) Jeśli komputer testowy nie jest przewidziany na CUDA, to na niewiele się zdadzą ;) - Spine 2011-08-08 11:42

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