kurs javascript w kontekście algorytmów ciężkich obliczeniowo

chcę przeportować mój algorytm kompresji bezstratnej do javascript, a moja znajomość javascript jest kiepściutka. czy zna z was ktoś tutorial do javascriptu który skupia się na pisaniu w nim algorytmów? wiem, że np w najnowszym ecmascript są typed arrays i są one chyba szybsze niż zwykłe tablice, ale to tyle jeśli chodzi o wydajność. przydałyby się jeszcze jakieś bajery typu obsługa strumieniowania dużych plików, np jeśli mam 1 gb plik do obrobienia, to żeby zrobić jakiś trik, żeby go całego do pamięci nie ładować i żeby mieć możliwość w kawałkach na dysk zapisywać. itp itd

linki do google także mile widziane :P oczywiście takie z sensownymi wynikami

ps:
jakie są limity pamięci na skrypty w przeglądarkach? jeżeli chciałbym zaalokować 1 GiB pamięci w skrypcie to przeglądarki na to pozwolą?

A gdzie to ma działać? W przeglądarkach? Jakich? A może w NodeJS?

"Obecną" wersją JavaScriptu jest ECMAScript 5 (w skrócie: ES5), definiowana przez standard ECMA-262, edycja 5. W słabszych przeglądarkach, jak IE8, nie ma nawet pełnej implementacji ES5, a ES5... nie zawiera wspomnianych przez Ciebie typed arrays.

Komitet pracujący nad rozwojem JavaScriptu posiada propozycję takich tablic, ale trafią one najwcześniej do kolejnej wersji ECMAScriptu, prawdopodobine ES6. Ta wersja jeszcze nie została zatwierdzona i nawet nie ma pewności, że będzie się nazywała ES6, choć prace nad nią (i nad kolejnymi wersjami) są zaawansowane.

Tutaj link do propozycji specyfikacji tych "tablic":
http://wiki.ecmascript.org/doku.php?id=strawman:typed_arrays

Pamiętaj, że JavaScript nie ma klasycznych wątków i jeśli ot tak fragment Twojego programu wykonywałby się przez kilka sekund, to na te kilka sekund zamrożona zostanie cała przeglądarka. Tu z kolei pomóc Ci mogą WebWorkery, wprowadzające coś w rodzaju wątków. Ale one też nie są dostępne we wszystkich przeglądarkach.

Dobra wiadomość jest taka, że nowoczesne przeglądarki, a nawet IE10, szybko te nowe bajery podłapują i nawet niektóre rzeczy z Harmony (czyli wersji rozwojowej JavaScriptu; swoistego nadzbioru czegoś co się może stanie ES6) są dostępne już teraz.

Nie kojarzę jednak tutorialu, o który pytasz. Ten algorytm masz napisany obiektowo? Funkcyjnie? Czy jest to głównie kod proceduralno-strukturalny? JS dość mocno różni się od innych języków, nie ma np. blokowego zasięgu zmiennych (Harmony już ma) i takie rzeczy mogą Cię ugryźć.

Ma działać w przeglądarkach, wystarczy jak będzie działać na samym Chrome. IE10 odpada, bo jest tylko na Win8 i nikomu nie będzie się chciało tego instalować, żeby się moim dziełem pobawić.

Kod jest głównie proceduralno-strukturalny. Do tego lekka nuta dziedziczenia, tzn mam klasę Common ze wspólnymi metodami + klasy Encoder i Decoder, które raczej wiele nie nadpisują, a tylko korzystają z tego co jest w Common - spokojnie dałoby się obejść bez dziedziczenia tutaj.

Załóżmy, że znasz kodowanie Huffmana, chociaż.. W skrócie kodowanie Huffmana przypisuje znakom (jednoznacznie dekodowalne) kody, których długość nie jest zawsze równa 8 bitom, a potem tworzy ciąg bitów z tych kodów. Załóżmy, że problem jest taki:

• chcę zrobić koder Huffmana - mam algorytm, który pobiera tablicę o rozmiarze max 1 megabajt i wypluwa tablicę o rozmiarze max 1 megabajt + 5 bajtów (nagłówek) zawierającą skompresowane dane,
• koder będzie wczytywał dane po kawałku, kompresował je i zapisywał, dzięki temu nie musiałby wczytywać wszystkiego naraz, ani zapisywać wszystkiego naraz,

Teraz pytanie jest takie:

• jak zrobić obsługę plików? Tzn robię formularz na stronie HTML, w której można podać plik o rozmiarze dowolnym rozmiarze, następnie użytkownik klika przycisk "kompresuj", pojawia się okno zapisu pliku i ja wtedy odpalam mój algorytm, który wczytuje po kawałku plik wejściowy i z tych kawałków generuje wyjście.

Do obsługi plików będziesz pewnie chciał użyć 'File API' z HTML-a 5. Pogooglaj: "html5 file api", albo zerknij prosto do specyfikacji:
http://www.w3.org/TR/FileAPI/

Nie jest to część JavaScriptu; to tylko API, które jest dostępne w nowoczesnych przeglądarkach, podobnie jak DOM czy BOM.

I tak, opiera się to na elementach <input type="file">, tzn. ten element udostępni Ci pliki, które ktoś chce wczytać. W samej specyfikacji są przykłady w JavaScripcie (podpisane jako ECMAScript).

Szczerze mówiąc, za wiele z tym API nie pracowałem i nie natknąłem się na limity wielkości, więc tutaj pewnie będziesz musiał pogooglać.

w silniku chrome'a V8 wszystkie tablice są domyślnie właściwie "typed" - wystarczy że używasz w nich ciągle tego samego typu;
przykładowo dorzucenie nagle floata do tablicy intów spowoduje zaboksowanie wszystkich wartości do wspólnego typu i zmniejszenie wydajności
warto też wspomnieć że tablice indeksowane po kolei i bez dziur są (co najmniej w chrome) szybsze od typowanych nazwami, czy też posiadające dziury - wtedy silnik przeglądarki przerabia właściwie tablicę na hashmapę i traci na wydajności

powinno też się tworzyć zamknięte obiekty i mimo że javascript na to pozwala to nie dopisywać do nich nowych właściwości podczas działania - przeglądarka z obiektów tworzy w pamięci klasy i używa ich kiedy tylko może; dodanie nowej właściwości po utworzeniu tworzy w pamięci całkiem nową klasę i rzutuje obiekt do niego

ogólnie v8 pozwala dość fajnie analizować kod i jego wydajność na stronie about:tracing
można też podpatrzeć jak kod się wykonuje, ile kodu jest poprawnie kompilowanego i wykonywanego natywnie, ile razy silnik musiał kod deoptymalizować (na skutek właśnie utrudniania życia przez zmienianie kodu (lub jego ścieżki) podczas działania, dodawanie nowych właściwości czy używanie eval)
polecam pooglądać prezentacje google'a na ten temat

a i warto wspomnieć że jak to zwykle bywa - wszystkie popularne algorytmy jakie tylko da się zaimplementować w javascript są już w nim przez kogoś zaimplementowane ;)
więc jeżeli nie robisz tego tylko dla ćwiczeń to nie warto wynajdywać koła na nowo
przykładowo kompresor zip w javascript: http://stuartk.com/jszip/

zauważ że nie za bardzo da się jeszcze w javascript dać plik do pobrania z nadaną nazwą (działa tylko w chrome) - tutaj wykorzystywane jest połączenie javascriptu i flasha