Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Pomiar czasu i odejmowanie - ciekawy problem

leburaque 25 Paź 2010 15:48 2841 13
  • #1 25 Paź 2010 15:48
    leburaque
    Poziom 17  

    Potrzebuję zmierzyć w programie czasy reakcji użytkownika i czas operacji. Dokładność ma być maksymalna, interesują mnie milisekundy. Oczywiście najczęściej procesor "odzywa się" co jakieś 55 milisekund, ale o to akurat mniejsza. Bo problem leży w odejmowaniu.

    Dokonując pomiaru czasu w większości języków programowania otrzymuje się cztery zmienne - odpowiadają one za godzinę, minutę, sekundę i sekundę setną zegara. Oczywiście każdy, kto chciałby obliczyć ile czasu trwa operacja postąpi wg. algorytmu:

    Pomiar_czasu1
    Operacja
    Pomiar_czasu2
    Porównanie_pomiarów.

    W teorii po prostu wystarczy odjąć od czasu2 czas1, prawda? Schody zaczynają się, kiedy łapiemy, że nie otrzymujemy 1 danej dla pomiaru czasu, tylko cztery. Odejmowanie przebiega więc etapowo. Można pomijając jakość algorytmu np. sprowadzić cztery zmienne do jednej - czyli do wartości setnych sekund. Godzina to 60 minut, czyli 60*60=3600 sekund, czyli 60*60*100=360000 milisekund. Mnożymy poszczególne dane, sumujemy i mamy:

    GG:MM:SS:S100
    11:35:56:81 = 11*360000+35*6000+56*100+81

    To przynajmniej proponują widoczne w sieci algorytmy. Po sprowadzeniu obu pomiarów do takich danych mamy dwie liczby całkowite, które odejmujemy od siebie i powinniśmy dostać w milisekundach ile czasu upłynęło między pomiarami...

    NIC bardziej MYLNEGO!

    Ten algorytm nie ma prawa działać, bo działa do momentu w którym każda z liczb pomiarowych1 jest większa od liczb pomiarowych2:

    GG1<GG2
    MM1<MM2
    SS1<SS2
    S1001<S1002

    W przeciwnym razie dostaje się dane błędne

    Weźmy na przykład dwa takie czasy:
    czas1 - 23:59:00:02
    czas2 - 00:00:01:07

    Jak widać minęło między nimi 1 sekunda i 55 milisekund.
    Powyższy algorytm zaś przedstawi:

    czas2 - czas1 =
    GG1*360000+MM1*6000+S1*100+S1001
    - GG2*360000+MM2*6000+S2*100+S1002

    107 - 83154002 = -83153895 milisekund, co jest wynikiem absurdalnym. Można by znaleźć więcej problemów, ale chodzi o zwrócenie uwagi na coś. Taki algorytm w najlepszym wypadku liczy arbitralną odległość w milisekundach od północy. Nie tyle problem tkwi w tym, że licznik czasu "przeskoczył" o północy i dlatego algorytm się wysypuje, tylko o odwieczną sprawę związaną z odejmowaniem pisemnym: "pożyczkę". Jeśli odejmuję czasy s1002-s1001 = 2-7 = -5, otrzymuję liczbę ujemną. Warto było by odliczyć to z sekund, jak przy odejmowaniu pisemnym odlicza się z pożyczki. Hmm... Tu zauważyłem, że trudno mi to opisać, ale wiadomo o co chodzi?

    W ogóle format czasu nie sprzyja takim prostym operacjom jak odejmowanie. Odejmowanie pisemne i jego algorytmy działają dobrze dla liczb które mają zakres 0-9 w każdym z pól. W takim czasie mamy cztery pola, gdzie jedno ma zakres 0-99, dwa 0-59, a jedno 0-23.

    Czy ktoś z Was ma pomysł, jak napisać algorytm odejmowania od siebie czasów pomiaru? Może być schemat. Preferuję Pascala, C, Assemblera. Ale chodzi o rozważenie problemu. Proszę o pomoc, bo muszę skończyć szybko badania;). Kto się zmierzy?

    0 13
  • #2 25 Paź 2010 16:37
    krzychoocpp
    VIP Zasłużony dla elektroda

    Te schody sam sobie wybudowałeś, większość funkcji operujących (w różnych bibliotekach i językach programowania) na czasie używa do tego znaczników czasowych które są jedną liczbą. Poszczególne pola uzyskuje się wtedy za pomocą funkcji formatujących. Zwykle, żeby poznać różnicę w czasie, wystarczy odjąć dwie liczby.

    Przy większej dokładności może być to tylko ciut bardziej skomplikowane: http://www.gnu.org/s/libc/manual/html_node/Elapsed-Time.html

    A jeśli już masz wszystko gotowe, metodę z postu zaimplementowałeś i jedynym problemem jest to że dzień się przekręca, to zawsze do pola godzin z drugiego czasu dodawaj 24 (lub wielokrotności tej liczby).

    Pozdrawiam, Krzysztof.

    0
  • #3 25 Paź 2010 17:41
    leburaque
    Poziom 17  

    Widzę w C bibliotekę time.h i jest tam "struct tm *localtime(const time_t *timep)", który zwraca ilość sekund od 1 stycznia 1970 r. na czas lokalny w postaci wskaźnika do struktury tm.

    Jest też "difftime" które porównuje dwa czasy. Także w sekundach.

    Po pierwsze to nie milisekundy o które mi chodzi, więc i tak byłoby trzeba pisać jakiś dodatkowy kod różnicowania do kontroli milisekund. A zakładając powyższe wcale nie byłoby łatwo, zwłaszcza, kiedy chodzi o "pożyczenie" tych milisekund z sekund.

    Po drugie nie mam pojęcia jak wygląda funkcja wewnętrznie, a potrzebuję ALGORYTMU który mógłbym implementować do różnych języków, np. assemblera, a nie zasadniczo ezoterycznej funkcji dostępnej z jednego języka programowania i to konkretnej jego biblioteki.

    Dziękuję jednak za odzew i pozdrawiam!

    P.S. Właściwie to muszę dodać: dotychczas większość algorytmu do swoich badań pisałem w pascalu/assemblerze. Stąd pytanie o algorytm, bo będzie mi go łatwo przenosić między językami, a uzależniony też jestem od swojego promotora, który zadecyduje co "wygląda czytelniej".

    0
  • #4 25 Paź 2010 19:23
    190175
    Użytkownik usunął konto  
  • #5 25 Paź 2010 20:12
    leburaque
    Poziom 17  

    Piszę w jak najprostszych językach, kompiluję w praktycznie w dosie, bo zależy mi na tym, żeby analizować algorytmy i upraszczać kod do maximum. Nie wiem, może jestem laikiem, ale jak skompiluję ten sam kod w środowisku np. Lazarusa, to mam 250% objętości programu i spadek formy każdej wykonanej operacji o min. 20%. Widać to od razu po całych algorytmach. Pamięta ktoś jeszcze o wydajności kodów?

    Analizuję przesunięcia w matrycach 100x100x3, w dużym skrócie są to analizy wpływu. Mniejsza zresztą o to - nie przerzucę teraz wszystkiego do języków wysokopoziomowych. Widzę jednak, że rady sprowadzają się do: "zmień język". A zadałem przecież absolutnie konkretne pytanie.

    W wątkach podanych powyżej są takie kwiatki jak "wykorzystaj Time2Long(h,m,s,s100);", które są po prostu czyjąś prywatną procedurą, bez opisu jej działania zresztą.

    Jeśli napiszę niewydajną procedurę, to spadnie mi szybkość wykonywania przesunięć w matrycach. W takiej procedurze jak powyższe mam 4 mnożenia i min 16 porównań, a ja tu walczę o każdy ruch procesora... :/ Zresztą - lepsze przeca porównania niż mnożenie... ;)

    0
  • Pomocny post
    #6 25 Paź 2010 20:58
    190175
    Użytkownik usunął konto  
  • #7 25 Paź 2010 21:18
    leburaque
    Poziom 17  

    OK, to już do mnie trafia. Zobaczę, co wygrzebię w ASM, ale w międzyczasie zrobiłem sobie plan takiego superprostego algorytmu. W zasadzie czas oczekiwania pomiędzy pomiarami waha się od kilku milisekund do kliku sekund. W zasadzie więc porównania zawierają się w zakresie dwóch operacji, pomijam przy pomiarze minuty i godziny (na razie, potem to pewnie dopracuję).

    Idea wygląda tak:

    1) Odejmij milisekundy od siebie: pomiar_obecny - pomiar_początkowy.
    2) Jeśli wynik jest ujemny, odejmij 1 od sekund_pomiaru_początkowego.
    3) Użyj na sekundach wartości bezwzględnej.
    4) Odejmij od siebie sekundy, a wynik przemnóż przez 100.
    5) Zsumuj wyniki odjęć sekund i milisekund.

    Mało operacji porównawczych, dwa razy tłukę w procek mnożeniem. Wydajne powinno być. Przynajmniej na razie. Jak to wygląda?

    0
  • #8 25 Paź 2010 21:50
    trol.six
    Poziom 30  

    Dodawanie i odejmowanie z przeniesieniem to chyba najprostsze operacje ;) i wcale nie takie wolne. Mnożenie też jest szybkie. Zdecydowanie ładowanie zmiennych do rejestrów może być dłuższe.

    Jak chcesz mieć wydajnie to nie mierzysz czasu i tyle :) Jeśli pomiar trwa więcej jak 3% algorytmu, to imho nie ma sensu, poza początkowym testem na bawienie się w takie rzeczy. Myśle ze krzychoocpp dość sensownie napisał.

    Tak to wygląda po rozważeniu :)

    0
  • #9 25 Paź 2010 21:56
    190175
    Użytkownik usunął konto  
  • #10 25 Paź 2010 22:28
    leburaque
    Poziom 17  

    Tak to wygląda: prosto i w pascalu.

    Code:
    type czas_operacji = record
    
                           G, M, S, S100 : word;
                         end;

    var
    CzasOstatniej, CzasAktualnej : czas_operacji;

    procedure ObliczCzas;
    var a, b, c, d: integer;
    begin
      CzasOperacji := 0;
      a := CzasAktualnej.S100;
      b := CzasOstatniej.S100;
      c := CzasAktualnej.S;
      d := CzasOstatniej.S;

      if (a - b) < 0
        then begin
               Dec(c);
               Inc(a, 100);
             end;

      if (c - d) < 0
        then begin
               Inc(c, 60);
             end;

      CzasOperacji := Abs(a - b) + Abs(c - d) * 100;
    end;

    procedure CzekCzas;
    begin
      CzasOstatniej := CzasAktualnej;
      GetTime(CzasAktualnej.G, CzasAktualnej.M,
              CzasAktualnej.S, CzasAktualnej.S100);
      ObliczCzas;
    end;

    To na początek, jest w miarę zrozumiałe?

    Dodano po 24 [minuty]:

    W zasadzie to po wszystkich przesunięciach w tablicy czas mierzalny oscyluje w okolicach 250ms. Jak skompilowałem w środowisku win to mi skoczył do 600-800. Traktuję komplet przesunięć jak jedną ogólną operację, której czas mierzę. Oczywiście to nie jest optimum, powinienem to przerzucić w ASM, ale kurczę muszę wyniki podać promotorowi, to ważne;).

    Optymalizację mogę jeszcze poczynić tak, że będę pobierał czasy co 10, albo i 100 operacji i wyciągał średnią. Wyjdzie w zasadzie na to samo, ale mogę wówczas zapomnieć o "widoczności" dużych odchyłów od średniej. A to też dla mnie ważne.

    Przez chwilę też próbowałem implementować ten ASM powyżej, ale pojawia mi się wtedy problem konwersji otrzymanych danych na setne sekundy. Co sądzicie? W którą stronę poprawiać?

    Dodano po 3 [minuty]:

    Aha - bo nie wiem, czy to widoczne, w starym Pasku się kiepsko pracuje na Wordach, bo nie można wykonać działania odejmowania w locie (od razu runtime error;). Operacje na wordach są traktowane jak wordy, więc żeby mieć ujemne musiałem dodać 4 zmienne. Chyba je jednak przerzucę na globalne. Różnica może znikoma, ale podziała chyba?

    Proszę pamiętać o używaniu znaczników code. - arnoldziq

    0
  • #11 25 Paź 2010 23:58
    190175
    Użytkownik usunął konto  
  • #12 26 Paź 2010 18:15
    leburaque
    Poziom 17  

    W sumie 2ch zwraca cztery różne liczby. Ale skoro jest bliższe procesora, to może coś zaoszczędzę? W sumie te Gettime w Pasku są na nich bezpośrednio robione, więc szybkość się nie zmieni jakoś widocznie, a i tak będę musiał wykonać szereg porównań. Na razie chyba to co mam tam to jakiś środek między wydajnością a prostotą.

    Swoją drogą to muszę się przyznać, że nie pamiętam/nie wiem jak w ASM sprawdzić znak wartości. Oświeciłby mnie ktoś?

    0
  • Pomocny post
    #13 27 Paź 2010 22:37
    190175
    Użytkownik usunął konto  
  • #14 01 Lis 2010 15:40
    leburaque
    Poziom 17  

    Czegoś takiego potrzebowałem. Chyba nieco pomodyfikuję, ale cieszę się, że jest odzew.

    Zapomniałem podziękować:).

    0