Konkurs na najszybszy kod [etap 0]

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ę?

0

FFT, BigNum, BLAS, itp numeryczne zabawy.

0

To może RPN :D?

0

Kto napisze najszybszy kompilator C++ :]

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...

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

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.

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.

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 :)

0

Konkurs imienia Piotra Olszewskiego - najszybszy skaner antywirusowy w Delphi.

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?

0

Faktycznie nie sprecyzowałem. Raczej chodzi o jak najszybszą implementację już istniejącego algorytmu.

A jeżeli chodzi o funkcję to jakiś konkretny pomysł?

0

To może usunię duplikatów z b. dużego pliku (> 20G) zawierającego słowa?
Plusy takiego zadania:

  • zadanie jest często spotykane w praktyce, więc sam chętnie bym je rozwiązał
  • jedynym gotowym narzędziem do zrobienia tego jest sort -u, które nie jest najwydajniejszym sposobem
  • algorytm jest dosyć prosty, wystarczy policzyć wystąpienia wszystkich elementów i usunąć powtarzające się. Natomiast wielkość pliku sprawia, że rozwiązanie mocno się komplikuje (nie można sobie stworzyć mapy i trzymać jej w pamięci).
  • mają szanse wygrać rozwiązania napisane w językach innych niż C i assembler, gdyż wąskim gardłem są operacje wejścia/wyjścia a nie obliczenia
0

To może to czym ja się teraz zajmuję, czyli szukanie przecięć krzywej (złożonej z odcinków) z samą sobą. Wynikiem mogą być punkty przecięcia oraz dodatkowo segmenty które się w tych punktach przecinają. Są do tego gotowe biblioteki, ale albo nie podają wystarczających wyników (CGAL), albo są drogie (LEDA). Dodatkowe założenia to, że przecięć jest dość mało (co wynika z ograniczonej odgórnie długości jednego odcinka) oraz współrzędne są całkowite. Nawet najprostszy sensowny algorytm (Bentleya-Ottmanna) jest ciężki w implementacji biorąc pod uwagę wszystkie możliwe przypadki. W dość długi czas udało mi się to jakoś zrobić, ale wydajność nie jest najlepsza oraz moja implementacja nie uwzględnia pionowych wektorów (co akurat nie było potrzebne). Są jeszcze lepsze algorytmy, ale są bardzo akademickie (szczególnie, że ten problem to i tak jest fragment większego algorytmu z pisma o grafice obliczeniowej). Spodziewana wielkość krzywej: do paru tysięcy odcinków.

0

To może raytracer?
Pod uwagę będzie brana jakość oraz czas w jakim grafika została wyrenderowana.

0

Ciężko będzie to automatycznie oceniać

0

Ja mam taką wolną sugestię by tworzyć statystyki na podstawie dwóch kategorii:

  • Najszybszy kod niezależnie od języka
  • Najszybszy kod w danym języku

Pomoże to rozeznać się w różnych odmianach, których pewnie trochę będzie.

0

Powodzenia w pisaniu zestawów do pomiaru czasu wykonywania w kilkunastu językach. Nie można tak po prostu liczyć czasu wykonywania całej aplikacji.

0

Stroną techniczną zajmuje się Demonical, ale na razie nie zagląda na 4p

0

To może rozpoznawanie twarzy na obrazach ASCII-Art?

1

Widzę, że tu potrzebny jest najpierw meta-konkurs - konkurs na najlepsze zadanie konkursowe.

0

ja mam tylko pytanie: "po co?" :]
komu to zycie ulatwi, co ma na celu ten konkurs, i czy nie ma jakiegos bardziej produktywnego zajecia :>?

0

A ciekawe, że nikt nie pytał się po co konkurs na najbardziej poryty kod :]

0

To może zamiana bitmapy na ASCII?
;)

0

@cepa - dla zabawy i satysfakcji? No chyba, że liczysz na jakąś wartościową nagrodę?

0

A może zamiast kolejnego spoja zrobić turniej programów walczących?

Najpierw wybierze się jakąś prostą grę dla co najmniej 2 graczy: kólko i krzyżyk (nxn dla n>3 lub w wielu wymiarach, więcej niż 2 graczy kółko, krzyzyk i litera N), okręty, piłkarzyki na papierze, warcaby?, wariację gry karcianej: poker w otwarte karty lub jakąś własną inną niż tutaj:
http://pl.wikipedia.org/wiki/Kategoria:Gry_karciane
http://pl.wikipedia.org/wiki/Kategoria:Gry_w_kt%C3%B3rych_u%C5%BCywa_si%C4%99_kartki_papieru
http://pl.wikipedia.org/wiki/Kategoria:Gry_planszowe

Potem zdefiniuje standardowy interfejs którym programy będą się porozumiewały z sędzią.
Np. w grze kólko i krzyżyk na wejściu program przyjmuje pozycję na którą przeciwnik umieścił swój znak, na wyjściu pozycja na którą umieszcza własny znak.
W grze w okręty po uruchomieniu program przekazuje sędziemu pozycje swoich okrętów, a następnie na wyjściu wypisuje pozycje na które strzela, na wejście efekty strzałów <pudło> <trafiony> <zatopiony>.
Zwycięstwo któregoś gracza stwierdza sędzia i przerywa grę, albo killując je brutalnie albo wysyłając im na wejście specjalną komendę <exit>.

Sędzia (problem Demonicznego Mnicha) - program pobierający od programu zawodnika wyjście, sprawdzający poprawność z regułami i przekazujący to innym programom-zawodnikom na wejście. W przypadku gdy wyjście jest niezgodne z zasadami zawodnik jest dyskwalifikowany i odpada z gry (ale nie z turnieju) i jeżeli gra jest 2 osobowa to wygrywa przeciwnik, jeśli nie to inne programy zostają powiadomione o dyskwalifikacji i grają dalej. Ponadto sędzia powinien także mierzyć czas odpowiedzi zawodnika i rozmiar używanej pamięci, aby go zdyskwalifikować gdyby przekroczył pewną ustaloną wartość.

Turniej, dla zwiększenia emocji powinien zostać rozłożony na wiele dni.
Jeśli zgłoszono by wiele programów to najpierw powsadzano by je do grup (każdy z każdym), a potem system pucharowy.
Każdy programista może zgłosić więcej niż jeden program do turnieju.

0

albo coś z automatów komórkowych

0

@ITPW: Może kiedyś

0

Granie w 4P TD na losowej mapie.

0

To na serwerze są Xy i przeglądarka? :O

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