#algorithm

wszystkie notatki oznaczone etykietą "algorithm"

Konwersja liczb binarnych do kodu BCD (AVR)

Na forum elektrody natrafiłem na temat związany z operowaniem na dużych liczbach na małych mikrokontrolerach AVR. W istocie temat dotyczył algorytmu szybkiej konwersji dużych liczb zapisanych w naturalnym systemie dwójkowym na ich reprezentację w kodzie BCD. Zagadnienie to wydało mi się na tyle ciekawe i praktyczne (w kilku projektach będę przechodził podobny problem), związane też jest to pokrótce z multipleksowaniem 7-segmentowych wyświetlaczy LED, dlatego postanowiłem zrobić kilka testów (porównań) różnych algorytmów.

Czytaj dalej

Algorytm set_differences

Zbiór gotowych algorytmów ze standardowej biblioteki języka C++ jest bardzo użyteczny, o tym nie trzeba długo nikogo przekonywać. Choć czasem, gdy trzeba wykonać kilka rzeczy naraz, bądź kilka kolejnych algorytmów na tych samych danych, możemy stracić na wydajności, szczególnie jak danych jest wiele, a złożoność algorytmu liniowa. Czasem warto trochę pomyśleć i napisać coś dedykowanego, ewentualnie połączyć 2 algorytmy. Oczywiście tylko, jeśli jest to możliwe i w miarę proste, np. gdy oba algorytmy mają podobną budowę.

Czytaj dalej

Algorytm copy_if

Nic nie jest doskonałe. Tak samo C++ i STL ma swoje braki i różne przeoczenia. W standardowej bibliotece języka C++ zabrakło bardzo użytecznego algorytmu, jakim jest copy_if, czyli kopiowania z predykatem. Prawdopodobnie został on usunięty przez przypadek z dostarczanych przez bibliotekę algorytmów generycznych. Na szczęście z tego co się orientuję, można znaleźć o nim wzmianki w drafcie nowego standardu (C++0x), także jest szansa, że błąd ten zostanie naprawiony. Tymczasem, jeśli jest potrzeba, to można korzystać z bardzo prostej implementacji tego algorytmu:

Czytaj dalej