Algorytm LFU Dla Pamięci Cache – Rozwiązanie W Stałym Czasie – O(1)

Algorytm LFU dla pamięci cache – rozwiązanie w stałym czasie – O(1)

Z nieistniejącego jeszcze cyklu: pytania algorytmiczne oraz struktury danych u gigantów doliny krzemowej: Google, Amazon, Microsoft etc.

Pamięć podręczna cache to pamięć o bardzo szybkim dostępie, której jest bardzo mało. Tworząc procesor twórcy implementują jeden z algorytmów do zarządzania pamięcią, który decyduje, który element z pamięci ma wylecieć, aby utworzyć miejsce dla nowego elementu.

Wikipedia podaje kilkanaście różnych podejść w celu rozwiązania tego problemu. Miedzy innymi jest:

  • Usuwanie najdawniej użytego elementu – Least Recently Used (LRU)
  • Usuwanie ostatnio użytego elementu – Most Recently Used (MRU)
  • i bohater dzisiejszego odcinka – Usuwanie najrzadziej używanego elementu – Least Frequently Used (LFU)

Tych co nie wiedzą czym jest notacja Dużego-O, przypomnienie: O(x) określa jak rozwiązanie problemu w czasie, będzie wzrastać razem z zwiększeniem problemu. O(n) wzrost liniowy (szukanie elementu w tablicy), O(n^2) wzrost kwadratowy (sortowanie bąbelkowe), O(lg n) wzrost logarytmiczny (wyszukiwanie binarne), O(1) czas stały (dostęp do elementu w tablicy).

Jeżeli masz trudność z zdecydowaniem się jaki algorytm lub struktura danych ma jaką złożoność obliczeniową to udaj się na Big O Cheat Sheet.

Algorytmu do obsługi pamięci cache muszą być dwa.

  • wstawianie wartości metoda set(key, value): void
  • wyciąganie wartości metoda get(key): value

(po dwukropku informacja o wartości zwracanej przez funkcję).

Prostym rozwiązaniem, nie optymalnym jest wykorzystanie dwóch Hash Table, więc .NET’owych Dictionary.

Pierwszy Dictionary przechowuje wartości pod kluczem Dictionary<string, TValue>, drugi Dictionary przechowuje jak często dany klucz jest wykorzystany czyli Dictionary<string, int>.

Metoda get(key) zwiększa licznik użycia dla danego klucza oraz zwraca wartość przechowywaną w pierwszym Dictionary. Obie te operacje są operacjami O(1) więc wyjściowa złożoność get(key) jest równa O(1). Połowa za nami.

Druga metoda set(key, value), musi znaleźć najmniej używany klucz i go w to miejsce podmienić. Niestety operacja szukania najmniej używanego klucza „kosztuje nas” O(n), więc cała metoda kosztuje nas O(n).

Jak zoptymalizować to rozwiązanie? Do czasu O(1)

Czytaj resztę...
Visual Studio 1.8 Tryb Zen, Wyjście Na Gorąco Oraz łatwiejsza Edycja Ustawień Aplikacji.

Visual Studio 1.8 Tryb Zen, Wyjście na gorąco oraz łatwiejsza edycja ustawień aplikacji.

Nowy miesiąc duże zmiany w Visual Studio Code, bo zbliża się okres świąteczny, więc trzeba było zrobić nowych funkcjonaliści „na zapas”. Styczeń powinien być chudy jeżeli chodzi o usprawnienia mojego ulubionego edytora.

Pełna wersja angielska jest dostępna pod grudniowym adresem. A najlepsze kąski po polsku znajdziesz poniżej.

Hot Exit

Od teraz Visual Studio Code nie wyświetli takiego komunikatu przy wychodzeniu z programu (przez X w górnym prawym rogu):

unsaved_file

Nie zapisane zmiany będą trzymane w pamięci podręcznej aplikacji. W momencie gdy wrócisz z powrotem do twojego projektu, wszystkie zmiany bądą zachowane, czekając na twój zapis.

Funkcjonalność można wyłączyć w ustawieniach programu (File->Preferences->User Settings) ustawiając files.hotExit na wartość false. Domyślnie Hot Exit jest włączony.

To także oznacza, że przypadku kiedy Visual Studio Code przestanie nagle działać, to przywróci dane z swojego backupu, nie zależnie czy Hot Exit jest włączony czy nie.

Zmiany w Activity Bar

Activity Bar to nazwa dla tego paska narzędziowego:

activityBar

Czytaj resztę...
Nie Odbieraj Telefonu, Gdy Jestem Przy Twoim Biurku!

Nie odbieraj telefonu, gdy jestem przy twoim biurku!

Mój tata nauczył mnie wielu rzeczy i dzisiaj podzielę się zasadą którą wprowadziłem w swoim życiu.

W sytuacji, kiedy ktoś przychodzi do mojego biurka, to ta osoba jest najważniejsza. To z nią rozmawiam i jej poświęcam czas. Kiedy zadzwoni telefon podczas Code Review (lub innego spotkania twarzą-w-twarz), telefon jest natychmiast odrzucany. Dlaczego? Bo jestem zajęty. Przez telefon nie możesz prowadzić dwóch rozmów jednocześnie [1], a twoim aktualnym rozmówcą jest, ta osoba przy biurku.

[1] – wiem, że to jest możliwe przy  użyciu X technologii, chodzi o to, że na 99% dostaniesz sygnał „abonent jest zajęty”

Przede wszystkim najważniejsze jest abyśmy siebie nawzajem szanowali. Osoba przychodząca do twojego biurka jest gościem, a ty gospodarzem. Jak byś się ty czuł jakby gospodarz nagle wyszedł, bo musi coś zrobić.

Ale to ważny telefon! Co mnie to obchodzi? Takie spotkania nie trwają długo (i nie powinny trwać długo). Zawsze można oddzwonić za 15 minut. Nachalnych dzwoniących traktuję krótko: po drugim odrzuceniu wyłączam komórkę.

PS: Dzisiaj mija rok od rozpoczęcia pracy w DGS. Najkrótsza recenzja: jest normalnie. W skali od 1-3 to zdobywa ocenę 2.

Czytaj resztę...
Czego Nauczyłem Się Po 5 Latach Programowania; Wspominki Soltys Programmer Bot

Czego nauczyłem się po 5 latach programowania; Wspominki Soltys Programmer Bot

Wstęp

3 grudnia minie 5 lat od kiedy zacząłem pisać grę Soltys Programmer Bot.

5 lat temu napisałem dwa posty na ten temat moich doświadczeń przy pisaniu tej gry.

Na moich studiach inżynierskich, na 2 drugim roku trzeba było napisać grę 3D z wykorzystaniem OpenGL. Gołego OpenGL, bez silników graficznych.

Cały rok pisał w C++, ja jak Che Guevara rewolucyjnie postawiłem, że napiszę grę w C#. Wiązało się, że nie będę miał supportu od prowadzących zajęcia, ale opłaciło się podjąć to ryzyko. Dzięki temu, że nie skupiałem na prawidłowej alokacji pamięci udało mi się „dostarczyć” więcej w krótszym czasie.

Kod jest dostępny na GitHub. Uruchomienie tego kodu wymaga jego znajomości. 😀

Gra jest klonem light-Bot. Jeżeli chcesz zobaczyć jaka to była gra to zagraj w light-bot.

Ostatecznie gra zajęła 3 miejsce w konkursie wewnątrz wydziałowym na najlepszą grę roku.

Co sądzę o swoim projekcie po 5 latach?

„Domyślny” dla Visual Studio .gitignore ignoruje pliki .obj

Jak pisałem ten kod to nie używałem systemu kontroli wersji git. Nie pamiętam czy nie używałem systemu kontroli wersji w ogóle czy używałem lokalnego SVNa.

Tak czy siak, po skończeniu poznałem GitHuba.

Czytaj resztę...
Recenzja Doom (2016)

Recenzja Doom (2016)

Pisanie recenzji gry, który wyszła 13 maja, kiedy kalendarz wskazuje 13 listopada nie ma sensu. Ten blog nie ma sensu, więc wszystko się zgadza 🙂

id Software wskrzesza swoją największą markę – Doom. Gra jest rebootem serii opowiada o inwazji demonów z piekła na czerwoną planetę. Z gry można się dowiedzieć skąd się Ty tam wziąłeś i dlaczego jesteś tak dobry w pozbawianiu demonów życia.

Fabuła jest odpowiednia do gry. Nie jest skomplikowana, nie sili się na “nie oczekiwane” zwroty akcji.

Najważniejsze w grze takiej jak Doom jest strzelanie, rozrywanie stworów na krwawe kawałki, poczucie tego, że walczy się z niesamowicie wielkim wrogiem, ale ty go pokonujesz, bo sam jesteś WIELKIM bohaterem tej opowieści.

Czytaj resztę...
Dlaczego Wybory W USA Odbywają Się We Wtorek?

Dlaczego wybory w USA odbywają się we wtorek?

Trzeba cofnąć się do początków Stanów Zjednoczonych, kiedy samochodów nie było.

Nie odbywają się w niedziele, jak u nas to dzień święty i trzeba iść do kościoła, a po kościele jest szabat nie wolno nic robić.

Wybory nie odbywają się w poniedziałek, bo taki farmer może nie dojechać na koniu do większej miejscowości w ciągu 24h.

Postanowili więc, aby wybory były we wtorek.

Czytaj resztę...
TypeScript Dzielenie Kodu Na Wiele Plików, Moduły I WebPack – Krok Po Kroku

TypeScript dzielenie kodu na wiele plików, moduły i WebPack – Krok po kroku

Ostatnio skończyliśmy na HelloWorld, teraz skupimy się jak można podzielić nasz kod na wiele plików.

Kod TypeScript tak jak JavaScript dzieli się na moduły.

Aby umożliwić korzystanie z modułów w TypeScript należy z edytować tsconfig.json i dodać

Określając module określamy jaki wzorzec, akceptowany przez popularne ładowarki-pakietów. Zmiana ustawienia module zmienia kod, który jest generowany przez słowa kluczowe export i import

Czytaj resztę...
Nowości W Visual Studio Code 1.7.1. Automatyczne Poprawki Lintera, Formatowanie Zaznaczonego Kodu.

Nowości w Visual Studio Code 1.7.1. Automatyczne poprawki lintera, formatowanie zaznaczonego kodu.

Nowy miesiąc – nowa wersja mojego ulubionego edytora – Visual Studio Code.

Wydanie listopadowe nie odbyło się bez problemów. Wersja 1.7.0 posiadała możliwość automatycznego ściągania plików opisujących typy w bibliotekach JavaScript dla języka TypeScript. Problem w tym, że popularność automatycznego ściągania plików nie spodobała się serwerom npmjs.org. Po paru godzinach dużego obciążenia serwerów npmjs.org Microsoft był zmuszony wycofać wersję 1.7.0. No i teraz mamy wersję 1.7.1 pozbawione możliwości automatycznego ściągania typów.

Listę zmian można przeczytać na stronie listopadowej.

A oto moja lista najważniejszych zmian wydanych w wersji 1.7.1.

Poziome dzielenie edytora

Od jakiegoś czasu mogłeś mieć otwarte kilka plików jednocześnie w jednym oknie. Pliki pokazywały się w kolumnach, od 1.7.1 mogą pokazywać się w wierszach.

Horizontal Layout

Czytaj resztę...
10 Najpopularniejszych WPF-owych Pytań Rekrutacyjnych

10 najpopularniejszych WPF-owych pytań rekrutacyjnych

Zdjęcie wykonane przez Michała Wachowskiego.

  1. Różnica między Attached property a Dependency property
  2. Różnica między Template a ContentTemplate
  3. Czym jest behavior?
  4. Opisz Binding, DynamicResource, StaticResource, TemplateBinding
  5. Jak definiuje się animacje?
  6. Podaj przykład zastosowań konwertera.
  7. Czym jest MVVM? Podaj zasady tworzenia MVVM?
  8. Po co implementuje się INotifyPropertyChanged
  9. Czym jest Bubbling events?
  10. Różnica między Margin a Padding?
Czytaj resztę...