Czy sposób pisania pętli for ma wpływ na wydajność?

Home

Przy okazji codziennej prasówki natknąłem się na ten artykuł na temat wydajności pętli for w JavaScript'cie dla różnych przeglądarek. W skrócie chodzi o to czy powinniśmy pisać pętlą for tak:

for (int i = 0; i < array.Length; i++)
   ...

A może raczej tak, czyli zapamiętać długości tablicy w zmiennej pomocniczej i nie odczytywać jej przy każdym przebiegu pętli:

for (int i = 0, len = array.Length; i < len; i++)
   ...

Z ciekawości sprawdziłem czy taka mikro optymalizacja ma jakiekolwiek znaczenie w przypadku programowania na platformę .NET. Do zmierzenia czasu użyłem takiej metody pomocniczej:

public static void MeasureIt<T>(Action<T> action, T arg, int noOfIterations)
{
   var sw = new Stopwatch();
   sw.Start();

   for (var i = 0; i < noOfIterations; ++i)
      action(arg);

   sw.Stop();
   Console.WriteLine("Total time: " + sw.ElapsedMilliseconds);
}

Następnie wykonałem następujący test:

var noOfIterations = 100000;
var noOfElements = 10000;
var array = Enumerable.Repeat(1, noOfElements).ToArray();
//Przypadek 1
MeasureIt(arg =>
{
   var total = 0;
   for (var i = 0; i < arg.Length; i++)
      total += a[i];  
}, array, noOfIterations);
//Przypadek 2
MeasureIt(arg =>
{
   var total = 0;
   for (int i = 0, len = arg.Length; i < len; i++)
      total += a[i];
}, array, noOfIterations);

Dla rzetelności testy uruchomiłem wielokrotnie. Czas wykonywania obliczeń w obu przypadkach wynosił około 320ms z dokładnością do kilku milisekund. Czasami pierwsze podejście było szybsze, a czasami drugie. Z jednej strony czegoś takiego się spodziewałem. Z drugiej strony sądziłem, że jednak zaobserwuję pewien zysk w drugim przypadku. Dlaczego?

Otóż jeśli spojrzymy na kod pośredni wygenerowany przez kompilator to te dwie implementacje bynajmniej nie są identyczne. W pierwszym przypadku długość tablicy odczytywana jest wielokrotnie na koniec pętli, a w drugim tylko raz przed właściwą pętlą. Najwidoczniej jest to jednak tak szybka operacja, że się nie liczy (w IL do odczytania długości jednowymiarowej tablicy istnieje dedykowana instrukcja ldlen).

Dodatkowo przeprowadziłem podobny test dla użycia listy generycznej List<T>. Tym razem różnice były już zauważalne i wynosiły około 27% na rzecz zapamiętania liczby elementów listy w dodatkowej zmiennej. Średnio pierwsza wersja wykonywała się 957ms, a druga 752ms. Wynika to z tego, że aby odczytać liczbę elementów w liście należy odczytać właściwość Count czyli metodę get_Count. Na poziomie IL jest to robione przy pomocy instrukcji callvirt (w telegraficznym skrócie służącej do wołania metod na rzecz obiektów), a nie dedykowanej (i pewnie zoptymalizowanej) instrukcji ldlen jak ma to miejsce w przypadku tablic. Pomimo tych różnic uważam jednak, że w codziennej praktyce programistycznej nie należy się tym przejmować gdyż różnice w czasach obliczeń, w porównaniu do dużej liczby iteracji (100000), są zbyt małe.

Życzenia świąteczne

Home

Kolejne Święta Bożego Narodzenia już tuż tuż. W tym roku czekam na nie jeszcze bardziej niż zwykle, bo to pierwsze wydarzenie tego rodzaju dla naszej córeczki. Wszystkim czytającym mojego bloga i nie tylko życzę dużo radości w gronie bliskich Im osób, a w Nowym Roku ciekawych wyzwań zawodowych oraz zapału do nauki i doskonalenia się.

Serdecznie Pozdrawiam,
Michał Komorowski

Czego prawdopodobnie nie wiedzieliście o Excel'u

Home

Sądzę, że wielu z Was otarło się na studiach o programowanie liniowe oraz algorytm sympleks. Ja uczyłem się o tym na przedmiocie zwanym w skrócie POBO, co rozwija się dumnie brzmiące Podstawy badań operacyjnych. Od czasów studiów nie zajmowałem się tym zagadnieniem, aż do dzisiaj. Pomagając siostrze w rozwiązywaniu zadań na studia dowiedziałem się o możliwościach Excel'a, których w ogóle nie byłem świadomy, a są naprawdę super i każdy ma do nich dostęp. Mam tutaj na myśli dodatek Solver, który, między innymi, implementuje algorytm sympleks w bardzo przystępnej formie. Tyle tytułem wstępu. Spójrzmy na prosty przykład.

Zaczynamy od uruchomienia Excel'a. Następnie klikamy tą fikuśną okrągłą ikonę w lewym górnym roku okna i wybieramy Opcje programu Excel. Dalej przechodzimy do zakładki Dodatki i klikamy przycisk Przejdź.



W oknie, jakie się pojawi, wybieramy Dodatek Solver i zatwierdzamy.



Po zatwierdzeniu w zakładce Dane na wstążce pojawi się nowa opcja.



Teraz spróbujmy rozwiązać przykładowe proste zadanie. Załóżmy, że mamy 5 fabryk i chcemy znaleźć lokalizację centrum dystrybucyjnego tak aby suma odległości od wszystkich fabryk była minimalna. Dodatkowe ograniczenie jest takie, że odległość od każdej z fabryk nie może być większa niż 60. Położenia fabryk podane są we współrzędnych kartezjańskich. Odległość pomiędzy fabrykami, a centrum obliczamy przy pomocy standardowego wzoru. Sytuacja początkowa wygląda tak. Dla ułatwienia naniosłem położenia fabryk i początkowe położenie centrum na wykres.



Teraz uruchamiamy Solver. Jako komórkę celu wybieram pole z sumą odległości i zaznaczam, że tą wartość chcę minimalizować. Jako komórki zmieniane wybieram współrzędne centrum. Dodajemy też ograniczenie na odległość każdej z fabryk od centrum. Na koniec uruchamiam obliczenia i klikam Rozwiąż.



Wynik końcowy wygląda w następujący sposób:



To tylko wierzchołek góry lodowej. Dodatek Solver ma dużo większe możliwość i wiele opcji. Można go wykorzystać do harmonogramowania, zdefiniować wiele ograniczeń, ustalić maksymalny czas obliczeń, dokładność uzyskanego wyniku i wiele więcej. Sądzę, że warto sobie zapamiętać, że Excel ma takie możliwości i w razie potrzeby doczytać i douczyć się jak z tego korzystać.

Wykrywanie nieużywanych elementów bibliografii

Home

Moim zdaniem LaTeX ma wspaniałą obsługę cytowań i bibliografii. Jest to jeden z powodów, dla którego tak lubię go używać np.: bardzo łatwo znaleźć cytowania w formacie rozumianym przez LaTeX'a, nie musimy martwić się o formatowanie, odpowiednie posortowanie czy numerowanie.

Domyślnie jest dodamy jakąś pozycję do bazy danych odnośników literaturowych, a jej nie zacytujemy to w finalnym dokumencie wygenerowanym przez LaTeX'a (np.: PDF) zostanie ona pominięta. Może to być zachowanie pożądane lub nie. Jeśli nie jest z pomocą przychodzi komenda \nocite, w szczególności jej forma \nocite{*}, która powoduje, że cokolwiek dodamy do spisu odnośników to znajdzie się to w finalnym dokumencie w sekcji z bibliografią. W pewnym momencie możemy jednak chcieć uporządkować bazę odnośników i sprawdzić co używamy, a czego nie. Przy dużym dokumencie, z dziesiątkami lub setkami cytowań nie jest to sprawa oczywista.

W takiej sytuacji z pomocą przychodzi, odkryty przeze mnie ostatnio, pakiet refcheck. Po jego włączeniu dla każdego nieużywanego elementu bibliografii, ale także dla każdej nieużywanej etykiety zostanie wygenerowane ostrzeżenie. Dodatkowo nieużywane elementy zostaną oznaczone w wygenerowanym dokumencie przy pomocy etykiet na marginesie dokumentu.

Kolejny raz okazuje się, że czegokolwiek bym sobie nie zamarzył to istnieje już pakiet, który to zapewnia :)

Latex i drzewa

Home

Wczoraj już późno w nocy zamarzyło mi się umieścić w dokumencie tworzonym w LaTeX'u rysunki drzew binarnych. Początkowo myślałem o narysowaniu ich w jakimś programie graficznym, a następnie wyeksportowaniu do jpg z czym LaTeX już sobie poradzi. Potem pomyślałem jednak, że to nie ma sensu bo z pewnością już ktoś miał taki problem i stworzył odpowiedni pakiet gotowy do użycia. Nie pomyliłem się. Bardzo szybko znalazłem pakiet qtree i już 5 minut później miałem w swoim artykule piękne drzewka. Przykład użycia:.

\Tree[.{L0 - Root} 
 [.{L1 - Left child} 
  [.{L2 - Left child} ] 
  [.{L2 - Right child} ]]
 [.{L1 - Right child} ]]

Efekt końcowy wygląda natomiast następująco:



LaTeX z pewnością jest trudniejszy w użyciu niż taki Word, ale jak już się go poznasz to zrobisz wszystko. Społeczność około LaTeX'owa stworzyła tyle różnych pakietów, że nie pozostaje nic innego jak brać i korzystać.